What is a multi-tape Turing machine?

A multiple tape Turing machine is a variant of the simple Turing machine. It consists of multiple tapes, each having its head pointer. It can be taken as a 2D array.

The heads of the multiple tapes can move in different directions independently. Initially, the input is placed in the first tape and is transferred to the other tapes as per convenience.

To learn more about the simple Turing machine, click here.

Formal theorem

The multi-tape Turing machine is a six tuple machine $(Q, Σ, q_0, \Gamma, δ, F)$

• $Q$ - set of states
• $Σ$ - set of input alphabets
• $q_0$ - initial state
• $\Gamma$ - set of tape alphabets
• $δ$ - transition function that is $Q \space * \Gamma^i \to Q \space * \Gamma^i \space *$
  (Left, right, stationary)^i
• $F$ - set of final states

Formation of the tapes

Initial multi-tapes are as follows:

All the tapes involved are filled with the delta(Δ) symbols and grow infinitely to the right side. The first tape contains the input initially.

Example

Let's develop a two-tape Turing machine for a palindrome. Suppose our palindrome is $aba$. Initially, our tapes will be as follows:

The strategy we wish to use is that we copy the input into the second tape and compare the two tapes; the first from the beginning and the second backward.

Now for the Turing machine, each transition will be of the type:

$(x,y) / (x',y'), (D_1,D_2)$where $x$and $y$are the elements where the heads are pointing, $x'$and $y'$are the changes made in the pointed element, and $D_1$and $D_2$are the directions (L, R, S) to be made by both heads, respectively.

The Turing machine for $aba$ palindrome will be:

Explanation

• $q_0 \to q_1$: The first delta in both tapes is skipped, and the heads move to the right.
• $q_1 \to q_1$ : The first tape's input is skipped but copied into the second.
• $q_1 \to q_2$: When the input is exhausted, the head pointer of the first tape is moved left so that it can reach the starting of the input, whereas the pointer of the second tape is kept stationary as we want to compare the second tape backwardly.
• $q_2\to q_2$: The pointer keeps on skipping elements and moves to the leftmost element.
• $q_2\to q_3$: As both the pointers are at the opposite sides, they are moved towards right and left, respectively.
• $q_3\to q_3$: Here, both the tapes are compared.
• $q_3 \to H_a$: The Turing machine reaches the final state if the string is a palindrome.

Multi-tape Turing machines are beneficial in solving complex problems and limit the amount of work, unlike a simple Turing machine.