Variants — multi-tape TM, non-deterministic TM, all equivalent: Visual walkthrough

Prerequisites we lean on: Turing Machine — formal definition (what a tape, head, and $δ$ are) and, at the very end, the Church–Turing Thesis.

Step 1 — What a Turing machine actually is (the picture we build on)

WHAT we are looking at: the simplest machine — one tape, one head.

WHY start here: this is the "humble" machine everything must collapse to. If we can make it imitate a fancier machine, the fancy machine gives no new power.

PICTURE: one strip, one triangle pointing at the current cell.

Figure — Variants — multi-tape TM, non-deterministic TM, all equivalent

Step 2 — The multi-tape machine, drawn honestly

Reading each symbol where it sits:

$Q$ — the finite set of "moods" (states) the control can be in.
$Γ$ — the alphabet of symbols a cell may hold; $Γ^{k}$ means "one symbol from each of the $k$ tapes, bundled into a $k$ -tuple."
${L, R}^{k}$ — a $k$ -tuple of moves, one per head, so head 1 can go left while head 2 goes right, all in the same step.

WHAT: three tapes here ( $k = 3$ ), each with its own arrow, reading three symbols simultaneously.

WHY it feels stronger: to compare the start and end of a string, a 3-tape machine puts one copy on tape 2, another on tape 3, and walks both heads inward — no shuffling. That is faster and easier to program. Our job is to show it is not more powerful.

PICTURE: three separate strips, three arrows, the rule reading all three at once.

Step 3 — The key trick: fold the tapes onto one strip

We invent exactly one new symbol:

$#$ — the block separator ("fence"). It never appears inside a virtual tape's data, so the single-tape machine can always tell where one virtual tape ends and the next begins.

So the single tape now reads: $# a_{1} a_{2} a_{3} # b_{1} b_{2} # c_{1} c_{2} #$ where the first block is (virtual) tape 1's contents, the second is tape 2's, the third is tape 3's.

WHAT: we glued three strips into one, with fences.

WHY this move and not another: a single tape has no notion of "which tape" — the fence $#$ manufactures that distinction with a plain symbol, which is all a TM is allowed to use.

PICTURE: the three strips of Step 2 flattened into one strip with orange fences.

Step 4 — Remembering where each head was: the dot trick

One more piece of notation, earned:

$\overset{x}{˙}$ — a dotted symbol, meaning "a virtual head is parked on this cell." For every ordinary symbol $x$ we add a twin $\overset{x}{˙}$ to the alphabet. There is exactly one dotted symbol per block.

So a snapshot might be: $# \overset{a}{˙}_{1} a_{2} a_{3} # b_{1} \dot{b}_{2} # \overset{c}{˙}_{1} c_{2} #$

$\overset{a}{˙}_{1}$ — virtual head 1 is on the first cell of tape 1.
$\dot{b}_{2}$ — virtual head 2 is on the second cell of tape 2.
$\overset{c}{˙}_{1}$ — virtual head 3 is on the first cell of tape 3.

WHAT: we marked three head positions with dots.

WHY dots and not a separate list of numbers: numbers would need arithmetic to keep them lined up with the data as it shifts; a dot rides along with its cell automatically, so it stays correct for free.

PICTURE: the flattened strip with a green dot over one symbol per block.

Step 5 — Sweep ONE: gather all the heads' symbols

After the sweep the control is holding the tuple $(\overset{a}{˙}_{1}, \dot{b}_{2}, \overset{c}{˙}_{1})$

each entry is the symbol one virtual head is reading;
the control has finitely many states, and there are finitely many possible tuples, so "remembering the tuple" costs only finitely many extra states — legal.

WHAT: one left-to-right pass that collects the $k$ read symbols.

WHY a sweep is necessary: the heads are scattered across the strip; there is no way to see them all at once, so we serialise the simultaneous read into one walk.

PICTURE: a blue arrow sweeping right, snapshotting each dotted symbol into the control box.

Step 6 — Sweep TWO: apply the rule (write + move every head)

