<p>Just an extended comment to underline how the question is (up to my knowledge) far from being solved (and easy).</p>
<p>First of all there are no &quot;natural&quot; 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 <span class="math-container">$O(n^2)$</span> problem on a 1-tape Turing machine that cannot be solved faster on a 2-tape TM would imply a major breakthrough.</p>
<p>On the opposite direction, one should be able to find a &quot;universal&quot; 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 - (<em>steps are parallel and use local information</em>); and it is conjectured that the only way to know the state of the system after <span class="math-container">$n$</span> steps is to evolve the system <span class="math-container">$n$</span> times according to the rules (see e.g the (famous? :-) <em>computational irreducibility</em> - CIR - conjectured by S. Wolfram and analyzed in H. Zwirn and J.P. Delahaye, Unpredictability and Computational Irreducibility).</p>
<p>For example for every 1-D CA <span class="math-container">$A$</span> there is an <span class="math-container">$O(n^2)$</span> 1-tape TM <span class="math-container">$M_A$</span> that solves the problem:</p>
<blockquote>
<p>Given a configuration <span class="math-container">$x$</span>, is the state of <span class="math-container">$A$</span> equal to <span class="math-container">$x$</span> after <span class="math-container">$|x|$</span> steps from a blank initial configuration?</p>
</blockquote>
<p>in <span class="math-container">$O(|x|^2)$</span> time.</p>
<p>Just use an expanded alphabet to overlap the target (input) configuration <span class="math-container">$x$</span>, the current step evolving configuration and the next step configuration, and an extra bit for a &quot;distributed&quot; counter to stop the evolution after  <span class="math-container">$|x|$</span> steps.</p>
<p>E.g.</p>
<pre><code>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
</code></pre>
<p>The TM sweeps from left to right and apply the CA rules writing the new configuration in the &quot;next step&quot; bits. At the end of a sweep the role of the next/current bits are swapped. Furthermore, at every sweep it deletes an <span class="math-container">$s$</span>, when no more <span class="math-container">$s$</span>  it simply compares the current configuration to the target configuration.</p>
<p>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.</p>

CC BY-SA 4.0
2020-10-09T11:11:11.783Z
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)
Zachary Vance
CC BY-SA 4.0
2020-10-08T11:32:56.863Z
2020-10-08T13:43:26.453Z
2020-10-08T13:43:26.453Z
Marzio De Biasi
<p>In <span class="math-container">$O(n^2)$</span> steps, a 1-tape TM can simulate a 2-tape TM that runs for <span class="math-container">$O(n)$</span> steps.</p>
<p>How fast is an equivalent 2-tape TM known to run compared to a <span class="math-container">$O(n^2)$</span> time, 1-tape TM?
&quot;Open question&quot; is a fine answer.</p>
<p>Edit: removed the word &quot;simulate&quot; and replace with question about equivalent TMs for clarity, add below facts.</p>
<p>Here are some (uninteresting) related problems I do know bounds on:</p>
<ul>
<li><span class="math-container">$DTIME_{1-tape}(O(n)){\subseteq}DTIME_{2-tape}(O(n))$</span>. It's easy to make an equivalent 2-tape TM by ignoring one tape.</li>
<li>There is a a <span class="math-container">$O(n)$</span> time 1-tape TM (recognizing <span class="math-container">$\{1^n\}$</span>) that takes <span class="math-container">$O(n)$</span> time for any equivalent 2-tape TM to run.</li>
<li><span class="math-container">$DTIME_{2-tape}(O(n)){\subseteq}DTIME_{1-tape}(O(n^2))$</span>. This is the well-known method mentioned above, to simulate a 2-tape TM on a 1-tape TM.</li>
<li><span class="math-container">$DTIME_{1-tape}(O(n^2 logn)){\not\subseteq}DTIME_{2-tape}(O(n))$</span>. Suppose every <span class="math-container">$O(n^2logn)$</span> time 1-tape TM ran in <span class="math-container">$O(n)$</span> time for some 2-tape TM. Then we would have <span class="math-container">$DTIME_{1-tape}(O(n^2logn)){\subseteq}DTIME_{2-tape}(O(n)){\subseteq}DTIME_{1-tape}(O(n^2))$</span> This would contradict known time hierarchy bounds for 1-tape TMs.</li>
</ul>

