我們走到哪了，以及我們即將重用的那一招
這一階的第一篇做了人頭普查：語言有不可數那麼多，而圖靈機只有可數那麼多，所以大多數語言根本沒有機器——不可判定、甚至不可辨識的語言必定存在。那是一個存在性證明：它告訴你怪物就在外頭，卻沒讓你看見任何一隻。第二篇指向了一隻具體又有用的怪物——停機問題：給定一支程式與一個輸入，它會停機還是永遠繞圈？這一篇要做計數論證做不到的事：拿一個具體的語言，用明確的建構證明它的判定器不可能存在。
扛起全部工作的那一招就是 對角線論證（diagonalization），而你早已見過它。回到數學那一階，康托爾用對角線論證證明實數不可數：把任何一份號稱列盡實數的清單擺出來，再造一個新實數，讓它在第一位數字上與清單第一個數不同、在第二位上與第二個數不同，如此沿著對角線往下走——造出的這個數不可能在清單裡的任何位置，矛盾。我們即將施展一模一樣的招式，只是這次「清單」是一張機器對輸入的表格，而「翻一位數字」這一步變成了「機器做什麼，我就反著做」。同樣的骨架，換上計算的血肉。
那張表，以及那條無處安身的對角線
我們倚靠的核心事實是這樣：一支程式不過是文字，而文字不過是字串，所以一台圖靈機 M 可以寫成一個有限字串，記作編碼 `<M>`。這意味著我們可以把一台機器自己的描述當作輸入餵給機器——一台機器讀得了一台機器。現在想像一張巨大的表。沿著左緣，把每一台圖靈機 M1、M2、M3、…… 都列出來（可數那麼多，所以塞得進一張清單）。沿著頂端，把每一個輸入字串都列出來——而既然機器描述本身就是字串，就用描述 `<M1>、<M2>、<M3>、……` 當作欄標題。在第 Mi 列、第 `<Mj>` 欄的格子裡，寫下機器 Mi 是否接受字串 `<Mj>`：接受寫 A，其他任何情形（拒絕或繞圈）寫成「非接受」。
<M1> <M2> <M3> <M4> ...
M1 [ A ] . A .
M2 A [ . ] . A
M3 . A [ A ] A
M4 A A . [ . ]
...
Read the boxed DIAGONAL: M1 on <M1>=A, M2 on <M2>=., M3 on <M3>=A, M4 on <M4>=.
Now build D so it does the OPPOSITE down the diagonal:
D on <M1> -> not A (M1 said A)
D on <M2> -> A (M2 said .)
D on <M3> -> not A (M3 said A)
D on <M4> -> A (M4 said .)
D's behaviour on <Mi> differs from Mi's at every i, so D is NO ROW in the table.
But every machine is a row. So D cannot be a machine. Contradiction.盯著那條對角線——機器 Mi 遇上它自己描述 `<Mi>` 的那些格子。現在定義一台新機器 D，它的行為按設計就是那條對角線的翻轉：D 在輸入 `<Mi>` 上接受，恰恰當 Mi 不接受 `<Mi>` 時；D 不接受，恰恰當 Mi 接受時。於是 D 在第 1 欄與 M1 唱反調、在第 2 欄與 M2 唱反調、在第 3 欄與 M3 唱反調——與每一台機器都在某處不合。所以 D 那一列的行為，與表中任何一列都對不上。但這張表本應列盡每一台機器。唯一的逃路就是 D 根本不在清單上——D 不可能是一台圖靈機。於是，為了造出 D 而被我們偷偷假設的那個能力，必定是不可能的。下一節要釘死那個被禁止的能力究竟是什麼。
那台問自己、然後反著做的機器
讓我們把 D 弄具體，看看它需要什麼。那個有名的標靶是 通用接受語言，記作 A_TM（「TM」指圖靈機）：A_TM = { `<M,w>` : M 是一台圖靈機，且 M 接受字串 w }。一台辨識 A_TM 的機器，不過就是一台通用圖靈機——餵給它一支程式與一個輸入，它就在那個輸入上模擬那支程式，程式接受它就接受。通用機器顯然存在；直譯器（interpreter）就是這玩意。困難的問題在於 A_TM 是否可判定——是否存在某台機器 H，對每一個 `<M,w>` 都能停機並正確說出是或否，包括在 M 本會於 w 上繞圈時乾淨地說一聲「否」。為了導出矛盾，先假設這樣一台判定器 H 存在。
把 H 當作一個副程式，造一台小巧、完全合法的機器 D，它接受單一一個機器描述 `<M>` 當輸入。D 跑 H 去問那個自我指涉的問題「M 接受它自己的描述 `<M>` 嗎？」接著 D 反著做 H 的答案：若 H 說 M 接受 `<M>`，那 D 就拒絕（停機、不接受）；若 H 說 M 不接受 `<M>`，那 D 就接受。因為 H 總會停機（這正是整個假設），D 也就總會停機——D 是一台貨真價實、定義完好的機器。到目前為止毫無弔詭。陷阱只在我們把 D 跑在一個非常特定的輸入上時才彈起。
- 把 D 自己的描述餵給它：在輸入 `<D>` 上跑 D。按 D 的定義，D 先問 H：「D 接受 `<D>` 嗎？」這就是那個自我指涉的動作——機器把問題指回它自己。
- 情形一——假設 H 回答「是，D 接受 `<D>`」。那麼按 D 的接線，D 反著做，於是拒絕 `<D>`。所以 D 不接受 `<D>`。但這與 H 的「是」相矛盾。不可能。
- 情形二——假設 H 回答「否，D 不接受 `<D>`」。那麼按 D 的接線，D 反著做，於是接受 `<D>`。所以 D 確實接受 `<D>`。但這與 H 的「否」相矛盾。同樣不可能。
- H 僅有的兩種可能答案都通向一個徹底的矛盾。我們假設進存在的那一樣東西——總會停機的判定器 H——就是元兇。因此 H 不可能存在：A_TM 是不可判定的。
順著矛盾往外走：一個連機器都辨識不了的語言
A_TM 不可判定，但請注意它仍然可辨識：通用機器辨識得了它（在 w 上模擬 M；它接受就接受；而若 M 在 w 上繞圈，模擬也跟著繞圈——這對辨識器是被允許的）。所以 A_TM 就住在前幾篇談的那道縫隙裡：可辨識卻不可判定。順理成章的下一問是：有沒有什麼東西躺得更外面——一個沒有任何圖靈機辨識得了的語言，連可靠地拿到一聲「是」都辦不到？答案是有，而我們手上已經有找到它的工具：A_TM 的補集。
回想可判定性那一階那幅乾淨的三環圖：一個語言可判定，恰好當它既可辨識又可餘辨識——也就是它與它的補集都可辨識時。把這句話倒著用。我們剛剛證明了 A_TM 可辨識卻不可判定。倘若它的補集——A_TM 的補集——也可辨識，那 A_TM 就既可辨識又可餘辨識，於是可判定——但它並不可判定。矛盾。所以 A_TM 的補集不可能可辨識：它是一個貨真價實的不可辨識語言。這正是計數論證許諾過、卻交不到你手上的那隻怪物：在這裡，有名有姓、釘得死死的。
Rice 定理：矛盾推廣到幾乎一切
A_TM 是一個不可判定的問題，但它感覺像個孤立的怪例。Rice 定理的震撼在於它根本不是怪例——不可判定才是常態，不是例外。仔細地陳述：圖靈機所辨識之語言的每一個非平凡性質，都不可判定。把這兩個被特意挑出的字眼拆開。性質是關於語言（機器接受的那組字串）的，不是關於機器的原始文字——像「這台機器辨識的是空語言嗎？」「它辨識的是正規語言嗎？」「它曾接受字串 hello 嗎？」這類問題。而非平凡的意思是：這性質對某些可辨識語言成立、對另一些不成立——它真的把機器分成了「是」一堆和「否」一堆。
為什麼語言對程式碼這個區分扛起這麼多分量？因為許多你能輕易檢查的事，是程式碼的性質、而非語言的性質，Rice 碰都不碰它們。「這支程式超過 100 行嗎？」「原始碼含有 print 這個字嗎？」「它恰好有 7 個狀態嗎？」——全都可判定，因為你只要讀文字就行。這些都不是機器所辨識之語言的性質；兩台原始碼天差地別的機器可以辨識完全相同的語言。Rice 只談語言、行為、它接受什麼——而關於那件事的任何非平凡事實，都不可判定。語意層面的問題才是無望的；語法層面的問題可以好端端的。
又為什麼性質非得是非平凡的？那兩個平凡性質正是仍然可判定的逃生口。「所辨識的語言是可辨識的語言嗎？」對每一台機器都成立——判定器永遠回答「是」就好，毫不費力。「所辨識的語言是不可辨識的語言嗎？」對每一台機器都不成立——永遠回答「否」。這兩個對輸入什麼也沒說，所以平凡地可判定。但只要一個性質真的把某個可辨識語言與另一個區分開來，Rice 定理就把門甩上：判定它，將透過一個回到 A_TM 的歸約，讓你能判定停機問題，而那我們剛剛證明過是不可能的。其機制就是同一套被對角線化的自我指涉，裹在一個歸約裡——這台引擎你會在下一篇把它鍛成一件通用的武器。