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

Before we start, one shared vocabulary reminder — no new symbol will be used before it is named here:

Definition Symbols used on this page

$Q$ ::: the set of states (the machine's finite "memory of where it is in the rules").
$Γ$ ::: the tape alphabet (every symbol that can appear on a tape, including the blank).
$L, R$ ::: the two head-move directions — $L$ means "move the head one cell left," $R$ means "one cell right." Every step must move a head one way or the other.
$δ$ (delta) ::: the transition function — the machine's rulebook. Given the current state and the symbol(s) under the head(s), it returns what to do next: which state to enter, what to write, and which way to move. It is written as a type signature $δ : inputs \to outputs$ .
$δ$ for a single-tape TM ::: $δ : Q \times Γ \to Q \times Γ \times {L, R}$ (read one symbol → new state, symbol to write, one move).
$δ$ for a $k$ -tape TM ::: $δ : Q \times Γ^{k} \to Q \times Γ^{k} \times {L, R}^{k}$ — it reads the $k$ symbols under all $k$ heads at once ( $Γ^{k}$ ), then writes $k$ symbols and moves each of the $k$ heads independently ( ${L, R}^{k}$ ).
$k$ ::: the number of tapes on a multi-tape machine.
$t (n)$ ::: the number of steps a machine takes on an input of length $n$ (its running time).
$b$ ::: the branching factor of a non-deterministic machine — the largest number of choices any single transition offers.
address tape ::: in the NTM→DTM simulation, a bookkeeping tape whose contents are a string over the alphabet ${1, 2, \dots, b}$ ; the string names which choice to take at each step of one branch (e.g. 2 1 3 = "step 1 take choice 2, step 2 take choice 1, step 3 take choice 3").
"Recognize a language" ::: accept exactly the strings in that language (and never accept a string outside it).

If any of these feel shaky, revisit Turing Machine — formal definition first.

Level 1 — Recognition

(Can you recall the definitions and the headline facts?)

Problem 1.1

A $k$ -tape Turing machine has how many independent read/write heads, and where does the input string start?

Recall Solution 1.1

WHAT: A $k$ -tape machine has exactly $k$ heads — one per tape, each moving independently. WHERE the input goes: the input string is written on tape 1; every other tape (tape 2 through tape $k$ ) starts completely blank. WHY it matters: because the transition reads all $k$ heads simultaneously, having a blank scratch tape is what lets multi-tape machines be cleaner to program, not more powerful. See Turing Machine — formal definition.

Problem 1.2

Fill in the type signature. A deterministic single-tape TM has $δ : Q \times Γ \to___$ . A non-deterministic TM has $δ : Q \times Γ \to___$ . What is the one structural difference? (Recall from the Symbols list: $δ$ is the rulebook, and ${L, R}$ are the two head-move directions.)

Recall Solution 1.2

Deterministic: $δ : Q \times Γ \to Q \times Γ \times {L, R}$ The output is a single triple: one next state, one symbol to write, one move ( $L$ or $R$ ).

Non-deterministic: $δ : Q \times Γ \to P (Q \times Γ \times {L, R})$ The output is a set of triples ( $P$ means "power set" = "the collection of all possible subsets"). So instead of one forced move, the machine may have several legal moves.

The one difference: deterministic returns one option; non-deterministic returns a set of options. Everything else is identical.

Problem 1.3

True or false: an NTM can recognize a language that no deterministic TM can recognize.

Recall Solution 1.3

FALSE. Every NTM has an equivalent deterministic TM that recognizes the same language (via the breadth-first tree search shown in the parent note). Non-determinism can make a machine faster or easier to describe, but adds zero new recognizable languages. This equivalence is exactly why the Church–Turing Thesis is believable.

Level 2 — Application

(Plug numbers into the cost formulas.)

Problem 2.1

A 4-tape TM (transition function $δ : Q \times Γ^{4} \to Q \times Γ^{4} \times {L, R}^{4}$ ) runs in $t (n) = 50 n$ steps. Using the multi-tape→single-tape simulation, give a Big-O bound on the single-tape simulator's running time, and evaluate it at $n = 100$ (as a Big-O expression, then the dominant term's value).

Recall Solution 2.1

WHAT tool & WHY: the simulation cost is $O (t (n)^{2})$ — quadratic — because each simulated step needs a couple of sweeps across a tape region of length $O (t (n))$ . (Why quadratic and not linear? In $t (n)$ steps no head can move more than $t (n)$ cells, so the "used" region is $O (t (n))$ long, and we cross it once per simulated step: $t (n) \times O (t (n))$ .)

