Thursday, June 12, 2003

Turing Fundamentalists

Revised June 13

What's the deal with people defending the Turing Machine? This seems to come up everywhere: at the O'Reilly ETech conference, on the Coherence Engine discussion board, on a Boing Boing discussion board a year or so ago. Whenever anyone mentions the possibility that there might be a more powerful model than the Turing Machine, people go nuts. I usually get accused of not understanding the abstraction. Well, that might be true, although my old computational complexity professor would be disappointed to hear that. But the fact is that the Turing Machine is mostly certainly not the most powerful model out there.

This is, however, a complicated question. Let's break it into pieces. First, there's the issue of whether a computational model can, in any amount of time, solve a certain problem. Recall that it was Turing's proof that there are problems that the Turing machine cannot solve, notably the Halting Problem. This is an extension of Godel's incompleteness principle. Keep this in mind: Turing's accomplishment was not showing the universality of the machine, although he did do that; it was in showing the fundamental limits of it.

Now even given two models that can solve a problem, there's still performance questions. This isn't a trivial difference; a model that can solve a problem in polynomial time really is fundamentally more powerful than one that takes exponential time. And there are tons of complexity classes that describe computational models that solve problems in polynomial time that it would take a standard deterministic TM exponential time. Just for one example, if a DTM can call upon an oracle to answer questions, it can outperform a standard DTM. And of course DNA computers can solve NP problems in linear time, although requiring exponential space.

There seems to be debate in the complexity field over whether quantum computers will be a more powerful class than deterministic Turing Machines. The complexity class in question is BQP, for "bounded quantum in polynomial time." Is BQP a proper superset of P, meaning that there are problems that a quantum TM could compute in polynomial time that a DTM couldn't? Even more provocatively, it's possible that a quantum computer could compute problems non-computable (obviously we are dancing dangerously here with the word "compute," however) by any Turing Machine.

This is a field of study known as hypercomputation, that studies computational models more powerful than the Turing Machine, including, yes, believe it or not you skeptics, models that could solve the Halting Problem. It's a sketchy field as yet, but it's real; there are publications and workshops and proceedings and everything. I'm going to work through the field and blog it as I go; I'm still at the lit review stage.

But there's a social question buried here. Why are people so freaked out and defensive that there might be a more powerful model? I think perhaps people have taken "universal" the wrong way. Turing didn't prove the universality of the Turing Machine; he proved that a) a single Universal Turing Machine can simulate all other Turing Machines and b) the Turing Machine model was equivalent to a number of mechanical algorithms for solving problems. But this really is a bit of a circular argument: our definition of "computation" is "the thing that a Turing Machine does," so of course Turing Machines can do anything that's computation.

The open question is whether there are ways to solve problems that cannot be specified in the mechanical algorithm fashion of Turing Machines. And the signs are that there almost certainly are.