<p>There are many models of computability, all giving the same notion of 'computable function'. To pick a few examples:</p>
<ul>
<li>Turing machines (with variants: one-ended, two-ended, multiple tapes...)</li>
<li>RAM machines</li>
<li>Fractran</li>
<li>Game of Life</li>
</ul>
<p>I believe that in all these examples, there is a natural notion of &quot;time&quot; 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.</p>
<p><strong>Question:</strong> Is this a necessary feature? Are there any known classical computational models with a natural different notion of “polynomial time”?</p>
<p>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?</p>
<hr />
<p><strong>Update</strong>: 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.</p>

CC BY-SA 4.0
2021-08-21T20:27:08.887Z
Would you say that quantum Turing machines are "a classical computational model"? If yes, the answer is presumably no.
Geoffroy Couteau
CC BY-SA 4.0
2021-08-21T21:09:54.510Z
see Extended Church Turing Thesis in variation section of https://en.m.wikipedia.org/wiki/Church%E2%80%93Turing_thesis
Kaveh
CC BY-SA 4.0
2021-08-22T15:15:07.510Z
@GeoffroyCouteau, no, I'm interested in indeed classical deterministic models.
Dylan Thurston
CC BY-SA 4.0
2021-08-22T15:27:18.147Z
@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.
Dylan Thurston
CC BY-SA 4.0
2021-08-22T15:31:00.250Z
I'm still interested in anything addressing the question of weaker models than Turing Machines.
Dylan Thurston
CC BY-SA 4.0
2021-08-22T15:36:26.850Z
Background: in teaching about quantum computing, I want to make the point that quantum computers appear to be stronger than all classical computing models, which are all equivalent to each other. But I want to check that last statement is believed to be correct. (And since this is an intro, I'm not going to get into subtleties of polynomial vs constant factor, etc)
Dylan Thurston
CC BY-SA 4.0
2021-08-23T11:57:12.973Z
I see. See also chapters in Odifreddi's Classical Recursion Theory books, iirc, there were some very interesting discussions.
Kaveh
<cc.complexity-theory><polynomial-time>
Is polynomial-time the same in all classical computational models?
Dylan Thurston
# Is polynomial-time the same in all classical computational models?

(Asked by: username_0 on 2021-08-21)

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.

**Tags:** cc.complexity-theory, polynomial-time

> **Comments:**
> **username_1**: Would you say that quantum Turing machines are "a classical computational model"? If yes, the answer is presumably no.  
> **username_2**: see Extended Church Turing Thesis in variation section of https://en.m.wikipedia.org/wiki/Church%E2%80%93Turing_thesis  
> **username_0**: @GeoffroyCouteau, no, I'm interested in indeed classical deterministic models.  
> **username_0**: @username_2, 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.  
> **username_0**: I'm still interested in anything addressing the question of weaker models than Turing Machines.  
> **username_0**: Background: in teaching about quantum computing, I want to make the point that quantum computers appear to be stronger than all classical computing models, which are all equivalent to each other. But I want to check that last statement is believed to be correct. (And since this is an intro, I'm not going to get into subtleties of polynomial vs constant factor, etc)  
> **username_2**: I see. See also chapters in Odifreddi's Classical Recursion Theory books, iirc, there were some very interesting discussions.  

---

## 0 answers

