next up previous contents
Next: Implications of Theorem 3 Up: Theorem 3 Previous: Theorem 3

If a language and it's complement are r.e, they are both recursive

This is tricky, but a TM M accepting an r.e. language will always halt for $w \in L(M)$. Since w is always in either L or $\bar{L}$,either M or $M^{\prime}$ will always halt. But, by Theorem 1, the complement of a recursive language is recursive. Therefor, both L and $\bar{L}$ are recursive if both are r.e.