<p>Let <span class="math-container">$k$</span> be an (fixed, <span class="math-container">$3$</span> for instance) integer, what is the fastest simulation of a <span class="math-container">$k$</span> tape Turing machine by a two tape Turing machine?
That is we're looking for the best 2 tape TM <span class="math-container">$U$</span>, such that when given <span class="math-container">$&lt;\#M,x&gt;$</span> as input where <span class="math-container">$\#M$</span> is a representation of <span class="math-container">$M$</span> a <span class="math-container">$k$</span> tape TM, <span class="math-container">$U$</span> returns <span class="math-container">$M(x)$</span></p>
<p>As far as I know the best we can do is a logarithmic factor slowdown. Meaning the fastest <span class="math-container">$U(&lt;\#M,x&gt;)$</span> we know will stop in <span class="math-container">$O(T\log T)$</span> steps if <span class="math-container">$M(x)$</span> takes <span class="math-container">$T$</span> steps to stop. However I've read here and there in the literature and on this forum that if <span class="math-container">$k$</span> is fixed, then we can get rid of that logarithmic overhead. For instance this comment <a href="https://cstheory.stackexchange.com/a/33937/55419">https://cstheory.stackexchange.com/a/33937/55419</a> (but it's not the only place in which I've read it).</p>
<p>Here is a paper first showing the <span class="math-container">$T\log T$</span> slowdown. There doesn't seem to be anything indicating that we may go faster if <span class="math-container">$k$</span> is fixed.</p>
<p><a href="https://dl.acm.org/doi/10.1145/321356.321362" rel="nofollow noreferrer">https://dl.acm.org/doi/10.1145/321356.321362</a></p>
<p>I thought about it for a little while and I don't see any way to have a constant factor slowdown, even if it just were simulating <span class="math-container">$3$</span> tapes Turing machines with <span class="math-container">$2$</span> tapes. It's important for a result I'm writing if we could indeed have a constant factor slowdown, if you believe it to be true could you provide a proof?</p>

CC BY-SA 4.0
2022-03-17T13:10:09.177Z
I suspect that you are misreading the linked answer by Kaveh. Although the wording is not quite clear, what it is saying that for any constant $k\ge2$, a $k$-tape universal Turing machine can simulate any $k$-tape Turing machine without logarithmic overhead. It does not say that you can simulate a $k$-tape Turing machine on a $2$-tape Turing machine. (Indeed, it says *if we want to simulate an arbitrary constant number of tapes then AFAIK we don't know any such simulation*.)
Emil Jeřábek
CC BY-SA 4.0
2022-03-17T14:40:06.070Z
I did indeed have some doubts about the way to interpret the answer by Kaveh, he does not repeat the "respectively" twice... However the quoted sentence does not rule out simulating k tapes by two tapes (as far as Kaveh knows), since there is a difference between "arbitrary" and "as large as you want but fixed". In any case it's not the first place where I think I've read this assertion (I could have misread the other authors). As far as the initial question went, do you reckon the best known simulations are in fact with a logarithmic slowdown ?
ULechine
CC BY-SA 4.0
2022-03-17T15:25:36.750Z
I am no expert in this particular area, but a cursory reading suggests that nothing better than the logarithmic slowdown is known. E.g., [Dmytro Taranovsky](https://cstheory.stackexchange.com/a/39062) writes *It is plausible that for every $k$, $k+1$-tape machines cannot be simulated by $k$-tape machines without a logarithmic overhead*. He’s very thoughtful about subtle details, so it carries some weight if he says that.
Emil Jeřábek
CC BY-SA 4.0
2022-03-19T17:41:55.847Z
I think that answers my initial question. I'll spell it out for future readers : as far as we know it is not possible to simulate a k+1 tape machine with a k tape machine without a logarithmic overhead.
ULechine
<cc.complexity-theory><time-complexity><universal-computation><universal-turing-machines><time-hierarchy>
Simulating a $k$ tape Turing machine with a 2 tape Turing machine
ULechine
# Simulating a $k$ tape Turing machine with a 2 tape Turing machine

(Asked by: username_0 on 2022-03-17)

Let $k$ be an (fixed, $3$ for instance) integer, what is the fastest simulation of a $k$ tape Turing machine by a two tape Turing machine?
That is we're looking for the best 2 tape TM $U$, such that when given $<\#M,x>$ as input where $\#M$ is a representation of $M$ a $k$ tape TM, $U$ returns $M(x)$

As far as I know the best we can do is a logarithmic factor slowdown. Meaning the fastest $U(<\#M,x>)$ we know will stop in $O(T\log T)$ steps if $M(x)$ takes $T$ steps to stop. However I've read here and there in the literature and on this forum that if $k$ is fixed, then we can get rid of that logarithmic overhead. For instance this comment <https://cstheory.stackexchange.com/a/33937/55419> (but it's not the only place in which I've read it).

Here is a paper first showing the $T\log T$ slowdown. There doesn't seem to be anything indicating that we may go faster if $k$ is fixed.

<https://dl.acm.org/doi/10.1145/321356.321362>

I thought about it for a little while and I don't see any way to have a constant factor slowdown, even if it just were simulating $3$ tapes Turing machines with $2$ tapes. It's important for a result I'm writing if we could indeed have a constant factor slowdown, if you believe it to be true could you provide a proof?

**Tags:** cc.complexity-theory, time-complexity, universal-computation, universal-turing-machines, time-hierarchy
> **Comments:**
> **username_1**: I suspect that you are misreading the linked answer by Kaveh. Although the wording is not quite clear, what it is saying that for any constant $k\ge2$, a $k$-tape universal Turing machine can simulate any $k$-tape Turing machine without logarithmic overhead. It does not say that you can simulate a $k$-tape Turing machine on a $2$-tape Turing machine. (Indeed, it says *if we want to simulate an arbitrary constant number of tapes then AFAIK we don't know any such simulation*.)  
> **username_0**: I did indeed have some doubts about the way to interpret the answer by Kaveh, he does not repeat the "respectively" twice... However the quoted sentence does not rule out simulating k tapes by two tapes (as far as Kaveh knows), since there is a difference between "arbitrary" and "as large as you want but fixed". In any case it's not the first place where I think I've read this assertion (I could have misread the other authors). As far as the initial question went, do you reckon the best known simulations are in fact with a logarithmic slowdown ?  
> **username_1**: I am no expert in this particular area, but a cursory reading suggests that nothing better than the logarithmic slowdown is known. E.g., [Dmytro Taranovsky](https://cstheory.stackexchange.com/a/39062) writes *It is plausible that for every $k$, $k+1$-tape machines cannot be simulated by $k$-tape machines without a logarithmic overhead*. He’s very thoughtful about subtle details, so it carries some weight if he says that.  
> **username_0**: I think that answers my initial question. I'll spell it out for future readers : as far as we know it is not possible to simulate a k+1 tape machine with a k tape machine without a logarithmic overhead.  

---

## 0 answers

