停機問題的對角線證明（diagonalization proof）

這是「停機問題無法解決」的著名證明，靠著一個鋒利到幾乎像作弊的把戲運作——正是驅動說謊者悖論（「這句話是假的」）的同一種自我指涉。計畫是反證法：先假設存在一個完美的停機判定器，然後造出一台搗蛋的機器，它去問判定器「關於它自己」的問題，再故意做出與判定器預測相反的行為。這台機器的行為無法符合任何預測，所以那個完美的判定器根本不可能存在。

以下用白話走一遍步驟。假設存在一台機器 H，給定一台機器 M 的程式碼與一個輸入 w，它總會停下並輸出：若 M 在 w 上停機就輸出「停機」，若 M 在 w 上無窮迴圈就輸出「迴圈」。現在造一台新機器 D，它接收一個輸入：某台機器 M 的程式碼。D 在配對 (M, M) 上執行 H——把一台機器的程式碼當成自己的輸入餵給它——然後做出相反的事：若 H 說 M 在 M 上停機，則 D 永遠迴圈；若 H 說 M 在 M 上迴圈，則 D 停機。最後，在 D 自己的程式碼上執行 D：問 D 在輸入 D 上會怎樣。若 H 預測 D 在 D 上停機，則依建構 D 在 D 上迴圈——矛盾。若 H 預測 D 在 D 上迴圈，則依建構 D 在 D 上停機——矛盾。無論哪種，預測都是錯的。

既然我們唯一的假設是「H 存在且永遠正確」，那這個假設就必為假：這樣的 H 不存在，停機問題是不可判定的。「對角線」一詞來自想像一張巨大的表，列是機器、行是輸入，每格記錄停機或迴圈；D 被精心設計成在第 n 個輸入上與第 n 台機器不同，也就是沿對角線與每一台機器都唱反調，所以 D 不可能是表中任何一台機器——然而它明明就是一台機器。這個矛盾正是整個重點。