Turing Machine Variant – Multiple Tapes

A multi-tape Turing Machine (TM) is a TM with access to a fixed finite number of tapes. A -tape TM has access to tapes.

Initial Configuration

The input string is placed on the first tape. All other tapes are blank. All tape heads point to the start of their respective tapes.

Transition Function

The transition function is mapped as follows



Based on the current state and the current-tape cell read by each of the tapes, the transition specifies the next state, what to write on each of the tapes and the direction to move the tape-head on each of the tapes.

The direction implies staying on the current cell.



Equivalence to Single Tape

Any multi-tape Turing Machine computation can be carried out by an equivalent single-tape Turing Machine.

The single-tape TM has the tape contents of the individual tapes separated by a separator symbol (). The tape-head of each individual tape is marked by the dotted equivalent of the symbol it points to.

To carry out one transition of a -tape TM on the single-tape

1. Scan right to the first dotted symbol. Remember this symbol in the current state.
2. Repeat step 1 to scan and remember symbols in the current state.
3. The current state and the symbols will have a finite number of possibilities.
4. Use the transition function to find the next configuration.
5. Bring tape-head back to the start.
6. Scan right to the first dotted symbol. Apply the configuration for the first tape. This involves writing a symbol, and moving the tape-head (reapplying the dot). If the dotted symbol is one cell to the left of a separator, a new blank cell must be added to accommodate for a transition.
7. Repeat step 6 to scan and apply the configuration for each of the tapes.

Remembering symbols

A Turing Machine can remember by using specific states. Say the tape alphabet is and there are tapes. There can be a state to remember that the current state is , the tape-heads point to on the first-tape, on the second-tape and on the third-tape. From this state it can make an appropriate transition by following the transition function.

Finite number of possibilities

To remember multiple symbols, a single-tape TM equivalent to a -tape TM (with states) will need new states for each of the states for a total of states.