# Multitape Turing machines against single tape Turing machines

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?

-

## migrated from cstheory.stackexchange.comOct 30 '12 at 13:14

This question came from our site for theoretical computer scientists and researchers in related fields.

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.