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

• EVEN
• PRIME
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:

• It has 2 items of input instead of one.
• One of its inputs is a `program' not a number.
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

• 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.
Clearly
• 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).
(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

• 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
--**********************************
-- 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;
```
• 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.

### There is a number,

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

as input?

### BAD does NOT halt on input

Suppose

This can only happen if

is false,

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

is false,

means that

### BAD does NOT halt on input

On the other hand, suppose

### BAD does NOT halt on input

This can only happen if

is true,

But what does this mean? It means that

is true,

means that

In summary we have shown that:
• 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.