But (11.1) now implies that
Alternatively, if we assume that a k is in L, then a k ∉ and (11.2) implies that
But then from (11.1) we get that
The contradiction is inescapable, and we must conclude that our assumption that
is recursively enumerable is false.
To complete the proof of the theorem as stated, we must still show that L is
recursively enumerable. For this we can use the known enumeration procedure
for Turing machines. Given a i , we first find i by counting the number of a’s. We
then use the enumeration procedure for Turing machines to find M i . Finally, we
give its description along with a i to a universal Turing machine M u that simulates
the action of M on a i . If a i is in L, the computation carried out by M u will
eventually halt. The combined effect of this is a Turing machine that accepts
every a i ∈ L. Therefore, by Definition 11.1, L is recursively enumerable.
The proof of this theorem explicitly exhibits, through (11.1), a well-defined
language that is not recursively enumerable. This is not to say that there is an
easy, intuitive interpretation of ; it would be difficult to exhibit more than a
few trivial members of this language. Nevertheless, is properly defined.
A Language That Is Recursively Enumerable but Not
Recursive
Next, we show there are some languages that are recursively enumerable but not
recursive. Again, we need do so in a rather roundabout way. We begin by
establishing a subsidiary result.