1936 - Turing 機（可計算性的數學定義）#

案件摘要#

1936 年，23 歲的 Alan Turing（1912–1954） 在《倫敦數學學會會刊》發表 On Computable Numbers, with an Application to the Entscheidungsproblem：

\[ \boxed{\text{定義了一台假想的機器，它涵蓋了「一切可計算」}} \]

圖靈機的構造驚人地簡單： - 一條無限長的紙帶（分格，每格一個符號）； - 一個讀寫頭（讀、寫、左移、右移）； - 一張狀態表（有限的規則）。

\[ \text{無限紙帶} + \text{有限規則} = \text{一切可計算}. \]

他用這台機器證明了 Hilbert 的判定問題（Entscheidungsproblem）無解—— 停機問題（halting problem）不可判定。十年後，這台假想的機器變成了真實的電腦（1946 ENIAC）—— 圖靈機是資訊科學的「創世紀」。

前因 -- 為什麼會有這個案子#

Hilbert 的判定問題（1928）： Hilbert 在 1928 年提出判定問題（Entscheidungsproblem）：

\[ \boxed{\text{「是否存在一個演算法，判定任何數學命題的真偽？」}} \]

這是 Hilbert 計畫（形式化一切數學）的核心—— 若判定問題有解，則數學可以被機械化。 - Gödel 的不完備（1931）： Gödel 證明任何足夠強的公理系統都有不可證明的真命題—— 但 Gödel 的證明用的是遞迴函數（哥德爾編碼），語言抽象。

\[ \text{Gödel（1931）：不完備定理} \xrightarrow{\text{Turing（1936）：停機問題}} \text{同源的不同表述}. \]

Turing 的洞察（1935）： Turing 在劍橋聽 Max Newman 的課（Hilbert 問題的介紹），意識到：

\[ \text{「計算」這個直覺概念需要一個**數學定義**}. \]

他設計了一台最簡單的機器——只用紙帶與狀態表—— 並證明它涵蓋一切可計算（Church–Turing 論題）。 - Church 的平行發現（1936）： Alonzo Church 用 λ 演算（lambda calculus）在同年證明了同一結果—— 兩人的定義被證明等价（Church–Turing 論題）：

\[ \text{圖靈機} \equiv \lambda \text{ 演算} \equiv \text{遞迴函數}. \]

線索與推理 -- 數學式、程式、理論#

第一條線索：圖靈機的形式定義#

圖靈機 = \((Q, \Gamma, b, \Sigma, \delta, q_0, F)\) ： - \(Q\) ：有限狀態集合； - \(\Gamma\) ：紙帶符號集（含空白 \(b\) ）； - \(\Sigma \subseteq \Gamma \setminus \{b\}\) ：輸入符號集； - \(\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}\) ：轉移函數； - \(q_0\) ：初始狀態； \(F\) ：接受狀態集。

計算過程：讀寫頭讀當前格 → 查 \(\delta\) → 寫新符號、移動、轉狀態。

第二條線索：通用圖靈機（Universal Turing Machine）#

Turing 的最強結果：存在一台通用圖靈機 \(U\) ：

\[ U(\langle M\rangle, x) = M(x) \quad\text{（模擬任何圖靈機 } M\text{）}. \]

\(\langle M \rangle\) ：機器 \(M\) 的編碼（描述）；
這是「軟體」概念的誕生——程式（機器的描述）可以被當作資料輸入！

\[ \boxed{\text{程式 = 資料（軟體的革命性思想）}} \]

這是 1946 ENIAC 之後一切電腦的理論基礎—— 儲存程式電腦（von Neumann 架構，1945）的數學預言。

第三條線索：停機問題的不可判定性#

定理（Turing, 1936）：停機問題不可判定：

\[ \boxed{\text{不存在演算法 } H(M, x) \text{ 判定 } M(x) \text{ 是否停機}} \]

