1936：圖靈機 — 圖靈「論可計算數」與可計算性理論#

案情#

1936 年 5 月，年僅 23 歲的劍橋國王學院學生艾倫・圖靈（Alan Turing）完成論文〈論可計算數及其在判定問題上的應用〉（On Computable Numbers, with an Application to the Entscheidungsproblem），發表於 1936 年 11 月的《倫敦數學學會會刊》。他在紙上定義了一種理想化的機器——後世稱為「圖靈機」——並證明了停機問題的不可判定性。

前因#

• 1900 年希爾伯特提出著名 23 問題，其中第二問要求數學公理系統完備且可判定；1928 年他進一步提出「判定問題」（Entscheidungsproblem）：是否存在機械程序判定任意數學命題的真偽。
• 1931 年哥德爾不完備定理已擊碎「完備性」的夢想，但「可判定性」仍需更強的武器。
• 判定問題要求嚴格定義「什麼是機械可執行的程序」——這個定義本身成為難題。
• 1936 年春，丘奇（Alonzo Church）以 λ 演算先一步發表否定解答；圖靈的進路不同，他直接構造「機器」。

線索與推理#

圖靈的偵探式洞察在於：不要抽象地談「有效方法」，而要具體刻畫一個人在紙上計算時到底能做什麼。分析顯示，人類計算者的行為可以化約為——眼睛注視紙上有限個符號、依內心狀態與所見符號決定動作（寫下符號、擦除、左移或右移、改變心態）。將紙帶無限延伸、心態有限化、動作離散化，便得到一台機器。這是驚人的「現象學還原」：把人腦的計算剝到最簡骨架。接著推理分兩步：第一，證明存在一台「通用圖靈機」能讀入任何機器的描述並模擬之——這是程式（軟體）概念的誕生；第二，用對角線法證明「自己不停機的機器」無法被任何機器判定，於是停機問題不可解，判定問題亦不可解。證明的結構與哥德爾自我指涉一脈相承，卻以機器語言重述，直接指向可實作的計算裝置。

理論#

圖靈機的定義： \(M = (Q, \Gamma, b, \Sigma, \delta, q_0, F)\) ，其中轉移函數

丘奇—圖靈論題：一切「可有效計算」的函數恰為圖靈可計算函數。

停機問題定理：不存在圖靈機 \(H(M, x)\) 對所有輸入正確判定 \(M(x)\) 是否停機。證明採對角化：若 \(H\) 存在，構造

則 \(D(D)\) 導出矛盾。可計算函數的類別對照：圖靈可計算 = λ 可定義 = 遞迴函數。

後果#

1. 通用圖靈機是「儲存程式電腦」的理論藍圖：程式即資料，可被機器讀取執行。
2. 停機問題成為計算複雜性與歸約證明的基石；不可解問題族譜由此展開。
3. 1945 年後圖靈直接參與 ACE、曼徹斯特機設計，理論落地為工程。
4. 1950 年圖靈測試開啟人工智慧議題；現代作業系統、程式語言、虛擬機概念皆可溯至 1936 年。

冷案檔案#

• 時間：1936 年（論文 11 月刊出），劍橋—倫敦。
• 案由：圖靈以理想機器證明停機問題不可解，解決希爾伯特判定問題。
• 歷史定位：計算機科學的奠基石——「電腦」在成為機器之前，先成為數學。