What exactly is the halting problem?

Question

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)
{
   x++;
   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?

UPDATE

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;
    else 
        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))
        for(;;);
    else
        return;
}

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?

Answer 1

I would suggest to read this: http://en.wikipedia.org/wiki/Halting_problem, especially http://en.wikipedia.org/wiki/Halting_problem#Sketch_of_proof in order to understand why this problem can't be solved in algorithmic way.

Answer 2

Assume that you write an algorithm that can check any arbitrary piece of code and tell if it halts.

Now give your algoritm itself to check.

Answer 3

Here is a simple explanation of the proof that the halting problem is undecidable.

Assume you have a program, H, which computes whether or not a program halts. H takes two parameters, the first is a description of a program, P, and the second is an input, I. H returns true if P halts on input I, and false otherwise.

Now write a program, p2, which takes as it's input the description of another program, p3. p2 calls H(p3, p3), then loops if H returns true and halts otherwise.

What happens when we run p2(p2)?

It must loop and halt at the same time, causing the universe to explode.

Answer 4

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
    else
        x = 3*x +1

Answer 5

A proof from another perspective

Suppose we got a cpu with instructions like mov, add, jmp, but without in nor out. And we got memory. Not like other cpus, this one has another register, called paraReg. This register is like a file, we can mov unlimited content into it, get the size of it, seek to the middle of it, delete some of the content from it, which are done through some additional instructions .

Before we start, let's define some words. A program is a bunch of instructions, which is a string. Before we run a program, we clear all the registers and memory to zero except paraReg , which holds the parameter(a string), and then put the program into memory location zero and set ip register to zero. A process is when a program is running.

Now the halting problem can be stated like this : given any program, called proObj(if it takes a parameter para0, we add an instruction on the first line of it: mov paraReg , para0), is there a program which takes proObj as the parameter and can decide whether proObj will halt when proObj starts to run on paraReg set to zero?

Suppose we got such a program, called p1. Then we can create another program, called p2 which takes a parameter para0. Through p1, we can tell if a program whose content is para0, whose parameter is para0, will halt or not.(We do it this way. Construct a program whose first line is [mov paraReg , para0], the rest is para0. Name this program pro0. Then we set paraReg to pro0 and call p1. ) If it will halt,we let p2 enter into an infinite loop, otherwise we let p2 halt.

If we put p2 into paraReg and run p2, will the process halt or not? If it halts, from the definition of p2, we know when we put p2 into paraReg and run p2, it should not halt; likewise , if it doesn't halt, we know when put p2 into paraReg and run p2 ,it should halt. Then we can say there is no p2, and there is no p1.

Answer 6

Yet another example. I recently ran into something called hailstone numbers. These numbers form a sequence with these rules

f(n) is odd  -  f(n+1) = 3*f(n)+1
f(n) is even -  f(n+1) = f(n)/2

Currently, it is assumed that all starting points will eventually arrive at 1, and then repeat 4,2,1,4,2,1,4,2,1... However there is no proof for this. So right now the only way to determine if a number terminates when fed into the hailstone sequence is to actually compute it until you arrive at 1.

This is the key to how I understand the halting problem. How I understand it is that you cannot for sure know a that a program will/will not halt unless you actually run the program. So any program that you write that could give you an answer for sure to the halting problem, would have to actually run the program.