Cantor 對角線論證（Cantor diagonalization）

對角線論證是一個巧妙的把戲，用來建造一樣保證不在任何清單上的東西——做法是刻意在不同的位置與清單上的每一項唱反調。想像有人遞給你一份無限的目錄，聲稱列出了每一個由是／否答案組成的無限序列。你沿著對角線往下看來建造一個新序列：取第一項第一個答案的相反、第二項第二個答案的相反，依此類推。你的新序列在第 k 個位置與第 k 項不同，所以它不可能等於清單上的任何一項。原來那份清單並不完整。

Georg Cantor 正是用這個方法證明某些無限比其他無限更大。假設你能把所有無限二元序列列成第 1 列、第 2 列、第 3 列等等。構造一個新序列，使它的第 k 位是第 k 列第 k 位的反轉。這個新序列在位置 1 與第 1 列不同、在位置 2 與第 2 列不同、一般而言在位置 k 與第 k 列不同——所以它與任何一列都不相符。然而它是一個完全合法的無限二元序列。那份被假設為完整的清單不可能存在；這類序列的集合是不可數的。同樣的機制顯示任何集合的冪集都嚴格大於該集合本身。

這是可計算性中最深刻結果背後的結構骨架。完全相同的對角線一步，套用到一份「所有程式連同其行為」的假想清單上，便構造出一種清單上沒有任何程式能擁有的行為——這正是證明停機問題不可判定、以及不可辨識語言存在的方法。一點重要的誠實聲明：本條目涵蓋對角線技巧本身；運用它的那些具體不可判定性證明（停機問題、自我指涉論證）屬於不可判定性的內容。這裡的把戲是引擎；那些則是它驅動的車輛。