Universal Turing machine: Visual walkthrough — Coding deep dive

Step 1 — What a single machine looks like

WHAT. Before we can copy a machine, we must see one. A Turing machine is just four physical things:

a tape: an endless strip of boxes, each holding one symbol (think of squared paper);
a head: a single finger pointing at exactly one box, which can read and overwrite it;
a state: a little label in the machine's "mind", like a mood — one word telling it what it is in the middle of doing;
a rule-book: a fixed list saying "if you are in this mood and your finger sees this symbol, then do that."

WHY these four and nothing more. Everything a computer does reduces to look at one thing, then change one thing, then change your mind about what to do next. Strip away screens and keyboards and this skeleton is what remains — so this is the honest atom of computation.

PICTURE. The blue strip is the tape, the pink triangle is the head, the yellow bubble is the current state $q_{0}$ .

Step 2 — Why one machine is not enough

WHAT. The machine in Step 1 has its rule-book baked into its body. It can do one job forever and nothing else.

WHY this hurts. If I want to also check palindromes, I must build a different body with a different baked-in rule-book. That is a world with one gadget per task — a drawer full of single-purpose calculators.

PICTURE. Three separate machines, three separate frozen rule-books. Notice: the rule-book lives inside each box, unreachable.

Step 3 — Turn a machine into a string (the encoding)

WHAT. We write $M$ 's entire rule-book as one finite line of symbols, called == $⟨ M ⟩$ == (read aloud: "the encoding of $M$ "). The angle brackets $⟨ ⟩$ are just packaging tape meaning "the written-down description of the thing inside."

WHY it is even possible. The states are finite and the symbols are finite, so the rule-book has finitely many rows. A finite table can always be flattened into a finite string — like writing a spreadsheet out as one long sentence. (See Church-Turing Thesis for why "reasonable encoding" is all we ever need.)

HOW, concretely. Give everything a tally number and glue with separators:

state $q_{i} \to$ the tally $i + 1 zeros 0 \dots 0$ (so $q_{0} = 0$ , $q_{1} = 00$ , …);
each symbol $\to$ its own tally;
direction $L \to 0$ , $R \to 00$ ;
a single 1 separates fields inside one rule; a 11 separates whole rules.

$⟨ M ⟩ = start marker 111 rule_{1} gap 11 rule_{2} \dots end marker 111$

PICTURE. The frozen rule-book of Step 2 melts into a ribbon of $0$ s and $1$ s.

Step 4 — Give $U$ a place to keep the program, the data, and the mood

WHAT. We give our universal body $U$ three tapes (a multi-tape machine, which is exactly as powerful as a one-tape machine, so no cheating):

Tape	Holds	Chalk colour below
Tape 1	$⟨ M ⟩$ — the program to look rules up in	yellow
Tape 2	$M$ 's simulated tape — the data	blue
Tape 3	$M$ 's current state $q$ — the mood	pink

WHY three. Separation of concerns: the rule-book you consult must not get overwritten by the data you compute on, and you need a scratch spot to remember which mood you are pretending to be in. Three roles → three tapes.

PICTURE. The three stacked tapes with their heads.

Step 5 — The fetch: find the matching rule

WHAT. One turn of the simulation begins. $U$ reads the symbol $a$ under Tape 2's head and the mood $q$ on Tape 3, then slides along Tape 1 until it finds the rule whose left side is exactly $(q, a)$ .

WHY. This is the act of computing $δ (q, a)$ — except instead of the rule being wired into a body, $U$ hunts for it in written form. In a real CPU this is the fetch phase.

PICTURE. Tape-3 mood $q_{0}$ and Tape-2 symbol 1 glow; $U$ 's Tape-1 head scans left-to-right and locks onto the matching block.

Step 6 — The execute: apply the rule

