1936 圖靈機#
環節標註：數學⇒技術——為回答一個純數學問題而發明的抽象機器，成為電腦的理論藍圖；兼技術⇒數學。
案發現場#
1936 年，劍橋國王學院，23 歲的艾倫·圖靈（Alan Turing, 1912–1954）提交論文〈論可計算數及其在判定問題上的應用〉（On Computable Numbers, with an Application to the Entscheidungsproblem）。
他攻擊的目標是希爾伯特綱領的最後堡壘——可判定性問題（Entscheidungsproblem）：是否存在一套機械程序，能對任何數學命題判定真偽？（見 1900-希爾伯特23問題.md）
這個問題有一個致命的前置困難：「機械程序」是什麼？程序這個概念人人直覺上懂，但要證明某種程序不存在，必須先把「程序」變成嚴格的數學對象。模糊的日常概念無法被否定——就像要證明「永動機不存在」，得先定義什麼是機器。
偵查過程#
圖靈的破案手法，是把「計算」拆到不能再拆的原子。
第一層：圖靈機的發明。 圖靈問：一個人拿紙筆計算時，到底在做什麼？答案是三件事——看著紙上某個符號、根據當前心狀（狀態）改寫或移動、進入下一個心狀。於是他定義了一台極簡機器：一條無限長的紙帶（分成一格一格）、一個讀寫頭、一張有限狀態轉移表。每一步只做一件事：讀一格、寫一格、左移或右移一格、換狀態。就是這麼一台簡陋到近乎可笑的機器，圖靈主張：任何機械可計算的函數，這台機器都算得出來——這就是後來被稱為「圖靈—丘奇論題」的斷言。
第二層：停機問題不可判定。 有了嚴格定義，否定性證明水到渠成。圖靈證明：不存在一台圖靈機，能對任意輸入的程式判定「它會停機還是無限跑下去」。證明是優雅的反證法——假設這台「停機判定機」存在，就把它餵給「如果判定我會停機我就無限循環」的搗蛋程式，立即自相矛盾。數學中存在不可計算的問題——希爾伯特的可判定性問題就此判死：如果連停機都不可判定，判定任意命題的真偽更不可能。哥德爾在 1931 年用邏輯證明的極限（見 1900-希爾伯特23問題.md），圖靈用機器重新證了一遍，而且更直觀。
第三層：意外的寶藏——通用機器。 為了證明不可判定，圖靈先構造了一台通用圖靈機（Universal Turing Machine）：它的紙帶上裝載另一台圖靈機的轉移表（即「程式」），就能逐一模擬那台機器的每一步。這是史無前例的斷言：存在一台固定的機器，可以計算任何可計算的東西——只要換紙帶上的描述。硬體不必為每個任務重新建造；任務以「程式」的形式寫進資料。這正是電腦與一切軟體的理論核心：程式即資料，機器即模擬器。
結案報告#
希爾伯特的問題被判死，但死刑執行書上附帶了一份人類歷史上最值錢的藍圖：
- 電腦的理論藍圖——通用圖靈機證明「通用計算」存在。馮紐曼在 ENIAC 之後設計的儲存程式架構（1945），正是通用圖靈機的工程實現（見 1946-ENIAC.md）；電晶體（1947-電晶體.md）與微處理器（1971-微處理器.md）則把這台機器越縮越小、越算越快。
- 可計算性理論誕生——「什麼能算、什麼不能算」成為數學分支；停機問題不可判定成為一切「不可能證明」的標尺（Rice 定理、複雜性理論的 P vs NP 都源於此）。
- 演算法成為科學對象——「程序」被數學化之後，演算法的效率、正確性、複雜度都能被嚴格研究，電腦科學作為一門數學化的工程學科就此奠基。
- 哲學餘波——心靈是否也是一台圖靈機？圖靈 1950 年的「模仿遊戲」（圖靈測試）把這個問題正式搬上檯面。
一台為證明「不可能」而發明的紙帶機器，最終成為改變一切的機器之母。
促進鏈分析#
- 數學⇒技術：圖靈機這個純數學抽象證明「通用計算」存在，直接成為電腦的理論藍圖——儲存程式架構、軟體、編譯器、乃至手機裡的每一行程式碼，都是數學的技術物化（見 1900-希爾伯特23問題.md、1946-ENIAC.md）。
- 數學⇒數學：可計算性理論內部自我促進——停機問題→Rice 定理→複雜性理論（P/NP），一個否定性結果成為一整個領域的起點。
- 技術⇒數學：真實電腦的出現反哺數學——數值分析、蒙特卡羅方法、電腦輔助證明（四色定理，1976）；同時，電腦的工程實踐（除錯、無限迴圈）又讓停機問題從抽象定理變成每天的現實。
- 數學⇒實驗：可計算性為「模擬實驗」立法——既然通用機器能模擬任何過程，電腦模擬（氣候、核爆、蛋白質摺疊）就成為理論與實驗之外的第三種科學方法。
證據與工具#
# 實作一個極簡圖靈機模擬器：二進位加一（00011 -> 00100，即 3+1=4）
# --- 第一部分：圖靈機的定義 ---
# 紙帶：字元列表；讀寫頭：位置索引；狀態 + 轉移表
# 轉移表：{(狀態, 讀到) : (寫入, 移動方向, 新狀態)}
# 任務：二進位數加一（從最右端開始）
TRANSITIONS = {
# 狀態 q0：往左掃過最低位，準備加一
("q0", "0"): ("1", "停", "HALT"), # 0+1 無進位，寫 1 停機
("q0", "1"): ("0", "L", "q0"), # 1+1 進位：寫 0，繼續往左
("q0", "_"): ("1", "停", "HALT"), # 全是 1（如 111=7）=> 進位出新位 => 1000=8
}
def turing_machine(tape, head, state, transitions, max_steps=100):
tape = list(tape)
for step in range(max_steps):
symbol = tape[head] if 0 <= head < len(tape) else "_"
if (state, symbol) not in transitions:
print(f" 步驟 {step}: 無規則可循，停機（狀態 {state}）")
return tape, head
write, move, new_state = transitions[(state, symbol)]
# 圖靈機的三個原子動作：寫一格、移一格、換狀態
if 0 <= head < len(tape):
tape[head] = write
elif symbol == "_" and write != "_":
tape.append(write)
print(f" 步驟 {step}: 讀到 '{symbol}' → 寫 '{write}'、"
f"{'左移' if move == 'L' else '移動' if move != '停' else '停'}、"
f"狀態 {state} → {new_state} 紙帶: {''.join(tape)}")
if new_state == "HALT" or move == "停":
return tape, head
head += -1 if move == "L" else 1
state = new_state
return tape, head
# --- 第二部分：執行——二進位加一 ---
print("--- 圖靈機執行：二進位 011 (3) 加一 ---")
tape, _ = turing_machine("011", head=2, state="q0", transitions=TRANSITIONS)
result = "".join(tape).lstrip("0") or "0"
print(f"結果：{result}（二進位）= {int(result, 2)}（十進位）")
print("\n--- 圖靈機執行：二進位 111 (7) 加一（全進位）---")
tape, _ = turing_machine("111", head=2, state="q0", transitions=TRANSITIONS)
result = "".join(tape).lstrip("0") or "0"
print(f"結果：{result}（二進位）= {int(result, 2)}（十進位）")
# --- 第三部分：通用性的意義 ---
print("\n--- 通用性的意義 ---")
print("這台機器的『硬體』只有一個：讀、寫、移、換狀態。")
print("換一張 TRANSITIONS 轉移表（= 程式），它就能做任何計算：")
print(" - 換成減法表 → 做減法")
print(" - 換成搜尋表 → 窮舉丟番圖方程（見 1900-希爾伯特23問題）")
print(" - 換成模擬表 → 模擬任何其他圖靈機（通用圖靈機）")
print("程式即資料、機器即模擬器——這就是 1946 年 ENIAC 之後")
print("儲存程式電腦（馮紐曼架構）的理論藍圖。")
print("而『某些程式會不會停機』無法判定——圖靈 1936 年證明的，")
print("正是這台無所不能的機器的極限。")