We know that the recursive languages are a subset of the recursively enumerable
languages, We will now show that they are a *proper* subset.

We have shown how to enumerate strings for a given alphabet, w_{1}, w_{2},
w_{3}, .... We have also shown how to enumerate Turing machines, T_{1}, T_{2},
T_{3}, .... (Recall that each Turing machine defines a recursively enumerable
language.) Consider the language

L = {w_{i}: w_{i}
L(T_{i})}

A little thought will show that L is itself recursively enumerable. But now consider its complement:

-L = {w_{i}: w_{i}
L(T_{i})}

*If* -L is recursively enumerable, then there must exist a Turing machine that
recognizes it. This Turing machine must be in the enumeration somewhere -- call it T_{k}.

Does w_{k} belong to L?

- If w
_{k}belongs to L then (by the way we have defined L) T_{k}accepts this string. But T_{k}accepts only strings that do not belong to L, so we have a contradiction. - If w
_{k}does not belong to L, then it belongs to -L and is accepted by T_{k}. But since T_{k}accepts w_{k}, w_{k}must belong to L. Again, a contradiction.

We have now defined a recursively enumerable language L and shown by contradiction that -L is not recursively enumerable.

We mentioned earlier that if a language is recursive, its complement must also be recursive. If language L above were recursive, then -L would also be recursive, hence recursively enumerable. But -L is not recursively enumerable; therefore L must not be recursive.

We have therefore shown that L is recursively enumerable but not recursive, therefore the set of recursive languages is a proper subset of the set of recursively enumerable languages.

Copyright © 1996 by David Matuszek

Last modified Apr 1, 1996