Hi i'm trying to figure out this question:

Give a formal definition of multihead-multitape Turing machine. Then show how such a machine can be simulated by a standard Turing machine

Can someone explain or provide proof that a standard TM can work with this other turing machine variation?


A multitape Turing Machine is mostly the same as a single tape machine, except we have an extended transition function $Q\times\Gamma^{k}\rightarrow Q\times\Gamma^{k}\times\{L,R\}^{k}$ where $k$ is the number of tapes. So in each state, the transition function reads the contents of each tape, moves to a new state, (maybe) writes something on each tape and moves each head - just a regular TM, except now we have more things to read, write and move.

As your question suggests, such a machine can be simulated by a single tape TM. Even better, it can be done with only quadratic slowdown (so for polynomially closed classes, it's sufficient to talk about single tape machines).

The proof for this is somewhat involved, and easily available with a simple web search, so I'll just sketch the key mapping of the $k$ tapes to a single tape.

The basic idea is pretty straighforward; we simple add a few new symbols and keep track of each tape and head one after the other. At each step in the computation we can only have seen a finite amount of any of the tapes, so we need only to store this much information about each tape. To for each $\gamma \in \Gamma$ we add a new symbol $\underline{\gamma}$ to $\Gamma$ which will indicate where the head (for each tape) is at any point in the computation. We also introduce a separator character $\#$ to $\Gamma$ which will indicate the start and end of the "virtual" tapes. Given input $\omega = \omega_{1}\ldots\omega_{n}$ (we can assume that even on the multitape machine that the input is on the first tape - proving why is a good exercise) on the multitape machine, our single tape machine will have input $$ \underbrace{\#\underline{\omega_{1}}\ldots\omega_{n}\#\underline{\sqcup}\#\underline{\sqcup}\#\ldots\#\underline{\sqcup}\#}_{k \text{ sections, one per tape}}\sqcup\sqcup\sqcup\sqcup\sqcup\sqcup\ldots $$

We then use the state of the single tape machine to encode what state the multitape machine is in and what the heads are looking at and the transition function of the single tape machine is a multistage simulation of the multitape transition function, where we perform the $k$ different tape actions appropriately, moving up the single tape to each section in turn. The only wrinkles left are shifting everything along when we run out of space in a section (but such a sub-machine is a simple exercise) - we never reduce the size of each section.

  • $\begingroup$ Hi could you explain how multihead would be incorporated into this as well? $\endgroup$ – Thresh Mar 28 '13 at 17:24
  • $\begingroup$ @Thresh, if you want to have more than one head per tape, so $k$ tapes each with (up to) $h$ heads, then we can take the "head symbol" idea (the $\underline{\gamma}$) to the next step, and for each $\gamma \in \Gamma$ introduce $h$ new symbols $\underline{\gamma}_{1}, \dots, \underline{\gamma}_{h}$ where each $\underline{\gamma}_{i}$ indicates that the simulated head $i$ is at that position on that simulated tape. Then the rest is largely the same; the states of the single tape single head machine encode the state and current characters under the heads of the multitape/head machine (cont.) $\endgroup$ – Luke Mathieson Mar 29 '13 at 3:12
  • $\begingroup$ you just get a lot of states ($Q\times\Gamma^{h}$-ish). $\endgroup$ – Luke Mathieson Mar 29 '13 at 3:13

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.