How to map the tapes of a "k-tape" Turing Machine into the single tape of a "1-tape" Turing Machine

Question Detail: 

I'm reading Sipser and I'm finding it hard to understand what the process is such that if you give me k Turing machines with k tapes, I can spit out an equivalent Turing machine with only one tape. An example would be nice. Actually, a worked out example that shows how to go from TM that has $k$ tapes to one that has 1 tape is what I'm really looking for. I have been unable to find one so far. I'm also not looking for any proofs.

Asked By : user678392

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14619

Answered By : Luke Mathieson

An answer shamelessly copied from myself:

A multi-tape 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 as 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 straightforward; we simply 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 visited a finite amount of any of the tapes, so we need only to store this much information about each tape. Thus 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 multi-tape machine all of the input is on the first tape - proving why is a good exercise) on the multi-tape 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 multi-tape machine is in and what the heads are looking at. The transition function of the single-tape machine is a multistage simulation of the multi-tape 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.

A (hopefully) simple example:

Say we have a 3-tape TM, where the input alphabet is just $\Sigma=\{0,1\}$, the tape alphabet is $\Gamma=\{0,1,\sqcup\}$ and the input is $\omega=10101$. The initial tape state of the machine looks like: $$ \begin{array}{lc} \text{Tape 1:} & \underset{\wedge}{1}0101\sqcup\sqcup\sqcup\ldots\\ \text{Tape 2:} & \underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\sqcup\ldots\\ \text{Tape 3:} & \underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\sqcup\ldots\\ \end{array} $$ The "$\wedge$" is to denote where the read/write head is on each tape.

To construct the combined single-tape machine, we need to add new symbols to the tape alphabet:

1. We need a symbol that will denote the start and end of the simulated tapes
2. For each symbol in $\Gamma$ we also need a version that indicates that the simulated tape head is at that character on the simulated tape.

So for the single-tape machine, our new tape alphabet is $\Gamma' =\{0,1,\sqcup,\underline{0},\underline{1},\underline{\sqcup},\#\}$. The initial state of the tape is: $$ \#\underset{\wedge}{\underline{1}}0101\#\underline{\sqcup}\#\underline{\sqcup}\#\sqcup\sqcup\sqcup\ldots $$ Note the difference between the head of the machine (the $\wedge$) and the simulated heads of the 3 simulated tapes (the underlined characters). Of course the tape extends infinitely to the right as usual. I have also cheated mildly by moving the tape head to the first character on the first string; strictly it should start out on the leftmost cell, but this is a trivial technicality.

So we have three marked out sections (between the $\#$ marks), which will correspond to the 3 tapes of the original machine.

Now let's make up an action for the machine. Let's say that the original machine reads from the first tape, if it sees a $1$, it writes a $1$ on the second tape, if it sees a $0$ it writes a $1$ on the third tape. At each read or write, the head moves to the right.

So after the first "step" (perhaps requiring several states and transitions in the actual machine), the tapes should have a $1$ on the second tape, and the first and second heads will have moved right one step:

$$ \begin{array}{lc} \text{Tape 1:} & 1\underset{\wedge}{0}101\sqcup\sqcup\sqcup\ldots\\ \text{Tape 2:} & 1\underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\ldots\\ \text{Tape 3:} & \underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\sqcup\ldots\\ \end{array} $$

On the second go around, the first tape reads a $0$, so we write to the third tape instead:

$$ \begin{array}{lc} \text{Tape 1:} & 10\underset{\wedge}{1}01\sqcup\sqcup\sqcup\ldots\\ \text{Tape 2:} & 1\underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\ldots\\ \text{Tape 3:} & 1\underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\ldots\\ \end{array} $$

The single-tape machine simulates this by moving the underline (by using the alternate version of the characters in $\Gamma'$, and writing to the appropriate simulated tape. So after the first step, the combined tape looks like:

$$ \#1\underset{\wedge}{\underline{0}}101\#1\underline{\sqcup}\#\underline{\sqcup}\#\sqcup\sqcup\sqcup\ldots $$

After the second step:

$$ \#10\underset{\wedge}{\underline{1}}01\#1\underline{\sqcup}\#1\underline{\sqcup}\#\sqcup\sqcup\sqcup\ldots $$

Of course this is a high level view of the process - I haven't attempted to explain how to construct the states, or how each simulated tape gets longer (for this, you need a little routine that checks if you've run into the end of the simulated tape, then moves everything to the right one step along and squeezes in a new blank - i.e. it only adds simulated tape cells when they're needed).