Definition: A decision problem is a problem that requires a yes or no answer.
Definition: A decision problem that admits no algorithmic solution is said to be undecidable.
The halting problem takes two inputs:
The decision problem is: does P halt on input D?
Sometimes the problem is trivial:
/* Always halts regardless of input */
D := 1;
Sometimes the problem is easy, but dependent on the input:
/* Halts only if D is > 0 and even */
repeat D := D - 2 until D = 0;
Sometimes the problem is very very hard:
/* Halts iff Fermet's Last Theorem is false */
Fermat(D:integer);
a := 1; done := false;
while not done do
for b := 1 to a do
for c := 2 to a+b do
if a**D + b**D = c**D then
done := true;
a := a + 1;
end while;
Can we build a program that solves the halting problem for any program?
That is, is there a program that takes two inputs (P and D) and stops with the answer yes if P halts on input D, or stops with the answer no if P does not halt on input D?
If we had such a program, we could use it to check for infinite loops in programs.
Unfortunately no such program exists; the halting problem is undecidable!
Proof by contradiction: Assume we have a procedure HALTS that takes as input a program P and input data D and answers yes if P halts on input D and no otherwise.
Since there are no assumptions about the type of inputs we expect, the input D to a program P could itself be a program.
Given the program HALTS, we can construct a new (more limited) program that tests whether a program P halts when the input data is a copy of P.
procedure NEWHALTS(P);
if HALTS(P,P) then writeln('Yes');
else writeln('No');
Given NEWHALTS, we can construct another program that does just the opposite of NEWHALTS:
procedure OPP(P);
if NEWHALTS(P) outputs 'Yes' then
loop forever
else halt;
What happens when we call OPP(OPP)?
This is a contradiction! Since our only assumption was the existence of HALTS, procedure HALTS cannot exist.
The halting problem can be used to show that other problems are undecidable.
Totality Problem: A function (or program) F is said to be total if F(x) is defined for all x (or similarly, if F(x) halts for all x). Determining whether or not a function F is total is undecidable.
Proof: Suppose that it is decidable. Assume there is a procedure TOTAL that takes as input a program P and outputs 'Yes' if P halts on all inputs and 'No' otherwise.
We can use the procedure TOTAL to solve the halting problem for a program P and its input D by writing a procedure that simulates P(D).
procedure SIMPD(i);
/* Ignores input i */
P(D);
Using SIMPD, we can solve the halting problem as follows:
procedure HALTS(P,D);
if TOTAL(SIMPD) outputs 'Yes'
then writeln('YES')
else writeln('No);
Since SIMPD is total iff P(D) halts, we have constructed a solution to the halting problem. Since such a solution cannot exist, our assumption that TOTAL exists is false.
Equivalence Problem: Given two programs P and Q, do they compute the same function? (ie, is P(x) = Q(x) for all x?) This problem is also undecidable.
Proof: Consider the following program
procedure TOTALP(x);
P(x);
writeln('YES');
If P(x) halts, then TOTALP(x) halts and outputs Yes.
procedure CONST(x);
/* Ingore input and always output true */
writeln('Yes');
CONST prints Yes for all inputs. If CONST = TOTALP, then TOTALP outputs Yes for all inputs, which implies that P(x) halts on all inputs, which implies that P(x) is total.
Thus, if we can determine whether CONST = TOTALP, we can solve the totality problem. Therefore, the equivalence problem is undecidable.
Note that this means that in general, you can't tell whether an original program P and an optimized version P' produced by an optimizing compiler compute the same thing.
A computable function is one that always halts and gives an answer, either yes or no. A partially computable function halts and gives a yes on those inputs for which 'yes' is the correct solution, but never halts on other inputs.
Example: The halting problem is partially computable. To determine HALTS(P,D), simply call P(D). Then, HALTS(P,D) halts and outputs Yes if P(D) halts, and loops otherwise.
If a problem is computable or partially computable, then anytime an algorithm halts, the answer can be checked in a finite amount of time and space.
Example: If the halting problem HALTS(P,D) halts and says Yes, it is easy to check that P(D) halts by showing a simulation of P(D). Thus, whenever HALTS(P,D) halts, we know that a hand simulation will halt, and be a proof that HALTS(P,D) = true.
If a problem is not even partially computable, there is no way of checking even a YES answer.
Example: The equivalence problem is not partially computable. Suppose EQUALS(P,Q) is true. How would you check it? There are an infinite number of inputs to each, and they can't all be checked.
The recursion theorem states that for any algorithm that operates on a sequence of characters, there is an algorithm that does the same thing to itself.
Example: There exists an algorithm that accepts a program as input and prints the program as output. By the recursion theorem, there is a program that prints itself.
Here is a Pascal program that almost does the trick. Can you find and fix the problem?
program Z(output);
var A: array [1..240] of char;
procedure P(i,j,k:integer);
begin
for k := i to j do write(A[k]);
end;
begin
A :=
'program Z(output);
var A:array[1..240] of char;
procedure P(i,j,k:integer);
begin
for k := i to j do write(A[k]);
end;
begin
A := ;
P(1,129,0); P(1,129,0); P(130,188,0);
P(130,188,0) end.';
P(1,129,0);
P(1,129,0);
P(130,188,0);
P(130,188,0)
end.
The recursion theorem has practical significance. We can use it to prove that there is no program to automatically supply an adequate set of test data for a program that fully exercises the program.
Theorem: There is no algorithm Test(P) that given program P produces a set of test inputs I that adequately tests program P.
Proof by contradiction: Assume algorithm Test exists.
Consider the following program:
/* Procedure to increment a variable */
procedure Inc(x:integer);
/* Get set of test inputs for P */
I := Test(P);
if x in I then print x+1
else print 0;
end;
This procedure operates correctly (it outputs x+1) for every value in the test suite, and incorrectly (it outputs 0) for all the other possible inputs.
The recursion theorem states there is another program Inc2 that operates exactly like Inc, when P is a copy of Inc2. Inc2 uses Test to generate test data for itself, but it prints the wrong answer for every input not included in the test data. Clearly then, the test data is not adequate, so Test does not exist.
Conclusion: automatic testing can't be guaranteed to always work, even if it can be used to generate some useful test cases.