the.com/diagonalization
the proof that builds a monster no list can contain, then points and says: see, you missed one.
means a proof technique that constructs a new object by systematically differing from every item in an assumed complete list, showing the list was never complete.
from georg cantor unveiled it in 1891 to prove the real numbers cannot be counted like the integers; he arranged decimal expansions in a grid and built a number that disagrees with the nth digit of the nth entry, guaranteeing it matches nothing on the list.
turing borrowed itused it to prove the halting problem undecidable in 1936
godel tooencoded self-reference to build his incompleteness theorems
named for a gridthe trick literally walks down a diagonal of entries
predates computerspure set theory, decades before turing machines existed
for instance
cantor's uncountability proof — 1891 paper showing reals outnumber naturals
turing's halting problem — 1936 proof no algorithm decides all program halts
russell's paradox — 1901 set-of-all-sets-that-don't-contain-themselves construction