[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 L(Ti)}

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

-L = {wi: wi 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?

• If wk belongs to L then (by the way we have defined L) Tk accepts this string. But Tk accepts only strings that do not belong to L, so we have a contradiction.
• If wk does not belong to L, then it belongs to -L and is accepted by Tk. But since Tk accepts wk, wk 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.