Define multitape Turing machine

A multitape Turing machine is a Turing machine with k ≥ 2 tapes, each with its own read/write head, and a single finite control.

Formal definition

M = (Q, Σ, Γ, δ, q0, ⊔, F), where

• Q is a finite set of states, q0 the start state, F ⊆ Q the final states,
• Σ is the input alphabet, Γ ⊇ Σ the tape alphabet, ⊔ ∈ Γ − Σ the blank,
• δ is the transition function

δ : Q × Γᵏ → Q × Γᵏ × {L, R, S}ᵏ

In one move, depending on the current state and the k symbols under the k heads, the machine

1. changes state,
2. writes a new symbol on each tape, and
3. moves each head independently left, right or stays.

The input is placed on tape 1; the other tapes start blank, with all heads at the left end.

 finite control (state q)
     |      |      |
  ┌──v──────v──────v──┐
 T1│ # │ 1 │ 0 │ # │ ⊔ ...
 T2│ # │ ⊔ │ ⊔ ...
 T3│ ⊔ │ ⊔ │ ...

Equivalence with the single-tape TM

A multitape TM is no more powerful than a single-tape TM: every language accepted by a k-tape machine is accepted by a one-tape machine. The single tape stores all k tapes side by side, separated by a marker, with a mark for each head position, and each move is simulated by sweeping the tape. If the k-tape machine takes t(n) steps, the one-tape machine takes O(t(n)²) steps.

Multitape machines are used because they are easier to design (copying, adding, comparing) and to analyse for time complexity.