4
$\begingroup$

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?

$\endgroup$

migrated from cstheory.stackexchange.com Oct 30 '12 at 13:14

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

10
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Basically the trick in the construction is to buffer updates to the tape in a clever way. This has the effect that you have to update far away portions of the tape only when you have enough changes to carry out and it pays off. $\endgroup$ – A.Schulz Oct 30 '12 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.