Elements of Complexity Theory - A Classical Introduction to Cryptography: Applications for Communications Security - page 217

Since Turing machines over an alphabet are totally defined by a finite set of states

and a function δ over finite sets, we define an encoding technique in order to represent

pairs ( M , x ) of Turing machines M and input word x as words over the alphabet { 0 , 1 } .

Let x ). Let us now consider the language L which

consists of all words representing a pair

M , x denote the encoding of ( M ,

for which M accepts the word x .We
call L the universal language . We can easily see that L is computable: we can build a
Turing machine A such that for any Turing machine M , M accepts x if and only if A
accepts

M , x

M , x .

Since the set of words is enumerable, the set of all Turing machines is enumerable.
Thus, the set of all computable languages is enumerable. But, the set of all languages is
not enumerable, which can be proven by a standard diagonal argument : let ( w 1 , w 2 ,... )

be an infinite sequence which contains all words, and let ( M 1 , ) be an infinite

sequence which contains all Turing machines. Putting these two sequences together
makes arbitrary pairs

M 2 ,...

M i , w i of Turing machines and words. Now let L d be the set of

all w i for which L .If L d were a computable language, it would have been

accepted by some Turing machine. Let M j be this machine, and let us consider the
corresponding word w j . By definition of L d , w j is in L d if and only if

M i , w i ∈

L ,
namely if, and only if M j does not accept w j . But since the acceptance language of M j
is L d , M j accepts w j if and only if w j ∈

M j , w j ∈

L d , namely if and only if M j does not accept
w j ! This leads us to a contradiction. Hence, no Turing machine can accept L d .

8.2.3 Decisional Problems and Decidability

Limits of computability are even more puzzling when we realize that deciding whether
a word is accepted or not cannot be algorithmically decided.

More precisely, we have seen that the above universal language L is computable.
Let L denote the set of all pairs for which M does not accept x . We notice that

if L is computable, there exists a Turing machine M which can tell us when x is not
accepted by M . By using the notations of Section 8.2.2, we can build a new Turing
machine which accepts L d as follows.

M , x

1. Enumerate all M i , w i pairs until w i is the input x

2. Simulate M on

M i , x

This Turing machine accepts the language L d (from Section 8.2.2). This contradicts
the fact that L d is not computable. Therefore,

L is not computable.

This means that the acceptance problem is essentially asymmetric: we have seen
that we can make a universal Turing machine which can tell when x is accepted by M ,
but we cannot make a Turing machine which tells when x is not accepted by M . Telling
whether or not a word is accepted is called a decisional problem . We have seen that de-
ciding whether a given M accepts a given x is undecidable . In particular, it cannot decide
whether or not M eventually halts on x . This problem is called the halting problem.