3.2 阿蘭·圖靈與圖靈機：無限紙帶與狀態轉移，證明停機問題無解#

1935 年的劍橋：一個問題的嗅覺#

阿蘭·圖靈（Alan Turing, 1912–1954）在劍橋國王學院讀本科時就讀過《數學原理》與哥德爾的論文（當時是紐曼(Max Newman)開設的基礎課程把哥德爾介紹給了他）。1935 年他決定正面攻擊希爾伯特的判定問題。

他的直覺與邱奇完全不同：先回答「人類計算員在做什麼」，再談機器。

圖靈問：一個拿著紙筆的人，計算時到底能做什麼？他逐條分析（論文第 9 節）：

於是得到圖靈機（Turing machine）：

無限紙帶：一格一符號（空白算一種）
讀寫頭：讀當前格、寫、左移、右移
有限狀態集 + 轉移函數 \(\delta(\text{state}, \text{symbol}) \to (\text{new symbol}, \text{move}, \text{new state})\)
停機狀態：進入即結束

flowchart LR
    subgraph TM["圖靈機"]
    T[紙帶 □ a b □ ...] --- H[讀寫頭] --- S[有限狀態控制器]
    end
    S -->|規則表驅動| T

每一個元件都是對「人類計算」的最小抽象——沒有多餘的浪漫。這就是為什麼圖靈機比其他模型更有說服力：它不是發明的數學遊戲，而是對計算現象的現象學還原。

關鍵一步（論文第 6、7 節）：圖靈注意到，轉移規則表本身可以用編碼寫在紙帶上。於是可以造一台特殊的圖靈機 \(U\)（通用機）：

\(U\) 讀入「機器 \(M\) 的編碼 \(\langle M\rangle\) + 輸入 \(w\)」，然後模擬 \(M\) 在 \(w\) 上運行。

\[U(\langle M\rangle, w) = M(w)\]

1936 年——比第一台電腦早九年——「儲存程式」的概念已在紙上成立：資料（輸入）與程式（機器描述）同質，都是紙帶上的符號；軟體與硬體的分離、作業系統、解譯器、虛擬機，全部包含在這個公式裡。馮·諾伊曼 1945 年的架構（第 4 章）是它的工程實現，而他本人清楚知道思想源頭。

定義問題：給定機器 \(M\) 與輸入 \(w\)，是否存在演算法判斷 \(M(w)\) 會停機還是永轉？

反證（圖靈版的對角線法）。假設存在判斷器 \(\text{HALT}(M, w)\)。構造惡魔機器 \(D\)：

\[D(M):\ \text{若 } \text{HALT}(M, M) \text{ 為「停」→ 進入死循環；否則停機}\]

現在問：\(D(D)\) 會停機嗎？

所以 \(\text{HALT}\) 不存在。∎

注意結構與哥德爾證明完全同構（說謊者句 ↔ \(D(D)\)），只是繞過了算術化——機器模擬機器，比質數冪積編碼直觀得多。這也是為什麼圖靈的證明成為計算機科學的入門第一課：可讀性就是傳播力。

停機問題一成立，一大片問題連坐（歸約技術）：

工程含義：所有靜態分析工具（編譯器警告、防毒、型別檢查、AI 代碼審查）註定不完備——要嘛漏報、要嘛誤報。現代工具鏈的全部設計（樂觀/悲觀策略、可判定子集、型別系統），都是在這片不可判定海域上的航道規劃。

圖靈的天才伴隨著社會的殘酷：

1939–45 布萊切利園：領導破解恩尼格瑪密碼（設計 Bombe 解碼機），史家估計縮短二戰兩年以上、拯救數百萬生命。戰時秘密制度讓他的功績封存數十年——英雄史由檔案解密重寫，是二十世紀的常態
1948–51：曼徹斯特大學，參與首批儲存程式電腦（Manchester Baby, 1948）的程式設計；寫下第一個西洋棋程式的思路與「圖靈測試」（1950《計算機器與智能》——本書第 17 章的預言書）
1952 年被捕：同性戀在英國是刑事罪，他被定罪、接受化學閹割；1954 年中毒身亡（氰化物，普遍認為自殺）。法律與社會偏見殺死了計算機科學之父——2013 年英國女王正式赦免，2017 年「圖靈法」追溯赦免同類受害者
英國 50 鎊紙鈔（2021）印上圖靈像——一個被國家定罪的人，被印上國家的鈔票，這遲到的正名本身就是一部社會思想史

圖靈機的三重遺產：