The Consequences of the Halting Problem

By Alex Allain

So what does it mean that there is no program that can determine whether any given program will halt on a given input? Perhaps surprisingly, quite a bit. In fact, there are quite a few examples that are incredibly surprising -- for instance, it's not possible to write a program that can determine whether any given program will output its own binary code (i.e., the problem of detecting viruses is theoretically undecidable).

NOTE: For readers just joining us, you should be familiar with the halting problem to follow the arguments in this discussion.

How can this be? Well, remember that if we can determine whether or not a particular condition is true, we must be able to do so for every possible program. Now, what if we decide to put whatever program is in question as the first part of a particular program; for instance, say we had a program that could tell whether a particular program output "Hello world"; we'll call it DETECT-HELLO. DETECT-HELLO takes one argument, a program.

Now, let's build a program that tests whether some program we're interested in will halt on a given input: first, we'll run the program in question on that input, and then our new program will output "Hello world". Of course, if the program we're testing never halts, then the program we built will never output "Hello world".

So, to determine if the program in question halts on the input we've given it, all we need to do is run DETECT-HELLO on the program that we have constructed. In effect, DETECT-HELLO uses the output of the program we constructed as a flag for whether or not the program being tested will actually halt.

This approach is called a reduction because the goal is to show how solving the halting problem could be reduced to solving another type of problem. Using reductions, you can show that it is impossible to write programs to do all sorts of apparently simple things. In many cases, the problem is determining a YES/NO answer -- for instance, DETECT-HELLO can always tell us when "Hello world" will be output. The problem is that it has trouble determining if it won't ever be output.

Of course, in some cases, we can certainly prove that a given program will not halt, or that a given program cannot output "Hello world". But that's not really the point of all of this theory -- the point is that no general method, no algorithm, can be devised that will work in all cases. It's a bit like the difference between knowing the times tables and being able to multiply any two numbers -- in one case, you can answer questions about a few different inputs (5 times 6 or 7 times 8) but you won't be able to multiply everything (123 times 542).