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;
```
What does BAD do?
• 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).

### 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.

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.

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

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

The program corresponding to BAD_NUMBER halts on input BAD_NUMBER.

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

is true,

means that

### BAD DOES halt on input BAD_NUMBER

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.
• 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.
We can therefore conclude that

i.e.

### The Halting Problem is undecidable. PED Home Page