<p>A key idea that enables this is <em>data as code</em>: we want to execute the encoding of a machine directly, rather than indirectly via an interpreter. Some ways to turn that idea into a formal model of computation:</p>
<ul>
<li><p>A basic variant of modern computer architectures: registers, basic arithmetic, read and write in memory, and jumps. Then you can write a program in memory and jump to it.</p>
</li>
<li><p>If we want to stick to Turing machines (state machine + tape), we can add a new type of transition that, when taken, loads a Turing machine, encoded on the tape, into wherever the currently running Turing machine is stored, and continues by running as the new machine. <a href="https://en.wikipedia.org/wiki/Homoiconicity" rel="noreferrer">Homoiconicity</a> is sometimes used to refer to such a feature in programming languages.</p>
</li>
</ul>
<blockquote>
<p>why do we care about Turing machine ? Why not just do everything in RAM and say goodbye to those pesky log factors. I suspect it is because of historical developments but I may be wrong.</p>
</blockquote>
<p>Turing machines are simple and intuitive.</p>
<p>For a different model than Turing machines to become the standard, it should at least make it no harder to re-prove existing results in the field, many of which aren't affected by log factors to begin with.</p>
<p>For example, the Cook-Levin theorem proves that SAT is NP-complete by encoding the execution of a Turing machine as a boolean formula. This encoding relies crucially on a kind of &quot;locality&quot; of Turing machine operations which would be broken by the addition of &quot;jump&quot; or &quot;eval&quot; operations as in the alternative models above.</p>

CC BY-SA 4.0
2024-07-17T15:59:49.710Z
Thanks for the homoiconicity, I had the same idea and started writing about it but now I see that's it's been thought of before. Do you have a reference to homonoic Turing machines ? I think it needs the possibility to add tapes in order to be of constant slowdown.
ULechine
CC BY-SA 4.0
2024-07-14T14:11:40.310Z
2024-07-14T14:11:40.310Z
Li-yao Xia
<p>For any fixed k &gt; 1, the k-tape Turing machine model has a universal Turing machine with only linear slow down.  This is a result due to Martin Fürer: The Tight Deterministic Time Hierarchy. STOC 1982: 8-16.</p>
<p>The proof is technically involved, and presumably the reson why people don't use this model when (for instance) defining <span class="math-container">$K^t$</span>, is because they don't want to argue that 3-tape Turing machines (or 8-tape Turing machines, etc.) is the model they want to use.</p>
<p>The RAM model is simple, but in its simplest form it's not terribly realistic, and modifying the model to make it more realistic seems to make the resulting model unpalatably complicated.</p>

