# Simulating a $k$ tape Turing machine with a 2 tape Turing machine

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?

• 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.) Mar 17 at 13:10
• 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 ? Mar 17 at 14:40
• 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 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. Mar 17 at 15:25
• 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. Mar 19 at 17:41