UNSOLVABLE PROBLEMS

It would be very useful to have a way of quickly knowing whether any particular program, when provided
with any particular set of inputs, will execute to completion and halt, or instead continue endlessly. In computer
science, this is known as the “halting problem.” Given a program, and a set of inputs, will the program execute
to completion or not? Is there some algorithm one can apply that will, for any program and any set of inputs,
determine whether the program will run to completion or not?
One might suggest simply running the program, providing the particular inputs, and seeing whether the
program halts or not. If the program were to run to completion and halt, you would know that it halts. However,
if the program were to continue to run, you would never know whether the program would continue forever, or
halt eventually. What is needed is an algorithm for inspecting the program, an algorithm which will tell us
whether the program will eventually halt, given a particular set of inputs.
If there is such an algorithm for inspecting a program, there is a TM to implement it. Unfortunately however,
the halting problem has been shown to be an unsolvable problem, and the proof that there is no solution is
a proof by contradiction. We begin by assuming there is, indeed, a TM that implements a solution to the halting
problem. We will call this TM 'H', for it solves the big halting problem.
The input to H must include both the program under test p, and the input to the program i. In pseudocode,
we call H like this:
H(p, i)
We assume that H must itself halt, and that the output from H must be true or false—the program under
test must be found either to halt, or not to halt. Whatever H does, it does not rely on simply running the
program under test, because H itself must always halt in a reasonable time.
Now suppose that we create another TM called NotH that takes a symbolic argument that will include the
encoding of a program, p. NotH will call H, passing the code for p as both the program p and the input data i
to be tested. (TMs can be linked this way, but the details are not important to this discussion.) NotH will return
true if H fails to halt under these conditions, and will loop forever if H does halt. In pseudocode NotH looks
like this


NotH(p)
if(H(p, p) is false) return true
else
while(true) {} //loop forever
endNotH
Now suppose we test NotH itself with this approach. That is, suppose we pass the code for NotH itself to
NotH. We will refer to the code for NotH as 'nh', and we can ask, “Does the program NotH halt when it is
run with its own code as input?” Saying this another way, does NotH(nh) halt?
If NotH(nh) halts, this can only be because H(nh,nh) reports that NotH does not halt. On the other
hand, if NotH(nh) does not halt, this can only be because H(nh,nh) reports that NotH does halt. These are
obviously contradictions.

The original assumption, that a TM does exist that can determine whether any particular program will
run to completion when presented with any arbitrary input data, must be incorrect. That assumption led to the
contradictory state illustrated by NotH. Therefore, computer scientists conclude that there can be no one algorithm
that can determine whether any particular program will run to completion, or fail to run to completion, for every
possible set of inputs.
It would be very nice to have a program to which we could submit new code for a quick determination as
to whether it would run to completion given any particular set of inputs. Alas, Turing proved that this cannot
be. One can and should write test programs, but one will never succeed in writing one program which can test
every program.
The “halting problem” is one of the provably unsolvable problems in computing (Turing, Alan, “On computable
Numbers with an Application to the Entscheidungsproblem”, Proceedings of the London Mathematical
Society, 2:230–265, 1936). No one algorithm will ever be written to prove the correct or incorrect execution
of every possible program when presented with any particular set of inputs. While no such algorithm can be
successful, knowing that allows computer scientists to focus on problems for which there are solutions.