Posted by MacDood
link
Geoff Cohen's posted another provocative and fascinating essay about the limitations of Turing Machines.

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 computational complexity classes above the standard P and NP that represent problems that deterministic and non-deterministic Turing Machines can solve in polynomial time. Just for one example, the class of problems that can be solved by a Turing Machine that can, in turn, use another Turing Machine as an oracle is more powerful than a single Turing Machine.

LinkDiscuss [Boing Boing]