Mr. Turing’s amazing machines - The Computing Universe: A Journey through a Revolution - page 112

The halting problem and the Entscheidungsproblem

Using Turing's universal machine, it is possible to prove that there is no
way to tell, in general, whether the execution of a given program will termi-
nate on any given input. If we have a program to calculate the square of x we
can be confident that, after we input x into the machine, we will be able to read
x 2 on the tape when the machine halts. Termination is not always so obvious.
Suppose we have a program that takes a number as input and either divides it
by two, if the number is even, or triples it and adds one, if it is odd. The pro-
gram then takes this new number as input and repeats the process. When the
output is one, the program halts. Can we be sure that this will happen? This is
known as the 3x + 1 problem - what computer scientist David Harel calls the
“simplest-to-describe open problem in mathematics.” 7 If we try this with the
starting value of x = 7 we get the sequence 7, 22, 11, 34, 17, 52, 26, 13, 40, 20,
10, 5, 16, 8, 4, 2, 1 and the sequence terminates. With other values of x we find
that the program sometimes terminates but for some values of x it just keeps
on generating numbers with no repeating pattern until we decide we have seen
enough. This is one specific instance of the “halting problem” - a program for
which we cannot determine whether it terminates or not. More generally, the
halting problem is concerned with the termination of any program for any
input.
How can this result be proved? If we have a Turing machine T that calcu-
lates some function F , can we find a computable function that predicts whether
or not the machine T will halt or not? If there is such a function, we know that
it too must be describable by another Turing machine. This concept, of Turing
machines telling us about other Turing machines, is a very powerful tool. This
device can be used to prove that the halting problem is noncomputable. The
trick is to assume the existence of a machine that can predict whether a pro-
gram halts and then show that this leads to a contradiction, meaning that the
original assumption that such a machine exists is incorrect.
We begin our sketch of a proof by supposing we have a machine D that
takes as input a tape that contains a description d T of the machine T - these
are just the quintuples that define T - as well as T T's input tape t . Machine D is
required to tell us whether T will halt or not and then come to a halt ( Fig. 6.7.a ).
We now introduce another machine Z which takes the machine description d T
and uses this as the input tape for the machine D . This machine Z reacts to the
output from D in the following way:

B.6.7. Alonzo Church (1903-95) was
very supportive of Turing's ideas
and he was first to use the term
Turing machine . This, along with the
Church-Turing thesis on computabil-
ity, is now one of the cornerstones of
computer science.

d T , t d T , t

D D

No No Yes Yes

Halt Halt Halt Halt

Fig. 6.7a. A hypothetical Turing machine
for the halting problem.

If T halts ( D says “yes”), then Z does not halt.
If T does not halt ( D says “no”), then Z halts.

d T d T

d T , d T d T , d T

We can arrange this to happen by introducing two new states in the “yes”
branch. The machine now oscillates between them indefinitely and this pre-
vents our Z machine from halting if D halts (says “yes”) as in Figure 6.7b . Now
we arrive at the crux of the argument. We get Z to operate on itself by taking
as input the quintuples d Z that define the Z machine and substitute Z for T in
the above argument. We find:

Z Z

D D

R R L L

No Yes Yes

No

Halt

Fig. 6.7b. A paradoxical Turing machine
to demonstrate the halting problem.

Z applied to d Z halts if and only if Z applied to d Z does not halt.