Uncomputability 319
- If an arbitrary string d does not belong to Halt, either because d does not have the form
A%%In or because d does have this form but A does not halt on In, then H returns
FALSE.
Consider a simple-minded attempt at solving the halting problem. Given the string
d = A%%In, run the given program A on the input In and see what happens. Suppose
algorithm A is executed for 1,000,000 steps on input In. If, in 1,000,000 or fewer steps, A
comes to a halt, then A halts on input In. However, what if it does not halt within 1,000,000
steps? It might halt in exactly 1,000,001 steps. It might halt in exactly 9,876,543,210 steps.
It might never halt. The fact that the algorithm has not halted in any specific amount of
time does not, by itself, say anything about whether the algorithm will ultimately halt.
On the other hand, as anyone who has ever checked someone else's program knows,
there are many cases where a person can just look at a program and tell whether it will
go into an infinite loop. So, there seems to be some hope for testing whether a program
will halt by examining a program. Unfortunately, it is easy to write a program that is so
complicated that other people are totally baffled by it. Therefore, perhaps Turing's theorem
(see Theorem 1) now seems to be very plausible.
The proof of the theorem is reminiscent of the ancient liar's paradox: "This sentence
is a lie." Work through it: If it is a lie, then it is not a lie, and if it is not a lie, then it is a
lie. This paradox tells us, in part, why logicians are so careful in defining the syntax and
semantics of their logics (see Chapter 2): They want to make sure they do not allow "This
sentence is a lie" as a legal sentence in the formal logic.
Theorem 1. (Unsolvability of the Halting Problem, Turing) The halting problem,
Halt, is undecidable.
Proof Suppose such an algorithm H existed. Let NegSelfRef be the following algorithm,
with the input of a character string A representing an algorithm. 0
INPUT: Character string A
OUTPUT: That is the question
if (H(A%%A) = FALSE)
return TRUE
else
while (0 = 0) do /* repeat forever: */
x = 0 /* something trivial executed */
/* ... infinitely many times ...
return FALSE /* so this statement will
never be reached
Note that if H works as we supposed above, NegSelJRef (A) halts if and only if
H(A, A) = FALSE, if and only if the calculation of A does not halt on input A.
