Worked examples — Universal Turing machine

This page is a drill. The Universal Turing machine parent note told you what $U$ is and why it exists. Here we run it — by hand — across every kind of situation a machine $M$ can be in when you hand $⟨M⟩$ and $w$ to $U$.

Before we start, two symbols you will see everywhere, defined from zero:

We also use the arrow $\downarrow$ to mean "halts" (stops, gives an answer) and $\uparrow$ to mean "loops forever" (never stops). These come straight from the parent's halting notation.

The scenario matrix

Every UTM run lands in exactly one of these cells. If you can hand-simulate all of them, you have seen every case class this topic can throw.

The examples below are labelled with the cell(s) they cover.

Example A — $M$ accepts (the happy path)

1. Initialize. Tape 3 (state) $=q_0$; Tape 2 (data) $=0$ with the head on that 0. Why this step? $U$ must start $M$ in $M$'s start configuration — same as pressing "run".
2. Fetch. $U$ scans Tape 1 for the rule whose left side is $(q_0,0)$. It finds $\delta (q_0,0)=(q_{acc},1,R)$. Why this step? This is the "look up $\delta$" line — find which instruction applies.
3. Execute. Write 1 on Tape 2, move the head R, set Tape 3 $=q_{acc}$. Why this step? Apply the extracted $(q^{\prime },b,D)=(q_{acc},1,R)$ exactly.
4. Halt check. New state is $q_{acc}$ → $U$ accepts. Why this step? $U$'s halting must mirror $M$'s: $M$ reached accept, so does $U$.

Verify: Direct run of $M$ on 0: reads 0, writes 1, goes to $q_{acc}$ → accepts, tape 1. $U$ produced accept + tape 1. Same output ✔. Contract $U(⟨M⟩,0)=M(0)$ holds.

Example B — $M$ rejects (mirror the reject)

1. Initialize. Tape 3 $=q_0$, head reads 0. Why? Start config again.
2. Fetch. Match $(q_0,0)$ → rule $(q_{rej},0,R)$. Why? Look up the instruction.
3. Execute. Write 0, move R, Tape 3 $=q_{rej}$. Why? Apply it faithfully.
4. Halt check. State is $q_{rej}$ → $U$ rejects. Why? Halting is not the same as accepting. $U$ copies the kind of halt.

Verify: $M(0)$ rejects. $U$ rejects. Match ✔. Lesson: "halted" splits into two outcomes and $U$ must pick the same one $M$ would.

Example C — $M$ loops forever (the halting trap)

1. Initialize. Tape 3 $=q_0$, head on the first symbol. Why? Start config.
2. Fetch. Match $(q_0,a)$ → $(q_0,a,R)$. Why? Look up the instruction — it always matches.
3. Execute. Keep symbol, move R, stay in $q_0$. Why? Apply it.
4. Halt check. State is still $q_0$, never $q_{acc}$ or $q_{rej}$ → go to step 2 again. Why? Nothing signals a halt, so the loop repeats — forever.

Verify: $M$ on this input never halts ($\uparrow$). $U$ also never halts ($\uparrow$). Match ✔.

Example D — Empty input $w=\epsilon$ (degenerate data)

1. Initialize. Tape 2 is entirely blank; the head sits on a $\square$. Tape 3 $=q_0$. Why? An empty input means the working tape is all blanks — the head still reads something, namely $\square$. Degenerate inputs never leave the head "reading nothing."
2. Fetch. Match $(q_0,\square )$ → $(q_{acc},\square ,R)$. Why? The rule for the blank symbol is a genuine table row; we look it up like any other.
3. Execute. Keep $\square$, move R, Tape 3 $=q_{acc}$. Why? Apply it.
4. Halt check. $q_{acc}$ → accept.

Verify: $M(\epsilon )$ accepts (its only reachable rule leads to $q_{acc}$). $U$ accepts. Match ✔. Key idea: empty input ≠ undefined behaviour; the blank symbol is a first-class symbol.

Example E — No matching rule (partial $\delta$)

1. Initialize. Tape 3 $=q_0$, head reads 1. Why? Start config.
2. Fetch. $U$ scans the whole of Tape 1 for a left side $(q_0,1)$. It reaches the end marker 111 without a match. Why? $\delta$ is a partial function — some (state, symbol) pairs simply have no row.
3. Halt with no move. By convention, a missing transition means $M$ halts and rejects (there is nowhere to go). $U$ therefore enters its own reject. Why? $U$ must adopt the same convention $M$'s definition uses; "no rule" is a defined, halting outcome, not a bug in $U$.

