Turing Machine Variation

3k Views Asked by At

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?

1

There are 1 best solutions below

3
On

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.