7
$\begingroup$

In $O(n^2)$ steps, a 1-tape TM can simulate a 2-tape TM that runs for $O(n)$ steps.

How fast is an equivalent 2-tape TM known to run compared to a $O(n^2)$ time, 1-tape TM? "Open question" is a fine answer.

Edit: removed the word "simulate" and replace with question about equivalent TMs for clarity, add below facts.

Here are some (uninteresting) related problems I do know bounds on:

  • $DTIME_{1-tape}(O(n)){\subseteq}DTIME_{2-tape}(O(n))$. It's easy to make an equivalent 2-tape TM by ignoring one tape.
  • There is a a $O(n)$ time 1-tape TM (recognizing $\{1^n\}$) that takes $O(n)$ time for any equivalent 2-tape TM to run.
  • $DTIME_{2-tape}(O(n)){\subseteq}DTIME_{1-tape}(O(n^2))$. This is the well-known method mentioned above, to simulate a 2-tape TM on a 1-tape TM.
  • $DTIME_{1-tape}(O(n^2 logn)){\not\subseteq}DTIME_{2-tape}(O(n))$. Suppose every $O(n^2logn)$ time 1-tape TM ran in $O(n)$ time for some 2-tape TM. Then we would have $DTIME_{1-tape}(O(n^2logn)){\subseteq}DTIME_{2-tape}(O(n)){\subseteq}DTIME_{1-tape}(O(n^2))$ This would contradict known time hierarchy bounds for 1-tape TMs.
$\endgroup$
9
  • 1
    $\begingroup$ There is a lower bound of $\Omega(n^2/\log n\,\log\log n)$ by Ming Li, "Lower Bounds by Kolmogorov-Complexity", Proceedings of ICALP 1985, pp 383-393. In other words, up to poly-logarithmics factors the quadratic bound is tight. $\endgroup$ – Gamow Oct 3 '20 at 15:58
  • 2
    $\begingroup$ @Gamow That’s for the simulation of 2-tape on 1-tape, isn’t it? The question is about simulation of 1-tape on 2-tape, which is obviously at most $n$ (and, frankly, I have no idea what better bound the OP is expecting, as it’s clearly tight for problems that can be solved in linear time on the 1-tape TM). $\endgroup$ – Emil Jeřábek Oct 3 '20 at 16:36
  • 2
    $\begingroup$ What is the exact model for the 2 tape TM? 1 read only only left to right moves input tape + 1 work tape, 1 read only input tape + 1 work tape, 1 read write input tape + 1 work tape? $\endgroup$ – Marzio De Biasi Oct 4 '20 at 9:50
  • 2
    $\begingroup$ ... or equivalently is there a problem that requires $O(n^2)$ on a 2 tape TM that can be solved in $O(n^2)$ also on a 1 tape TM ? $\endgroup$ – Marzio De Biasi Oct 4 '20 at 10:18
  • 1
    $\begingroup$ I've heard this question before and don't know the answer. You're asking if having an extra tape always allows you to solve problems more quickly, kind of like how increasing the tape alphabet allows you to solve problems more efficiently by the Linear Speed-up Theorem: en.wikipedia.org/wiki/Linear_speedup_theorem $\endgroup$ – Michael Wehar Oct 5 '20 at 3:29
3
$\begingroup$

Just an extended comment to underline how the question is (up to my knowledge) far from being solved (and easy).

First of all there are no "natural" quadratic lower bounds with respect to multi-tape Turing machines (see e.g. K.W.Regan, On Superlinear Lower Bounds in Complexity Theory). So the approach, find an $O(n^2)$ problem on a 1-tape Turing machine that cannot be solved faster on a 2-tape TM would imply a major breakthrough.

On the opposite direction, one should be able to find a "universal" way to speed-up the simulation of a 1-tape TM on a 2-tape TM, but there are some examples for which the task seems hard; for example a 1-tape TM can efficiently simulate a dynamic non-linear system such as 1-D cellular automata - CA - (steps are parallel and use local information); and it is conjectured that the only way to know the state of the system after $n$ steps is to evolve the system $n$ times according to the rules (see e.g the (famous? :-) computational irreducibility - CIR - conjectured by S. Wolfram and analyzed in H. Zwirn and J.P. Delahaye, Unpredictability and Computational Irreducibility).

For example for every 1-D CA $A$ there is an $O(n^2)$ 1-tape TM $M_A$ that solves the problem:

Given a configuration $x$, is the state of $A$ equal to $x$ after $|x|$ steps from a blank initial configuration?

in $O(|x|^2)$ time.

Just use an expanded alphabet to overlap the target (input) configuration $x$, the current step evolving configuration and the next step configuration, and an extra bit for a "distributed" counter to stop the evolution after $|x|$ steps.

E.g.

x = 1 1 0 1 0 0 1  (target configuration)

x = [1 0 0 s ] [100s] [000s] [100s] [000s] [000s] [100s]
     | | | +-step counter
     | | +---next step CA configuration
     | +-----current step CA configuration
     +-------target configuration

The TM sweeps from left to right and apply the CA rules writing the new configuration in the "next step" bits. At the end of a sweep the role of the next/current bits are swapped. Furthermore, at every sweep it deletes an $s$, when no more $s$ it simply compares the current configuration to the target configuration.

There are not known ways to speed-up the simulation of a 1D CA on a k-tape TM, and (probably) such speed-up would imply that the Computation Irreducibility conjecture is false.

$\endgroup$
1
  • 1
    $\begingroup$ K.W.Regan's paper is news to me, and it's quite helpful background. Computational Irreducibility is not something I've seen well-defined before (although I see the Zwirn+Delhaye paper attempts to do so). Has much effort been put into proving or disproving this specific fomulation? I wouldn't really expect so (edit: although yes, I might expect effort has gone into speeding up 1-D CA) $\endgroup$ – Zachary Vance Oct 9 '20 at 11:11

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.