the diagonalization proof of the halting problem
This is the famous proof that the halting problem cannot be solved, and it works by a trick so sharp it almost feels like cheating, the same self-reference that powers the liar paradox ('this sentence is false'). The plan is proof by contradiction: assume a perfect halt-decider exists, then build a single mischievous machine that asks the decider about ITSELF and then deliberately does the opposite of whatever the decider predicts. The machine's behaviour cannot match any prediction, so the perfect decider could not have existed.
Here are the steps in plain language. Suppose a machine H exists that, given the code of a machine M and an input w, always halts and outputs 'halts' if M halts on w, and 'loops' if M loops on w. Now construct a new machine D that takes one input, the code of a machine M. D runs H on the pair (M, M) — feeding a machine its own code as input — and then does the OPPOSITE: if H says M halts on M, then D loops forever; if H says M loops on M, then D halts. Finally, run D on its own code: ask what D does on input D. If H predicts D halts on D, then by construction D loops on D — contradiction. If H predicts D loops on D, then by construction D halts on D — contradiction. Either way the prediction is wrong.
Since the only assumption we made was 'H exists and is always correct', that assumption must be false: no such H exists, and the halting problem is undecidable. The word 'diagonalization' comes from picturing a giant table whose rows are machines and whose columns are inputs, with each cell recording halt or loop; D is engineered to differ from machine number n on input number n, that is, to disagree with every machine along the diagonal, so D cannot be any machine in the table — yet it plainly is a machine. The contradiction is the whole point.
Tabletop version: row M, column M holds 'what M does on its own code'. D is defined to disagree with that diagonal cell — halt where it loops, loop where it halts. Asking 'what is D in its own row and column?' has no consistent answer, exactly the contradiction.
Build a machine that does the opposite of every diagonal prediction; it cannot exist if the decider does, so the decider does not.
The contradiction kills the ASSUMED decider, not computation itself. Nothing here is paradoxical once you see it as a clean reductio: 'if a decider existed, an impossible machine would follow'.