<p>No. Consider the problem <span class="math-container">$L=\{(n,x) ; x_n = 1 \}$</span> (where <span class="math-container">$n$</span> is a number written in binary). This is solvable in <span class="math-container">$O(\log(n))$</span> by a RAM machine but it takes at least <span class="math-container">$O(n)$</span> to be solved by a Turing machine. Now granted this is a stupid example relying on the fact that we don't need to read every bit to answer and the only bit of interest is far away. Can we get bounds for problem not in <span class="math-container">$O(n)$</span>?</p>
<p>Sorting can be done in <span class="math-container">$O(n\log(n))$</span> on a RAM machine but best known algorithm for sorting on Turing machine are larger than <a href="https://cs.stackexchange.com/questions/71291/is-the-runtime-complexity-of-sorting-on-log-n-or-on-log2-n?noredirect=1&amp;lq=1">that</a>.</p>
<p>As far as proving it goes, the issue is that we don't have any lower bound for any problem in the multitape Turing machine model (appart from problem like <span class="math-container">$L=\{ (M,1^n) ; M  \text{ stops in $n^2$ steps}\}$</span> and trivial you-have-to-read-every-bit argument which only yield <span class="math-container">$O(n)$</span> lower bounds). So unless you can prove that you can solve <span class="math-container">$L$</span> in <span class="math-container">$o(n^2)$</span> with a RAM (which you probably cannot because it is false) you would have to first come up with a problem for which you can prove a lower bound for Turing machines, which I believe would be of major interest (at least to me since I've never heard of such a problem).</p>

CC BY-SA 4.0
2024-07-23T16:41:53.240Z
2024-07-24T11:09:49.770Z
2024-07-24T11:09:49.770Z
ULechine
<p>I doubt it, but I have no proof.  Consider the following problem:</p>
<p>Input: A permutation <span class="math-container">$\sigma$</span> of <span class="math-container">$\{1,2,\dots,n\}$</span>, represented as the list <span class="math-container">$(\sigma(1),\sigma(2),\dots,\sigma(n))$</span> (i.e., <a href="https://en.wikipedia.org/wiki/Permutation#One-line_notation" rel="nofollow noreferrer">one-line notation</a>), and a positive integer <span class="math-container">$k$</span><br>
Output: <span class="math-container">$\sigma^k(1)$</span></p>
<p>It is easy for a RAM machine to solve this problem in <span class="math-container">$O(n)$</span> time, but I doubt that a multi-tape Turing machine can solve it in <span class="math-container">$O(n)$</span> time, or even <span class="math-container">$O(n \log n)$</span> time.</p>

CC BY-SA 4.0
2024-07-23T08:45:31.050Z
I guess a crucial question is how the RAM accesses the input, does it have random access on it as well? In that case, if we have a binary string as input and want to accept if and only if the $k$th symbol is 1, then the RAM can solve it even in $O(1)$ time?
Christian Komusiewicz
CC BY-SA 4.0
2024-07-23T08:56:50.340Z
@ChristianKomusiewicz, Good question.  That seems worth asking about separately.  I do not know the answer.
D.W.
CC BY-SA 4.0
2024-07-22T21:59:53.357Z
2024-07-22T21:59:53.357Z
D.W.
<p>It is known that many-tape Turing machines can be simulated by a one tape Turing machine with extra runtime costs. Furthermore, a single-tape Turing machine with a larger alphabet can be simulated by a 4-element alphabet with extra runtime as well. Can a RAM machine with a polynomial amount of memory be simulated by a multi-tape Turing machine without extra time or space costs?</p>

CC BY-SA 4.0
2024-07-22T21:56:02.333Z
https://cstheory.stackexchange.com/q/47670/5038
D.W.
<cc.complexity-theory><ds.algorithms><automata-theory><turing-machines>
Can a RAM machine with polynomial memory be simulated by a multi-tape Turing machine without extra time or space costs?
BooleanBoy18
# Can a RAM machine with polynomial memory be simulated by a multi-tape Turing machine without extra time or space costs?

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

It is known that many-tape Turing machines can be simulated by a one tape Turing machine with extra runtime costs. Furthermore, a single-tape Turing machine with a larger alphabet can be simulated by a 4-element alphabet with extra runtime as well. Can a RAM machine with a polynomial amount of memory be simulated by a multi-tape Turing machine without extra time or space costs?

**Tags:** cc.complexity-theory, ds.algorithms, automata-theory, turing-machines

> **Comments:**
> **username_1**: https://cstheory.stackexchange.com/q/47670/5038  

---

## 2 answers

### Answer by username_2 on 2024-07-23. Score: 5

No. Consider the problem $L=\{(n,x) ; x\_n = 1 \}$ (where $n$ is a number written in binary). This is solvable in $O(\log(n))$ by a RAM machine but it takes at least $O(n)$ to be solved by a Turing machine. Now granted this is a stupid example relying on the fact that we don't need to read every bit to answer and the only bit of interest is far away. Can we get bounds for problem not in $O(n)$?

Sorting can be done in $O(n\log(n))$ on a RAM machine but best known algorithm for sorting on Turing machine are larger than [that](https://cs.stackexchange.com/questions/71291/is-the-runtime-complexity-of-sorting-on-log-n-or-on-log2-n?noredirect=1&lq=1).

As far as proving it goes, the issue is that we don't have any lower bound for any problem in the multitape Turing machine model (appart from problem like $L=\{ (M,1^n) ; M \text{ stops in $n^2$ steps}\}$ and trivial you-have-to-read-every-bit argument which only yield $O(n)$ lower bounds). So unless you can prove that you can solve $L$ in $o(n^2)$ with a RAM (which you probably cannot because it is false) you would have to first come up with a problem for which you can prove a lower bound for Turing machines, which I believe would be of major interest (at least to me since I've never heard of such a problem).


---

### Answer by username_1 on 2024-07-22. Score: 3

I doubt it, but I have no proof. Consider the following problem:

Input: A permutation $\sigma$ of $\{1,2,\dots,n\}$, represented as the list $(\sigma(1),\sigma(2),\dots,\sigma(n))$ (i.e., [one-line notation](https://en.wikipedia.org/wiki/Permutation#One-line_notation)), and a positive integer $k$  
Output: $\sigma^k(1)$

It is easy for a RAM machine to solve this problem in $O(n)$ time, but I doubt that a multi-tape Turing machine can solve it in $O(n)$ time, or even $O(n \log n)$ time.

> **Comments:**
> **username_3**: I guess a crucial question is how the RAM accesses the input, does it have random access on it as well? In that case, if we have a binary string as input and want to accept if and only if the $k$th symbol is 1, then the RAM can solve it even in $O(1)$ time?  
> **username_1**: @ChristianKomusiewicz, Good question.  That seems worth asking about separately.  I do not know the answer.  

---

