The annotated Turing

Charles Petzold

Mentioned 3

Provides an expansion of Turing's original paper, a brief look at his life, and information on the Turing machine and computability topics.

More on

Mentioned in questions and answers.

Whenever people ask about the halting problem as it pertains to programming, people respond with "If you just add one loop, you've got the halting program and therefore you can't automate task"

Makes sense. If your program has an infinite loop, then when your program is running, you have no way of knowing whether the program is still crunching input, or if it is just looping infinitely.

But some of this seems counter intuitive. What if I was writing a halting problem solver, which takes source code as its input. rascher@localhost$ ./haltingSolver source.c

If my code (source.c) looks like this:

for (;;) {  /* infinite loop */  }

It seems like it'd be pretty easy for my program to see this. "Look the loop, and look at the condition. If the condition is just based on literals, and no variables, then you always know the outcome of the loop. If there are variables (eg while (x < 10)), see if those variables are ever modified. If not, then you always know the outcome of the loop."

Granted, these checks would not be trivial (calculating pointer arithmetics, etc) but it does not seem impossible. eg:

int x = 0
while (x < 10) {}

could be detected. along with - albeit not trivially:

int x = 0
while (x < 10)
   if (x == 10)
      x = 0

Now what about user input? That is the kicker, that is what makes a program unpredictable.

int x = 0;
while (x < 10) 
   scanf("%d", &x); /* ignoring infinite scanf loop oddities */

Now my program can say: "If the user enters a 10 or greater, the program will halt. On all other input, it will loop again."

Which means that, even with hundreds of inputs, one ought to be able to list the conditions on which the program will stop. Indeed, when I write a program, I always make sure someone has the ability to terminate it! I am not saying that the resulting list of conditions is trivial to create, but it doesn't seem impossible to me. You could take input from the user, use them to calculate pointer indexes, etc - but that just adds to the number of conditions to ensure the program will terminate, doesn't make it impossible to enumerate them.

So what exactly is the halting problem? What am I not understanding about the idea that we cannot write a problem to detect infinite loops? Or, why are "loops" such an oft-cited example?


So, let me change the question a little bit: what is the halting problem as it applies to computers? And then I will respond to some of the comments:

Many people have said that the program must be able to deal with "any arbitrary input." But in computers, there isn't ever any arbitrary input. If I only input a single byte of data, than I only have 2^8 possible inputs. So, as an example:

int c = getchar()

switch (c) {
   case 'q':
      /* quit the program */

All of the sudden, I have just accounted for all of the possibilities. If c has the bit pattern 0x71, it does one thing. For all other patterns, it does something else. Even a program that accepts arbitrary string input is never really "arbitrary", since resources are finite, which means that while the theory of "arbitrary" applies... it isn't exactly one-to-one with the practice.

The other example people cited is this:

while (n != 1)
    if (n & 1 == 1) 
        n = 3 * n + 1;
        n /= 2;

If n is a 32-bit integer... then I can visually tell you whether or not this will halt.

I guess this edit isn't asking anything, but the most convincing example I've seen is this one:

Assume that you have your magical program/method to determine that a program halts.

public bool DeterminesHalt(string filename, string[] args){
    //runs whatever program you tell it do, passing any args
    //returns true if the program halts, false if it doesn't

Now lets say we write a small piece of code such as...

public static void Main(string[] args){
    string filename = Console.ReadLine(); //read in file to run from user
    if(DeterminesHalt(filename, args))

So for this example, we can write a program to do the exact opposite of our magical halting method does. If we somehow determine that a given program will halt, we just hop into an infinite loop; otherwise if we determine that the program is in an infinite loop, we end the program.

Then again, if you intentionally write a program which contains an infinite loop... "solving the halting problem" is kind of moot, isn't it?

From Programming Pearls, by Jon Bentley

4.6 Problems

5. Prove that this program terminates when its input x is a positive integer.

while x != 1 do
    if even(x)
        x = x/2
        x = 3*x +1

A lot of interesting specific examples/analogies so far. If you want to read deeper into the background, there's a good book on Turing's original paper, The Annotated Turing, by Charles Petzold.

In a related, sideways-sorta, vein, there's a really neat essay up on the web, Who Can Name the Bigger Number? which brushes on Turing machines and Ackermann functions.

What is a Turing machine and why do people keep mentioning it? My IBM PC is all I need to do my computation! Why does anyone care about these machines?

In addition to the Wikipedia entry, you might want to pick up the book The Annotated Turing by Charles Petzold. Subtitled "A Guided Tour through Alan Turing's Historic Paper on Computability and the Turing Machine", it includes the complete paper, broken into chunks with lots of discourse on the topic, including a historical perspective.

Given a rational number, would it be possible to know whether the root or some other power of the number is an irrational number? Can an automaton be designed for such a purpose?

An irrational number is an infinite string, and if you want an automaton that can read it, it will need to continue reading infinitely.

You cannot build a decider (a machine that always halts with output true or false), but you can build an acceptor (a machine that halts with false, but continues forever for true), which is what I believe you're asking.

Consider a machine that accepts the irrational number of the form


Where the lengths of runs of 1s is always growing between 0s. It's relatively easy to define a Turing machine that can accept this number.

(For the implementation for such a machine, I'd suggest The Annotated Turing, which also has an implementation for a machine that accepts √2.)