1
$\begingroup$

Suppose a Turing machine $M$ has a read-only input-tape and $k$ read-write work-tapes whose non-blank cells are each bounded by $f(|x|)$ where $|x|$ is the length of the input.

Is there some constant $C(k)$ and Turing machine $M^{'}$ with a read-only input tape such that $M^{'}$ accepts exactly when $M$ accepts, $M^{'}$ has only one read-write work tape, and the blank cells of that tape are bounded by $C f(|x|)$?

If there doesn't exist such a constant $C(k)$ that is independent of $M$, does there exist a constant $C(k, M)$? In other words does reducing the number of tapes preserve space complexity?

$\endgroup$
2
$\begingroup$

You can take $C(k)=1$.

Simulate the $(k+2)$-tape machine (input, output, $k$ work tapes) by storing the $i$th character of all the simulated tapes in the $i$th character of the single tape. This is a standard construction, which also requires you to store the head positions using the characters on the tape. Now, you can do the whole computation without using any extra space.

In a little more detail, suppose you're simulating a Turing machine with tape alphabet $\Sigma$. Let $\Sigma'$ be the alphabet containing a character $a'$ for each character $a\in\Sigma$. We'll simulate using alphabet $(\Sigma\cup\Sigma')^{k+2}$, so each character on the simulating tape is a tuple $(c_1, \dots, c_{k+2})$. If $c_j\in\Sigma$, that means that the corresponding cell on the $j$th tape of the simulated machine contains that character; if $c_j=a'\in\Sigma'$, that means the cell contains character $a$ and that tape's head is in this position.


Note that it only makes to talk about space $\Omega(n)$ on single-tape Turing machines, since you now have to count the space used by the input.

$\endgroup$
  • $\begingroup$ I'm having trouble seeing how this would work. What if the heads on the different work tapes aren't all moving in the same direction? How would this standard construction simulate reading from the different positions on the various work tapes? $\endgroup$ – Alex Williams Aug 28 '18 at 18:50
  • $\begingroup$ @AlexWilliams use the characters on the tape to code both the tape contents and the head positions. I’ll add more detail later, when I have time. (Ping me if I haven’t within the next few hours.) $\endgroup$ – David Richerby Aug 29 '18 at 7:52
  • $\begingroup$ Thanks. I found a construction where it was clear that the overall space bound could be preserved. $\endgroup$ – Alex Williams Aug 29 '18 at 21:52
  • $\begingroup$ @AlexWilliams Thanks for the reminder. :-) I've added a little more detail anway, in case anyone else wants to know. $\endgroup$ – David Richerby Aug 29 '18 at 22:05

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.