1976 Michael Rabin & Dana Scott —— 自動機理論的雙子星偵探#

「1959 年，兩個 20 多歲的年輕人在同一篇論文裡，寫下了計算理論的半壁江山。一篇論文如何同時孕育隨機演算法與程式語言語義？」

案件檔案#

1956 年，哈佛普林斯頓時代的兩位青年在普林斯頓共處一室。問題：Church–Turing 論題確立了「可計算」的邊界（λ演算史 1936 案），但計算的內部結構——什麼是狀態、什麼是機器的行為類型—— 仍是迷霧。

Rabin & Scott 證明：非決定性有限自動機（NFA）與確定性自動機（DFA）承認完全相同的語言，且 NFA 可指數級轉為 DFA （子集構造）。

語言等價性：L(NFA) = L(DFA) = 正則語言
狀態數爆炸：n 狀態 NFA → 最多 2ⁿ 狀態 DFA

非決定性看似是幻術（機器「同時」走多條路），但它是描述的壓縮：以指數少的狀態描述同樣能力。這個「猜測—驗證」的抽象後來成為 NP 理論的心象基礎（1985 Karp 案、2023 Wigderson 案）。

Rabin 之問：既然確定性有時太笨，能否讓機器擲骰子？

1976 年 Miller–Rabin 質數測試：以隨機基底檢驗費馬小定理的變體，誤判率 ≤ 4^(−k)。沒有已知的多項式時間確定性演算法（AKS 2002 才出現，但實務上仍用隨機版）。
1981 年 Rabin 指紋匹配：字串匹配 O(n) 期望時間—— 隨機演算法學派（Las Vegas / Monte Carlo）的奠基。
這啟發 Yao（2000 案）的偽隨機性理論與複雜度類 BPP 的研究。

Scott 之問：程式的「意義」是什麼？ 他與 Strachey 建立指稱語義（λ演算史 1972 案），並為遞迴定義構造數學模型 D∞ 域（domain）：用完備偏序集（CPO）+ 最小不動點解釋

f : D → D  遞迴程式的語義 = f 的最小不動点 lfp(f)
           = ⋃ fⁿ(⊥)   （⊥ 為「未定義」，n→∞）

遞迴不再神祕：程式 = 方程式，執行 = 迭代逼近不動點。

同一篇 1959 論文的兩位作者走向兩極：Rabin 把機率帶入計算，Scott 把數學語義帶入程式。一案兩破，恰證自動機理論是整座理論計算機科學大廈的地基。