從一個不可判定的問題，到一整片汪洋
本階的第 2、3 篇交給你一個震撼的事實：停機問題是不可判定的——沒有任何演算法能拿一個任意的程式與輸入，總是正確地說出它停不停機——而那個通用接受語言 A_TM（「機器 M 接受字串 w 嗎？」）也是不可判定的，兩者都由那台「問自己、再做相反之事」的對角線機器所證明。這算解決了一個問題。你也許會盼望，身為程式設計師你在意的其餘問題還是安全的。Rice 定理用一句話粉碎了這份盼望：關於一個程式做了什麼，幾乎每一個有趣的是非問題都不可判定。不只是停機——空性、等價、正確性、「它會不會印出 42」，全都是。
在我們歡呼或恐慌之前，得謹慎地把定理說出來，因為有兩個小字眼承擔了幾乎全部的工作，而初學者常常漏掉其一、得出錯誤的結論。那兩個字眼是「非平凡」，以及最關鍵的——「語言的」。把它們弄錯，你要嘛會以為 Rice 定理顯然是假的（並不是），要嘛會以為它禁止了它其實樂於允許的事（並沒有）。所以本篇主要就是慢慢讀懂一句話。回想可判定性那一階：一台圖靈機 M 的語言，寫成 L(M)，不過就是 M 所接受之字串的集合。Rice 定理談的，是那些答案只取決於這個集合、而不取決於 M 怎麼寫的問題。
是語言的性質，不是程式碼的性質
這裡是那個關鍵的區分，也是整門學科裡最常被誤解的一點。Rice 定理談的是機器所識別之語言的性質，不是程式碼的每一個語法性質。一個性質 P 是針對圖靈機的一道是非測驗，並且在以下這個精確意義上是語意的：只要兩台機器識別相同的語言，P 就會給它們相同的答案。用符號寫：若 L(M) = L(N)，則 P(M) = P(N)。這道測驗只能「看見」被接受之字串的集合；它必須對機器的內部構造視而不見。
比較關於機器 M 的兩個問題。問題甲：「L(M) 含有空字串 epsilon 嗎？」這是語意的——它只取決於 M 接受哪些字串，所以任何兩台語言相同的機器都會給出相同的答案；Rice 定理適用，於是該問題不可判定。問題乙：「M 的原始碼恰好有 100 個狀態嗎？」這不是語意的——兩台機器可以識別完全相同的語言，卻一台有 100 個狀態、另一台有 99 個。Rice 定理對問題乙什麼都沒說，而乙確實完全可判定：數一數狀態就好。數狀態、檢查排版、問程式裡有沒有字母 Q——全都可判定、全都是語法的、全都在 Rice 的射程之外。這條定理講的是意義，不是文字。
非平凡：它必須把可識別語言一分為二
第二個承重的字眼是非平凡。一個性質是平凡的，當它對所有圖靈機給出相同的答案——要嘛每台機器都有它、要嘛全都沒有。「L(M) 是個可識別語言嗎？」是平凡的：依定義，任何圖靈機的語言就是可識別的，所以答案永遠是「是」。「M 的語言是否既含 epsilon 又不含 epsilon？」是另一個方向的平凡：不可能，所以永遠是「否」。平凡性質之所以可判定，是出於一個無聊的理由——判定器可以完全無視輸入，直接印出那個常數答案。一個性質是非平凡的，當某些機器有它、而某些機器沒有它；這個性質確實把可識別語言切成一個非空的「是」堆與一個非空的「否」堆。
現在我們終於能乾淨地把它說出來。Rice 定理：一台圖靈機所識別之語言的每一個非平凡語意性質，都是不可判定的。把它讀成：挑任何一道是非測驗，只要它（1）只取決於 L(M)、而且（2）不是恆為「是」或恆為「否」——那麼就沒有任何演算法能對所有機器判定這道測驗。「L(M) 是空的嗎？」、「L(M) 有限嗎？」、「L(M) 是正規的嗎？」、「L(M) 等於這台固定參照機器的語言嗎？」、「L(M) 是所有偶數長度字串的集合嗎？」——每一個都是語意的、每一個都是非平凡的，所以每一個都不可判定。這條定理不是一個一個地檢查它們；它一筆就把它們全部禁掉。
它為何為真：把停機問題藏進性質裡
證明是一個歸約——一個把某問題轉成另一問題的翻譯器——並重複利用你已經證過的 A_TM 不可判定性。點子是一個小小的巧計：給定任何非平凡語意性質 P，我們造一套「機器構造法」，偷偷把「M 接受 w 嗎？」這個問題夾帶進「我構造出的機器具有性質 P 嗎？」這個問題裡。若我們能回答後者，就能回答前者；但前者已知不可判定，所以後者也必然不可判定。整個把戲全靠一件事：能依需求造出一台機器，使它的語言恰好是兩個值之一，端看 M 是否接受 w。
把構造法擺好。因為 P 是非平凡的，至少存在一個具有性質 P 的語言，也至少存在一個不具有它的語言。空語言（那台什麼都不接受的機器）落在這兩邊之一；為了具體起見，就說空語言不具有 P（鏡像情況完全相同）。既然 P 非平凡，便存在某台機器 T，其語言 L(T) 確實具有 P。這兩個錨點——「空語言沒有 P、L(T) 有 P」——是整個論證的樞紐。
- 為了導出矛盾，假設存在某台判定器 D 能回答這個性質：當且僅當某台機器的語言具有 P 時，D(機器) = 是。我們要用 D 去判定 A_TM（「M 接受 w 嗎？」），而那是不可能的——那個矛盾正是目標。
- 給定任意的 M 與 w，造出一台新機器 M_w，它對自己的輸入 x 是這樣運作的：M_w 先在 w 上跑 M（暫且無視 x）；唯有當 M 接受 w 時，M_w 才接著在 x 上模擬錨點機器 T，並恰好在 T 接受時接受。這個構造純粹是改寫程式碼——容易，而且總會停機。
- 把 M_w 的語言讀出來。若 M 接受 w，則對每個 x 第一階段都通過、M_w 模仿 T，於是 L(M_w) = L(T)——它具有性質 P。若 M 不接受 w，第一階段就永遠迴圈或拒絕，於是 M_w 什麼都不接受：L(M_w) 是空語言——它不具有 P。
- 於是「M_w 具有性質 P」為真，恰好當「M 接受 w」為真。把 M_w 餵給那台假想的判定器 D：它的答案就把 A_TM 的答案交到我們手上。那便判定了 A_TM——矛盾。因此根本不存在這樣的 D，而 P 不可判定。（正因 P 是語意的，D 對 M_w 給出的答案，確實與任何其他語言相同之機器所得的相同，這正是此法奏效的原因。）
停下來體會剛才發生了什麼，因為它很美。我們從頭到尾沒看 P 究竟是哪個性質——空、有限、正規、等於某固定集合，隨便哪個。我們只用到 P 把空語言與某個別的語言分開這一點。那一個落腳處，就足以把停機問題像寄生蟲一樣栓到 P 身上。這是整階反覆出現的招式：要證明一個新問題不可判定，你不必從零重跑對角線論證——你把一個已知不可判定的問題歸約到它，造一個翻譯器，使得新問題的解法者就能解出那個古老而不可能的問題。
Rice 沒說什麼——以及它真正讓程式設計師付出什麼代價
現在來看誠實的細則，因為 Rice 定理涵蓋面雖廣，卻非全能。它沒說語法問題不可判定——數狀態、查風格、偵測字面字串「goto」有沒有出現，全都可判定。它沒說每個實例都很難——對一個特定、固定的程式，你很可能就能證明它做了什麼；該定理禁的是一台對所有程式都奏效的單一演算法。它沒說這個性質不可識別——這些性質許多仍是可識別的（你能確認一個「是」），它們只是無法可判定（你無法總是了結一個「否」）。而且它不適用於較弱的模型：DFA 之語言的性質，如空性與等價，是可判定的，因為 DFA 是個有限、可完全攤開描繪的物件，不是圖靈機。Rice 只在喬姆斯基層級的頂端咬人，那裡住著完整的計算能力。
但在它咬得到的地方，它咬得很狠，而這一部分應當改變你看待軟體的方式。不存在通用的停機檢查器：沒有工具能拿任何程式、總是正確地判定它是否終止。不存在通用的等價檢查器：「這兩個程式計算同一個函數嗎？」不可判定，所以沒有編譯器能保證驗證某項最佳化對所有輸入都保持了行為。不存在完美的找蟲工具：「這個程式會不會抵達這個被禁止的狀態？」不可判定，所以全自動、完備又健全的程式驗證在數學上就是搆不著。任何聲稱能做到這些事的工具，必然在三種誠實的方式之一上「作弊」：它只對受限的語言奏效、它有時回答「我不知道」、或它有時是錯的。