等價的計算模型（equivalent models of computation）

想像不同國家的發明家彼此從不交談，各自試圖造出「最一般的計算裝置」。一個造了帶子加讀寫頭的機器，另一個造了純函數系統，第三個造了一格格閃爍的方格陣列，第四個就只用一種程式語言。你會以為他們最後得到的能力天差地遠。結果是，他們每一個計算的恰好都是同一組函數。等價的計算模型（equivalent models of computation）就是這些差異懸殊的形式系統——它們違背一切直覺，全都在「何謂可計算」周圍畫出了完全相同的那條線。

這份名單種類之豐富令人驚嘆。圖靈機（帶子、讀寫頭、狀態）。λ 演算（只有函數）。μ-遞迴函數（純算術）。計數器機與暫存器機（整數加上遞增與遞減）。標籤系統（tag systems）與 Post 系統（依規則改寫字串的開頭）。細胞自動機（cellular automata），如康威的生命遊戲或 Rule 110（細胞依局部規則更新，已被證明圖靈完備）。以及每一種尋常的通用程式語言：C、Python、Lisp、組合語言。對每一對模型，你都能寫出雙向的模擬——機器模擬語言、語言模擬機器——證明它們計算的函數完全相同。

這種匯聚是邱奇-圖靈論題核心的經驗證據。若「可計算」取決於你恰好選了哪個形式系統，這概念就會是任意的；而數十個獨立嘗試全都落在同一個類別這件事，強烈暗示它們捕捉到了機械計算中某種真實而絕對的東西。兩個誠實的提醒。其一，這裡的「等價」指計算能力相等（可計算的函數相同），而非速度相等，模擬可能帶來巨大的慢化。其二，等價性永遠是被證明的——靠明確的相互模擬；而論題本身——這個共享的類別等於非形式的「可有效計算」——仍是無法證明的主張。