A Language That Is Not Recursively Enumerable
Since every language that can be described in a direct algorithmic fashion can be
accepted by a Turing machine and hence is recursively enumerable, the
description of a language that is not recursively enumerable must be indirect.
Nevertheless, it is possible. The argument involves a variation on the
diagonalization theme.
Theorem 11. 3
There exists a recursively enumerable language whose complement is not
recursively enumerable.
Proof: Let Σ = {a}, and consider the set of all Turing machines with this input
alphabet. By Theorem 10.3, this set is countable, so we can associate an order
M 1 , M 2 ,…with its elements. For each Turing machine M i , there is an associated
recursively enumerable language L (M i ). Conversely, for each recursively
enumerable language on Σ, there is some Turing machine that accepts it.
We now consider a new language L defined as follows. For each i ≥ 1, the
string a i is in L if and only if a i ∈ L (M i ). It is clear that the language L is well
defined, since the statement a i ∈ L (M i ), and hence a i ∈ L, must be either true or
false. Next, we consider the complement of L,
which is also well defined but, as we will show, is not recursively enumerable.
We will show this by contradiction, starting from the assumption that is
recursively enumerable. If this is so, then there must be some Turing machine,
say M k , such that
Consider the string a k . Is it in L or in ? Suppose that a k ∈ . By (11.2) this
implies that