Multitape Turing Machines
Imagine designing a Turing machine to check whether a string is a palindrome. With a single tape you must shuttle back and forth. You repeatedly overwrite symbols and re-scan the whole input. This lets you compare characters from both ends. The bookkeeping is possible but painful. The same headache recurs for sorting, copying substrings, or simulating a stack. A multitape Turing machine removes this friction. It gives the machine several independent tapes, each with its own read/write head. An algorithm can keep a working copy on one tape. A counter can sit on another, and scratch space on a third. This mirrors exactly how real programmers use multiple arrays or data structures. This extra convenience is not just a comfort. It clarifies what "efficient" should mean for the abstract model of computation. Suppose multiple tapes let us solve some problem in far fewer steps than one tape allows. Then the number of tapes would matter to the definition of complexity classes like P. The whole edifice of computability and complexity theory would need a tape-count parameter baked into it. This article proves a remarkable fact. This never happens at the level of what is computable. It only mildly happens at the level of how fast. Every multitape Turing machine can be simulated by a single-tape Turing machine. This simulation costs at most a quadratic slowdown. The big picture is a robustness theorem. The set of languages recognized by Turing machines does not change. This holds no matter how many tapes you allow, or how many heads you allow. It also holds, as later articles show, whether you allow nondeterminism. This robustness is one of the pillars supporting the Church-Turing Thesis. The precise mathematical notion of "algorithm" seems insensitive to reasonable changes in the machine model. This is strong evidence that Turing machines have correctly captured the informal notion of "effective computation." This article defines the k-tape Turing machine formally. It walks through the standard simulation that encodes k tapes onto one. It proves the simulation correct and analyzes its overhead. It also traces the encoding through a worked example step by step. It closes by connecting the result to nondeterministic machines and to the Church–Turing Thesis. Both of these reuse this same "simulate on one tape" technique.
- A k-tape TM has k tapes and k independent heads, all controlled by one finite state, moving on every step.
- Multitape TMs recognize exactly the same class of languages as single-tape TMs — no new computational power.
- The standard simulation interleaves all k tapes onto one tape using a larger alphabet with head markers.
- Simulating one multitape step costs O(n) single-tape steps, where n bounds the space used so far.
- A t-step multitape computation is simulated in O(t²) single-tape steps — polynomially related, not equal.
- This equivalence underlies why the Church-Turing Thesis treats "reasonable" machine variants as identical.
Extra tapes buy convenience and at most a quadratic speed-up, but never buy new computational power.
The idea
A k-tape Turing machine is a Turing machine equipped with `k` tapes, each infinite in one or both directions, and `k` tape heads that move independently. Formally it is a 7-tuple ``` M = (Q, Σ, Γ, δ, q0, qaccept, qreject) ``` identical in spirit to the single-tape definition, except the transition function now reads and writes on all `k` tapes simultaneously: ``` δ : Q × Γᵏ → Q × Γᵏ × {L, R, S}ᵏ ``` On each step, the machine is in some state `q`, and each of the `k` heads is reading some symbol. The function `δ` looks at the current state together with the `k` symbols currently under the heads, and it outputs a new state, a symbol to write on each tape, and a direction (Left, Right, or Stay) for each head to move. All `k` heads move in the same step — this is the key source of parallelism that makes multitape machines convenient: the machine can, for instance, copy a symbol from tape 1 to tape 2 and simultaneously advance a counter on tape 3, all in a single transition. A configuration of a k-tape TM records the current state, the full contents of all k tapes, and the position of each of the k heads — a direct generalization of the single-tape configuration from prior material on configurations and computations. The machine accepts an input `w` (placed on tape 1, with the other `k-1` tapes blank) if some sequence of configurations, each following from the last by `δ`, leads from the start configuration to a configuration in state `qaccept`. Rejection and looping are defined exactly as for single-tape machines. A language is multitape-decidable if some multitape TM decides it, and multitape-recognizable (Turing-recognizable) if some multitape TM recognizes it. The central theorem of this article is an equivalence theorem: > Theorem. Every multitape Turing machine has an equivalent single-tape Turing machine — one that > recognizes exactly the same language. Equivalence here means language equivalence, not step-for-step equivalence: the single-tape machine will, in general, take far more steps to process the same input, but it accepts, rejects, and loops on exactly the same set of inputs as the multitape machine. This distinguishes the notion of "computable" from the notion of "efficiently computable" — the former is unaffected by adding tapes, while the latter changes only by a polynomial factor, never by more.
How it works
The proof of the equivalence theorem is constructive: given any k-tape machine `M`, it builds an explicit single-tape machine `S` that simulates `M`. The construction has one central idea — interleave the k tapes onto one tape using an expanded alphabet, and mark the position of each virtual head with a special symbol.
Encoding k tapes as one
Label the k tapes of `M` as tape 1, …, tape k. Choose a new tape alphabet for `S` that packs one symbol from each of the k tapes into a single composite "column," together with a marker (say `#`) separating the columns from each other, and a distinguished dotted version of each alphabet symbol used to indicate "the head is currently here." Concretely, `S`'s tape looks like ```
# a₁ ḃ₁ c₁ # a₂ b₂ ċ₂ # a₃ b₃ c₃ ⨯ ... ``` where the block between the `i`-th and `(i+1)`-th `#` holds the contents of virtual tape `i` at that column, and a dot over a symbol marks where tape `i`'s head currently sits. Reading off the dotted symbols from left to right across the k blocks tells `S` everything `M`'s transition function needs to know: the k symbols currently scanned by `M`'s k heads.
Simulating one step of M
To simulate a single step of `M`, `S` performs one left-to-right sweep over the used portion of the tape, recording the k dotted symbols it encounters (one per tape-block), and then a second sweep to actually update the tape: it writes the new symbols dictated by `δ`, moves each dot marker one cell within its own block (possibly shifting all subsequent cells right if a virtual tape needs to grow), and updates `S`'s single finite-control state to the new state of `M`. Two sweeps (or a constant number of passes) suffice for a constant number of tapes, since each pass only touches cells that already store useful information. ``` SIMULATE-MULTITAPE(M = (Q, Σ, Γ, δ, q0, qacc, qrej), input w): // Phase 1: build the initial single-tape encoding write "# ẇ1 w2 w3 ... wn # # # ..." onto S's tape // tape 1's block holds w with its head-dot on the first symbol, // tapes 2..k are blank blocks, each with a dot on the first (blank) cell, // one '#' block-separator before each tape's content S.state <- q0 loop: // Phase 2: scan left to right once, reading off the k symbols under the dots symbols <- array of size k scan across the tape from the left '#' to the right '#', whenever a dotted symbol is found in block i, record it as symbols[i] if S.state == qacc: ACCEPT if S.state == qrej: REJECT // Phase 3: consult M's transition function (newState, writeSymbols, moves) <- δ(S.state, symbols) // Phase 4: scan again, applying the update to each block for i in 1..k: in block i, overwrite the dotted cell with writeSymbols[i] move the dot in block i one cell Left/Right/Stay as moves[i] dictates if the dot moves past the current right end of block i's used region: shift all blocks to the right of block i one cell further right to make room, inserting a fresh blank cell with a new dot if the dot moves off the LEFT end of the tape (tape 1 only, if unbounded left): shift the entire tape one cell to the right to make room S.state <- newState // (loop continues until qacc or qrej is reached, or forever if M loops) ``` Two implementation details deserve emphasis, since they are exactly where a naive design breaks: 1. Growing a virtual tape. Because all k virtual tapes are packed end-to-end on one physical tape, if virtual tape `i` needs a new cell (its head moved right onto previously unallocated space), `S` must shift every block to the right of block `i` one cell over to make room — otherwise blocks would collide. This shifting is what makes each simulated step cost time proportional to the total tape usage so far, not a constant. 2. Two-ended tapes and the left end. If a virtual tape is infinite in only one direction and a head tries to move left past the start, `S` must recognize this as an error condition (or, if the model allows two-way infinite tapes, `S` reserves space by shifting everything right on demand). Handling this correctly avoids the classic off-by-one bug of overwriting the block separator `#`. The simulation halts (accepts/rejects) precisely when `M`'s simulated state becomes `qaccept` or `qreject`, so `S` accepts exactly the strings `M` accepts, rejects exactly the strings `M` rejects, and loops exactly when `M` loops. This gives language equivalence.
Complexity & correctness
Correctness. Correctness follows from an invariant maintained across every simulated step: > Invariant. After `S` has simulated the first `t` steps of `M`, the single tape of `S` encodes exactly > the contents of all k tapes of `M` after t steps, the dot in each block marks the exact position of the > corresponding head of `M`, and `S`'s finite control state equals `M`'s state after t steps. The invariant holds at `t = 0` by construction (Phase 1 copies the input onto virtual tape 1 and blanks the rest, with each dot at the start). Assuming it holds after `t` steps, Phase 2 correctly recovers the k symbols `M` would read at step `t+1` (since the dots mark the true head positions by the invariant), so applying `δ` in Phase 3 computes exactly the transition `M` itself would take. Phase 4 then writes the new symbols and moves each dot exactly as `M`'s heads would move, expanding blocks as needed so that no information is ever overwritten or lost. Hence the invariant holds after `t+1` steps. By induction it holds for all `t`, so `S` enters `qaccept`/`qreject` at exactly the same step `M` would, giving `L(S) = L(M)`.
Time complexity. Suppose `M` runs for `t` steps on some input of length `n`, and let `n' = O(n + t)` be the maximum number of cells any tape of `M` could have used (a machine cannot use more cells than steps it has taken, plus the input length). Each simulated step requires `S` to sweep across the entire used portion of its tape — of length `O(n')` — twice (read phase, write phase), plus possibly shifting a suffix of the tape, which is also `O(n')`. So:
Simulating all `t` steps of `M` therefore costs
single-tape steps, since `t ≥ n` for any machine that must at least read its input (formally, whenever `t = Ω(n)`, which holds unless the machine is trivial). This is the celebrated quadratic slowdown: a k-tape machine running in time `t(n)` is simulated by a single-tape machine running in time `O(t(n)²)`. The constant hidden in the `O(·)` depends on `k` and on the size of `M`'s alphabet, but not on the input.
Space complexity. `S` uses `O(n')` = `O(n + t)` cells, the same order as the total space used by all k tapes of `M` combined — the interleaving encoding adds only a constant-factor overhead (the `#` separators and the dot-marking), so space usage is asymptotically unaffected.
Honesty about the tradeoff. The quadratic bound is tight in general — there exist k-tape machines (e.g., ones exploiting parallel scanning of two ends of a string, as in palindrome-checking) that run in `O(n)` time on k tapes but provably require `Ω(n²)` time on any single-tape machine, so the simulation's overhead is not merely an artifact of a suboptimal proof; it reflects a genuine, provable time-complexity gap between the one-tape and multi-tape models. This is precisely why complexity theory defines classes like `P` using a polynomially robust notion of "efficient" (see Nondeterministic Turing Machines for the analogous but exponential gap when simulating nondeterminism on a single tape) — a quadratic slowdown does not change whether a language is decidable in polynomial time, only the specific polynomial.
Worked example
Let `M` be a 2-tape machine that copies its input from tape 1 onto tape 2, symbol by symbol, then accepts. Concretely, on each step, if tape 1's head reads a non-blank symbol `s`, `M` writes `s` onto tape 2, and moves both heads right; when tape 1's head reads blank (`☐`), `M` enters `qaccept`. Let the input be `w = 01`. Trace the single-tape simulation `S` builds internally. Write the encoded tape as `#[tape-1 block]#[tape-2 block]#`, with a dot over the currently-scanned symbol in each block.
| Simulated step | Tape 1 (M) | Tape 2 (M) | S's encoded tape (dots shown as `_̇`) | S's sweeps this step |
|---|---|---|---|---|
| 0 (start) | `0̇1` | `☐̇` | `# 0̇ 1 # ☐̇ #` | Phase 1: build encoding |
| 1 | `0 1̇` | `0̇ ☐` | `# 0 1̇ # 0̇ ☐ #` | read `(0, ☐)`; write `0` to tape 2, both heads → right |
| 2 | `0 1 ☐̇` | `0 1̇ ☐` | `# 0 1 ☐̇ # 0 1̇ ☐ #` | read `(1, 0)`; write `1` to tape 2, both heads → right |
| 3 (halt) | `0 1 ☐̇` | `0 1 ☐̇` | `# 0 1 ☐̇ # 0 1 ☐̇ #` | read `(☐, 1)`; `M` enters `qaccept` |
Notice how, at step 2, tape 1's head moves right off the previously-written region onto its blank cell — this is exactly the "block growth" case from Phase 4: `S` must extend tape 1's block by one cell (and shift tape 2's block one cell further right on the physical tape) before it can place the new dot. This single conceptual event (a virtual tape growing) is what forces `S` to re-sweep from the beginning on every step, rather than simply remembering an offset — because the absolute position on the physical tape where tape 2's block begins shifts every time tape 1 grows. Counting concretely: `M` takes `t = 3` steps (two copy-steps plus the accept-check) on an input of length `n = 2`. Each simulated step sweeps a tape of length `O(n' ) = O(4)` cells at worst (a small constant here because `n` is tiny), giving a total of about `3 × O(4) = O(12)` single-tape steps for the full simulation — consistent with the `O(t²)` bound (here `t² = 9`, and the true constant-factor overhead from `#` markers and two sweeps per step brings it into that range). For larger `n`, the same accounting scales exactly as `O(t² )`.
Common pitfalls & traps
| Pitfall | Why it happens | Fix |
|---|---|---|
| Forgetting to shift the tape when a virtual tape grows | Treating block boundaries as fixed rather than dynamic | Always check, on every write, whether the dot moved past the block's used region, and shift the suffix right if so |
| Confusing "equivalent" with "equally fast" | The theorem says same language, not same running time | State the tradeoff explicitly: language-equivalent, but with an `O(t²)` time overhead |
| Assuming a constant number of sweeps handles unboundedly many tapes | The two-sweep argument assumes `k` is a fixed constant | For `k` tapes, each step still needs `O(k)` sweeps or a single sweep tracking `k` markers, so the constant grows with `k`, not with `n` |
| Losing track of which block a `#` belongs to after multiple shifts | Off-by-one errors when re-scanning after insertions | Use a delimiter symbol disjoint from `Γ` (never reusable as data) and re-derive block boundaries by counting `#`s, not by cached indices |
| Believing multitape machines can decide strictly more languages | Confusing efficiency gains with computational power | Recall the equivalence theorem: decidability and recognizability are identical across k-tape and 1-tape models |
Pioneers & history
The multitape Turing machine and its simulation by a single-tape machine were part of the foundational toolkit built up as Turing's original 1936 model was refined into the machine used throughout complexity theory. The equivalence theorem is a direct descendant of Turing's own insight that a "universal" single mechanism can imitate the behavior of arbitrarily elaborate special-purpose devices — the same idea later crystallizes in the Church-Turing Thesis and in the notion of a universal Turing machine.
Origins · 1 minAlan Mathison Turing and how this was discovered
Where this matters
The equivalence of multitape and single-tape Turing machines is not merely a tidy theorem — it licenses how theoretical computer scientists design algorithms and machines throughout the rest of the subject. When proving a language is decidable or Turing-recognizable, it is standard practice to describe an algorithm using several tapes (one for the input, one as a counter, one as scratch space) because this matches how real programs use multiple arrays, stacks, and registers — and the equivalence theorem guarantees this convenience costs nothing in terms of decidability, and at most a polynomial cost in running time. This is exactly the mindset used when constructing Nondeterministic Turing Machines simulations and when arguing that random access machines, register machines, and real programming languages are all polynomially equivalent to Turing machines — a chain of robustness results that together support the Church-Turing Thesis's claim that "any reasonable model of computation" defines the same class of computable functions. Compiler design, virtual machine architectures, and even the theoretical justification for treating "polynomial time" as machine-independent all rest on this same style of simulation argument: encode auxiliary structures into a single linear memory, pay a polynomial overhead, and preserve everything that mattered.
Ask the tutor: How does the simulation change if the multitape machine is also nondeterministic?
Does adding more tapes ever let a Turing machine compute a function no single-tape machine could compute?
No. The equivalence theorem shows that for any k-tape machine there exists a single-tape machine deciding or recognizing exactly the same language. Extra tapes are a convenience for the algorithm designer — they make it easy to keep several pieces of information (input, scratch work, a counter) separate — but every computation they enable can be reproduced, symbol by symbol, by interleaving all the tapes onto one long tape and using extra alphabet symbols to mark head positions. This is why computability theory defines "decidable" and "recognizable" without reference to tape count: the notion is robust to this variation in the model, which is part of the evidence supporting the Church-Turing Thesis.
Why does the simulation cost O(t²) time instead of O(t) or O(t log t)?
Each simulated step requires sweeping across the entire used portion of the encoded tape, which can be as large as O(t) cells after t steps (since a machine cannot use more tape cells than the number of steps it has taken). Repeating an O(t)-cost sweep for each of t simulated steps gives O(t · t) = O(t²) total. This bound is tight for some machines — certain linear-time multitape algorithms (like symmetric string comparisons) provably require quadratic time on any single-tape machine, so no encoding trick can bring the general bound below O(t²) using this style of simulation.
How is a configuration of a multitape machine different from a single-tape configuration?
A single-tape configuration records one tape's contents, one head position, and the current state. A k-tape configuration generalizes this directly: it records all k tapes' contents, all k head positions, and the current state, which is shared across all tapes. The transition function reads all k currently-scanned symbols at once and updates all k tapes and all k heads simultaneously in a single step — this is what makes multitape machines convenient for tasks like comparing two strings position by position without repeatedly re-scanning.
What exactly does S's finite control need to track during the simulation?
S's finite control must remember M's current state (a single symbol from M's state set Q), and, during the two sweeps of each simulated step, it must temporarily remember the k symbols read under the k dots (this requires expanding S's own state set to include "memory slots" for these k symbols while sweeping). Once the sweep completes and δ is applied, S returns to tracking just M's state before beginning the next step's first sweep. This is why S's state set is larger than M's, though still finite.
Does this equivalence theorem say anything about nondeterministic Turing machines?
Not directly, but it uses the identical proof technique. Simulating a nondeterministic machine on a deterministic single-tape machine (covered under Nondeterministic Turing Machines) also relies on encoding multiple pieces of information — in that case, all branches of the computation tree — onto a single tape. The overhead there is exponential rather than quadratic, illustrating that not every "reasonable" model variation is polynomially free; nondeterminism appears to add real power to efficient computation, unlike extra tapes.
Is the O(t²) bound the best possible for simulating any multitape machine on one tape?
For the general interleaving technique described here, yes — it is tight, since specific problems (informally, those requiring comparison of far-apart symbols, like palindrome checking) can be solved in linear time with two tapes but require quadratic time on one tape, by a separate lower-bound argument using an information-flow counting technique. So while smarter encodings exist for special cases, no universal simulation scheme beats O(t²) in the worst case over all multitape machines.
Why does this matter for defining complexity classes like P?
Complexity class P is usually defined using an arbitrary "reasonable" deterministic machine model, precisely because results like this one show that switching between single-tape, multitape, or other reasonable models changes running time by at most a polynomial factor. Since P is defined as "solvable in time polynomial in input length," a polynomial-factor slowdown (like the quadratic one from this theorem) never moves a language into or out of P. This robustness is why P is considered a machine-independent, mathematically natural class.