There are many models of computability, all giving the same notion of 'computable function'. To pick a few examples:
- Turing machines (with variants: one-ended, two-ended, multiple tapes...)
- RAM machines
- Game of Life
I believe that in all these examples, there is a natural notion of "time" of a computation that are all polynomially-related to each other; so, although one-ended Turing machines are vastly slower than RAM machines, the relationship is still polynomial.
Question: Is this a necessary feature? Are there any known classical computational models with a natural different notion of “polynomial time”?
Given what we believe about the strong Church-Turing thesis, if there are different models presumably the would be slower than the standard class above. Of course non-deterministic computational models are believed to go the other direction, as does quantum computation. But are there computational models giving standard computation that are more than polynomially slower than Turing machines?
Update: After a little more thought, Fractran and other counter machines are exponentially slower than Turing machines, since numbers can only be represented in unary, answering my question in the negative. Apologies for not thinking it through enough.