Multi-tape Turing Machine

The multi-tape Turing machine is an extension of the standard Turing machine which adds finite ‘work tapes’, essentially increasing the size of the tape the Turing machine can use as ‘scratch paper’ to compute on. This does not affect the input tape. Multi-tape TM’s are, in fact, equivalent in power to their standard counterpart.

Definition §

Multi-tape Turing Machine

A multi-tape Turing Machine with $k$ tapes ($k-1$ ‘work tapes’), $M$ is defined as the 8-tuple:

$$M_k=(\Sigma ,\Gamma ,b,Q,\delta ,q_0,q_a,q_r)$$

• See Turing Machine definition for the meaning of the symbols
• Only the first tape has the input string. The remaining $k-1$ work tapes are filled with blank ($b$) symbols.

The key difference in a multi-tape TM is that the transition function, $\delta$, takes in a state ($q_{cur}$) and $k$ different input characters (one per tape), then transitions to another state ($q_{next}$) moving each tape left or right independently, optionally overwriting characters.

$$\delta :Q\setminus \{q_a,q_r\}\times {\Gamma }^k\to Q\times {\Gamma }^k\times \{\text{L, R}{\}}^k$$

For example, take a 3-tape Turing Machine, having 2 work tapes would have a $\delta$ given by:

$$\delta (q_{cur},c_1,c_2,c_3)=(q_{next},d_1,d_2,d_3,L/R,L/R,L/R)$$

Theorems §

T1: Turing recognisability is equivalent for multi-tape Turing machines

Let $A$ be a language. Then:

$$\text{A is Turing-recognisable}⟺\exists \text{Multi-tape TM, Mk, s.t. }\text{M recognises A}$$

Proof

Since this proof is an equivalence we need to prove both sides.

Let’s start with the right side $⟹$:

• $A$ being T-recognisable implies there exists a Turing machine, $M$ that recognises $A$
• $M$ is technically a multi-tape Turing Machine ($k=1$)
• Hence we have a multi-tape TM that recognises $A$.

Now the left side $⟸$ is a bit harder:

• We need to convert our multi-tape TM $M_k$ to a single-tape TM.
• We can do this by a TM Simulation
• Let $S$ be a single-tape TM that simulates $M_k$
• It combines all of $M_k$’s tapes into one tape, by using a symbol to allocate ‘blocks’ of tapes (such as a vertical divider | )
  • Note: The only reason this works is that we can capture the infinite blank symbols of each work tape onto a single tape because the TM will always halt on accepting inputs. So there are only a finite number of symbols that are actually important for each work tape.
• It simulates the head of each tape by replacing a symbol with a dotted version of it.
• At every step it:
  • Scans the entire tape to find all the head’s location (by dotted symbols)
  • Scans again to overwrite the tape according to the $\delta$ of $M_k$
  • If the allocated blocks are too small, it ‘shifts’ them by copy-pasting each symbol to the right as needed. Note the similarities to memory reallocation for arrays
• $S$ accepts/rejects whenever it goes to the same $q_a$ or $q_r$ as $M_k$