對角線反證法（與 Gödel 的方法同源）： 1. 假設存在 \(H\) 判定停機； 2. 構造「矛盾機器」 \(D\) ：對輸入 \(x\) ，

\[ D(x) = \begin{cases} \text{停機} & \text{若 } H(x, x) = \text{不停機} \\ \text{無限迴圈} & \text{若 } H(x, x) = \text{停機}\end{cases} \]

問： \(D(\langle D\rangle)\) 停機嗎？

\[ D(\langle D\rangle) \text{ 停機} \Longleftrightarrow H(\langle D\rangle, \langle D\rangle) = \text{不停機} \Longleftrightarrow D(\langle D\rangle) \text{ 不停機}. \]

矛盾！故 \(H\) 不存在。

Python：圖靈機的模擬與停機問題的反證#

# 1) 一個簡單的圖靈機模擬器：二進位加一（Increment）
def turing_increment(tape):
    """圖靈機：對二進位數加一（從最右端開始）"""
    tape = list(tape)
    head = len(tape) - 1
    state = "q0"
    while True:
        if head < 0:                 # 進位超過最左端
            tape.insert(0, '1')
            break
        sym = tape[head]
        if state == "q0":
            if sym == '1':
                tape[head] = '0'     # 1+1=0，進位
                head -= 1
            elif sym == '0':
                tape[head] = '1'     # 0+1=1，停機
                break
            else:                    # 空白，補 1
                tape[head] = '1'
                break
    return ''.join(tape)

print("圖靈機：二進位加一")
for b in ["1011", "1111", "1000", "0"]:
    print(f"  {b} + 1 = {turing_increment(b)}")

# 2) 停機問題的反證法（矛盾機器 D 的邏輯推演）
print("\n停機問題的反證法：")
print("  假設存在 halt(M, x) 判定 M(x) 是否停機")
print("  構造矛盾機 D：")
print("    D(x) = 停機   若 halt(x,x) = 不停機")
print("    D(x) = 迴圈   若 halt(x,x) = 停機")
print("  問 D(D) 停機嗎？")
print("    D(D) 停機 ⟺ halt(D,D) = 不停機 ⟺ D(D) 不停機  → 矛盾！")
print("  故 halt 不存在——停機問題不可判定 ✓")

# 3) 有限狀態機：檢查二進位字串是否含「11」
def fsm_has_11(s):
    """FSM：掃描字串，狀態 = {start, seen1, seen11}"""
    state = "start"
    for ch in s:
        if state == "start":
            state = "seen1" if ch == '1' else "start"
        elif state == "seen1":
            state = "seen11" if ch == '1' else "start"
        # seen11 是吸收狀態
    return state == "seen11"

print("\n有限狀態機（圖靈機的特例，無紙帶寫入）：")
for s in ["101", "1101", "010", "111", "0000"]:
    print(f"  '{s}' 含 11？{fsm_has_11(s)}")

# 4) 圖靈機 vs FSM 的能力對照
print("\n計算能力的階層：")
print("  FSM（正則語言）     < 圖靈機（一切可計算）")
print("  FSM 不能計數（如 aⁿbⁿ）——需要紙帶（無限記憶）")
print("  → 無限紙帶是圖靈機的關鍵：有限狀態 + 無限記憶 = 通用計算")

輸出：

圖靈機：二進位加一
  1011 + 1 = 1100
  1111 + 1 = 10000
  1000 + 1 = 1001
  0 + 1 = 1

停機問題的反證法：
  假設存在 halt(M, x) 判定 M(x) 是否停機
  構造矛盾機 D：
    D(x) = 停機   若 halt(x,x) = 不停機
    D(x) = 迴圈   若 halt(x,x) = 停機
  問 D(D) 停機嗎？
    D(D) 停機 ⟺ halt(D,D) = 不停機 ⟺ D(D) 不停機  → 矛盾！
  故 halt 不存在——停機問題不可判定 ✓

有限狀態機（圖靈機的特例，無紙帶寫入）：
  '101' 含 11？False
  '1101' 含 11？True
  '010' 含 11？False
  '111' 含 11？True
  '0000' 含 11？False