Compute: $O (t (n)^{2}) = O ((50 n)^{2}) = O (2500 n^{2}) = O (n^{2}) .$ The constant $2500$ is absorbed by Big-O. At $n = 100$ , the dominant term $2500 n^{2} = 2500 \cdot 10000 = 25, 000, 000$ steps. Takeaway: number of tapes ( $k = 4$ ) does not appear in the exponent — it only affects the hidden constant. See Time Complexity and Big-O.

Problem 2.2

An NTM with branching factor $b = 2$ accepts every string within depth $t (n) = n$ . How many leaves at most does its computation tree have at $n = 10$ , and what is the Big-O class of the deterministic simulation?

Recall Solution 2.2

WHAT tool & WHY: each node of the computation tree can branch into at most $b$ children, so after $t (n)$ steps the tree has at most $b^{t (n)}$ leaves. (Why exponent? Every extra level multiplies the count by $b$ ; repeated multiplication is an exponential.)

Compute leaves at $n = 10$ : $b^{t (n)} = 2^{10} = 1024.$ Simulation class: the DTM may visit the whole tree, so $DTM time = 2^{O (t (n))} = 2^{O (n)} .$ This exponential blow-up is precisely the mystery behind P vs NP problem — the simulation works (same power) but is (as far as anyone knows) slow.

Problem 2.3

An NTM has these transition entries with these option-set sizes: entry A gives 3 options, entry B gives 1 option, entry C gives 4 options, entry D gives 2 options. What is the branching factor $b$ , and how many distinct branch-addresses of length exactly 3 are possible in the worst case? (Recall from the Symbols list: the address tape holds a string over ${1, \dots, b}$ .)

Recall Solution 2.3

Branching factor $b$ = the maximum option-set size across all entries: $b = max {3, 1, 4, 2} = 4.$ Why max, not sum or average? The address tape uses digits ${1, \dots, b}$ ; it must be able to name the widest choice-point, so it sizes itself to the largest.

Addresses of length 3: an address is a string over ${1, \dots, b}$ , so length-3 addresses number $b^{3} = 4^{3} = 64.$ (Some of these are "invalid" at run time when a narrower entry is reached — the simulator simply aborts those branches.)

Level 3 — Analysis

(Explain the "why" behind a design choice.)

Problem 3.1

In the NTM→DTM simulation we search the computation tree breadth-first, not depth-first. Construct a concrete NTM behaviour where depth-first search fails but breadth-first succeeds, and explain exactly where DFS gets stuck.

Recall Solution 3.1

Construct the villain branch. Suppose on input $w$ the NTM's very first transition offers two choices:

Choice 1: enter a loop that keeps moving right forever, never accepting, never halting — an infinite non-accepting branch.
Choice 2: take one step and accept.

What DFS does (and why it fails): depth-first commits to Choice 1 first and follows it to its end. But Choice 1 has no end — it runs forever. DFS never backtracks to try Choice 2, so it loops eternally and misses an accepting branch that was one step away. The machine would fail to accept a string it should accept.

What BFS does (and why it wins): breadth-first explores all branches at depth 1, then all at depth 2, and so on. Choice 2 accepts at depth 1, so BFS finds it before ever getting lost in Choice 1's infinite depth. Rule: any accepting branch at finite depth $d$ is found after finitely many BFS layers.

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

Problem 3.2

Why does the DTM simulator keep the input on a separate read-only tape (tape 1) instead of just re-deriving it? Give the failure mode if it didn't.

Recall Solution 3.2

WHAT tape 1 is for: it holds a pristine, untouched copy of the input $w$ . WHY separate & read-only: each branch of the tree simulation must start from the exact same input. During a branch, the working tape (tape 2) gets overwritten as the NTM computes. If there were no clean master copy, the next branch would begin from a corrupted, half-computed tape. Failure mode without it: branch 2 inherits branch 1's scribbles → it simulates the wrong computation → the DTM may accept or reject strings incorrectly, breaking the "same language" guarantee. So tape 1 is copied to tape 2 fresh at the top of every loop iteration, while the address tape (tape 3, holding a string over ${1, \dots, b}$ ) decides which choices to take. This is why we needed 3 tapes (input, work, address) — and 3-tape is fine because 3-tape ≡ 1-tape.

Level 4 — Synthesis

(Combine two results.)

Problem 4.1

A problem is solved by a non-deterministic 3-tape TM in $t (n) = n^{2}$ steps with branching $b = 3$ . You must implement it on a plain single-tape deterministic TM. Chain the two simulations and give the final Big-O time bound. Show which factor dominates.

Recall Solution 4.1

