# Why is it that every k-tape Turing machine has a 1-tape TM that runs in $O(t^2(n))$?

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.

-

## 1 Answer

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)

-
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