Problem Detail: 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.
Asked By : David Faux
Answered By : Hendrik Jan
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 $Bin Sigma$, the single tape simulator has alphabet $Sigma^kcup{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)
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7056
