The Halting Problem

Page last updated 04/24/01

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


Unsolvable Problems

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 = ON
red = amber = OFF
   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.




The Halting Problem

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.




Sketch of a proof that the Halting Problem is unsolvable

This proof was devised by Alan Turing, 1936

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.

halter.gif (1705 bytes)

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

  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.

halter2.gif (2128 bytes)

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

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

halter3.gif (2972 bytes)

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.