** Next:** Implications of Theorem 3
** Up:** Theorem 3
** Previous:** Theorem 3

This is tricky, but a TM *M* accepting an r.e. language will always
halt for . Since *w* is always in either *L* or ,either *M* or will always halt. But, by Theorem 1, the
complement of a recursive language is recursive. Therefor, both *L*
and are recursive if both are r.e.

*root*

*6/10/1998*