[Overview] [Previous] [Next]
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:
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