Problem Detail: Introduction: I recently learned that a multi-tape Turing Machine $text{TM}_k$ is no more “powerful” than a single tape Turing machine $text{TM}$. The proof that $text{TM}_k equiv text{TM}$ is based on the idea that a $text{TM}$ can simulate a $text{TM}_k$ by using a unique character to separate the respective areas of each of the $k$ tapes. Given this idea, how would we prove that a process taking $t(n)$ time on a $text{TM}_k$ can be simulated by a 2-tape Turing machine $text{TM}_2$ with $ O(t(n))log(t(n))$ time?
Asked By : URL87
Answered By : Vor
Look at the original paper by Hennie and Stearns: F.C. Hennie and R.E. Stearns, “Two-Tape Simulation of Multitape Turing Machines”, Journal of the ACM (JACM), Volume 13 Issue 4, Oct. 1966, pp. 533-546 The construction is a little bit elaborate, but not extremely difficult to understand. The basic idea is to store and keep the current symbol of each tape in the same fixed column (home column) and simulate a shift of the $k$ tapes using a series of partially filled “buffers” of increasing length placed on the two tapes on the left and right side of the home column in order to avoid a full shift (that would require $O(t(n)^2)$ steps). If you need further help, modify the question and ask about the points in the paper that are not clear.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6385
