[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, w₁, w₂, w₃, .... We have also shown how to enumerate Turing machines, T₁, T₂, T₃, .... (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.