[Overview] [Previous] [Next]

When Recursively Enumerable Implies Recursive

Suppose a language L is recursively enumerable. That means there exists a Turing machine T₁ that, given any string of the language, halts and accepts that string. (We don't know what it will do for strings not in the language -- it could reject them, or it could simply never halt.)

Now let's also suppose that the complement of L, -L = {w: w L}, is recursively enumerable. That means there is some other Turing machine T₂ that, given any string of -L, halts and accepts that string.

Clearly, any string (over the appropriate alphabet ) belongs to either L or -L. Hence, any string will cause either T₁ or T₂ (or both) to halt. We construct a new Turing machine that emulates both T₁ and T₂, alternating moves between them. When either one stops, we can tell (by whether it accepted or rejected the string) to which language the string belongs. Thus, we have constructed a Turing machine that, for each input, halts with an answer whether or not the string belongs to L. Therefore L and -L are recursive languages.

We have just proved the following theorem: If a language and its complement are both recursively enumerable, then both are recursive.