For a virtual tape whose head reads $\overset{x}{˙}$ , the rule tells us $(x^{'}, m)$ where $x^{'}$ is the new symbol and $m \in {L, R}$ :

write $x^{'}$ where the dot was;
if $m = R$ , dot the cell to the right; if $m = L$ , dot the cell to the left.

WHAT: a second pass that performs the simultaneous write-and-move for all $k$ heads.

WHY two sweeps and not one: you cannot decide what to write until you have read every head (that needs the whole first sweep). Only then is the rule determined, so the writing must wait for a second pass.

PICTURE: an orange arrow sweeping back; each block shows old symbol crossed out, new symbol written, dot hopped one cell.

Step 7 — The edge case: a virtual head walks off the end of its block

Fix: when a dot would land on a $#$ , the machine shifts the entire rest of the tape one cell to the right, drops a blank $⊔$ into the newly opened cell, and then puts the dot on that blank.

$⊔$ — the blank symbol; a virtual tape is conceptually all blanks past its written region, so opening one is faithful.
shifting "everything to the right" is a routine TM operation (copy each symbol one cell over, right-to-left).

WHAT: we handled the case where a virtual tape needs to lengthen.

WHY we cannot skip it: without this, long computations would hit the fence and stall — the simulation would be wrong, not just slow. Covering it makes the simulation faithful for every input length.

PICTURE: a head hitting $#$ ; the strip stretches, a red-outlined blank appears, the dot moves onto it.

Step 8 — The cost: why it is quadratic, term by term

Reading each factor where it sits:

$t (n)$ (first factor) — the multi-tape machine takes at most $t (n)$ steps on an input of length $n$ .
In those $t (n)$ steps no head can move more than $t (n)$ cells, so all the written data (all blocks + fences) fits in a region of length $O (t (n))$ .
$O (t (n))$ (second factor) — simulating one real step costs two sweeps across that $O (t (n))$ -long region (plus occasional shifts, which are also $O (t (n))$ ). So per-step work is $O (t (n))$ .
Multiply: $t (n) \cdot O (t (n)) = O (t (n)^{2})$ — a quadratic slowdown, and nothing worse.

WHAT: we measured the price of the trick.

WHY it matters: it proves the slowdown is polynomial, not explosive. Same class of solvable problems, just slower — exactly the parent's claim. (Contrast: the non-deterministic variant's simulation costs exponential time — a different story, told on its own page.) This is why time-based classes like those in Time Complexity and Big-O often ignore "how many tapes."

PICTURE: a bar showing the $O (t)$ -long used region, and the "two sweeps per step" that give the square.

The one-picture summary

Everything above in a single frame: three tapes → one strip with fences and dots → two sweeps per step → quadratic cost, identical power.

Recall Feynman: tell it to a 12-year-old

Imagine a kid with three notebook pages, doodling on all three at once with three pencils. Now a second kid has only one page. Can the one-page kid copy the three-page kid exactly? Yes! Rule the single page into three sections with a bold line ( $#$ ) between them — one section pretends to be each page. Put a little star ( $\overset{x}{˙}$ ) on the letter each imaginary pencil is touching. To copy one move of the three-pencil kid, the one-page kid: (1) reads left-to-right across all three sections, memorising the three starred letters, (2) reads back, updating each starred letter and moving each star one step. If a pencil runs off the end of its section, the kid squeezes in an extra blank box and stretches the page. It takes the one-page kid a few passes per move — so about square the time — but the answer is exactly the same. That "same answer, just slower" is the whole point: extra pages make you faster, never smarter. This robustness is the evidence that "computable" means one single, solid thing.

Recall Quick self-test

Why two sweeps, not one? ::: The first sweep reads every head's symbol; only after all are known is the rule $δ$ determined, so writing must wait for a second sweep. What does a dot $\overset{x}{˙}$ mean? ::: A virtual head is parked on that cell; there is exactly one dotted symbol per block. What happens when a virtual head hits a $#$ ? ::: The block is too short — shift the rest of the tape right, insert a blank $⊔$ , and put the dot there (the virtual tape grows). What is the slowdown factor? ::: Quadratic, $O (t (n)^{2})$ , because each of $t (n)$ steps costs $O (t (n))$ work on an $O (t (n))$ -long region. Does multi-tape recognise more languages than single-tape? ::: No — exactly the same class; only the speed differs.