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. There 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.
