7.3 不可判定性與停機問題#

本章導言#

停機問題（7.1 節）不是孤例，而是第一張骨牌：Turing 與 Church 1936 年之後，邏輯學與數學的許多中心問題被證明不可判定——一階邏輯有效性、Hilbert 第 10 問題（丟番圖方程）、群的字問題、甚至具體的數論問題。不可判定性成為「數學問題的複雜性地圖」中的深淵標記。本節系統展開：歸約技術、不可判定性清單、遞迴度階層，以及它們對「數學可否被完全形式化」的最終判詞。

歸約：不可判定性的傳染#

多一歸約： \(A \le_m B\) 若存在可計算函數 \(f\) 使 \(x \in A \iff f(x) \in B\) 。性質： \(B\) 可判定 ⟹ \(A\) 可判定；故 \(A\) 不可判定且 \(A \le_m B\) ⟹ \(B\) 不可判定。

**停機問題 \(K = \{e : M_e(e) \text{ 停機}\}\) ** 是原點。標準歸約鏈：

1. **一階邏輯有效性 \(VALID\) **：構造 \(\phi_{M, x}\) 使「 \(\phi_{M,x}\) 有效 \(\iff M(x)\) 停機」（Church 1936、Turing 1936）。
2. 丟番圖方程可解性（Hilbert 第 10 問題）：Matiyasevich 1970 證明 r.e. 集 = 丟番圖集（結合 Davis–Putnam–Robinson），停機問題歸約為「多項式方程是否有整數解」。
3. 群的字問題：Novikov 1955、Boone 1958 構造群 \(G\) 使「 \(w =_G 1\) 」編碼停機問題。
4. 具體數論命題：Matiyasevich 的結果意味着存在具體的多項式 \(P(x_1, \dots, x_9)\) ，「 \(P = 0\) 有自然數解」等價於停機——一個固定的多項式，其可解性編碼了所有停機。

歸約的方向是「把一般問題塞進特例」：要證新問題不可判定，構造可計算變換把老問題實例翻譯成新問題實例。這是 7.1 節例題 7.1.2（空白輸入特例）的一般化，也是整個可計算性理論的日常工作方式。

不可判定性清單：數學的深淵地圖#

模式：任何「足夠表達力」的系統（能模擬 Turing 機的系統）都繼承不可判定性。「模擬能力」與「可判定性」不可兼得——這是通用性（7.1 節）的價格。反之，弱系統（Presburger 算術、實閉域、有限自動機、線性邏輯片段）可判定——表達力與可判定性的 trade-off 橫貫邏輯與計算。

遞迴度：不可判定性的精細階層#

不可判定不是一個等級，而是一個譜系。Turing 歸約 \(A \le_T B\) ： \(A\) 可由「帶 \(B\) 為神諭（oracle）的 Turing 機」計算。圖靈度 = 等價類。

