[Overview] [Previous] [Next]

Recursively Enumerable But Not Recursive

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, w1, w2, w3, .... We have also shown how to enumerate Turing machines, T1, T2, T3, .... (Recall that each Turing machine defines a recursively enumerable language.) Consider the language

L = {wi: wi is a member of L(Ti)}

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

-L = {wi: wi is not a member of L(Ti)}

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 Tk.

Does wk belong to L?

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