Page last updated 04/24/01

**These notes are taken from the The Limits of Computing, by Henry M. Walker.**

The Halting Problem is one of the simplest problems know to be unsolvable. You will note that the interesting problems involve loops.

Consider the following Javascript program segments (algorithm):

for(quarts = 1 ;
quarts < 10 ; quarts++){liters = quarts/1.05671; alert( quarts+" "+liters); } |
green
= ONred = amber = OFF while(true){ amber = ON; green = OFF; wait 10 seconds; red = ON; amber = OFF; wait 40 seconds; green = ON; red = OFF; } |

limit =
prompt("Max Value","");for(quarts = 1 ; quarts < limit ; quarts++){ liters = quarts/1.05671; alert( quarts+" "+liters); } |

The first program clearly is a one that will terminate after printing in an alert 10 lines of output.

The second program alerts as many times as indicated by the input.

The last program runs forever.

Algorithms may contain loops which may be infinite or finite in length. The amount of
work done in an algorithm usually depends on the data input. Algorithms may consist of
various numbers of loops, nested or in sequence. The **Halting problem** asks the
question.

*Given a program and an input to the program,
determine if the program will eventually stop when it is given that input.*

Trial solution

Just run the program with the given input. If the program stops, we know the program stops.

But if the program doesn't stop in a reasonable amount of time, we cannot conclude that it won't stop.

Maybe we didn't wait long enough.

This proof was devised by Alan Turing, 1936

Suppose you have a solution to the halting problem called H.

H takes two inputs:

- a program P and
- an input I for the program P.

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

*ASIDE: When an algorithm is coded, it is expressed as a string of characters which
can also be interpreted as a sequence of numbers. We can treat the program as data and
therefore a program can be thought of as input. *

*For example, compilers take programs as input and generate machine code as output.
Netscape takes a Javascript program and generates output.*

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

- if H outputs "
" then K halts,**loop** - otherwise H's output of "
" causes K to loop forever.**halt**

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

function K() { if (H()=="loop"){ return; } else { while(true); //loop forever } }

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

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

We've shown that it is possible to construct an input that causes any solution H to fail.