Chapter 10: Decidahility and Recursively Enumerahle Languages l;l 313
10.4 UNDECIDABLE LANGUAGES
In this section we prove the existence of languages that are not recursively
enumerable and address the undecidability of recursively enumerable
languages.
Theorem 10.4 There exists a language over 2: that is not recursively
enumerable.
Proof A language L is recursively enumerable if there exists a TM M such
that L = T(M). As L is finite, 2:* is countable (that is, there exists a one-toone correspondence between 2:* and N).
As a Turing machine M is a 7-tuple (Q. 2:, f', 8, qo. b, F) and each
member of the 7-tuple is a finite set M can be encoded as a string. So the
set I of all TMs is countable.
Let J: be the set of all languages over 2:. Then a member of J: is a subset
of P (Note that P is infinite even though I is finite), We show that ;i is
uncountable (that is, an infinite set not in one-to correspondence with N).
We prove this by contradiction. If ;L were countable then J: can be
written as a sequence {L[, L 2 • L 3 , ... }. We \\Tite 2:* as a sequence {11']. W2'
We, . . . . }. So L i can be represented as an infinite binary sequence XnXi2Xi3' ..
where
r1 ihv} E L;
lO otherwise
Using this representation we write L; as an infinite binary sequence.
L] XI]X12 X 13
x]i
L, x2I x :: x :3
x:}
L i Xil X i2 X i3
xi)
Fig. 10.1 Representation of T
We define a subset L of 2:* by the binary sequence ."].":."3 ... where Y; =
1 - Xii' If Xii =0, Yi = 1 and if Xii = I, ."; =O. Thus according to our assumption
the subset L of I* represented by the infinite binary sequence YIY:Y3 ...
should be L k for some natural number k. But L =f. Lt. since Wk E L if and only
if Hk It: Lk~ This contradicts our assumption that ci is countable. Therefore 1.
is uncountable. As J is countable. ;L should have some members not
corresponding to any TM in 1. This proves the existence of a language over
2: tnat is not recursively enumerable.
I
Defmition 10.8 A TM = {(M, w) I The TM M accepts w}.