• \(0\) ：可判定集的度。
• \(0'\) ：停機問題的度（Turing 跳躍 \(K\) ）。
• \(0''\) ：停機問題的停機問題（「機器 \(M\) 對神諭 \(K\) 停機嗎」）。
• \(0^{(n)}\) ： \(n\) 次跳躍； \(\mathcal{O}\) ：算術層級的頂（ \(0^{(\omega)}\) ）。

結構定理：每個度之上有連續統多個更高的度（Kleene–Post 1954）；存在不可比度；跳躍反轉定理（Friedberg–Muchnik 1957）：存在 \(0 < A < 0'\) 的中間度——r.e. 度的世界比直覺豐富得多。

這張階層圖像與 2.2 節的基數階層平行：Cantor 對角線生成基數階層，Turing 對角線生成圖靈度階層——「不可判定」有無窮精細的等級，數學問題的困難度是被測量的對象。

一個具體例子#

例題 7.3.1：證明「判斷一台 Turing 機是否對任何輸入停機」（全停機問題 \(\mathrm{TOT}\) ）不可判定，且 \(\mathrm{TOT}\) 的圖靈度為 \(0''\) （比停機問題嚴格難）。

解：不可判定：歸約自 \(K\) 。給定 \((e, x)\) ，構造機 \(M_{e,x}\) ：對輸入 \(y\) ，先模擬 \(M_e(x)\) （忽略 \(y\) ） \(|y|\) 步；若 \(M_e(x)\) 在 \(|y|\) 步內停機則 \(M_{e,x}\) 無窮迴圈；否則停機。

• 若 \(M_e(x)\) 不停機： \(M_{e,x}\) 對一切 \(y\) 停機（模擬永不完成， \(|y|\) 步後停）。
• 若 \(M_e(x)\) 停機於 \(t\) 步： \(M_{e,x}\) 對 \(|y| \ge t\) 的輸入不停機。

故 \(\mathrm{TOT}(M_{e,x}) \iff \neg K(e, x)\) 。若 \(\mathrm{TOT}\) 可判定， \(K\) 可判定——矛盾。

**度為 \(0''\) **： \(\mathrm{TOT}(e) \equiv \forall x \exists t\, T(e, x, t)\) （ \(T\) 可判定），屬 \(\Pi^0_2\) ；且可證 \(K' \le_T \mathrm{TOT}\) （以 \(\mathrm{TOT}\) 神諭判定「機器 \(e\) 是否在神諭 \(K\) 上對一切輸入停機」的編碼）——故 \(\deg(\mathrm{TOT}) = 0''\) 。 \(\blacksquare\)

要點：「對所有輸入」的量詞跳躍使困難度嚴格上升一級——量詞交替（ \(\forall \exists \forall \cdots\) ）與圖靈跳躍的對應是算術層級定理（Kleene 1943）的內容：邏輯量詞深度 = 可計算困難度。5.1 節 \(\varepsilon\) – \(\delta\) 的量詞序在此獲得計算論的定量意義。

例題 7.3.2：用 Matiyasevich 定理的結論證明：存在一個具體多項式 \(P\) ，使「 \(P(\vec x) = 0\) 有自然數解」不可判定。

解：Matiyasevich–Davis–Putnam–Robinson（DPRM）定理： \(S\) 是 r.e. 集 \(\iff\) \(S = \{\vec a : \exists \vec x\, P_S(\vec a, \vec x) = 0\}\) ， \(P_S\) 整係數多項式。 \(K\) （停機集）是 r.e. 集，故存在整係數多項式 \(P_K(e, \vec x)\) 使

若「 \(P_K(\vec x) = 0\) 是否有解」可判定（對 \(\vec x\) 部分枚舉判定），則 \(K\) 可判定——矛盾。一個寫得下的具體多項式，其可解性超越一切算法。實際上可構造出顯式的 \(P_K\) （次數與變數數很大但有限）——不可判定性不是抽象存在，而是具體對象的性質。 \(\blacksquare\)

Hilbert 第 10 問題的歷史餘波#

Hilbert 1900 要求「給定丟番圖方程，設計過程判定可解性」。其解（1970）是否定的，且路徑橫貫整個世紀：Gödel 1931（可表達性）→ Church–Turing 1936（不可判定技術）→ Davis 1953（r.e. 集的丟番圖表示構想）→ Robinson 1961（指數丟番圖）→ Matiyasevich 1970（Fibonacci 數的丟番圖性補上最後一環，年僅 22 歲）。一個 1900 年的問題由 1930 年代的邏輯革命間接殺死——基礎研究對數學本體的反向輸出，沒有比這更清楚的案例。

歷史啟示#

• 不可判定性是普遍現象而非例外：任何能表達自身語法的系統都繼承之。「表達力 ⇔ 不可判定」是可計算性的守恆律。
• 量詞深度即困難度：算術層級把邏輯句法（ \(\forall\exists\) 交替）與圖靈跳躍一一對應——句法與計算的字典。
• Hilbert 的問題清單是「對」的：第 1 問題（CH）獨立、第 2 問題（一致性）不可能原版解決、第 10 問題不可判定——他的問題精確到足以被否定性解決，這本身就是偉大。

與其他章節及領域的關聯#

• 5.1–5.3 節：一階邏輯的半可判定與量詞結構。
• 6.1–6.2 節：不完備性是「不可判定語句」，本節是「不可判定問題」——同一現象的語句面與問題面。
• 2.2、4.3 節：圖靈度階層與基數階層的對角線譜系。
• 8.3 節：力迫條件的可計數性依賴可枚舉技術。
• 9.2 節：構造性證明的計算內容——可判定性反例的正面部分。
• 計算機科學：不可判定性是「驗證不可能性」的理論根源（Rice 定理：一切非平凡語義性質不可判定）；實踐對策是限制輸入類（有界驗證、模型檢查有限狀態系統）——不可判定性教會工程學「畫界」。
• 密碼學：平均情況難度（單向函數）與最壞情況不可判定性的分離是現代密碼的基礎。

練習#

1. 用歸約證明：「機器 \(M\) 的語言是否為空」不可判定。
2. 證明 Rice 定理：任何非平凡的 r.e. 集族 \(\mathcal{C}\) ，「 \(L(M_e) \in \mathcal{C}\) 」不可判定。
3. 計算 \(\mathrm{INF} = \{e : L(M_e) \text{ 無窮}\}\) 的算術層級位置（ \(\Pi^0_2\) ）並證明之。
4. 用例題 7.3.1 的技術證明 \(\{e : W_e \text{ 有限}\}\) 是 \(\Sigma^0_2\) -完備的。
5. 思考題：不可判定性清單中的具體問題（單一多項式、單一群的字問題）顯示「深淵」有具體地址。這對「數學問題分類」的計劃（如 Hilbert 式清單）有何影響？

進階研讀：三個深化場景#

場景一：Rice 定理——語義不可判定的總閘。Rice 1953：r.e. 語言族的任何非平凡性質（只依賴語義）不可判定。一切「程式做什麼」的問題都不可判定，只有「程式長什麼樣」的問題（語法）可判定——軟體工程的形式驗證邊界由此一條定理劃定。

場景二：Berger 的骨牌與混魔力。Berger 1966 證明「一組 Wang 骨牌能否鋪滿平面」不可判定，並構造出第一組非周期骨牌集（必須非周期地鋪滿）；後來 Penrose 13 塊、甚至 2 塊（Ollinger 2009）。不可判定性孕育了準晶體數學——Shechtman 1982 的實驗準晶獲 2011 諾貝爾化學獎，其數學根在 Berger 的對角線構造。邏輯→幾何→材料的鏈條。

場景三：Conway 的 \(\zeta(3)\) 式遺產與 Busy Beaver。Busy Beaver 函數 \(\Sigma(n)\) （ \(n\) 狀態機在停機前最大寫入數）增長快於一切可計算函數，其具體值（ \(\Sigma(5) = 47{,}176{,}870\) ，2024 年確定； \(\Sigma(6)\) 未知且已知下界巨大）是不可判定性的具體前沿——每個新的 \(n\) 都是一次人類計算對不可判定深淵的探底。

名詞速查表#

• **多一歸約 \(\le_m\) **：可計算的實例翻譯。
• Turing 歸約 \(\le_T\) ／圖靈度：神諭計算的等價類。
• **Turing 跳躍 \(0'\) **：停機神諭度； \(0^{(n)}\) 層階。
• 算術層級： \(\Sigma^0_n / \Pi^0_n\) （ \(\exists\forall\) 交替深度）與跳躍的對應。
• DPRM 定理：r.e. = 丟番圖（Hilbert 第 10 問題之解）。
• Rice 定理：非平凡語義性質不可判定。
• **Busy Beaver \(\Sigma\) **：增長超可計算的具體函數。

年表速查#

• 1936：Church–Turing（一階邏輯不可判定）。
• 1943：Kleene 算術層級。
• 1953：Rice 定理；Davis 丟番圖構想。
• 1954：Kleene–Post 度結構。
• 1955–58：Novikov–Boone 字問題；Markov 流形。
• 1957：Friedberg–Muchnik 度反轉。
• 1966：Berger 骨牌。
• 1970：Matiyasevich（第 10 問題之解）。
• 2024： \(\Sigma(5)\) 確定。

深化問答三則#

問：不可判定性是否「打擊」了數學？ 答：精確地說，打擊了「全算法數學」的夢想，但劃清了戰場：可判定片段（Presburger、SMT 的組合理論、格羅布納基可處理的代數幾何）成為自動推理的疆土；不可判定部分由人類數學家以創造性處理。不可判定性定理是把「數學實踐」從「算法學」中解放出來的證明。

問：具體多項式的不可判定可解性，與「每個具體方程都有答案」矛盾嗎？ 答：不矛盾。每個具體的方程要麼有解要麼沒有（排中律下），只是沒有算法統一判定。「有無具體解」與「可否機械判定」是兩個問題——這正是「真與可證」（6.1 節）、存在與可計算的分界在日常數學中的顯形。

問：遞迴度階層的實際用途？ 答：它為數學問題提供精確的困難度座標：如「König 引理的無窮版在 \(WKL_0\) 」「單純性定理在 \(ACA_0\) 」——逆數學（6.3 節）實質是「把定理放到層級座標上」的計劃。不可判定性不是終點而是測量的開始。

（本節完）