Halting Problem - Turing's proof

Jack Dikian

January 2011

A few days ago, I started reading David Leavitt’s book “The Man Who Knew Too Much – Allan Turning and the invention of the computer – 2007” and almost by coincidence met up with an old Uni friend – recalling the countless hours we spent discussing esoteric problems in philosophy and mathematics. Turning machines was a big favorite – universal, and easy to code. Another was the halting problem. Easy enough to understand, and the proof for its insolvability was provided by Turing in 1936.

I wanted to revisit this problem and present it in a form that avoids the deeper symbolic language of set theory.

In computability theory, the halting problem is a decision problem, deciding, given a program and an input, whether the program will eventually halt when run with that input, or whether it will run forever.

In 1936 Alan Turing proved that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. It is said that the halting problem is un-decidable over Turing machines.

Formal Convention

The formal representation of decision problem(s) is the set of objects possessing the property in question. The halting set is represented by

K := { (i, x) | program i will eventually halt if run with input x

And this set is recursively enumerable. I.e, there is a computable function that lists all of the pairs (i, x) it contains.

In practice

Programs may contain loops which may be infinite or finite in length. The amount of work done in any program will depend on the input. Programs may also consist of various numbers of loops, nested or in sequence.

Trial solution

We can just run the program with the given input. If the program stops, we know the program stops. But what if the program doesn't stop in a reasonable amount of time, what are we to conclude. We are not able to conclude that it won't stop.

A look at the proof

Suppose you have a solution to the halting problem called H. 
 H takes two inputs:

1. a program P and

2. an input I for the program P.

H generates an output "halt" if H determines that P stops on input I or it outputs "loop" otherwise.

Fig, 1

Prog P ---------->

---------> “Loop” or “halt”

Input 1 --------->

So now H can be revised to take P as both inputs (the program and its input) and H should be able to determine if P will halt on P as its input. Let us construct a new, simple algorithm K that takes H's output as its input and does the following

1. if H outputs "loop" then K halts,

2. otherwise H's output of "halt" causes K to loop forever.

That is, K will do the opposite of H's output.

function K() {

if (H()=="loop"){

return;

} else {

while(true); //loop forever

}

}

Fig 2

----> True ------> Halt

P ------------ H ------> Loop ? ---> False ----- > Loop

----->

Since K is a program, let us use K as the input to K.

Fig 3

----> True ---------> Halt

K ----------- H ---> Loop ---> False --------> Loop

---->

If H says that K halts then K itself would loop (that's how we constructed it).
If H says that K loops then K will halt. In either case H gives the wrong answer for K. Thus H cannot work in all cases.