Variants — multi-tape TM, non-deterministic TM, all equivalent: Worked examples

This is the hands-on companion to the parent topic. The parent proved the theorems; here we turn the crank on concrete machines so no scenario surprises you in an exam. If a term feels unfamiliar, it is built in Turing Machine — formal definition.

The scenario matrix

Every case this topic can throw at you falls into one of these cells. The worked examples that follow are each tagged with the cell they cover.

#	Case class	What is degenerate / extreme about it	Example
A	Multi-tape, normal step	all heads in the middle of their blocks	Ex 1
B	Multi-tape, head hits right `#`	a virtual tape is too short → grow on the right	Ex 2
B′	Multi-tape, head hits left `#`	head walks off the left end → grow on the left	Ex 2b
C	Multi-tape, $k = 1$ (degenerate)	"multi" with one tape = plain TM, zero overhead	Ex 3
D	Multi-tape time cost	plug numbers into $O (t (n)^{2})$	Ex 4
E	NTM, accepting branch exists	tree has ≥1 accept leaf → DTM must find it	Ex 5
F	NTM, all branches reject / loop	wrong order (DFS) traps you forever	Ex 6
G	NTM, branching factor $b = 1$ (degenerate)	non-determinism that never branches = DTM	Ex 7
H	NTM time cost	plug numbers into $2^{O (t (n))}$	Ex 8
I	Real-world word problem	translate a story into "which model, which cost"	Ex 9
J	Exam twist	combine variants + a trap in the reasoning	Ex 10

Multi-tape examples

Ex 1 — Cell A · a normal simulated step

We encode all three tapes on one tape, #-separated, dot = virtual head. Figure s01 shows the whole step at a glance: the top row is BEFORE, the bottom row is AFTER, and the three colours (magenta, violet, orange) track tapes 1, 2, 3.

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

Write the "before" tape. In s01's top row, each coloured block is one virtual tape and the small orange dot sits over the head cell: $# \overset{a}{˙} b c # d \overset{e}{˙} # \dot{f} g #$ Why this step? The single tape has no separate heads, so head positions must be stored as data — the orange dot in the figure is that storage.
Sweep 1 (gather). Read left→right, record the three dotted symbols $(\overset{a}{˙}, \overset{e}{˙}, \dot{f}) = (a, e, f)$ into the finite control. In s01, follow the top row left→right and read off the dotted cells. Why this step? The real $δ$ reads all three heads simultaneously; one sweep collects them so the control holds the full tuple.
Look up $δ$ . Control now knows $(a, e, f)$ , so it fetches $(x, e, g)$ and moves $(R, L, R)$ . This is the labelled arrow between the two rows of s01. Why this step? $δ$ is a finite table — once the read tuple is in hand the output is fully determined, no tape access needed.
Sweep 2 (write & move). At the dot in each block: write the new symbol, then shift the dot one cell in the move direction. Compare the bottom row of s01 to the top:
- Block 1 (magenta): write x, move dot R → $x \dot{b} c$
- Block 2 (violet): write e, move dot L → $\dot{d} e$
- Block 3 (orange): write g, move dot R → $f \overset{g}{˙}$ Why this step? This applies the simultaneous update the $k$ -tape machine did in one shot.

Result — "after" tape (bottom row of s01): $# x \dot{b} c # \dot{d} e # f \overset{g}{˙} #$

Recall Verify

