核心概念#
本章探討計算機能力的數學邊界。如同物理學上無法超越光速極限，計算機的能力也存在由數學本身決定的硬邊界，分別由圖靈和希爾伯特劃定。
圖靈劃定計算機可計算問題的邊界#
- 圖靈的思維方式：不同於常人從邊界內向外探索，圖靈先劃定計算的邊界——邊界外的問題與計算無關，不必費心；邊界內的問題則提供了通行的解決方法
- 圖靈的兩位導師：馮·諾依曼和希爾伯特。圖靈受馮·諾依曼的《量子力學的數學原理》啟發，認識到計算對應確定性的機械運動，而人的意識是不確定的，不屬於計算範疇
- 哥德爾不完全性定理：數學不是萬能的——一些命題即便是對的，也無法用數學證明。這與圖靈同時代的數學家哥德爾在 1930 年的證明一致
- 圖靈的三個本源問題：
- 世上是否所有數學問題都有明確的答案？
- 如果有答案，能否通過有限步的計算得到？
- 對於可以有限步計算的問題，能否有一種機器讓它不斷運轉，最後停下來時就解決了問題？
圖靈劃定的邊界告訴我們：知道邊界在哪裡不是厄運而是福氣，因為我們可以集中精力在邊界內解決問題，而不是把精力耗費在尋找邊界之外不存在的答案。
希爾伯特劃定有解數學問題的邊界#
- 希爾伯特第十問題（1900 年）：任意一個（多項式）不定方程，能否通過有限步的運算，判定它是否存在整數解？
- 不定方程（丟番圖方程，Diophantine equation）：含兩個或更多未知數的方程，解可能有無窮多個
- 例一：$x^2+y^2=z^2$ 有很多正整數解（勾股數）
- 例二：$x^N+y^N=z^N$（$N>2$）沒有正整數解（費爾馬大定理，1994 年由 Andrew Wiles 證明）
- 例三：$x^3+5y^3=4z^3$ 是否有正整數解，就不那麼直觀了
- 問題的解決：1970 年，蘇聯數學家尤里·馬蒂亞塞維奇（Yuri Matiyasevich）在大學畢業的第二年就解決了第十問題，證明了一般情況下無法通過有限步運算判定不定方程是否存在整數解
第十問題的解決對認知的衝擊遠大於數學本身：世上有很多問題我們無從得知是否有解，連是否有解都不知道，就更不可能通過計算來解決。而且無法判定是否有解的問題，遠比有答案的問題多得多。
問題的層次關係#
- 所有問題 > 數學問題 > 可判定問題 > 有答案問題
- 在有答案的問題中，只有一部分可以用圖靈機（計算機）解決，稱為可計算問題
- 可計算問題中，能在工程上有限步驟內解決的更少
- 今天人工智能能解決的問題，只是有答案問題中很小的一部分
延伸閱讀：關於圖靈機#
- 圖靈機的組成：無限長的紙帶（存儲）、可左右移動的讀寫頭（處理器）、控制規則表（算法）、狀態寄存器（狀態）
- 圖靈機的數學定義：一個有序的七元組 $(Q, \Gamma, \Sigma, b, \delta, q_0, F)$，其中 $Q$ 是狀態集合、$\Gamma$ 是字母表、$\delta$ 是轉移函數等
- 等價性：如果兩種圖靈機模型 $A$ 和 $B$ 可以互相模擬，則稱它們等價。特別地，字母表只有 0 和 1 的圖靈機與任意字母表的圖靈機等價——因此二進制和其他進制的計算機解決問題的能力相同
- 丘奇-圖靈論題：有明確算法的問題，都是可以在圖靈機上完成的可計算問題
本章小結#
通過希爾伯特和圖靈對計算邊界的思考，我們看到一種不同於常人的思維方法——不是一點點向前試探邊界在哪裡，而是高屋建瓴地從理論上找到一個不能越過的硬邊界。知道邊界在哪裡，我們便能集中精力在邊界內解決問題，而非把精力耗費在尋找邊界之外不存在的答案。