6
$\begingroup$

Apparently, for every k-tape Turing machine that runs in time $O(t(n))$, there exists a 1-tape Turing machine that runs in $O(t^2(n))$.

I can see how any multi-tape machine $M$ can be simulated by a 1-tape machine $S$. Just have the tape of $S$ contain all of $M$'s tapes separated by some symbol such as #.

However, why is the running time of $S$ $O(t^2(n))$ if the running time of $M$ is $O(t(n))$? I think it would be $O(t^k(n))$ since there exist $k$ tapes, and we have to traverse through all of them.

|cite|improve this question
$\endgroup$
7
$\begingroup$

In your suggestion you write the tapes next to one another. That has another disadvantage, if one of the tapes runs out of space one has to move the information to extend that space.

The solution is to write different tapes on "tracks", above each another, technically this is done by extending the alphabet to a cartesian product of alphabets. If the original tapes all have alphabet $\Sigma$ (for $i=1,\dots,k)$ and blank $B\in \Sigma$, the single tape simulator has alphabet $\Sigma^k\cup\{B\}$. Additionally one needs to mark the positions of the heads, leading to extra symbols on the tracks.

(edited to include answer to question in comment)

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Hmm, thanks, you bring up a good point. With my method, I would have to shift all of my cells when a section runs out of space... what Cartesian product are you referring to? $\endgroup$ – David Faux Dec 1 '12 at 0:33
  • $\begingroup$ @David: I have added extra details on the nature of the alphabet in my answer. $\endgroup$ – Hendrik Jan Dec 1 '12 at 0:42
  • 1
    $\begingroup$ Thanks! That makes sense. So have each cell represent the cells of each of the $k$ tapes as a Cartesian product. Then, have some other markings to denote where the head is for each tape... $\endgroup$ – David Faux Dec 1 '12 at 2:27

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.