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.