# 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.

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.
• 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