Visual walkthrough — Halting problem — undecidability proof by diagonalization

This page is the visual companion to the parent proof. Prerequisite ideas — Turing Machines, Decidable vs Recognizable Languages, Cantor's Diagonal Argument — are re-explained in pictures as they arise, so you can read straight through.

---

Step 1 — A program is just a string

WHAT. Before any logic, one plain fact: the source code of a program is a finite sequence of characters. That means a program can be stored, copied, and — crucially — handed to another program as ordinary input data.

WHY. The whole proof rests on feeding a program its own code. If code weren't just data, "run $P$ on $P$" would be nonsense. So we must earn this idea first. (This is the same insight that makes the Universal Turing Machine possible — one machine reading another machine's description.)

PICTURE. On the left, a little program P drawn as a scroll of text. An arrow carries that same scroll into an input slot on the right. The program and the data are the identical object — only the role differs.

Every one of these symbols is now defined. We will not use a new one before naming it.

---

Step 2 — Suppose the perfect predictor $H$ exists

WHAT. Assume — for the sake of argument — that somebody hands us a total program called $H$. "Total" means: $H$ always halts and always answers correctly. Its job:

$H(\underset{\text{code to inspect}}{\underbrace{P}},\underset{\text{its input}}{\underbrace{w}})=\{\begin{array}{ll}\text{HALT}& \text{if }P\text{ halts on }w\\ \text{LOOP}& \text{if }P\text{ loops on }w\end{array}$

Reading the equation term by term: $H$ takes two arguments — the first is the program we are curious about, the second is the input that program would receive. It returns one of exactly two labels, $\text{HALT}$ or $\text{LOOP}$.

WHY. We want to prove $H$ cannot exist. The cleanest weapon against "X exists" is proof by contradiction: pretend it does, then derive an absurdity. The absurdity we manufacture will force the pretence to collapse.

PICTURE. A black box labelled $H$ with two input wires (P and w) and one output wire that lights up either green $\text{HALT}$ or red $\text{LOOP}$. A tick mark reminds us: it always answers — never gets stuck.

---

Step 3 — The table of all behaviours (the grid we will attack)

WHAT. List every program down the rows: $P_1,P_2,P_3,\dots$ (there are infinitely many, but they can be numbered — that is what "listable" means). Across the columns, list the same programs $P_1,P_2,\dots$ used now as inputs. Cell $(i,j)$ records the answer to "does $P_i$ halt on $P_j$?" — an H or an L.

WHY. $H$, if it exists, fills in this entire grid correctly. To break $H$ we only need to break one column against one row — the diagonal. Laying out the grid makes the target visible. (This is exactly the stage on which Cantor's Diagonal Argument plays out: a grid, and a diagonal you deliberately disagree with.)

PICTURE. A grid. The diagonal cells $(i,i)$ — "does $P_i$ halt on itself?" — are highlighted in orange. Those diagonal answers are the only ones we will touch.

---

Step 4 — Build the troublemaker $D$

WHAT. Using $H$ as a helper, define a new program $D$ that takes one program $P$ as input:

D(P):
    if H(P, P) == HALT:   # ask: does P halt on its own code?
        loop forever      # then D deliberately loops
    else:                 # H said P loops on itself
        halt              # then D deliberately halts

Term by term: $D$ calls $H(P,P)$ — the diagonal question for $P$. Then $D$ does the opposite of that prediction. Predicted HALT $\Rightarrow$ $D$ loops. Predicted LOOP $\Rightarrow$ $D$ halts.

WHY. $D$ is a machine for disagreeing with the diagonal. In grid language: if the diagonal cell $(i,i)$ says H, $D$ produces L there; if it says L, $D$ produces H. $D$'s row is the flipped diagonal.

PICTURE. The orange diagonal from Step 3, and beneath it $D$'s behaviour row with every cell flipped (H↔L). Arrows show each flip. $D$ agrees with no program at its own column.

---

Step 5 — Feed $D$ its own code: run $D(D)$

WHAT. Since $D$ is a program, and programs are strings (Step 1), we may run $D$ on the input $D$. We now trace $D(D)$ and hit the trap.

WHY. $D$ was designed to disagree with the diagonal everywhere, including at its own cell. So we point $D$ at the one cell it cannot escape: itself. What does the table say cell $(D,D)$ should be? Whatever $H(D,D)$ predicts. And $D$ was built to contradict exactly that.

PICTURE. A flowchart of the single run $D(D)$: it calls $H(D,D)$; the two output branches (green HALT, red LOOP) each loop back to a contradiction stamp.

Let us walk both possible answers of $H(D,D)$ — there are only two, and we must cover each.

---

Step 6 — Case A: $H$ says HALT

WHAT. Suppose $H(D,D)=\text{HALT}$. By $H$'s definition, this is $H$ claiming "$D$ halts on $D$". But now trace $D$'s own code with this answer: the if H(P,P)==HALT branch is taken, so $D$ executes loop forever. Therefore $D(D)$ loops — it does not halt.

$\underset{H\text{ predicts: }D(D)\text{ halts}}{\underbrace{H(D,D)=\text{HALT}}}⟹\underset{\text{what }D\text{ actually does}}{\underbrace{D(D)\text{ loops}}}$

WHY. We are testing whether $H$'s prediction can be self-consistent. It cannot: $H$ predicted "halts", the machine actually loops. $H$ is wrong.

PICTURE. The green HALT wire out of $H$; following $D$'s code it lands on loop forever; a red ✗ marks the clash between the prediction (halts) and the reality (loops).

---

Step 7 — Case B: $H$ says LOOP

WHAT. Suppose instead $H(D,D)=\text{LOOP}$, i.e. $H$ claims "$D$ loops on $D$". Trace $D$: the if condition is false, so the else branch runs — $D$ executes halt. Therefore $D(D)$ halts.

$\underset{H\text{ predicts: }D(D)\text{ loops}}{\underbrace{H(D,D)=\text{LOOP}}}⟹\underset{\text{what }D\text{ actually does}}{\underbrace{D(D)\text{ halts}}}$

WHY. Again the prediction and the reality are opposite. $H$ predicted "loops", the machine actually halts. $H$ is wrong here too.

PICTURE. The red LOOP wire out of $H$; following $D$'s code it lands on halt; a red ✗ marks the clash (predicted loops, actually halts).

---

Step 8 — Collapse the two cases into one impossible sentence

WHAT. Chain Case A and Case B together. Case B says $D(D)$ halts exactly when $H(D,D)=\text{LOOP}$; and Case A says $H(D,D)=\text{LOOP}$ is forced precisely when $D(D)$ loops. Putting the whole loop of implications on one line:

$D(D)\text{halts}⟺H(D,D)=\text{LOOP}⟺D(D)\text{loops}$

Reading each link: the left $⟺$ is $D$'s code (halting means the else branch ran, which needs $H$ to have said LOOP). The right $⟺$ is the meaning of $\text{LOOP}$ (that label means $D(D)$ runs forever). Stripping the middle:

$D(D)\text{halts}⟺D(D)\text{loops}$

That is a statement equivalent to its own negation — like "this sentence is false". No truth value fits.

WHY. A thing cannot both halt and not-halt. The only ingredient we ever assumed was $H$. Everything after ($D$, running $D(D)$) was legal construction. So the assumption is the culprit.

PICTURE. A circular chain of three boxes — "$D(D)$ halts" → "$H$ said LOOP" → "$D(D)$ loops" → back to "$D(D)$ halts" — forming a closed contradiction ring, with a red lightning bolt where halts meets loops.

---

Step 9 — The degenerate case: "just simulate and watch" is not a decider

WHAT. A natural objection: "why bother with $H$ — just run $P$ on $w$ and see." Call this simulator $S$. If $P$ halts, $S$ eventually notices and reports $\text{HALT}$. But if $P$ loops forever, $S$ also runs forever and never reports anything.

WHY. This shows the boundary case matters. A decider must always halt with an answer. $S$ answers on the halting inputs but hangs on the looping ones — so $S$ is a recognizer (semi-decider), not a decider. $HALT$ is therefore recognizable but undecidable — a distinction lifted directly from Decidable vs Recognizable Languages.

PICTURE. Two timelines. Top: $P$ halts → simulator stops → outputs HALT ✓. Bottom: $P$ loops → simulator's clock spins forever → the LOOP answer never arrives (dashed, greyed out).

---

The one-picture summary

WHAT. One figure that compresses all nine steps: code-is-data → assume $H$ → the grid → flip the diagonal into $D$ → run $D(D)$ → both wires die → the impossible sentence.

PICTURE. A left-to-right pipeline of the whole argument, ending in the red contradiction ring; the flipped-diagonal grid sits above as the visual heart.

Recall Feynman retelling of the whole walkthrough

Start with one small truth: a program is just text, so I can hand a program a copy of itself. Now pretend a magic box $H$ exists that always tells me, correctly, whether any program eventually stops. I imagine a giant table: rows are programs, columns are the same programs used as inputs, and each cell says "stops" or "runs forever". I only care about the diagonal — each program run on its own code. I build a sneaky program $D$: it asks the box about a program running on itself, then does the opposite of the answer. Finally I show $D$ its own code. If the box says "$D$ stops", $D$ runs forever; if the box says "$D$ runs forever", $D$ stops. Either way the box is wrong — so "$D$ stops" and "$D$ runs forever" become the same thing, which is impossible. The only thing I ever guessed was the magic box, so the box can't exist. And if you object "just run it and watch" — that only works when the program does stop; if it loops, your watcher loops too and never says "runs forever", so watching is a recognizer, never a decider.

---

Recall

In cell $(i,i)$ of the grid, what question is being asked? ::: Does program $P_i$ halt when given its own code as input? What does $D$ do relative to $H$'s prediction about $P$ on itself? ::: The exact opposite (predicted HALT → $D$ loops; predicted LOOP → $D$ halts). Which single assumption does the contradiction destroy? ::: That the total decider $H$ exists. Why is "simulate and watch" only a recognizer? ::: If the program loops forever the simulation also never halts, so it can never output LOOP. State the collapsed impossible sentence. ::: $D(D)$ halts $⟺$ $D(D)$ loops.