**Jack Dikian**

**January 2011**

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.

## No comments:

## Post a Comment