數那不可數的：對角線論證

無限的兩種大小

我們以整個工具箱裡最令人瞠目的想法來結束本單元，而它直接從「把東西配對起來」這個簡單觀念長出來。兩個集合「一樣大」，若你能把它們的成員一對一配起來、誰也不剩——一個完美的雙射，就像把每隻左鞋配給它的右鞋。一個集合是可數的（countable），若你能把它所有成員排成一張單一的無限清單：第 1 項、第 2 項、第 3 項……如此下去，使每個東西都出現在某處。計數數字依定義是可數的；較不顯然地，整數、分數也是，而且——對我們至關重要的——所有有限字串的集合 Sigma-star（寫作 Σ*）也是。

為什麼 Σ* 雖然無限卻是可數的？因為你可以用一個合理的順序把它的字串列出來：先按長度排，同一長度內再按字母順序。在字母表 {a, b} 上，這張清單從 epsilon、a、b、aa、ab、ba、bb、aaa……開始。每個有限字串，無論多長，都出現在某個有限的位置上。這個訣竅——先列短的、在涵蓋完比它短的所有字串之前絕不讓長度暴衝——正是證明一個集合可數的標準配方。

Cantor 的對角線：一張必然不完整的清單

這就是 Cantor 的論證，是後面一切的引擎。假設有人聲稱握有一張完整的編號清單，列出了所有無限二進位序列（想成由 0 與 1 組成的無限長字串）。我們將製造出一個不可能在他清單上的序列，藉此證明這聲稱是錯的——而既然此人是任意的，這種清單就永遠不可能完整。這就是對角線論證，它其實是一個穿著非常特定戲服的反證法。

把那張號稱完整的清單擺成一個格狀表：第 n 列是第 n 個序列，第 m 行是它的第 m 個位元。於是表中第 n 列第 m 行存著位元 B(n, m)。
沿著主對角線走——位元 B(1,1)、B(2,2)、B(3,3)……——從每一列各取恰好一個位元，取的是列號等於行號的那一個。
藉由翻轉每一個對角線位元，建出一個新序列 D：D 的第 m 個位元是 B(m, m) 的相反。對角線說 0 的地方，D 就說 1，反之亦然。
現在問：D 能是某個第 n 列嗎？不能——依其構造，D 在第 n 個位置上與第 n 列不同（我們就是翻轉了那個位元）。所以 D 在某處與每一列都不一致，它不可能出現在清單上的任何地方。

這張清單本應包含每個無限二進位序列，然而 D 是一個它漏掉的無限二進位序列。矛盾。所以沒有任何清單能裝下它們全部：無限二進位序列是不可數的（uncountable）——一個嚴格大於計數數字的無限。其精妙處在於那條對角線：藉由「在恰好第 n 個位置上與第 n 列唱反調」，這個新物件就被保證能一次掃過、躲開整張清單。把這幅圖像記牢；下一個論證是同一幅圖像，只是換成了機器。

語言比機器多

現在我們把這個想法兌現。一個程式——一台圖靈機，那本你可以讀、可以擦、可以重寫的無盡筆記本——本身只是一個有限的描述，一個由符號組成的有限字串。所以所有程式的集合可以被列出來：程式 1、程式 2、程式 3……正如我們列出 Σ* 的方式。機器只有可數多個。 這是對「任何機械究竟能解多少問題」的一個硬性而誠實的上限，因為每台機器至多辨識一個語言。

但語言有多少個呢？Σ 上的一個語言不過是 Σ* 的一個子集——對那可數多個字串中的每一個給出「是／否」的裁決。把字串釘成字串 1、字串 2、字串 3……，一個語言就變成一個無限的位元序列：若字串 m 在語言裡則第 m 個位元為 1，否則為 0。這恰恰就是一個無限二進位序列——而我們剛剛證明了那些是不可數的。所以語言有不可數多個，能辨識它們的機器卻只有可數多個。於是計數論證以全副力道落下。

對停機問題做對角線

