1900 - Hilbert 第十題（列表算法的遺囑）#
案件摘要#
1900 年 8 月，David Hilbert 在巴黎國際數學家大會（ICM）上發表了 23 個問題—— 這份清單被後世稱為「數學的聖經」。其中第十題是一道幾何問題：
它本質上是「求根的演算法」的問題。Hilbert 在 1928 年的補充中把它修改為：
這個問題在 1900 年被列為「顯而易見」的基礎問題，1960 年代被數論家解掉：
Hilbert 第十題是「可計算性」與「不可計算性」的分水嶺。
前因 -- 為什麼會有這個案子#
- Hilbert 的演講（1900 年 8 月 8 日）：
「Hilbert 在 ICM 1900 上的演講，題為『數學的未來問題』， 23 個問題被視為 20 世紀數學的綱領。」 其中 7 個是千禧年級的（千禧年難題中，Hilbert 的問題佔了 2 個）。
- 第十題的原始措辭（1900）：
「第十題。給定一個 \(n\) 維整點多項式方程式的解，如何決定這些解的『存在性』？ 更精確地：給定一個有理係數的代數函數 \(f(x_1,\dots,x_n)\) ， 給定一個正整數 \(\phi\) ，求一個整數 \(m\) 使得
換言之——請給一個『列表算法』。」 核心是「存在一個有限的機械程序」的問題。 - 1928 年的 Hilbert 修改： 在布魯塞爾 ICM 上，Hilbert 把第十題改寫為一個更簡潔、更根本的版本：
更精確的版本（Single Machine Number Problem, SMNP, 1973 Matiyasevich）：
或「是否只含 0,1 的數字」——這個版本更簡潔，也更根本。 - 為什麼這個版本更根本？： 因為它是一個「數學問題是否可計算」的問題—— Hilbert 意識到第十題的真正困難是「可計算性」本身。
線索與推理 -- 數學式、程式、理論#
第一條線索：H10 的 SMNP 形式#
給定一個有理數 \(r \in (0,1)\) ，判定：
- 這個問題看起來很簡單，但 Matiyasevich（1973）證明它是 Undecidable（不可判定）。
- 更強的結果：
因為 \(\text{SMNP} \equiv \text{是否存在演算法決定 0 的存在} \Longrightarrow \text{Gödel 的不可判定性用例}\) .
\boxed{\text{所有遞歸可枚舉集（r.e. set）} = \text{存在多項式方程的整數解集}}
\text{SMNP 不可判定} \Longleftrightarrow \text{存在不可判定的遞歸可枚舉集} \Longrightarrow \text{H10 不可判定}.
\text{「只含 0,1 的數字」的存在性} \text{不可判定} \Longrightarrow \text{H10 不可判定}.
$$ 證明大綱： 1. 若存在一個可判定的演算法 \(A\) 判定 H10（SMNP）， 2. 則所有遞歸可枚舉集都可判定（用 MRDP 把它編碼成 H10 的實例）。 3. 但 H10 的程序無法判定 Gödel 句子的停機問題（Church-Turing 不可判定性）。 4. 矛盾。故 H10 不可判定。
第三條線索：對數學的深遠影響（1930–1970）#
H10 的不可判定性，把 Hilbert 的「可計算性計劃」徹底埋葬： $$
\text{Hilbert 第十題（Undecidable）} \xrightarrow{1960-70s} \text{MRDP 定理} \xrightarrow{} \text{計算數學的「不可解性」邊界}.
\text{Hilbert 第十題不可判定} \Longrightarrow \text{不是「沒解」，是「原理上無法有解」}.
$$ 這是「數學問題的不可判定性」的第一個幾何/算術的例子。
理論與數學式：不可判定性的邏輯結構#
Hilbert 第十題（1900）：找一個演算法，判定任意整係數多項式方程 （Diophantine 方程） $$
P(x_1, \dots, x_n) = 0
\text{遞歸可枚舉集} = {\, \vec{x} : \exists\, \vec{y}\;\; P(\vec{x}, \vec{y}) = 0 \,} \quad \Longrightarrow \quad \text{H10 不可判定}.
$$ 「不可判定」不是「還沒找到演算法」，而是「原理上不存在演算法」—— 若 H10 可判定，就能判定 Gödel 句子的真假，矛盾。
| 問題 | 形式 | 可判定性 |
|---|---|---|
| 一元二次 \(x^2 = 4\) | 根的存在性 | 可判定（±2 可算） |
| 二元二次 \(x^2 + y^2 = n\) | 兩平方和 | 可判定（數論和定理） |
| 一般 Diophantine 方程 | \(P(x_1,\dots,x_n)=0\) | 不可判定（MRDP 1970） |
| 停止問題（Turing, 1936） | 程式是否停止 | 不可判定 |
H10 是「數學問題的邊界」的第一個算術例子——有些問題不是難，是不可能。
結案 -- 後果與影響#
- Hilbert 第十題的命運：
- 1900：列為 23 問題的第十題（列表算法）。
- 1928：Hilbert 自己修改為 SMNP 版本（更根本）。
- 1960–1970：Davis、Putnam、Robinson、Matiyasevich（MRDP 定理）證明其不可判定。
- 1973：Matiyasevich 明確說：H10 不可判定。 $$
\text{H10（1900）} \xrightarrow{\text{不可解}} \text{MRDP（1970）} \xrightarrow{} \text{計算數學的邊界（1970s）}.
\text{Hilbert 計劃（形式化一切）}} \xrightarrow{\text{Gödel}} \text{邏輯計劃的頂點}} \xrightarrow{\text{不可判定}} \text{「計劃」的失敗}.
\text{幾何（空間）} \xrightarrow{\text{H10}} \text{計算（時間）}.$$ - 歷史定位：Hilbert 第十題是「Hilbert 計劃」的最後一顆子彈—— 它引出了 20 世紀數學最深的三個問題：H10、Gödel 不完備、 \(P\) vs \(NP\) 。 這三個問題把 20 世紀數學推到了「可計算性的邊界」。
關鍵人物與文獻#
- D. Hilbert：Grundlgen der Geometrie（1899）；Mathematische Probleme（1900）；SMNP 版本 (1928)。
- M. Davis：Hilbert's Tenth Problem（1950）；H. Putnam：J. Symbolic Logic (1960)。
- J. Robinson：MRDP（1962）——「不可判定性的編碼」。
- Y. Matiyasevich：MRDP 定理（1970）；Hilbert's Tenth Problem（1973）。
- K. Gödel：不完備定理（1931）；C. H. Papadimitriou：Computational Complexity (1994)。
- 相關案件：
1899-希爾伯特幾何基礎.md、計算理論/1936-圖靈機.md、2003-佩雷爾曼龐加萊猜想.md。