4
$\begingroup$

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?

$\endgroup$
4
  • 2
    $\begingroup$ 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.) $\endgroup$ Mar 17 at 13:10
  • $\begingroup$ 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 ? $\endgroup$
    – ULechine
    Mar 17 at 14:40
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 17 at 15:25
  • $\begingroup$ 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. $\endgroup$
    – ULechine
    Mar 19 at 17:41

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.