[Overview] [Previous] [Next]

When Recursively Enumerable Implies Recursive

Suppose a language L is recursively enumerable. That means there exists a Turing machine T1 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 is not a member of L}, is recursively enumerable. That means there is some other Turing machine T2 that, given any string of -L, halts and accepts that string.

Clearly, any string (over the appropriate alphabet sigma) belongs to either L or -L. Hence, any string will cause either T1 or T2 (or both) to halt. We construct a new Turing machine that emulates both T1 and T2, 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.


Copyright 1996 by David Matuszek
Last modified Apr 1, 1996