CC BY-SA 4.0
2020-10-03T15:58:18.237Z
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.
Gamow
CC BY-SA 4.0
2020-10-03T16:36:00.617Z
@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).
Emil Jeřábek
CC BY-SA 4.0
2020-10-03T23:05:22.153Z
Yeah, it's obviously tight for linear time TMs. I was wondering if it was was possible to do the reverse (simulate an O(n^2) time 1-tape TM, on an O(n) time 2-tape TM). I would assume not, but I don't know a result that says so. Feel free to write your comment as an answer, since you've answered the question as written?
Zachary Vance
CC BY-SA 4.0
2020-10-04T09:50:38.103Z
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?
Marzio De Biasi
CC BY-SA 4.0
2020-10-04T09:57:50.497Z
@EmilJeřábek: I think the OP asks if there are problems that requires $O(n^2)$ time on a 1 tape TM but the $O(n^2)$ does not depend on the limitation of the 1 tape TMs when performing "comparisons" or "matches" or "copy operations" between different portions of the tape, that can be done efficiently on a 2 tape-TM but force an $O(n^2)$ on a 1 tape TM.
Marzio De Biasi
CC BY-SA 4.0
2020-10-04T10:18:02.997Z
... 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 ?
Marzio De Biasi
CC BY-SA 4.0
2020-10-05T03:29:42.100Z
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: https://en.wikipedia.org/wiki/Linear_speedup_theorem
Michael Wehar
CC BY-SA 4.0
2020-10-06T23:05:00.323Z
Marzio: That's closely related, yes. An answer of "yes" would fully answer my question, certainly. An answer of "no" would be a partial answer.
Zachary Vance
CC BY-SA 4.0
2020-10-07T18:20:58.190Z
Whoops! That claim is indeed wrong, will correct. I tried to re-write it to be more concise and screwed up.
Zachary Vance
<turing-machines><universal-turing-machines>
How fast is an equivalent 2-tape TM compared to a $O(n^2)$ 1-tape TM?
Zachary Vance
# How fast is an equivalent 2-tape TM compared to a $O(n^2)$ 1-tape TM?

(Asked by: username_0 on 2020-10-03)

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.

**Tags:** turing-machines, universal-turing-machines

> **Comments:**
> **username_1**: 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.  
> **username_2**: @username_1 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).  
> **username_0**: Yeah, it's obviously tight for linear time TMs. I was wondering if it was was possible to do the reverse (simulate an O(n^2) time 1-tape TM, on an O(n) time 2-tape TM). I would assume not, but I don't know a result that says so. Feel free to write your comment as an answer, since you've answered the question as written?  
> **username_3**: 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?  
> **username_3**: @EmilJeřábek: I think the OP asks if there are problems that requires $O(n^2)$ time on a 1 tape TM but the $O(n^2)$ does not depend on the limitation of the 1 tape TMs when performing "comparisons" or "matches" or "copy operations" between different portions of the tape, that can be done efficiently on a 2 tape-TM but force an $O(n^2)$ on a 1 tape TM.  
> **username_3**: ... 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 ?  
> **username_4**: 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: https://en.wikipedia.org/wiki/Linear_speedup_theorem  
> **username_0**: Marzio: That's closely related, yes. An answer of "yes" would fully answer my question, certainly. An answer of "no" would be a partial answer.  
> **username_0**: Whoops! That claim is indeed wrong, will correct. I tried to re-write it to be more concise and screwed up.  

---

## 1 answers

### Answer by username_3 on 2020-10-08. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: 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)  

---

