從「某個語言不可判定」到一個你叫得出名字的語言
上一篇留給你一個縈繞不去卻抽象的事實：語言比機器多，所以不可判定語言必然存在。那是個計數論證——它告訴你那些缺席的答案就在某處，就像證明一個乾草堆裡有根針，卻從不指出它在哪。本篇要來指出它。我們會擺出一個具體、有用、再自然不過的問題，並證明它根本沒有判定器。它的名字是停機問題（halting problem），而一旦你見過它，不可判定性就不再是一條人口統計，而成了一件你拿得到手裡的東西。
首先是一件你在圖靈機那一階已見過、但如今要挑大樑的機械裝置：任何一台圖靈機 M，本身都能寫成一串有限的符號——它的狀態、它的轉移表、全部——就跟一支程式不過是檔案裡的文字一樣。我們把那串符號寫成 ⟨M⟩，即 M 的編碼（encoding）。這是整門學科那股安靜的超能力：因為一台機器只是資料，一台機器就能拿另一台機器的描述當輸入，並對它進行推理。一支程式能讀一支程式。就這一個觀察，使得自我指涉——也因此使我們即將布下的陷阱——成為可能。
現在把問題精確地陳述出來，因為精確正是困難藏身之處。停機問題問的是：給定一台機器 M 的程式碼與一個輸入 w，M 在 w 上跑時究竟會最終停機（停下來），還是會永遠迴圈？作為一個語言，我們把所有「是」實例綑成一個集合，寫成 HALT = { ⟨M, w⟩ : 機器 M 在輸入 w 上停機 }。問「停機問題可判定嗎？」恰恰就是在問「語言 HALT 可判定嗎？」——是否存在一台固定的機器，餵給它任何一對 ⟨M, w⟩，它都總會停機並正確地回答「會停」或「不會停、會迴圈」？
通用機器：一台跑其他機器的機器
在壞消息之前，先來點我們稍後會當工具用的、真正的好消息。確實存在一台單一機器，能模擬任何其他機器。餵它 ⟨M, w⟩，它就會逐步忠實地仿效 M 在 w 上會做的事——它就是通用圖靈機（universal Turing machine），你用過的每一個直譯器與 CPU 的曾祖父。你的筆電就是一台通用機器：它並沒有為每個 app 燒進各別的電路；它讀那個 app（資料 ⟨M⟩）然後跑它。這件事竟然可能——一台固定的機器，能變成你所描述的任何機器——是整個計算領域裡最深刻的實用點子。
這台通用機器所環繞建造的語言，有它自己的名字：A_TM，即通用接受語言（universal acceptance language），定義為 A_TM = { ⟨M, w⟩ : 機器 M 接受輸入 w }。留意它與 HALT 的不同：HALT 問的是 M 究竟停不停機；A_TM 問的是稍有差異的問題——M 是否停機而且接受。兩者是近親，證明其一不可判定，便可藉一個簡短的歸約證明另一個不可判定，這在日後某篇會詳述。關鍵的半真相在這裡：A_TM 是可識別的。只要把通用機器在 ⟨M, w⟩ 上跑；若 M 接受 w，你的模擬就會抵達 M 的接受狀態，你便回答「是」。
但是——這正是全部的戲劇張力——可識別不等於可判定。若你把 M 在 w 上模擬，而那模擬跑了十億步還在磨，你就卡在可判定性那一階講過的「迴圈與否」兩難裡：也許 M 正要接受、也許它下一刻就拒絕、也許它會永遠跑下去，而你會陪它永遠等下去。你無法在有限時間內安全地宣告「M 不接受 w」，因為那需要知道 M 會迴圈，而那恰恰是你沒有辦法偵測的東西。所以 A_TM 是識別器的美夢、判定器的噩夢。下一節要證明，這場噩夢無可避免。
那個陷阱：一台問自己、然後反著做的機器
證明 A_TM（連同停機問題）不可判定的，是一個對角線化（diagonalization）論證，與康托爾用來證明實數多過整數的、同一把自我指涉的武器。策略是反證法：先姑且假設存在一台判定器，再造出一台機器，把那台判定器逼進一個邏輯上的不可能——一台依其建構方式就不可能自洽存在的機器。故事裡的反派，是一台小小的機器，它問一個關於它自己的問題，然後刻意去做別人告訴它的相反的事。讓我們慢慢走一遍。
- 假設敵人存在。為了導出矛盾，假設某台判定器 H 能了結 A_TM：給定 ⟨M, w⟩，H 總會停機，並在 M 接受 w 時輸出「接受」、在 M 不接受時（無論 M 是拒絕還是迴圈）輸出「拒絕」。H 絕不迴圈——這正是我們要炸掉的假設。
- 造一個唱反調者。建構一台新機器 D，它拿單一一個機器描述 ⟨M⟩ 當輸入。D 在內部對「⟨M, ⟨M⟩⟩」這一對呼叫 H——也就是問 H：「M 接受它自己的描述當輸入嗎？」然後 D 做出與 H 答案相反的事：若 H 說 M 接受，則 D 拒絕（或乾脆迴圈）；若 H 說 M 不接受，則 D 接受並停機。
- 扣下扳機：把 D 自己的描述 ⟨D⟩ 餵給 D。現在問那個致命的問題——D 在輸入 ⟨D⟩ 上會做什麼？在內部，D 向 H 探詢「D 接不接受 ⟨D⟩」，然後反著做。於是：D 接受 ⟨D⟩，恰好發生在 H 回報 D 不接受 ⟨D⟩ 的時候；而 D 不接受 ⟨D⟩，恰好發生在 H 回報它確實接受的時候。
- 讀出矛盾。D 接受 ⟨D⟩，若且唯若 D 不接受 ⟨D⟩。這是個赤裸裸的自我矛盾，就像一位「只替那些不替自己刮鬍子的人刮鬍子」的理髮師。整條推理鏈中唯一站不住的一步，就是最起初那一步——「H 存在」這個假設。所以這樣的 H 並不存在：A_TM 不可判定，停機問題也隨之不可判定。
為何這叫「對角線化」？想像一張巨大的表格：每台機器 M 一列、每個輸入字串一行，在格子 (M, w) 裡寫下 M 是否接受 w。機器 D 被刻意設計成沿著表格的對角線與每一台機器 M 都不同——在「拿列上那台機器問它自己的描述」的那個格子裡，D 被造得與它唱反調。一台在對角線上與每一列都唱反調的機器，不可能是任何一列；然而 D 是一台定義得好端端的機器，所以它應該是某一列。矛盾就在於：D 既必須、又不可能出現在「所有機器」這張清單上。完整的表格與對角線圖像是下一篇的核心；此處，請抓住這句結論：自我指涉，加上「反著做」，會引爆任何妄想成為通用停機檢查器的東西。
一個機器連識別都辦不到的語言
可判定性那一階給了你一句口號：可判定＝可識別而且余可識別。把它反著跑，它就成了一把鎚子。我們剛證明了 A_TM 可識別（跑通用機器即可）卻不可判定。由那條定理，A_TM 因此不可能同時是余可識別的——若它兩者皆是，它就會可判定，而我們剛剛駁倒了這點。所以 A_TM 的補集——那些「M 不接受 w」的對 ⟨M, w⟩ 所成的語言——是一個連可識別都辦不到的語言。它是一個不可識別語言，也是多數人頭一個叫得出名字的這類例子。
好好體會這有多怪。對 A_TM 本身來說，至少有一台機器能確認「是」的答案——它只是無法確認「否」的答案。但對 A_TM 的補集來說，沒有任何機器能可靠地確認連「是」的答案（在這裡「是」意味著「M 不接受 w」）都不行。要確認 M 永不接受 w，你得確定 M 不會在第一百億步、或第一百億零一步、或任何時候接受 w——而再多有限量的模擬都建立不起一個「永遠」。誠實的結論是：「M 在 w 上迴圈」與「M 永不接受 w」這類陳述，沒有任何你能在有限步內查核的正向見證者。這就是從不可判定躍升到不可識別的那一質的飛躍，它把困難的階梯，又比停機問題本身堆高了一階。
賴斯定理：問題從來不只在於停機這一件事
你或許指望停機問題是個孤獨的怪胎——一個我們可以隔離起來、然後照樣繼續造工具的病態問題。賴斯定理（Rice's theorem）以令人屏息的普遍性，碾碎了這個指望。仔細陳述出來，它說：一台機器所識別的語言的每一個非平凡性質，都不可判定。把這兩個謹慎的詞拆開。「語言的性質」指的是一個是非問題，它只取決於這台機器接受哪些字串——它的行為——而非程式碼怎麼寫。「非平凡」指的是：至少有一台機器具有該性質，且至少有一台沒有（一個對每台機器都成立、或對沒有任何機器成立的性質，是平凡地可判定的——永遠答「是」、或永遠答「否」就好）。
於是像「這台機器接受空字串嗎？」、「它究竟接不接受任何字串？」、「它的語言包含某個迴文嗎？」、「它的語言是正規的嗎？」、「它恰好接受所有偶數長度的字串嗎？」這類問題——每一個都不可判定，因為每一個都是行為的非平凡性質。其證明（日後某篇會給出）是一個從停機問題出發的歸約：一位把任何停機問題翻譯成「某台被建構出的機器是否具有該性質」的翻譯員。賴斯定理，正是為何沒有任何通用工具，能對任意程式碼判定那段程式碼意味著什麼。
這讓真實的程式設計師付出什麼代價
這不是數學珍奇博物館裡的一件展品；它是日常軟體工程腳下的基岩。停機問題說：沒有通用的停機檢查器——沒有任何工具，能對任意程式與輸入，都正確地告訴你「這會終止」對上「這會卡住」。所以你的 IDE 那個無窮迴圈警告，無論多聰明，必然有時會漏掉一個真正的迴圈、或對其實沒問題的程式碼喊狼來了。賴斯定理把傷害擴大：沒有任何完美、完全通用的「行為臭蟲」偵測器，沒有任何工具能對所有程式判定兩支程式是否等價，也沒有任何判定器能斷定某函式在每一種可能的執行下是否曾被以空引數呼叫。
不過要把這道天花板讀對，因為實務上的教訓是充滿希望的、而非失敗主義的。不可判定性禁止的是「一個對每個輸入都正確而且總會停機」的單一程序。它並不禁止那些大多數時候正確的工具、或那些被允許回答「我不知道」的工具、或那些只在一個受限、行為良好的程式子類別上運作的工具。型別檢查器、靜態分析工具（linter）、模型檢查器、終止性證明器，以及每個編譯器內部的最佳化階段，全都在這片空間裡活得好好的：它們繞過賴斯定理的方法，是做到健全但不完備（它們從不說謊，但有時聳聳肩），或只分析形狀較溫馴的程式。這條定理，是圈在「通用神諭」這個夢想四周的籬笆，而非圈在有用的近似四周。
最後一道護欄，好讓你正確地揮舞這件武器。不可判定性活在那無所不能的圖靈機那一層，正因為它能做任何真實電腦做得到的事。沿著喬姆斯基層級往下掉，那些牆便紛紛倒下：對一台有限自動機而言，空性、等價與接受全都可判定，因為一台 DFA 是個有限、可完全攤開描繪、無處藏匿無窮迴圈的物件。這正是你一路爬上階梯所見過的同一場抵換——能力以不可預測性換來。停機問題，就是你的模型一旦變得圖靈完備那一刻便到期的帳單：你的語言一旦能表達任意計算，它就能表達那台唱反調的機器 D，而那道牆便喀噠一聲卡進原位。