It is important to understand what the Halting Problem does and doesn't say, and how this applies to computer programming.

First, every existing programming language, and every forseeable programming language, has no more power than a Turing machine. Hence, this result applies directly to programming languages.

The theorem does *not* say that we can *never* determine whether or not a
given program halts on a given input. Most of the time, for most practical programs, we
can and do eliminate infinite loops from our programs. We can even write a meta-program to
check another program for potential infinite loops, and get this meta-program to work *most
of the time.*

The theorem *does* say that we cannot ever write such a meta-program and have it
work *all of the time.* Moreover, the result can be used to demonstrate that
certain other programs are also impossible. Here's the basic outline:

- If we could solve problem X, we could solve the Halting Problem.
- We can't solve the Halting Problem.
- Therefore, we can't solve problem X.

Sometimes you will be able to solve a useful, practical subset of problem X. However, unless you have a particularly understanding customer, you are generally better off avoiding problem X altogether.

Copyright © 1996 by David Matuszek

Last modified Mar 27, 1996