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

- Scan right to the first dotted symbol.
*Remember this symbol*in the current state. - Repeat step 1 to scan and remember symbols in the current state.
- The current state and the symbols will have a
*finite number of possibilities*. - Use the transition function to find the next configuration.
- Bring tape-head back to the start.
- 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. - 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.

## Adding a new blank cell

Adding a new blank cell involves shifting all the contents of the tape one cell to the right. This has to be done in a right-most first fashion.

## Conclusion

A language is recognized by a single-tape TM if and only if is recognized by a -tape TM.

A language is decided by a single-tape TM if and only if is decided by a -tape TM.