The Halting Problem
At approximately the same time that Gödel came up with his incomplete-
ness theorem (which perhaps should be called the incompleteness or in-
consistency theorem, but this doesn’t sound as good), mathematicians
were beginning to construct computers, and also to formulate the theory
that underlies the process of computation. The first relatively complicated
computer programs had been written, and mathematicians discovered a
nasty possibility lurking within the computational process: the computer
might go into an infinite loop, from which the only rescue was to halt the
program manually (this probably meant disconnecting the computer
from the power source). Here is an easy example of an infinite loop.Program Statement Number Instruction1 Go to Program Statement 2
2 Go to Program Statement 1The first instruction in the program sends the program to the second
instruction, which sends it back to the first instruction, and so on.
In the early days of computer programming, entering an infinite loop
was a common occurrence, and so a natural question arose: Could one
write a computer program whose sole purpose was to determine whether
a computer program would enter an infinite loop? Actually, the question
was phrased differently, but equivalently: If a program either halts or
loops, is it possible to write a computer program that determines whether
another computer program will halt or loop? This was known as the halt-
ing problem.
It was quickly shown that it was not possible to write such a computer
program; this result was known as the unsolvability of the halting prob-
lem. The following proof is due to Alan Turing, one of the early giants in
the field. Turing was not only a tremendously talented mathematician
and logician, but he also played a major role in helping decipher German
codes during World War II. However, he was a homosexual in an environ-
ment tremendously intolerant of homosexuality, and was forced to un-
dergo chemical treatments, which resulted in his eventual suicide.
Suppose that the halting problem is solvable, and there is a program H
that, given a program P and an input I, can determine whether P halts or
loops. The output from the program H is the result; H halts if it deter-
mines that P halts on input I, and H loops if it determines that P loops on
input I. We now construct a new program N that examines the output of
Even Logic Has Limits 125