計算能力的階層：
  FSM（正則語言）     < 圖靈機（一切可計算）
  FSM 不能計數（如 aⁿbⁿ）——需要紙帶（無限記憶）
  → 無限紙帶是圖靈機的關鍵：有限狀態 + 無限記憶 = 通用計算

結案 -- 後果與影響#

可計算性的分水嶺（1936）：

\[ \boxed{\text{「可計算」有了數學定義——圖靈機}} \]

Church–Turing 論題：一切「可有效計算」的函數都是圖靈機可計算的—— 這是無法被證明的「論題」（因為「可有效計算」是直覺概念），但 90 年來沒有任何反例。 - 資訊科學的創世紀（1936 → 1946）：

\[ \text{圖靈機（1936）：假想的機器} \xrightarrow{\text{ENIAC（1946）}} \text{真實的電腦} \]

儲存程式電腦（von Neumann 架構，1945）：程式 = 資料—— 圖靈的通用機的物理實現；
編譯器（1957 FORTRAN）、作業系統（1973 UNIX）、 資料庫（1970 Codd）——全部是圖靈機思想的工程實現。
圖靈獎（1966）： ACM 於 1966 年設立圖靈獎（A. M. Turing Award）—— 資訊科學界的諾貝爾獎，以這台假想機器的發明者命名。

\[ \text{圖靈機（1936）} \xrightarrow{\text{圖靈獎（1966）}} \text{資訊科學的聖杯}. \]

AI 的誕生（1950）： Turing 1950 年發表《計算機器與智慧》（Computing Machinery and Intelligence）：

\[ \boxed{\text{「機器能思考嗎？」——圖靈測試（Turing test）}} \]

這是人工智慧的「創世紀」——McCarthy（1958 LISP、1971 圖靈獎）與深度學習（2018 圖靈獎）都是這個問題的延續。 - 密碼學與戰爭（1939–1945）： Turing 在二戰期間於布萊切利園（Bletchley Park）破解Enigma 密碼—— 縮短戰爭約兩年（歷史學家的估計）。 1952 年，他因同性戀被定罪（當時英國法律視為犯罪）， 1954 年吃氰化物自殺，年僅 41 歲。 2013 年英國女王伊麗莎白二世正式赦免； 2021 年英國 50 英鎊鈔票印上圖靈的頭像。

\[ \text{天才的悲劇} \xrightarrow{60\text{ 年}} \text{國家的道歉與致敬}. \]

理論的極限（1936–）：停機問題的不可判定性是一切不可判定性的原型：
Rice 定理（1951）：圖靈機語言的任何非平凡性質都不可判定；
Hilbert 第十題（1970）：丟番圖方程不可判定（見 幾何學/1900-希爾伯特第十題.md）；
P vs NP（1971 Cook）：可判定但「算得慢」的問題（見「1971-庫克NP完全.md」）。
歷史定位：Turing 是資訊科學的牛頓—— 他用一台假想的機器，定義了「計算」的一切；

\[ \text{數學（1936）} \xrightarrow{} \text{電腦（1946）} \xrightarrow{} \text{軟體（1957）} \xrightarrow{} \text{AI（1950/2018）}. \]

一切從那條無限長的紙帶開始。

關鍵人物與文獻#

A. M. Turing：On Computable Numbers（1936）；Computing Machinery and Intelligence（1950）；Enigma（1939–1945）。
A. Church：λ 演算（1936）——平行發現（Church–Turing 論題）。
J. von Neumann：儲存程式電腦（1945）——圖靈通用機的物理實現。
D. Hilbert：判定問題（1928）——被 Turing 否決。
K. Gödel：不完備定理（1931）——同源的不同表述。
相關案件：1948-香農資訊理論.md、1971-庫克NP完全.md、幾何學/1900-希爾伯特第十題.md、計算理論/1936-圖靈機.md。