Java Reference
In-Depth Information
that is, it halts. Thus, contrary does the contrary of what halt says that it will
do.
The action of contrary is logically inconsistent with the assumption that
halt solves the Halting Problem correctly. There are no other assumptions we
made that might cause this inconsistency. Thus, by contradiction, we have proved
that halt cannot solve the Halting Problem correctly, and thus there is no program
that can solve the Halting Problem.
Now that we have proved that the Halting Problem is unsolvable, we can use
reduction arguments to prove that other problems are also unsolvable. The strat-
egy is to assume the existence of a computer program that solves the problem in
question and use that program to solve another problem that is already known to be
unsolvable.
Example17.4 Consider the following variation on the Halting Problem.
Given a computer program, will it halt when its input is the empty string?
That is, will it halt when it is given no input? To prove that this problem is
unsolvable, we will employ a standard technique for computability proofs:
Use a computer program to modify another computer program.
Proof: Assume that there is a function Ehalt that determines whether
a given program halts when given no input. Recall that our proof for the
Halting Problem involved functions that took as parameters a string rep-
resenting a program and another string representing an input. Consider
another function combine that takes a program P and an input string I as
parameters. Function combine modifies P to store I as a static variable S
and further modifies all calls to input functions within P to instead get their
input from S. Call the resulting program P 0 . It should take no stretch of the
imagination to believe that any decent compiler could be modified to take
computer programs and input strings and produce a new computer program
that has been modified in this way. Now, take P 0 and feed it to Ehalt . If
Ehalt says that P 0 will halt, then we know that P would halt on input I.
In other words, we now have a procedure for solving the original Halting
Problem. The only assumption that we made was the existence of Ehalt .
Thus, the problem of determining if a program will halt on no input must
be unsolvable.
2
Example17.5 For arbitrary program P, does there exist any input for
which P halts?
Proof: This problem is also uncomputable. Assume that we had a function
Ahalt that, when given program P as input would determine if there is
some input for which P halts.
We could modify our compiler (or write
 
Search WWH ::




Custom Search