WHAT. Having read $(q^{'}, b, D)$ off Tape 1, $U$ now:

writes $b$ onto Tape 2 (under its head),
moves the Tape-2 head one step $D$ ,
erases Tape 3 and writes the new mood $q^{'}$ .

WHY. These three edits are the transition $δ (q, a) = (q^{'}, b, D)$ carried out by hand. In a real CPU this is the execute phase. Notice $U$ changed only Tape 2 and Tape 3 — the program (Tape 1) is untouched, exactly as source code is not modified by running it.

PICTURE. Blue tape cell flips 1→0, blue head shifts right, pink mood updates $q_{0}$ → $q_{a cc}$ .

Recall Fetch vs execute in one breath

Fetch = find the row of the table. Execute = do what the row says. Loop. The pair of these, repeated, is the whole of $U$ .

Step 7 — Halting: when (and only when) $M$ would halt

WHAT. After each execute, $U$ checks the new mood $q^{'}$ :

if $q^{'} = q_{a cc}$ → $U$ accepts and stops;
if $q^{'} = q_{r e j}$ → $U$ rejects and stops;
otherwise → go back to Step 5.

$U (⟨ M ⟩, w) ↓ ⟺ M (w) ↓ (↓= halts)$

WHY this exact mirror, no more. $U$ must be honest. It stops precisely when $M$ would stop and gives the same verdict — never a "wiser" answer.

Degenerate case — $M$ loops. Suppose $M$ 's only rule is $δ (q_{0}, a) = (q_{0}, a, R)$ : same mood, keep walking right, forever. Then every turn $U$ fetches the same row, executes it, and never meets $q_{a cc}$ or $q_{r e j}$ . So $U$ loops too — and this is correct, not a bug. A $U$ that could detect all loops would decide the Halting Problem, which diagonalization proves impossible. Faithful, not omniscient.

PICTURE. Two branches: a halting run that reaches the pink $q_{a cc}$ dot, and a looping run whose mood arrow curls back on itself endlessly.

Step 8 — The self-eating case: $U$ runs $U$

WHAT. $U$ is itself a Turing machine, so $⟨ U ⟩$ is a perfectly valid string. We may therefore feed $U$ its own description: $U (⟨ U ⟩, ⟨ M, w ⟩) .$

WHY it works. Program and data live in the same alphabet of $0$ s and $1$ s. A program is just a string, and strings are exactly what $U$ eats — so a program is a legal input.

WHY it matters. This "a machine can read machines, including itself" is the seed that grows into the diagonal argument and the unsolvability of the Halting Problem, and it explains why recognisable-but-not-decidable languages exist.

PICTURE. A picture-in-picture: an outer $U$ whose Tape 1 holds $⟨ U ⟩$ , inside which a smaller $U$ runs, mirrors within mirrors.

The one-picture summary

Everything above collapses into a single machine diagram: three tapes feeding a fixed finite controller that loops fetch → execute → halt-check, with the program safely on Tape 1.

Recall Feynman retelling — say it to a 12-year-old

Imagine a robot with one tiny brain that never changes. On a yellow ribbon you write, in tallies, the rules of some other robot. On a blue ribbon you write that other robot's homework. On a pink sticky note you keep track of what mood the other robot is currently in. Now the tiny-brained robot just does two things over and over: it looks up the yellow ribbon to find the rule that matches the blue symbol and the pink mood (fetch), then it does what the rule says — flips a blue symbol, steps sideways, updates the pink note (execute). If the pink note ever says "accept" or "reject", it stops with that answer. If the other robot would run forever, our robot runs forever too — honestly, because knowing in advance would mean solving the impossible Halting Problem. That one never-changing robot, reading swappable ribbons, is the Universal Turing Machine — and it's why the same laptop runs a game, a browser, and a compiler.

Question: In the UTM, what physically holds the "unbounded complexity" — the controller or the tape?

The tape (the program

⟨ M ⟩

on Tape 1); the controller

U

has a fixed, finite state set.

Question: Why must

U

loop when

M

loops?

Because detecting looping in general is the Halting Problem, which is undecidable; faithful simulation forbids a "wiser" answer.

Question: Which two phases repeat inside

U

's main loop?

Fetch (find the matching rule on Tape 1) and Execute (apply it to Tapes 2 and 3).