1.3 決定性的問題與普林斯頓之行（1935–1936）#
1935 年 3 月，二十二歲的圖靈當選劍橋國王學院院士。有了院士資格與微薄薪俸，他獲得了最奢侈的東西：自由地選一個問題，做四年。他選的問題，是數學基礎的聖杯——希爾伯特（David Hilbert）的可判定性問題（Entscheidungsproblem，判定問題）（→ 詳見《希爾伯特傳記》）。
Hilbert 的問題：什麼是「機械地可判定」#
1928 年，Hilbert 與 Ackermann 在《數理邏輯原理》中把判定問題提煉為：是否存在一個機械程序，對任意一階邏輯語句，都能在有限步驟內判定其真假（可否證明）？
- 若答案是「有」，則整個數學可被一架「推理機器」自動窮盡；
- 若答案是「無」，則數學永遠有機器不可企及之處；
- Gödel 1931 年的不完備定理已經重創了 Hilbert 計畫，但嚴格說來，Gödel 證明的是「不完備」，還沒有人證明「不可判定」——需要一個精確的「機械程序」定義。
圖靈的洞見#
圖靈問了一個前人沒問過的問題：人類計算員（computer，當時指人）按指令工作時，到底在做什麼？
- 他在紙上有格子，眼睛注視一個格子，處於有限個心理狀態之一，依所見符號與狀態寫下符號、移動、換狀態；
- 那麼任何「機械程序」都可以抽象為一個在無限紙帶上讀寫符號的有限狀態機——這就是圖靈機（Turing machine）；
- 「可判定」於是化為「存在一臺圖靈機，對所有輸入在有限步停機並給出正確答案」。
1936 年春：論文寫成，消息傳來#
1935–36 學年，圖靈埋首攻關。1936 年 4 月，他提交了論文〈論可計算數及其在判定問題上的應用〉（On Computable Numbers, with an Application to the Entscheidungsproblem）初稿。就在此刻，劍橋的紐曼（M. H. A. Newman）帶來消息：美國普林斯頓的 Alonzo Church 已經用 λ 演算發表了同一個否定結果（→ 詳見《丘奇傳記》）。
- 一般學者可能就此放棄；紐曼卻看出圖靈的工作遠不止於結論：
- Church 的 λ 演算是精巧的函數系統，而圖靈機是對「計算」本身的概念分析——它同時是一臺可以被造出來的機器；
- 紐曼建議圖靈親赴普林斯頓，跟 Church 學習。
flowchart LR
A["1935 當選院士"] --> B["鎖定<br/>Entscheidungsproblem"]
B --> C["分析『人類計算員』<br/>→ 圖靈機概念"]
C --> D["1936.4 完成初稿"]
D --> E["紐曼轉達：<br/>Church 已解"]
E --> F["結論重疊<br/>但機器概念更強"]
F --> G["1936.9 赴普林斯頓<br/>師從 Church（見 2.2）"]出發前：普林斯頓之行的波折#
- 圖靈的導師申請一波三折：他原本想跟 Gödel，但 Gödel 未到普林斯頓；最終落在 Church 門下；
- 父親 Julius 起初反對兒子赴美，認為院士應安守劍橋；圖靈以「普林斯頓是邏輯學的世界中心」說服了他；
- 1936 年 9 月，他登上遠洋客輪，帶著一份將重新定義「計算」的手稿——以及在船上暈船暈得一塌糊塗。
論文的雙重命運#
1936 年 11 月，論文經 Church 修改建議後提交倫敦數學會會刊（Proceedings of the London Mathematical Society），分兩部分於 1936 年 11 月與 12 月刊出。其命運有二：
- 當下：反響平平，英國數學界視之為邏輯學的專門工作；
- 長期：它成為計算機科學的「創世文獻」——1945 年後每一臺電腦，都是圖靈機的工程化身（見 3.3、5.3）。
論文中最著名的兩個技術成果：
- 可計算數的普遍化：存在通用圖靈機（universal machine），可模擬任何其他圖靈機——「軟體」的概念在此誕生；
- 對角線法與停機問題：不存在能判定任意圖靈機是否停機的程序，從而 Entscheidungsproblem 無解（詳見 2.1）。
事件關聯與前因後果#
| 年份 | 事件 | 後續影響 |
|---|---|---|
| 1935.3 | 當選國王學院院士 | 獲得自由攻題的資源 |
| 1935 | 選定 Entscheidungsproblem | 從「證明」邊界轉向「計算」邊界 |
| 1936.4 | 完成論文初稿；Church 消息傳來 | 競爭觸發赴美 |
| 1936.9 | 搭船赴普林斯頓 | 進入世界邏輯中心（見 2.2） |
| 1936.11–12 | 論文分兩部分刊出 | 圖靈機、通用機、停機問題誕生 |
因果：這段歷史最富戲劇性的因果是競爭的推動——若非 Church 搶先，圖靈未必赴美，未必與 von Neumann、Church 直接共事，也未必有「Church–Turing 論題」的合流（見 2.2）。而紐曼的判斷是關鍵中介：他看出「誰先發表結論」遠不如「誰給了計算一個可操作的本體」重要。歷史證明紐曼是對的——λ 演算活在理論裡，圖靈機活在每一臺電腦裡。
與同時代的對照#
| 人物 | 1936 年的動作 | 與圖靈的交會 |
|---|---|---|
| Church | λ 演算解判定問題 | 導師（→ 詳見《丘奇傳記》） |
| Gödel | 對 Church 模型存疑，1938 才接受圖靈機 | 圖靈機成為 Gödel 認可的標準化定義 |
| von Neumann | 從量子力學轉向流體與經濟學 | 日後提供 IAS 與電腦舞台（→ 詳見《馮紐曼傳記》） |
| 香農 | MIT 碩士論文（開關電路） | 「邏輯的機器化」與「機器的邏輯化」同年呼應（→ 詳見《香農傳記》第 2 章） |
小結#
- 1935–36 年，圖靈用「人類計算員的抽象化」回答了 Hilbert 的問題：可判定性無解；
- 論文給出的不只是否定答案，更是一個正面遺產——圖靈機與通用機，即「程式」與「電腦」的數學原型；
- Church 的搶先沒有埋沒圖靈，反而把他送進了普林斯頓的關係網；
- 1936 年秋，二十三歲的圖靈帶著世界上最重要的計算理論橫渡大西洋——下一段，普林斯頓將給他導師、同儕，以及一個險些改變他人生選擇的邀留（見 2.2）。