The Halting Problem

Diagonalisation indicates that undecidable decision problems

exist

explicitly defined

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

• EVEN
• PRIME
• ADA_PROGRAM

But, all three of these are obviously,

decidable

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:

• It has 2 items of input instead of one.
• One of its inputs is a `program' not a number.

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

• m has a binary representation of the form

  x 00000000 y

  where x and y are binary strings;
• x is the ASCII binary representation of an ADA program, Px say, which takes a single number as input and returns a zero or one as output.

• The problem of checking whether an input is valid is decidable.
• No algorithm exists for HP if and only if no algorithm exists for HP2 (since we can translate from inputs for HP to inputs for HP2 and vice-versa).

THEOREM

The Halting Problem (HP) is undecidable

Thus there is no algorithm which solves the Halting Problem.

PROOF

There is an ADA program, HALT, which

• Reads an ADA program, P, and a single number, w, as its input.
• If P halts when given w as input then HALT returns 1 as output.
• If P does not halt when given w as input then HALT returns 0 as output.

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;

• BAD reads a single number, Q, as input.
• If Q, written in binary, corresponds to an ADA program which takes a single number as input then:
• BAD tests whether the program represented by Q halts when given th e number Q as input (using the Halting Problem procedure, HALT, to perform the test).
• If the Halting problem procedure says that Q halts when started with input Q then BAD goes into a non-terminating loop.
• If the Halting problem procedure says that Q fails to halt when started with input Q then BAD prints a message and stops.

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

• The input for BAD should be a number which (when written in binary) is an ADA program which takes a single number as input.
• BAD is an ADA program (since HALT is an ADA program).

THEREFORE

There is a 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

as input?

EITHER

BAD halts on input

OR

BAD does NOT halt on input

Suppose

BAD halts on input BAD_NUMBER.

This can only happen if

HALT( BAD_NUMBER, BAD_NUMBER )

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 )

means that

BAD does NOT halt on input

On the other hand, suppose

BAD does NOT halt on input

This can only happen if

HALT( BAD_NUMBER, BAD_NUMBER )

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 )

means that

BAD DOES halt on input BAD_NUMBER

• If a program to solve the Halting problem, HP, exists then the program, BAD exists.
• BAD on any valid input either halts or does not halt.
• BAD_NUMBER is a valid input for BAD.
• BAD on input BAD_NUMBER fails to halt only if BAD on input BAD_NUMBER halts.
• BAD on input BAD_NUMBER halts only if BAD on input BAD_NUMBER fails to halt.

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

The Halting Problem is undecidable.

• Overview
• Introduction to Computability and Complexity
• Existence of unsolvable problems
• Computational Complexity Theory
• NP and NP-completeness

PED Home Page