Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 7 down vote accepted

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)

share|cite|improve this answer
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? – David Faux Dec 1 '12 at 0:33
@David: I have added extra details on the nature of the alphabet in my answer. – Hendrik Jan Dec 1 '12 at 0:42
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... – David Faux Dec 1 '12 at 2:27

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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