Foundations — Halting problem — undecidability proof by diagonalization

Before you can follow the diagonalization proof in the parent note, every single piece of notation it throws at you needs to exist in your head as a picture, not just a symbol. This page builds them one at a time, in the order the proof uses them. Nothing here assumes you have seen the proof.

0. The mental model: a machine that reads a tape

Everything in this topic is about programs and whether they stop. To talk about that precisely we need a picture of what a program is.

The formal version of "program" in this subject is a Turing machine — a tiny device with a read/write head crawling along an infinite tape of cells. You do not need the full machinery here; you only need the picture below.

Look at the figure. The head (burnt-orange triangle) sits over one cell of the tape. Each tick it reads the symbol under it, writes something, and slides left or right. Halt = the head stops moving and the machine goes into a final state (the teal square). Loop = the head keeps stepping and never reaches that square.

Why we need this: the entire topic is the single yes/no question "does the head ever stop?" You cannot ask that question without first having the tape-and-head picture.

1. Halts vs. loops — the two outcomes

Look at the figure. On the left (teal) the step-count path ends at a solid dot — that program halts. On the right (plum) the path just keeps climbing off the page with an arrow — that program loops. There is no third option: at any moment a program is either still running or has stopped. This "exactly two outcomes" fact is what makes the later yes/no question well-posed.

Why we need this: the whole problem is deciding which of these two pictures a given program produces — without actually running it forever.

2. $P$, $w$, and running "$P$ on $w$"

Think of $P$ as a recipe and $w$ as the groceries. "$P$ on $w$" is cooking that recipe with those groceries — and the only thing we care about is whether the cooking ever finishes.

Why we need this: the parent note constantly writes phrases like "$P$ halts on $w$". Those two letters are just a compact way of saying "some program, some input". They carry no hidden meaning — they are placeholders you fill in.

3. The angle brackets $⟨\cdot ⟩$ — encoding as a string

Here is the pivotal idea of the whole subject.

Look at the figure. The recipe card (the program $P$) is photocopied into a barcode strip $⟨P⟩$ — same information, now in "input" form. The plum arrow shows that strip being dropped back into the machine's input slot: the program eating a description of itself.

Why we need this: without $⟨P⟩$ you could not write $H(P,P)$ or D(D) — the self-feeding that drives the contradiction.

4. The set-builder $\{x\mid \text{condition}\}$ and the word "language"

So the parent's $HALT=\{⟨P,w⟩\mid P\text{ halts on }w\}$ reads out loud as: "$HALT$ is the collection of all encoded pairs $⟨P,w⟩$ such that $P$ halts on $w$."

The symbol $\in$ means "is a member of". $⟨P,w⟩\in HALT$ ⟺ "$P$ halts on $w$".

Why we need this: turning a question ("does it halt?") into membership in a set ("is this string in $HALT$?") is what lets us apply the crisp machinery of decidable vs recognizable languages.

5. Decidable vs. recognizable

Look at the figure. Both machines answer YES cases fine (green paths reach a dot). The difference is the NO case: the decider (teal) still reaches a solid NO dot; the recognizer (plum) trails off with a "…forever" arrow — it may never answer NO. The parent's Example 1 ("just simulate and watch") builds exactly a recognizer: it confirms halting but can never confirm looping. That is why $HALT$ is recognizable but the proof shows it is not decidable.

Why we need this: the entire theorem is "$HALT$ is not decidable". You cannot understand that sentence without the decider's non-negotiable always-halts rule.

6. Proof by contradiction

Picture a tightrope: you assume the decider H stands on one end, walk the logic across, and the rope snaps in the middle. The rope was fine; the assumed weight is what wasn't allowed.

Why we need this: the proof never builds H. It supposes H exists and detonates it. If you expect a constructive "here's how to solve halting", you'll be confused — the method is destruction, not construction.

7. The "does-the-opposite" flip and diagonalization

The last ingredient is the trick behind the troublemaker program D.

This is borrowed straight from Cantor's Diagonal Argument, which uses the same diagonal flip to show you can never list all infinite sequences. The parent note's picture is the halting-flavoured copy of Cantor's grid.

Why we need this: "diagonalization" is in the very title of the topic. It is not a fancy word for contradiction — it is the specific act of flipping the diagonal to manufacture an object that escapes the list.

How these feed the topic

Read it top-down: program-is-text enables encoding, which enables self-feeding; the tape picture gives halts vs loops, which packs into the language $HALT$; a decider refines into the decidable/recognizable split; and contradiction plus the diagonal flip (from Cantor) combine to prove undecidability. Downstream this same toolkit powers Reductions and Mapping Reducibility and Rice's Theorem, and rests on the Church–Turing Thesis that "program" and "Turing machine" capture all mechanical computation.

Equipment checklist

Cover the right side and test yourself. If any answer is fuzzy, re-read that section before opening the proof.