Step 1 — collapse non-determinism (WHY first: it's the expensive one). A non-deterministic machine of running time $t (n)$ and branching $b$ becomes a deterministic multi-tape machine in $2^{O (t (n))} = 2^{O (n^{2})} steps.$ (The tree has $O (b^{t (n)}) = O (3^{n^{2}})$ nodes; $3^{n^{2}} = 2^{(l o g_{2} 3) n^{2}} = 2^{O (n^{2})}$ .)

Step 2 — collapse the tapes. That deterministic multi-tape machine now runs in some time $T (n) = 2^{O (n^{2})}$ ; simulating it on one tape costs $O (T (n)^{2})$ : $O ((2^{O (n^{2})})^{2}) = O (2^{2 \cdot O (n^{2})}) = 2^{O (n^{2})} .$

Which factor dominates & final answer: squaring an exponential only doubles the exponent's constant, which Big-O absorbs. The polynomial tape-slowdown is completely swallowed by the exponential search. $2^{O (n^{2})}$ Moral: stacking simulations preserves computability exactly; the cost is dominated by the single exponential blow-up of non-determinism, not by the tape bookkeeping.

Problem 4.2

Argue that a machine with a two-way infinite tape (unbounded in both directions) adds no computational power, using the same simulation strategy (marking + laying data side-by-side) that beat the multi-tape machine.

Recall Solution 4.2

WHAT the strategy is: "fold" the doubly-infinite tape onto a standard one-way-infinite tape by interleaving. HOW: label the two-way cells $\dots, - 2, - 1, 0, 1, 2, \dots$ . Map them onto a one-way tape by interleaving the negative and non-negative halves: $one-way position 0, 1, 2, 3, 4, \dots \leftrightarrow two-way 0, - 1, 1, - 2, 2, \dots$ The finite-state control keeps a single bit remembering "am I currently on the upper track or lower track," exactly like the dotted-symbol marking trick that tracked virtual heads. WHY it's no more powerful: everything the two-way machine reads/writes is reproduced by a one-way machine doing bounded extra bookkeeping (one tracking bit, a fixed remapping of moves). No step reaches outside "finite rules on an unbounded tape." Hence same recognizable languages ⇒ another confirmation of Church–Turing Thesis.

Level 5 — Mastery

(Prove / disprove; reason about the boundary.)

Problem 5.1

A classmate claims: "Because the DTM simulation of an NTM takes exponential time, there must be some language the NTM recognizes but the DTM cannot — the DTM just runs out of time." Refute this rigorously.

Recall Solution 5.1

The claim conflates two independent notions: recognizability vs. speed.

Refutation. "The DTM runs out of time" is not a property of a machine — a Turing machine has an unbounded tape and no time limit in the definition of recognition. For recognizability we only ask: does there exist a finite computation that accepts every string in the language and no others? The BFS simulation provides exactly that: for any string $w$ the NTM accepts, the accepting branch sits at some finite depth $d$ , and BFS reaches depth $d$ after finitely many steps — so the DTM does accept $w$ . It never "runs out of time"; it simply takes many (still finite) steps before halting-and-accepting.

What is actually true. The exponential cost affects efficiency (complexity), not capability (computability). The distinction is Decidability and Recognizability vs. Time Complexity and Big-O. If the language must be decided (halt-and-reject on non-members too), the same BFS works provided the NTM halts on every branch; the general recognizability result holds regardless. Verdict: the claim is false — the NTM and the simulating DTM recognize the same class of languages; only the running time differs.

Problem 5.2

Non-determinism collapses for finite automata too: an $n$ -state NFA has an equivalent DFA. That equivalent DFA can need up to $2^{n}$ states. Contrast what blows up in the NFA→DFA case versus the NTM→DTM case, and explain why both still count as "no extra power."

Recall Solution 5.2

NFA → DFA (subset construction). Determinizing an $n$ -state NFA can require a DFA with up to $2^{n}$ states — the blow-up is in space (number of states), but the resulting DFA still runs in linear time on any input. See Non-determinism in Finite Automata (NFA = DFA).

NTM → DTM. Here the machine's states stay finite and small; what explodes is time — the $2^{O (t (n))}$ tree search. The unbounded tape absorbs the "search state," so states don't blow up; the clock does.

The unifying point — why both are "no extra power":

	NFA→DFA	NTM→DTM
What explodes	states (space)	time
Same language class?	✅ regular = regular	✅ recognizable = recognizable
Extra computational power?	❌ none	❌ none

In both cases the class of languages is unchanged — that is the definition of "no extra power." Non-determinism is, in every model, a convenience you can eliminate by paying a resource cost (states here, time there).

Recall Final self-test (one line each)

Does adding tapes change the class of recognizable languages? ::: No — same class, only a polynomial ( $O (t (n)^{2})$ ) speed change. Does non-determinism change the class of recognizable languages? ::: No — same class, only a (known) exponential $2^{O (t (n))}$ speed change. What single word captures "reasonable tweaks don't change computability"? ::: Robustness (of the Turing-machine model). What thesis does all this robustness support? ::: The Church–Turing Thesis.