11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What do you mean by "an equivalent machine"? What is the input and what is the output? (Perhaps you meant one Turing machine with $k$ tapes?) $\endgroup$ – Yuval Filmus Sep 26 '13 at 4:26
  • $\begingroup$ Yes. One turning machine with k tapes. $\endgroup$ – user678392 Sep 26 '13 at 16:37
16
$\begingroup$

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).

$\endgroup$
  • 2
    $\begingroup$ Alternatively, use separate "tracks" to write the separate tapes next to one another in the same space. That however involves te introduction of a new alphabet. $\endgroup$ – Hendrik Jan Sep 26 '13 at 9:09
  • 2
    $\begingroup$ @user678392 Going through the construction in full detail and writing it all up here would take at least a couple of hours. If you're not even going to explain even which part you don't understand, why should anyone put in that much work on your behalf? And what if somebody does? Are you just going to say, "I don't understand it. Somebody else do it."? $\endgroup$ – David Richerby Sep 26 '13 at 21:01
  • 1
    $\begingroup$ @user678392 Thanks. And, just to clarify, is it the English you're having difficulty with (i.e., is rephrasing likely to help) or do you need more detail in the explanation? $\endgroup$ – David Richerby Sep 26 '13 at 22:09
  • 1
    $\begingroup$ @user678392, I've added an example of the high-level view of the first steps of the conversion and the practical output on the tape(s). I've avoided discussing how to construct the new set of states, as that is very complex and you won't get a better explanation than what's in Sipser or similar - it is inherently fiddly and mathematical. $\endgroup$ – Luke Mathieson Sep 27 '13 at 3:07
  • 1
    $\begingroup$ @RomaKarageorgievich It seems a number of the clearer proofs have disappeared over the last 5 years (don't trust the internet :D). The clearest I've found is here (warning, .doc file!). The proof in Martin's "Introduction to Languages and the Theory of Computation" is quite good, if you have access to that book (p. 244 in the 4th Ed.). The Proof in Sipser's "Introduction to the Theory of Computation" is sufficient (p. 177 in the 3rd Ed.). $\endgroup$ – Luke Mathieson Apr 16 '18 at 2:26

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.