MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 2 deleted 5 characters in body

Since you've asked the question here at MathOverflow rather than a CS theory site, let me try to give the perspective from computability theory rather than computational complexity theory. Thus, I give in a sense a math answer rather than a CS answer, although I realize that this is not the answer you seek.

From the perspective of computability theory, the most important fact about all the dozens or hundreds of varieties of computational models is precisely the fact that they are all equivalent. The differences don't matterThere is no "best" model.

It really is quite remarkable that all the models of computation that have been proposed give rise to exactly the same class of computable functions and decidable sets.

  • Turing machines, Turing machines with multiple tapes, single tape, big alphabets, multi-heads, etc., register machines, register machines with expanded instruction sets, machines with stacks, recursive functions, $\Sigma_1$-definable functions in arithmetic, etc. etc. and even game of life viewed as computation, group theoretic word problems, post correspondence computations, tiling problems viewed as computational models...

The fact that all the proposed models of computability are equivalent in this way indicates that this concept of computability is a highly robust mathematical idea. Indeed, the equivalence of the models is usually taken as strong or even decisive evidence for the Church-Turing thesis, the philosophical claim that any of these definitions of computability captures the notion of what is computable-in-principle.

It is easy to imagine, after all, that things might have turned out differently, and that there would be a hierarchy of computability, where having a stronger machine model would allow you to decide more sets and to compute a larger class of functions. But instead, we have a low-level threshold phenomenon, where once you attain a certain very primitive power of computability, then all the models can simulate all the other models.

Thus, from this computability theory point of view, there is no "best" model, and it doesn't matter at all which model you use. The purpose of the models in computability theory is not to design computers or to design algorithms, but to help us understand the power of computability and especially its limitations. Most computability theorists do not rely on a single model of computability, and prefer to fall back on abstract definability characterizations, which center on the idea of unbounded search, at the essence of computability.

I am reminded of conversations I've often had with students, who upon seeing the Turing machine model want to extend it by adding extra power to the machines, allowing the machine to do in one step what used to take several or augmenting the machine with registers and so on, in order to make a "better" Turing machine. Such efforts are completely pointless, because the purpose of the Turing machine model is not to program with it, but rather to have a theoretical model that is simple, yet fully powerful. We want a weak-seeming model, because we want to use the model to show that things are not computable, rather than that they are.

But I realize that this is probably not your perspective. It is sometimes said that the difference between computability theory and computational complexity theory is that the computability theorist is fundamentally interested in studying the non-computable, the hierarchy of Turing degrees, while the complexity theorist studies what is computable.

The equivalence between the models extends deeply down into complexity theory, in the sense that to my knowledge, all of the standard models of computability offer polynomial time simulation in each other. That is, any model can simulate any other model within a polynomial time factor.

Thus, the differences between the models arise only when one cares about the particular polynomial, as you indicate you do in your question. And this is a concern that takes one out of computability theory and into computational complexity.

show/hide this revision's text 1

Since you've asked the question here at MathOverflow rather than a CS theory site, let me try to give the perspective from computability theory rather than computational complexity theory. Thus, I give in a sense a math answer rather than a CS answer, although I realize that this is not the answer you seek.

From the perspective of computability theory, the most important fact about all the dozens or hundreds of varieties of computational models is precisely the fact that they are all equivalent. The differences don't matter.

It really is quite remarkable that all the models of computation that have been proposed give rise to exactly the same class of computable functions and decidable sets.

  • Turing machines, Turing machines with multiple tapes, single tape, big alphabets, multi-heads, etc., register machines, register machines with expanded instruction sets, machines with stacks, recursive functions, $\Sigma_1$-definable functions in arithmetic, etc. etc. and even game of life viewed as computation, group theoretic word problems, post correspondence computations, tiling problems viewed as computational models...

The fact that all the proposed models of computability are equivalent in this way indicates that this concept of computability is a highly robust mathematical idea. Indeed, the equivalence of the models is usually taken as strong or even decisive evidence for the Church-Turing thesis, the philosophical claim that any of these definitions of computability captures the notion of what is computable-in-principle.

It is easy to imagine, after all, that things might have turned out differently, and that there would be a hierarchy of computability, where having a stronger machine model would allow you to decide more sets and to compute a larger class of functions. But instead, we have a low-level threshold phenomenon, where once you attain a certain very primitive power of computability, then all the models can simulate all the other models.

Thus, from this computability theory point of view, there is no "best" model, and it doesn't matter at all which model you use. The purpose of the models in computability theory is not to design computers or to design algorithms, but to help us understand the power of computability and especially its limitations. Most computability theorists do not rely on a single model of computability, and prefer to fall back on abstract definability characterizations, which center on the idea of unbounded search, at the essence of computability.

I am reminded of conversations I've often had with students, who upon seeing the Turing machine model want to extend it by adding extra power to the machines, allowing the machine to do in one step what used to take several or augmenting the machine with registers and so on, in order to make a "better" Turing machine. Such efforts are completely pointless, because the purpose of the Turing machine model is not to program with it, but rather to have a theoretical model that is simple, yet fully powerful. We want a weak-seeming model, because we want to use the model to show that things are not computable, rather than that they are.

But I realize that this is probably not your perspective. It is sometimes said that the difference between computability theory and computational complexity theory is that the computability theorist is fundamentally interested in studying the non-computable, the hierarchy of Turing degrees, while the complexity theorist studies what is computable.

The equivalence between the models extends deeply down into complexity theory, in the sense that to my knowledge, all of the standard models of computability offer polynomial time simulation in each other. That is, any model can simulate any other model within a polynomial time factor.

Thus, the differences between the models arise only when one cares about the particular polynomial, as you indicate you do in your question. And this is a concern that takes one out of computability theory and into computational complexity.