Suppose a language L is recursively enumerable. That means there exists a Turing
machine T_{1} 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_{2} 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_{1}
or T_{2} (or both) to halt. We construct a new Turing machine that emulates
both T_{1} and T_{2}, 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