No head ran off the left/right end of its block (every dot landed on a real symbol), so no block grew — this is a clean case. Two sweeps total. State advanced $q \to q^{'}$ . The three virtual tapes now read x b c (head 2), d e (head 1), f g (head 2), which is exactly what the $3$ -tape machine would show. ✔

Ex 2 — Cell B · a head falls off the right end (grow on the right)

Sweep 1 (gather), then before-state. As always, the simulator first sweeps left→right gathering the dotted symbols $(\overset{a}{˙}, \dot{d}) = (a, d)$ and looks up $δ$ . The before-tape is $# \overset{a}{˙} b c # \dot{d} #$ . Why this step? This is the mandatory first of the two sweeps from the two-sweep definition above — even in a growth case we must gather all heads before touching anything.
Sweep 2 begins on block 2. Write d, then try to move the dot R. The cell right of d is #, not a tape symbol — the virtual tape 2 is shorter than the head now needs. Why this step? Real Turing tapes are unbounded; a # is only our drawing of a boundary, not a real end. We must extend the block during this write-and-move sweep.
Shift-right to insert a blank. Copy everything from that # rightward one cell further right, and drop a blank ␣ (the never-written symbol from the definition above) into the freed cell. Now the block reads d ␣ and the dot can sit on the new ␣. Why this step? Growing a virtual tape on a shared real tape means physically pushing all later blocks over to make one cell of room.

Before → After: $# \overset{a}{˙} b c # \dot{d} # ⟶ # a \dot{b} c # d \overset{␣}{˙} #$

Recall Verify

Tape 2 was length $1$ , now length $2$ — it grew by exactly one blank, which is what "reading past the written end" means for a real TM (unwritten cells are blanks ␣). Tape 1's head simply moved $R$ onto b. The dot now rests on a genuine cell, so the next step can read it. ✔

Ex 2b — Cell B′ · a head falls off the left end (grow on the left)

Figure s04 draws this mirror-image growth: the block gains a blank cell on its left side, and everything to the right slides over.

Sweep 1 (gather), then before-state. Sweep left→right gathering $(\overset{a}{˙}, \dot{d}) = (a, d)$ and look up $δ$ . Before-tape: $# \overset{a}{˙} b c # \dot{d} #$ . Why this step? Same mandatory first sweep of the two-sweep skeleton; only the move direction in sweep 2 will differ.
Sweep 2 on block 2. Write d, then try to move the dot L. The cell left of d is the opening # of block 2 — the head wants to stand before the first written cell. Why this step? Just like the right case, a # is only our drawing of a boundary; the real tape continues, unwritten, to the left.
Insert a blank on the left — precisely which cells move. Everything from block 2's opening # onward — that is, the # itself and all symbols and delimiters to its right (here just d and the final #) — is copied one cell to the right. The single freed cell, sitting immediately after the opening #, is filled with a blank ␣. Block 2 now reads ␣ d, and the dot sits on the new leading ␣. Why this step? To make room on the left we push the opening # and the entire rest of the tape one cell right, then fill the one-cell gap with a blank — nothing to the left of block 2's opening # moves.

Before → After: $# \overset{a}{˙} b c # \dot{d} # ⟶ # a \dot{b} c # \overset{␣}{˙} d #$

Recall Verify

Block 2 grew from d (length 1) to ␣ d (length 2), gaining its blank on the left, mirroring Ex 2's right-growth exactly. The head now sits on the fresh ␣, ready to be read. Both directions handled ⇒ every off-the-end case is covered. ✔

Ex 3 — Cell C · the degenerate case $k = 1$

Encode: $# a \dot{b} #$ . One block, one dot. Why this step? The general recipe still applies; there just happens to be a single block.
Observe: the two # delimiters and the single dot are pure decoration around the original tape a b. Why this step? To see that the "simulator" is doing genuinely nothing extra structurally.
Cost: each step is still 2 sweeps of an $O (1)$ -length-overhead block, i.e. constant-factor overhead — no quadratic blow-up because there is only one head to track. Why this step? The $O (t (n)^{2})$ bound comes from many blocks over a long tape; with one block the region is just the original tape.

Recall Verify

A $1$ -tape "multi-tape" machine is an ordinary single-tape TM, matching Turing Machine — formal definition exactly (up to the two harmless #s and the dot). The equivalence is trivial in this cell — a useful sanity anchor. ✔

Ex 4 — Cell D · plug the numbers into the time bound

Recall the bound: single-tape time $= O (t (n)^{2})$ . Why this step? Proven in the parent: used tape length $\leq t (n)$ , and $\sim 2$ sweeps per simulated step $\Rightarrow t (n) \cdot O (t (n)) = O (t (n)^{2})$ . (The " $\sim 2$ sweeps" and the " $k$ blocks per sweep" both sit in the hidden constant.)
Substitute $t (n) = 3 n$ : $O ((3 n)^{2}) = O (9 n^{2}) = O (n^{2}) .$ Why this step? The constant $9$ (and thus every trace of $k = 4$ ) vanishes inside big- $O$ — this is exactly the constant-dropping rule from the definition above, and why $k$ is a red herring for power and even for the asymptotic cost.
Evaluate the tight count $t (n)^{2} = (3 n)^{2}$ at $n = 10$ : $(30)^{2} = 900$ base step-units. Why this step? A concrete number makes "quadratic slowdown" tangible.

Recall Verify

The multi-tape machine took $3 \cdot 10 = 30$ steps; the simulator took on the order of $3 0^{2} = 900$ — a $30 \times$ slowdown, exactly the "square" the parent promised. $O (9 n^{2}) = O (n^{2})$ because the constant $9$ is dropped. ✔

Non-deterministic examples

Definition The DTM that simulates an NTM uses three tapes

Before the NTM examples, fix the machine we simulate with. The parent builds a 3-tape deterministic TM (and we already know 3-tape ≡ 1-tape from Ex 1–2b, so this is legal):

Tape 1 — input $w$ , read-only, never altered. Why? Each branch must restart from the same original input.
Tape 2 — working tape, a fresh copy of $w$ on which we simulate one chosen branch.
Tape 3 — the address, a string over ${1, \dots, b}$ (where $b$ is the max number of choices in any $δ$ entry) naming which choice to take at each step. The address 2 1 3 means "step 1 → choice 2, step 2 → choice 1, step 3 → choice 3."

The loop is: copy tape 1 → tape 2 (fresh start), simulate on tape 2 using tape 3's digits to pick choices, and if this branch accepts then accept, else increment tape 3 to the next address (shortest-first = BFS order) and repeat. Every NTM example below refers to these three tapes.

Ex 5 — Cell E · an accepting branch exists

Figure s02 draws the guess tree: the root is the empty address $ε$ , each downward edge appends a choice digit, and the accepting node 2 1 is circled in orange.

List the BFS order over ${1, 2}^{*}$ , shortest-first then lexicographic (read s02 level by level, left to right): $ε, 1, 2, 11, 12, 21, 22, \dots$ Why this step? Tape 3 enumerates addresses in exactly this order; BFS guarantees a finite-depth accepting branch is reached in finite time.
Walk them. For each address: copy tape 1 → tape 2 (fresh input), simulate using the tape-3 digits to pick choices, reject/abort, then increment tape 3. Why this step? This is the three-tape loop defined just above; the fresh copy on tape 2 is why the read-only input on tape 1 exists.
Find the winner. Addresses $ε, 1, 2, 11, 12$ all lead to reject/abort; address 21 (the orange-circled node in s02) reproduces the accepting run. Why this step? 2 1 = "step 1 take choice 2, step 2 take choice 1", the given accepting sequence.

The DTM accepts while tape 3 holds 2 1.

Recall Verify

21 is the 6th address in the enumeration $ε, 1, 2, 11, 12, 21$ . Since the accepting branch sits at depth $2$ , BFS reaches it after exhausting all depth- $\leq 2$ prefixes — finite, guaranteed. The DTM accepts iff some branch accepts, and one did. ✔ Compare with Non-determinism in Finite Automata (NFA = DFA), where the same "guess-and-verify collapses to deterministic" idea appears without the exponential cost.

Ex 6 — Cell F · why order matters (DFS trap)

Figure s03 contrasts the two strategies: the violet branch 1 spirals down into an infinite loop (where DFS dives and never returns), while the magenta branch 2 reaches ACCEPT at depth 1.

DFS attempt. DFS commits to choice 1 and follows it as deep as possible first. That path loops forever (the violet coil in s03), so DFS never returns to try choice 2. Why this step? DFS goes deep before wide; an infinite branch is a bottomless pit it never climbs out of.
Consequence. The machine loops instead of accepting — a wrong answer on an input in the language. That is a correctness failure. Why this step? Recognizing a language means: accept every string in it. Getting stuck = failing to accept = wrong.
BFS fix. BFS tries $ε$ , then 1 (one step — no loop yet), then 2 — and 2 (the magenta accept node in s03) accepts. It explores depth $1$ fully before diving into 1's infinite depth. Why this step? By bounding depth per round, BFS reaches every finite-depth accept leaf before any infinite branch can trap it.

Recall Verify

Accepting address 2 sits at depth $1$ ; BFS reaches it in round 1 (order $ε, 1, 2$ ). DFS would still be inside choice 1's loop. This is precisely why the parent insists on breadth-first. The distinction (loop vs accept) ties into Decidability and Recognizability: a recognizer may loop on non-members, but must never loop on a member. ✔

Ex 7 — Cell G · the degenerate NTM, $b = 1$

Tree shape. With $b = 1$ every node has one child: the "tree" is a single path. Why this step? Branching factor $1$ means no branching at all.
Address enumeration. Tape 3 addresses over ${1}^{*}$ are $ε, 1, 11, 111, \dots$ — but every step's only valid choice is 1, so the first full-length address already runs the unique computation. Why this step? No wrong guesses exist to skip; the enumeration is trivial.
Cost. Tree size $O (b^{t (n)}) = O (1^{t (n)}) = O (1)$ branches ⇒ simulation cost is just the cost of running that one branch: polynomial, no blow-up. Why this step? Substitute $b = 1$ into the parent's $O (b^{t (n)})$ node count.

Recall Verify

$1^{t (n)} = 1$ for every $t (n)$ , so there is exactly one branch — this NTM is a deterministic TM in disguise. The exponential blow-up of P vs NP problem appears only when $b \geq 2$ . ✔

Ex 8 — Cell H · plug the numbers into the exponential bound

Node count. A depth- $t (n)$ binary tree has up to $\sum_{d = 0}^{t (n)} 2^{d} = 2^{t (n) + 1} - 1 = O (2^{t (n)})$ nodes. Why this step? Level $d$ holds $\leq b^{d} = 2^{d}$ nodes; summing all levels the top term dominates ⇒ $O (2^{t (n)})$ .
DTM cost. The DTM may visit them all, so simulation time $= 2^{O (t (n))}$ . Why this step? BFS visits nodes; worst case it visits every one before the accept leaf.
Evaluate at $n = 5$ : total nodes $= 2^{5 + 1} - 1 = 2^{6} - 1 = 63$ ; the quadratic comparison value is $t (n)^{2} = 5^{2} = 25$ . Why this step? A concrete count to feel the explosion: $63$ nodes to walk versus $25$ step-units — already $2.5 \times$ larger.

Recall Verify

At $n = 5$ : multi-tape-style cost $t (n)^{2} = 25$ ; NTM-style node count $2^{t (n) + 1} - 1 = 63$ . Already $2.5 \times$ bigger at $n = 5$ , and the gap explodes as $n$ grows ( $n = 20$ : $400$ vs $2^{21} - 1 \approx 2 \times 1 0^{6}$ ). Same power, wildly different cost — the seed of P vs NP problem. ✔

Word problem and exam twist

Ex 9 — Cell I · real-world translation

Identify the variant. "Guess a route, then verify" = non-determinism: branch over all candidate routes, accept if any verifies. That is an NTM. Why this step? Guessing-then-checking is the textbook signature of the NTM's accept-if-any-branch rule.
Answer (a): the junior is describing an NTM.
Answer (b): By the parent's theorem, every NTM has an equivalent DTM (via BFS over the guess tree on the three tapes above, exactly as in Ex 5–6). So a deterministic machine can solve the exact same decision problem — the guess adds zero new computable languages. Why this step? Power = set of recognizable languages, which is identical across the two models.
The honest caveat. The known deterministic simulation costs $2^{O (t (n))}$ — exponential. So the guess might be faster, but "faster" is a claim about complexity, not computability. Why this step? Separating the two axes is the whole point of the topic (and of Church–Turing Thesis).

Recall Verify

The junior conflated power with speed. Correct scoring: (a) NTM ✔; (b) not more powerful — a DTM solves it too — but possibly (unproven) not as fast. This is exactly the P-vs-NP open question, per P vs NP problem. ✔

Ex 10 — Cell J · exam twist (combine variants + spot the trap)

Spot the trap. The word "combines" suggests two powers stacking into something new. Test that against the equivalence theorems. Why this step? Exam traps hide in unproven "combination" claims.
Chain 1 — strip non-determinism. A non-deterministic $3$ -tape TM has an equivalent deterministic $3$ -tape TM (NTM→DTM simulation works tape-count-agnostically; the BFS just runs on however many tapes exist). Why this step? The NTM→DTM simulation from the parent does not depend on there being one tape.
Chain 2 — strip extra tapes. A deterministic $3$ -tape TM has an equivalent single-tape deterministic TM (multi-tape→single-tape simulation, the #-and-dot encoding of Ex 1–2b). Why this step? The #-and-dot encoding collapses any $k$ down to $1$ .
Conclude. Non-det $3$ -tape $\equiv$ det $3$ -tape $\equiv$ det $1$ -tape. So it recognizes exactly the single-tape-recognizable languages — nothing new. Why this step? Equivalence is transitive; two hops land us back at the humblest model.

Verdict: FALSE. Both upgrades are finite bookkeeping conveniences; composing them still stays inside computability.

Recall Verify

Transitivity of " $\equiv$ " gives non-det-3-tape $\equiv$ 1-tape-DTM, so the class of recognized languages is identical — the claim of new power is false. Any efficiency difference is a complexity matter, not a computability one. This robustness under stacked variants is the strongest evidence for the Church–Turing Thesis. ✔

Recall One-line self-test

Does adding tapes or guessing ever make a new language recognizable? ::: No — same computability, only (possibly) different speed. Why BFS and not DFS for NTM→DTM? ::: A wrong first guess can loop forever; DFS would get trapped and miss a nearby accepting branch, breaking correctness. Multi-tape slowdown order? ::: $O (t (n)^{2})$ — quadratic. NTM→DTM slowdown order? ::: $2^{O (t (n))}$ — exponential. When a head runs off the left #, where does the blank go? ::: Inserted on the left of the block (push everything right, fill with ␣). How many tapes does the DTM that simulates an NTM use, and what are they for? ::: Three — tape 1 = read-only input, tape 2 = working copy for one branch, tape 3 = the address naming which choices to take.