Halting problem

The halting problem is undecideable: there does not exist a Turing machine H such that H(e,x)=1 if e encodes a Turing machine M which halts on input x, and H(e,x)=0 otherwise. Suppose for the sake of contradiction that such a machine H existed. Define a new machine H': H' reads one input x, then calculates H(x,x); if H(x,x)=0 it halts, else H(x,x)=1 and H' goes into an infinite loop. Let f be the encoding of H'. What does H' do on input f? It halts iff H(f,f)=0, which (by the definition of H) occurs iff the machine encoded by f does not halt on input f, i.e. iff H' does not halt on input f. Since H' must either halt on input f or enter an infinite loop (i.e. not halt), this is impossible: H'(f) halts iff it doesn't. Thus no such machine H can exist.

"There exists no computable algorithm which, when given as input a program and an input to that program, can decide whether the program will halt or not."

The Halting Problem is an unsolvable decision problem. Simply stated it says that it is impossible for any program, that will certainly halt, to be able to decide if another program will halt or carry on calculating forever.

Surely it is possible to tell if a program will loop forever. Why can't we just write a program that will check for infinite loops, if control variables get incremented when they should be decremented, does the program contain a return statement etc? This would be a very useful program especially for debugging.

This program must be total and computable; that is it must be defined (guaranteed to halt) for any input and it must be able to be implemented on a computer (i.e. a Turing Machine). After all we don't want it to loop forever and we will need to run it. How can we ensure that this program can decide if any given program will halt? Looking for obvious infinite loops is a good way to start but that is just a heuristic; it could easily miss some special case you forgot to make it check for. The only way it can possibly check all the possible outcomes from running the program is to step through all the steps of the program and see if it terminates.

The only way to check if a program terminates is to run it for infinite time and if it has stopped after that time then it is defined. Running anything for infinite time is not really an option so we must go back to the heuristic approach. Let us assume for a minute that we have found a fool-proof halting problem solver. Let's call it H. H takes for its input a program p and outputs TRUE if the program will halt and FALSE if it does not halt.

The flowchart for this program (H) would look like this:

                            p
                            |
                            |
                            v
                           / \
                          / p \
                         /     \_______TRUE
                         \Halts/  Yes
                          \ ? /
                           \_/
                            |
                            |No
                            |
                          FALSE

The cool thing is H will even work on itself and will, of course, output TRUE because the program will always halt. What happens if in testing our halting problem solver we accidentally introduce an infinite loop right at the end? Then the flowchart will look like:

                              p
                              |
                              |
                            __v__
                           |     |
                           |  H  |
                           |_____|
                              |__________
                     Output(o)|          |
                              |          |
                             / \         ^
                            / o \        |
                           /  is \_______|
                           \ TRUE/  Yes
                            \   /
                             \_/
                              |
                              |No
                              |
                            HALT

Now if H output says that the input program (p) will halt then H won't halt and if the program (p) won't halt then H will halt. Now, what will our program say if we give it itself (call it H') as input? If H' halts then H' will loop forever and if H' loops forever then H' will halt. This is impossible because H' cannot halt and not halt at the same time. This is what Hofstadter would call a strange loop because in being true it makes itself false and visa-versa.

Where is the problem here? All we added is a little loop after H. We know loops are computable even if they don't halt so the impossibility must be within H itself. This is indeed where the problem lies and this is how we know that the halting problem is unsolvable.

There are plenty of other unsolvable problems many of them can be reduced to the halting problem; in fact reducing a problem to halting is a very effective way of proving that it is unsolvable. Here are a couple of examples:

The Emptiness Problem (E):

An emptiness problem solver will tell you if there is a possible input to a program (p) will allow it to halt. This is quite a simple example. If you feed E itself as input it will tell you if there is a program (p) that will allow E to terminate. That is it will tell you if E will always halt or not. This is the halting problem again and so it is impossible.

The Comparison Problem (C):

This is also known as the equivalency problem. A comparison solver will tell you if two programs (A and B) are equivalent; that is they always give the same output for the same input. The trick with this one is just to overwrite one of the inputs (i.e. A or B) with the instruction HALT. C will then be telling you if, for all inputs, the the other program will halt. Sound familiar?