CC BY-SA 4.0
2024-07-17T16:20:08.223Z
Thank you I didn't know about this result. I realize now that my grievances with TM go beyond just this one issue. The inexistence of arrays, the strange lower bounds for sorting amongst other things are really annoying to deal with when designing algorithms for lower bounds proofs. For instance this problem "given a list of m numbers between [1;n], output a number in [1;n] different from the m ones" is solvable in O(m) time by a RAM machine but for Turing machine the lower bound is not clear at all.
ULechine
CC BY-SA 4.0
2024-07-18T18:12:42.683Z
The Turing machine model is also not "terribly realistic". After all, it suggests that SAT-solving is infeasible, yet we use SMT-solvers like Z3 all the time in real-world verification of hardware and software.
Martin Berger
CC BY-SA 4.0
2024-07-19T20:25:13.080Z
The comment regarding SAT solvers really says nothing about the Turing machine model.  It's really a comment regarding the relevance of the supposed worst-case complexity of SAT (on any "realistic" model).  Cryptographic tasks can easily be translated into SAT instances that on which SAT solvers fail miserably.  So the worst-case complexity of SAT on "realistic" models is relevant for some tasks.  That said, I'm not going to argue that the Turing machine model is a "realistic" programming model.  But at least it can be translated into hardware fairly efficiently.
Eric Allender
CC BY-SA 4.0
2024-07-21T16:06:55.337Z
@EricAllender Good point regarding worst-case complexity. Thanks. However, the TM model does not map well to modern hardware, such as GPUs with their extreme parallelism, and they also don't map well to what is costly in modern processors (data movement).
Martin Berger
CC BY-SA 4.0
2024-07-16T18:37:58.937Z
2024-07-16T18:37:58.937Z
Eric Allender
<p>One problem with Turing machines is that the universal Turing machine <span class="math-container">$U$</span> can simulate any machine <span class="math-container">$M$</span> but with a <span class="math-container">$\log$</span> slowdown, meaning <span class="math-container">$U(\#M,x)$</span> runs in time <span class="math-container">$O(T(n)log(n) + O(n))$</span>, where <span class="math-container">$n=|\#M|+ |x|$</span>, <span class="math-container">$\#M$</span> is a representation of <span class="math-container">$M$</span>, and function <span class="math-container">$T$</span> is the running time of <span class="math-container">$M$</span>. This <span class="math-container">$\log$</span> factor can get quite annoying sometime because you have to fiddle around it in definition like <span class="math-container">$K^t$</span> complexity (time bounded kolmogorov complexity), nowadays some paper just consider the <span class="math-container">$RAM$</span> model or change around the definition of <span class="math-container">$K^t$</span> (for instance considering actual steps in the machine <span class="math-container">$M$</span> instead of simulation steps by <span class="math-container">$U$</span>) to cater to their need. They also often spend a paragraph saying how their paper shouldn't be rejected because they sightly changed around the definitions.</p>
<p>My question then is : what are models of computation with only a constant slowdown factor ? Preferably realistic (in the sense explained below). I know the <span class="math-container">$RAM$</span> model but it jumps around registers at infinite speed. Then there is the boolean circuit model which I believe would have a constant slowdown (although simulation of a circuit by a circuit is not something I think I've ever come accross) but it is non uniform. As far as i'm concerned the Turing machine model is realistic in the sense that it can be implemented in real life without breaking the laws of physics (the infinite tape can be replaced by an ever-expanding one)</p>
<p>Second follow-up question : why do we care about Turing machine ? Why not just do everything in <span class="math-container">$RAM$</span> and say goodbye to those pesky <span class="math-container">$\log$</span> factors. I suspect it is because of historical developments but I may be wrong.</p>
<p>Third follow-up question : would people be interested in a realistic computation model with only a constant slowdown (I think that I can get that with a slight modification of the definition of Turing machines)</p>

CC BY-SA 4.0
2024-07-13T19:59:03.337Z
(if the universe is infinite :)
cody
CC BY-SA 4.0
2024-07-13T20:33:09.610Z
I mean if it is not then every language is finite so everything is in O(1). Or at least we have to severely revise the definition of time complexity lol
ULechine
CC BY-SA 4.0
2024-07-14T11:32:42.830Z
What do you mean by the RAM model jumping between registers at infinite speed?
Command Master
CC BY-SA 4.0
2024-07-14T14:55:41.920Z
In the RAM model (unless i'm mistaken) you can jump at a location in memory in constant time. In some definitions RAM models have infinitely many registers and you can access the content of a register in constant time
ULechine
<time-complexity><computability><universal-computation>
What are the computations model with a constant slowdown ? (and why do we care about Turing machines)
ULechine
# What are the computations model with a constant slowdown ? (and why do we care about Turing machines)

(Asked by: username_0 on 2024-07-12)

One problem with Turing machines is that the universal Turing machine $U$ can simulate any machine $M$ but with a $\log$ slowdown, meaning $U(\#M,x)$ runs in time $O(T(n)log(n) + O(n))$, where $n=|\#M|+ |x|$, $\#M$ is a representation of $M$, and function $T$ is the running time of $M$. This $\log$ factor can get quite annoying sometime because you have to fiddle around it in definition like $K^t$ complexity (time bounded kolmogorov complexity), nowadays some paper just consider the $RAM$ model or change around the definition of $K^t$ (for instance considering actual steps in the machine $M$ instead of simulation steps by $U$) to cater to their need. They also often spend a paragraph saying how their paper shouldn't be rejected because they sightly changed around the definitions.

My question then is : what are models of computation with only a constant slowdown factor ? Preferably realistic (in the sense explained below). I know the $RAM$ model but it jumps around registers at infinite speed. Then there is the boolean circuit model which I believe would have a constant slowdown (although simulation of a circuit by a circuit is not something I think I've ever come accross) but it is non uniform. As far as i'm concerned the Turing machine model is realistic in the sense that it can be implemented in real life without breaking the laws of physics (the infinite tape can be replaced by an ever-expanding one)

Second follow-up question : why do we care about Turing machine ? Why not just do everything in $RAM$ and say goodbye to those pesky $\log$ factors. I suspect it is because of historical developments but I may be wrong.

Third follow-up question : would people be interested in a realistic computation model with only a constant slowdown (I think that I can get that with a slight modification of the definition of Turing machines)

**Tags:** time-complexity, computability, universal-computation

> **Comments:**
> **username_1**: (if the universe is infinite :)  
> **username_0**: I mean if it is not then every language is finite so everything is in O(1). Or at least we have to severely revise the definition of time complexity lol  
> **username_2**: What do you mean by the RAM model jumping between registers at infinite speed?  
> **username_0**: In the RAM model (unless i'm mistaken) you can jump at a location in memory in constant time. In some definitions RAM models have infinitely many registers and you can access the content of a register in constant time  

---

## 2 answers

### Answer by username_3 on 2024-07-14. Score: 5 | Accepted answer

A key idea that enables this is *data as code*: we want to execute the encoding of a machine directly, rather than indirectly via an interpreter. Some ways to turn that idea into a formal model of computation:

* A basic variant of modern computer architectures: registers, basic arithmetic, read and write in memory, and jumps. Then you can write a program in memory and jump to it.
* If we want to stick to Turing machines (state machine + tape), we can add a new type of transition that, when taken, loads a Turing machine, encoded on the tape, into wherever the currently running Turing machine is stored, and continues by running as the new machine. [Homoiconicity](https://en.wikipedia.org/wiki/Homoiconicity) is sometimes used to refer to such a feature in programming languages.

> why do we care about Turing machine ? Why not just do everything in RAM and say goodbye to those pesky log factors. I suspect it is because of historical developments but I may be wrong.

Turing machines are simple and intuitive.

For a different model than Turing machines to become the standard, it should at least make it no harder to re-prove existing results in the field, many of which aren't affected by log factors to begin with.

For example, the Cook-Levin theorem proves that SAT is NP-complete by encoding the execution of a Turing machine as a boolean formula. This encoding relies crucially on a kind of "locality" of Turing machine operations which would be broken by the addition of "jump" or "eval" operations as in the alternative models above.

> **Comments:**
> **username_0**: Thanks for the homoiconicity, I had the same idea and started writing about it but now I see that's it's been thought of before. Do you have a reference to homonoic Turing machines ? I think it needs the possibility to add tapes in order to be of constant slowdown.  

---

### Answer by username_4 on 2024-07-16. Score: 9

For any fixed k > 1, the k-tape Turing machine model has a universal Turing machine with only linear slow down. This is a result due to Martin Fürer: The Tight Deterministic Time Hierarchy. STOC 1982: 8-16.

The proof is technically involved, and presumably the reson why people don't use this model when (for instance) defining $K^t$, is because they don't want to argue that 3-tape Turing machines (or 8-tape Turing machines, etc.) is the model they want to use.

The RAM model is simple, but in its simplest form it's not terribly realistic, and modifying the model to make it more realistic seems to make the resulting model unpalatably complicated.

> **Comments:**
> **username_0**: Thank you I didn't know about this result. I realize now that my grievances with TM go beyond just this one issue. The inexistence of arrays, the strange lower bounds for sorting amongst other things are really annoying to deal with when designing algorithms for lower bounds proofs. For instance this problem "given a list of m numbers between [1;n], output a number in [1;n] different from the m ones" is solvable in O(m) time by a RAM machine but for Turing machine the lower bound is not clear at all.  
> **username_5**: The Turing machine model is also not "terribly realistic". After all, it suggests that SAT-solving is infeasible, yet we use SMT-solvers like Z3 all the time in real-world verification of hardware and software.  
> **username_4**: The comment regarding SAT solvers really says nothing about the Turing machine model.  It's really a comment regarding the relevance of the supposed worst-case complexity of SAT (on any "realistic" model).  Cryptographic tasks can easily be translated into SAT instances that on which SAT solvers fail miserably.  So the worst-case complexity of SAT on "realistic" models is relevant for some tasks.  That said, I'm not going to argue that the Turing machine model is a "realistic" programming model.  But at least it can be translated into hardware fairly efficiently.  
> **username_5**: @EricAllender Good point regarding worst-case complexity. Thanks. However, the TM model does not map well to modern hardware, such as GPUs with their extreme parallelism, and they also don't map well to what is costly in modern processors (data movement).  

---

