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?
1
-
$\begingroup$ cstheory.stackexchange.com/q/47670/5038 $\endgroup$– D.W.Commented Jul 22 at 21:56
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
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).
$\begingroup$
$\endgroup$
2
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), 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.
-
$\begingroup$ 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? $\endgroup$ Commented Jul 23 at 8:45
-
$\begingroup$ @ChristianKomusiewicz, Good question. That seems worth asking about separately. I do not know the answer. $\endgroup$– D.W.Commented Jul 23 at 8:56