What is a Multi-track Turing machine?

A multi-track Turing machine is a variant of the simple Turing machine. It consists of multiple tapes with a single head pointer. They are beneficial in solving complex problems and limit the amount of work, unlike a simple Turing machine.

As there is a single head, the direction of all the tapes changes together. The input is placed in the first tape and is transferred to the other tapes as per convenience.

Note: To learn more about the multi-tape Turing machine, click here.

Formal theorem

The Turing machine is a 6 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-track tapes look like the following:

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

Note: The head shows the movement of all the tapes.

Example

Let's develop a multi-track Turing machine for a system that doubles the amount of the given input such that:

The input set consists of 1's only, and we are to double the number of 1's by this Turing machine.

The initial state of this Turing machine is:

The strategy used in this case is that for every 1 we find in the input tape, we place a 1 in the second tape at the same place and then move towards the end of the tape and place the second 1. In simple words, for every 1 in the input, we have to output two 1's.

The Turing machine will be of the sort:

Transitions explanation

The transitions of the above Turing machine are explained below:

• $q_0 \to q_1$: The first delta in both tapes is skipped, and the heads move to the right.
• $q_1 \to q_2$: When a 1 is found on the input tape, a 1 is also placed on the second/output tape. The head moves rightward.
• $q_2\to q_2$: The pointer keeps skipping elements and moves to the end of the input tape.
• $q_2\to q_3$: When it reaches a delta, 1 is placed on the second/output tape. The head moves leftwards.
• $q_3\to q_3$: Here, the pointer skips elements until the second 1 in the input tape is found that has a corresponding 1 in its output tape.
• $q_3 \to q_1$: It loops back to repeat the above process for further 1's.
• $q_1\to H_a$: The Turing machine halts when the number of 1's is greater in the output machine.