Tuesday, June 17, 2003

Halting Steps

Here are some points made by Bruce MacLennan from the University of Tennesee, Knoxville, on why we shouldn't care about the Halting Problem, and why the Turing Machine is a broken metaphor for real life computing:

1. In real life, the issue isn't whether a computation will eventually halt, it's whether it will complete within acceptable time boundaries. If your brain needs to figure out what your eyes are looking at, it needs to do it in a fraction of a second. The "algorithm" it uses might be linear, or it might be superexponential, but it doesn't matter. Classic complexity theory ignores the constants, because analyses of performance are supposed to be independent of underlying hardware. Put another way, the algorithm is disembodied. But the real world is embodied.

2. The Halting Problem, and in fact the Turing Machine itself, is based on a computational model of exact answers. (There are in fact alternate models of the Turing Machine that return approximate answers.) But again, in real life, the issue isn't whether you get the exact answer, it's getting an approximation that's within an acceptable error range.

3. Inputs in the Turing Machine are exact symbols that represent atoms of meaning. But the real world is, well, real; that is, composed of real values. (This is unproven, but if it's discrete, it's discrete at an incredible fidelity, far beyond our mechanical embodiments of TMs. More on this later.) Not just real, but noisy.

4. The real world doesn't stop. Most processes in the real world are not just continuous, but continuing. Your brain doesn't stop figuring out what your eyes see once it recognizes someone; it just keeps on processing. There's really no equivalent of "halt" in natural computation.

MacLennan goes into great depth on these and other points.

Now, again, this is not to dismiss the importance of the Turing Machine, its relevance as a model of computation, or the intellectual achievement of Alan Turing in showing the limits of mechanical, embodied, computation. But it does show that as a metaphor, the Turing Machine is not well suited for describing "natural computation," the sorts of things that the real world does, and that embodied machines must be able to do as well.

And by the way, MacLennan lists four or five computational models capable of solving the Halting Problem.