1.1 1931哥德爾不完備定理與判定問題#

前言：為什麼需要研究可計算性？#

在 20 世紀初，數學界正處於一場宏大的基礎主義運動中。弗雷格（Gottlob Frege）、伯特蘭·羅素（Bertrand Russell）、希爾伯特（David Hilbert）等人希望為整個數學奠定嚴格的公理基礎：建立一個形式系統，所有數學定理都能從一小組公理經由邏輯推演而得。

希爾伯特的計畫包含兩個核心目標：完備性（completeness）——每個在該系統內的真命題都可證明；一致性（consistency）——該系統不可能證明出互相矛盾的命題。此外，他也重視決定性（decidability）的問題：是否存在一個通用的演算法，能對任意數學命題判定其真假？

然而，1931 年一篇名為《論形式系統的形式不可決定命題》（Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I）的論文，徹底動搖了這個理想。作者是 25 歲的庫爾特·哥德爾（Kurt Gödel）。哥德爾不完備定理不僅粉碎了希爾伯特的第一個夢想，更首次揭示了：形式系統的極限與可判定性本身密切相關。

哥德爾不完備定理：對角線法的登場#

第一定理：形式系統存在不可證明的真命題#

哥德爾所處理的對象是足夠包含算術（自然數加法與乘法）的形式系統 \(S\) ，例如 Peano 算術 \(PA\) ，前提是 \(S\) 一致且遞迴可枚舉（即公理與推演規則可由機械方式列出）。他證明了：

哥德爾第一不完備定理：若 \(S\) 是一致的遞迴公理系統，則存在一個算術命題 \(G\) ，在 \(S\) 中既不可證明也不可否證，且 \(G\) 在自然數的標準模型中是真命題。

這個證明的關鍵是哥德爾編碼（Gödel numbering）。哥德爾巧妙地將每個公式、每一個證明編號為一個自然數 \(g(\phi) \in \mathbb{N}\) ，進而將「 \(\phi\) 是可證明的」這個元語言性質，轉譯為「某個算術關係 \(Prov(g(\phi), y)\) 在自然數上成立」這種內部的算術性質。藉由構造一句自我指涉的命題

他得到了一個類似「我說謊」的數學版本。這種利用對角線技術進行自我指涉的手法，日後在圖靈證明停機問題時也扮演了決定性的角色。

第二定理：系統不能證明自身的一致性#

若將 \(Con(S)\) 表示「 \(S\) 不一致」的否定（即 \(S\) 一致），哥德爾進一步證明：

哥德爾第二不完備定理：若 \(S\) 一致且足夠強，則 \(S\) 無法在 \(S\) 內部證明 \(Con(S)\) 。

換言之，為了證明一個足夠描述算術的系統本身沒有矛盾，我們必須訴諸比該系統更強的形式工具。這不僅是數理邏輯的深刻洞見，更直接影響了 20 世紀後半部元數學（metamathematics）的發展方向。

從「完備性」到「判定問題」#

希爾伯特原本期望：對一個一致的形式系統，只要給定任意命題，總存在一套機械程序能在有限步驟內判定該命題是否可證明。這個問題在德文稱為 Entscheidungsproblem，中文常譯作判定問題（Decision Problem）。

哥德爾的結果讓人們首次意識到：存在著在自然數意義下真，卻在形式系統中不可判定的命題。但判定問題本身的嚴格否定，仍需要明確定義「機械程序」這個概念。

這正是計算理論史上最關鍵的銜接點：哥德爾開啟了對形式系統極限的探討，卻尚未給出「有效可計算（effectively computable）」的通用模型。這個空隙，將由圖靈、丘奇（Alonzo Church）、克林（Stephen Kleene）等人填補。

歷史脈絡與互相驅動的關係#

哥德爾的工作有著清晰的理論內部動力，同時也深刻地反饋到哲學與計算機科學：

• 邏輯史上的前因：受弗雷格的謂詞邏輯與羅素–懷特海《數學原理》的啟發，希爾伯特的形式主義試圖徹底化公理化。
• 理論的突破：哥德爾編碼與對角線法，是一種全新的「自我指涉」技術，源自數學本身卻直指計算的本質。
• 驅動計算模型的誕生：判定問題的形式化催生了圖靈機（Turing Machine）與 \(\lambda\) 演算的研究。圖靈更明確地刻劃了「人類計算者遵循有限規則進行演算」的過程，從而定義了機械計算的邊界。
• 對現代的影響：不完備定理啟發了自我描述、自我複製（馮·諾伊曼的自我複製機器思想亦與此有共鳴）、以及計算理論對「極限」的思考。它也在密碼學（理論上有無可證實的安全性？）、認知科學與 AI（心智是否可形式化？）領域引發持續討論。

特別值得強調：哥德爾→圖靈→馮·諾伊曼架構，形成了一條從數理邏輯到實際計算機的直接傳遞線。圖靈在論文中明確引用了希爾伯特的判定問題，並受哥德爾的對角線手法影響。馮·諾伊曼則熟稔圖靈的思想（1946年《First Draft of a Report on the EDVAC》中便與圖靈機有深刻呼應），最終設計出存放程式與資料於同一記憶體的普適架構。

核心理論的簡要形式化#

為了理解哥德爾證明的精髓，讓我們概略地看編碼的思路。定義 \(\bar{n}\) 為自然數 \(n\) 的形式表示（例如 \(S(\cdots S(0)\cdots)\) ）。若 \(A(x)\) 是帶一個自由變數的公式，則定義

為其哥德爾數。存在一個原始遞迴函數 \(Sub\) 使得

即將變數 \(x\) 替換為 \(n\) 的哥德爾數。接著定義 \(Diag(m) = Sub(m,m)\) ，構造公式 \(D(x)\) 表示「 \(Diag(x)\) 不是可證明公式的哥德爾數」。令 \(m_0 = \ulcorner D(x) \urcorner\) ，則

其中 \(\text{ProvSeq}\) 是所有證明序列的哥德爾數集合。由自我指涉可得： \(G\) 為真 \(\Leftrightarrow\) \(G\) 不可證明。此處的「可證明」是系統 \(S\) 內部的可推演性質。

從理論到後果：為什麼這很重要#

哥德爾不完備定理最重要的「後果」，不是「數學崩潰」，而是劃定了形式方法的邊界：

1. 可計算性的必要性：判定問題的探討要求精確定義「有效計算」。這直接促成了 1936 年三大計算模型（圖靈機、 \(\lambda\) 演算、遞迴函數）的提出。
2. 演算法不可解性的源頭：對角線法成為證明「不存在演算法」的標準武器。停機問題、Post 對應問題、Rice 定理等不可判定性結果，幾乎都脫胎自哥德爾的思路。
3. 編譯器與自動推理的基礎：元數學的研究催生了自動定理證明、模型檢查的早期構想，也影響了程式語言設計者對「語言是形式系統」的理解。
4. 計算機科學的獨立性：人們逐漸認識到，計算的極限不是「硬體不夠快」，而是邏輯上的不可行。這種「邊界性思考」塑造了理論計算機科學的核心氣質。

小結#

哥德爾不完備定理的價值，在於它將數學的自我省察推向頂點。透過哥德爾編碼與對角線法，我們第一次看清：一個足夠自足的系統，既強大到能描述自身，卻也因此註定無法完全掌握自身的全部真理。這一洞見，直接導向了「可計算是什麼？」的追問，而下一節將介紹圖靈機如何給出這個問題的精確答案。