Computability and Complexity - The Halting Problem

The Halting Problem

Diagonalisation indicates that undecidable decision problems

exist

It does not help in finding an

explicitly defined

undecidable decision problem.

That is: It does not identify an undecidable decision problem whose input and output behaviour can be given with a finite description.

The decision problems

are explicitly defined (we can give a finite description of each problem; we do not have to state each individual output for each individual input: that would be an infinite length description)

But, all three of these are obviously,

decidable

i.e. an algorithm (ADA program) can be written to solve them.

Alan Turing in 1936 exhibited the first explicit example of an undecidable decision problem:

The Halting Problem

The Halting Problem, HP, is the following decision problem:

Input: An ADA program, P, (which takes as input a single number, n) and an input w for P.

Output: 1 if P comes to a halt when run with input w ; 0 if P never halts when started with input w.

It may be objected that HP is not a decision problem in the sense that we have been using to date since:

However we can define an equivalent decision problem HP2 to which such objections do not apply.

HP2 takes as input a single number, m. This number is a valid input if

Clearly (Note: the `encoding trick' described above can be applied to transform any decision problem with `multiple inputs' into an equivalent one with a single number as input). Given this fact we will deal with the more `natural' problem HP instead of the precisely encoded version HP2.

THEOREM

The Halting Problem (HP) is undecidable

Thus there is no algorithm which solves the Halting Problem.

PROOF

Suppose that there is an ADA program, HALT, which solves the Halting Problem, HP. That is:

There is an ADA program, HALT, which

Since HALT is assumed to exist we can write an ADA program, BAD say, which uses HALT as a sub-procedure.

procedure BAD is
   Q : integer;
   function HALT (P integer; 
                        w integer) 
                       return boolean is
      if ADA_PROGRAM(P) then
       --**********************************
       -- Halting problem program goes
       -- here.
       --*********************************
      end if;
  end HALT;
  begin
     get (Q);
     if HALT (Q,Q) then
        loop
           put ("NOT OK");
        end loop;
     else
        put ("OK");
     end if;
  end BAD;
What does BAD do?

HP (which HALT solves) takes an ADA program and single number as input.

THEREFORE

There is a number,

BAD_NUMBER,

which when written in binary corresponds exactly to the ASCII representation of the ADA program BAD

BAD_NUMBER is therefore a valid input for the ADA program BAD.

What happens if BAD is given

BAD_NUMBER

as input?

EITHER

BAD halts on input

BAD_NUMBER

OR

BAD does NOT halt on input

BAD_NUMBER

Suppose

BAD halts on input BAD_NUMBER.

This can only happen if

HALT( BAD_NUMBER, BAD_NUMBER )

is false,

But what does this mean? It means that The program corresponding to BAD_NUMBER does not halt on input BAD_NUMBER.

But `the program corresponding to BAD_NUMBER' is BAD i.e.

HALT( BAD_NUMBER, BAD_NUMBER )

is false,

means that

BAD does NOT halt on input

BAD_NUMBER

On the other hand, suppose

BAD does NOT halt on input

BAD_NUMBER.

This can only happen if

HALT( BAD_NUMBER, BAD_NUMBER )

is true,

But what does this mean? It means that

The program corresponding to BAD_NUMBER halts on input BAD_NUMBER.

But `the program corresponding to BAD_NUMBER' is BAD i.e.

HALT( BAD_NUMBER, BAD_NUMBER )

is true,

means that

BAD DOES halt on input BAD_NUMBER

In summary we have shown that: We can therefore conclude that

No program to solve the Halting Problem, HP, can be written

i.e.

The Halting Problem is undecidable.

PED Home Page