patternModerate
Multitape Turing machines against single tape Turing machines
Viewed 0 times
againstsingletapemachinesturingmultitape
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#6385, answer score: 10
Revisions (0)
No revisions yet.