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?

Improve this question
$\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$
    – Emil Jeřábek
    Mar 17, 2022 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, 2022 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$
    – Emil Jeřábek
    Mar 17, 2022 at 15:25
  • 1
    $\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, 2022 at 17:41

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.