計數論證告訴我們「某個不可計算的語言就在某處」，卻氣人地對「是哪一個」含糊其辭。要點名一個具體的反派，我們再跑一次對角線把戲——這回格狀表的列是機器、行是輸入，而表中的條目是「它會停機嗎？」。這就是停機問題的對角線論證，它出名得有道理：它證明了停機問題是不可判定的，意思是沒有任何程式能對每一對「程式與輸入」都正確預測那次執行最終會停機、還是永遠迴圈下去。

為了導出矛盾，假設存在一個完美的停機檢查器 H。給 H 兩樣東西——一台機器 M 與一個輸入 w——它總會停下並回答「會，M 在 w 上停機」或「不會，M 在 w 上迴圈」。我們建出一個破壞者 D，它吃一個輸入（一個機器描述 M），並做出與「M 在它自己的描述上會做的事」相反的舉動：D 問 H「M 在輸入 M 上會停機嗎」；若 H 說「停機」，D 就故意永遠迴圈；若 H 說「迴圈」，D 就立刻停機。D 就是那條對角線——它恰好在每台機器自身的自我描述上與該機器唱反調，也就是主對角線上的那個條目。

Assume H(M, w) decides: "does machine M halt on input w?"

Build D, which takes one input -- a machine description M:

    D(M):
        if H(M, M) says "M halts on M":
            loop forever        <- do the OPPOSITE
        else (H says "M loops on M"):
            halt                <- do the OPPOSITE

Now run D on its OWN description:  what is  D(D) ?

    If D(D) halts   -> H(D, D) said "halts" -> D was built to loop. Contradiction.
    If D(D) loops   -> H(D, D) said "loops" -> D was built to halt. Contradiction.

Either way: impossible. So the assumed H cannot exist.

自我指涉的對角線：把 D 自己的描述餵給 D，無論哪條路都逼出矛盾。

現在問那個對角線問題：當 D 跑在它自己的描述上、也就是 D(D) 時，它會做什麼？若 D(D) 停機，那麼 H 必定說了「D 在 D 上停機」，但 D 在那種情形下被建成要迴圈——矛盾。若 D(D) 迴圈，那麼 H 說了「D 在 D 上迴圈」，但 D 被建成要停機——矛盾。每條分支都不可能，所以唯一的假命題就是 H 本身：完美的停機檢查器不可能存在。當初擊垮 Cantor 清單的那個「自我唱反調」，同樣擊垮了「萬用停機神諭」的美夢。這種自我指涉——一個程式讀自己的描述——就是引擎，它呼應著說謊者悖論，那句說「這句話是假的」的話。

這究竟意味著什麼（以及不意味著什麼）

請對結論說得精確，因為它很容易被誇大或低估。停機問題是不可判定的：沒有任何單一演算法能對每個輸入都停下、並總是給出正確的「停機或迴圈」裁決。這不是「我們還沒找到夠快的方法」，也不是「這問題只是非常慢」。它是一個永久的、數學上的不可能——沒有任何未來的硬體、更聰明的程式碼，也沒有任何量子電腦能改變它，因為這個矛盾是邏輯上的，無關乎速度。

兩個誠實的但書讓這個結果守在它的車道上。第一，不可判定並不表示「任何特定情形都無法回答」——你往往能判斷某個特定程式會不會停機；不可能的是「一個對全部都管用的方法」。第二，不可判定是比僅僅無法辨識更不同、更強的失敗。停機語言其實是圖靈可辨識的：一台機器只要模擬並等待就能確認停機，但若輸入永遠迴圈，模擬也永遠迴圈、絕不報告「否」。可辨識卻不可判定——辨識器可能永遠跑下去——正是對角線論證撬開的那道縫隙，你會在可判定性單元裡完整地探索它。

退一步，欣賞整個單元貫穿始終的那條主線。鴿籠原理證明了「擠迫會逼出重複」；結構歸納法跨越無限多個建造出來的物件去證明性質；而對角線論證——我們在歸納法那篇結尾所預告的近親——證明了「兩個無限可能無法匹配」，並用一條自我唱反調的對角線，製造出那個逃離任何清單的物件。這四個證明手法——歸納法、鴿籠原理、第二篇邏輯裡的證明技巧，以及對角線論證——就是整架階梯其餘部分所倚靠的全部數學脊樑。從這裡開始，每一條關於「機器能做與不能做什麼」的定理，都是用這些磚塊砌成的。