Verify: $M(1)$ has no applicable move → halts, rejects. $U$ rejects. Match ✔.

Example F — Multi-step accept (two rules, fixed controller)

1. Iteration 1 — fetch. State $q_0$, reads 0 → rule $(q_1,0,R)$. Why? Look up the first instruction.
2. Iteration 1 — execute. Keep 0, move R, Tape 3 $=q_1$. Not a halting state → loop again. Why? $q_1$ is neither accept nor reject.
3. Iteration 2 — fetch. State $q_1$, reads 1 → rule $(q_{acc},1,R)$. Why? Look up the next instruction from the new state.
4. Iteration 2 — execute + halt. Keep 1, move R, Tape 3 $=q_{acc}$ → accept. Why? Now we hit an accepting state; $U$ halts to mirror it.

Verify: $M(01)$: $q_0\to q_1\to q_{acc}$, accepts after 2 steps. $U$ fired its loop 2 times and accepted. Match ✔. Notice: $U$'s own state set never grew — the growing trace lives on the tape, not in $U$'s control (this is Cell I's punchline, previewed).

Example G — Self-reference $U(⟨U⟩,\dots )$ (code = data)

1. Type-check. $⟨U⟩$ is a finite string over the same alphabet that $U$ reads. Why? A program's encoding is just a string; $U$ eats strings. So $⟨U⟩$ is a perfectly valid input.
2. Outer $U$ runs. It reads $⟨U⟩$ off Tape 1 and simulates an inner copy of $U$. Why? Nothing forbids simulating a machine that happens to equal the simulator.
3. Inner $U$ runs $M$ on $w$. The inner copy reads $⟨M,w⟩$ and simulates $M$. Why? That is inner-$U$'s whole job.
4. Outcome equals $M(w)$. Peeling two layers, the net result is $U(⟨M⟩,w)=M(w)$. Why? Each simulation layer is faithful, so composing them changes nothing but speed.

Verify (with a concrete inner machine): take $M$ = bit-flipper from Example A and $w=0$. Then $U(⟨U⟩,⟨M,0⟩)$ = inner-$U$ on $⟨M,0⟩$ = $M(0)$ = accept, tape 1. Same as Example A ✔. This "programs are data" fact is the hinge of Diagonalization, the Halting Problem, and the Stored-Program Computer idea.

Example H — Word problem (the real-world interpreter)

1. Identify $U$. The fixed CPU + operating system that never changes between apps. Why? $U$ is the one finite controller that stays constant — like your silicon.
2. Identify $⟨M⟩$. The program you launch (browser.exe, game.bin). Swapping apps = swapping $⟨M⟩$ on Tape 1. Why? Different $⟨M⟩$ = different behaviour, same $U$. That is von Neumann Architecture: program lives in memory as data.
3. Identify $w$. The data you feed the app: the URL, the save file, the source .c. Why? $w$ is the input string on the simulated tape.
4. Read off the contract. "CPU running program on data" = $U(⟨M⟩,w)=M(w)$.

Verify (dimensional/analogy check): count the pieces. Direct: {program $M$, data $w$} → output. UTM: {$U$, $⟨M⟩$, $w$} → output. The extra piece $U$ is the reusable interpreter, and it maps 1-to-1 onto "the hardware you didn't have to rebuild." Consistent ✔. This is precisely the Church-Turing Thesis made physical.

Example I — Exam twist: how many states does $U$ need for a giant $M$?

1. Locate where $M$'s size lives. All $10^9$ states appear inside $⟨M⟩$ on Tape 1 — as data. Why? Encoding turns "$M$'s complexity" into string length, not into $U$'s wiring.
2. Recall $U$'s loop. $U$ only ever does: read, scan-for-rule, extract, write/move, halt-check. That is a fixed number of states, chosen once when $U$ was designed. Why? The loop's shape does not depend on which $M$ we picked.
3. Answer. $U$ needs a constant number of states — independent of $M$. Not $10^9$, not even $\log (10^9)$: it is $O(1)$. Why? "Fixed CPU, variable program" — the whole point of universality.

Verify: The parent's [!formula] states "$U$'s state count is independent of $M$." Our answer $O(1)$ is consistent ✔. Contrast with a multi-tape subtlety — see Multi-tape vs Single-tape TM: converting $U$ to single-tape keeps the state count finite too (only the tape/steps blow up, not the controller).

Coverage check