1
$\begingroup$

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
  • Fractran
  • 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.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Would you say that quantum Turing machines are "a classical computational model"? If yes, the answer is presumably no. $\endgroup$
    – Geoffroy Couteau
    Aug 21, 2021 at 20:27
  • 2
    $\begingroup$ see Extended Church Turing Thesis in variation section of en.m.wikipedia.org/wiki/Church%E2%80%93Turing_thesis $\endgroup$
    – Kaveh
    Aug 21, 2021 at 21:09
  • $\begingroup$ @GeoffroyCouteau, no, I'm interested in indeed classical deterministic models. $\endgroup$
    – Dylan Thurston
    Aug 22, 2021 at 15:15
  • 1
    $\begingroup$ @Kaveh, that was a good article to review again, thank you. In particular the van Emde Boas article in the Handbook of Complexity Theory seems to be a much more careful examination of the questions than I'd seen previously. $\endgroup$
    – Dylan Thurston
    Aug 22, 2021 at 15:27
  • 2
    $\begingroup$ I see. See also chapters in Odifreddi's Classical Recursion Theory books, iirc, there were some very interesting discussions. $\endgroup$
    – Kaveh
    Aug 23, 2021 at 11:57

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy