我們一路蒐集到的穩健性
在這篇之前的兩篇導引，悄悄地堆起了一樁案子。〈多帶、多模型、同樣能力〉證明了給圖靈機額外的紙帶並不會讓它算出任何新東西：一台多帶機器總能在單帶上被模擬，只付出時間上多項式的代價。〈非確定型圖靈機〉則對「猜測」展示了同一件事：一台非確定型機器辨識不出任何新語言——確定型機器能模擬它，最壞付出指數級的減速。不同的紙帶數、確定型還是猜測型——每一次都是同一批可計算函數。這台機器頑強到任何「有意義」的改動都動它不得。
不過一個自然的疑慮還在。也許那一切只是近親繁殖：我們試過的每一種變體，骨子裡仍是一台穿著戲服的圖靈機——仍是一個沿著紙帶挪動的讀寫頭。或許紙帶本身就是一座牢籠，而一個建立在全然不同想法之上的模型——沒有紙帶、沒有讀寫頭、沒有狀態——說不定能越獄、算出更多。這篇導引正面迎擊這個疑慮，做法是徹底把紙帶拋諸腦後。我們將會見到一些從完全不同的第一原理出發、由不同的人、往往在圖靈之前或同時設計出來的對手，並追問那個唯一要緊的問題：它們算的比圖靈機「多」、「少」、還是「恰恰一樣」？
Lambda 演算：只用函數來計算
Alonzo Church 的 lambda 演算在 1930 年代登場，比圖靈的機器早了一點，而它長得簡直天差地別。沒有紙帶、沒有時鐘、沒有狀態——只有函數，以及一條套用它們的規則。你用三樣東西構造運算式：一個像 x 的變數；一個函數，寫成 'lambda x. 主體'，意思是「拿一個叫 x 的輸入、回傳主體」；以及一個套用 '(f a)'，意思是「把 a 餵進 f」。整個語言就這樣。沒有內建的數字、沒有布林值、沒有迴圈。它就是「一條拿輸入、產出輸出的規則」這個赤裸的想法，別無其他。
計算就是一個動作反覆進行：beta 歸約，它不過是代入。當一個函數遇上一個引數，你就複製主體、把參數的每一次出現都換成那個引數——'(lambda x. x x) a' 變成 'a a'。把這個動作一遍又一遍地跑，直到再沒有可歸約的套用，你卡住所剩下的運算式就是答案。奇蹟在於：單單這個「代入再重複」就足以編碼一切。數字變成函數（數字 3 被編碼成「把某函數套用三次」）；真與假變成從兩個輸入中挑一個的函數；甚至連遞迴都被封進一個自我套用的運算式裡。完全沒有迴圈構造，lambda 演算卻能計算圖靈機能算的每一個函數——Church 與圖靈證明了他們的兩個模型挑出的，正是同一個類別。
遞迴函數與暫存器機器
第三個對手更加樸素：遞迴函數，由 Gödel、Kleene 等人作為自然數上的純數學打造而成，視野裡完全沒有任何一種機器。你從三個簡單到不行的種子函數出發——常數零、「加一」的後繼函數，以及只從一串引數中挑出一個的投影函數——而你被允許的，恰恰只有兩種把函數黏在一起的方式：複合（把若干函數的輸出餵進另一個）與原始遞迴（用 f 在 n 的值來定義 f 在 n+1 的值，就是課本上定義階乘或加法的那套）。單憑這些規則，就能捕捉到極其廣大的一片函數，但可以證明，捕捉不到全部。
補齊這套的，是再一個運算子：最小化，那個「搜尋最小的有效 n」的動作——不斷試 n = 0, 1, 2, ...，直到某條件頭一次成立。正是那個搜尋帶來了永遠跑下去的可能（搜尋或許永遠找不到目標），也正是它，把「僅僅是原始遞迴」的函數，抬升成完整的部分遞迴函數。而 Kleene 證明了，那個完整的類別與圖靈可計算的函數完全相同。注意這個規律：那個危險、可能不停機的運算子，是完整能力的代價——正如圖靈機能永遠迴圈下去，也是它完整能力的代價。
如果函數感覺太抽象，這裡有一個長得像嬰兒電腦的模型：暫存器機器（也叫計數器機器）。它有幾個暫存器，每個裝著一個自然數，外加一支由編號指令組成的小程式——本質上就只有「把暫存器 r 加一」、「把暫存器 r 減一」、以及「若暫存器 r 為零就跳到第 k 行，否則走下一行」。整套指令集就這樣。它感覺像是被削到只剩骨頭的組合語言，哪裡都沒有紙帶，然而一台少至兩個暫存器的計數器機器就已經是圖靈完備的了。同一個終點，一條長得跟紙帶毫不相像的路。
細胞自動機與真實的語言
讓我們把多樣性推到極限。一個細胞自動機根本沒有任何中央控制——只有一長排細胞，每個裝著幾種顏色之一，全體在每一聲滴答同時依一條固定的局部規則更新，比如「我下一刻的顏色只取決於我和我的兩個鄰居」。它是一個自我組織的格網，是 Conway 生命遊戲、以及 Stephen Wolfram 那些基本規則的宇宙。這個東西，沒有程式計數器、沒有讀寫頭，肯定算得比較少吧？不：某些細胞自動機（其中包括著名的規則 110）是圖靈完備的。你能把一個輸入鋪成一個起始的顏色圖樣，再從隨之演化、漣漪般的條紋中讀出一段計算。
還有那個你早已最熟悉的對手：一種真實的程式語言。Python、C、Java、Haskell，甚至一個試算表的公式引擎——每一個，在給予無界記憶體的前提下，計算的恰恰是圖靈可計算的函數，不多也不少。這就是那個深刻結果的日常面貌。當有人說一種語言是圖靈完備的，他們指的正是這件事：它能模擬一台圖靈機，因而它能表達任何其他合理模型能表達的任何計算。這也是為什麼一些出人意料的系統——C++ 樣板的型別檢查器、帶遞迴的 SQL、甚至某些設定檔格式和幾款遊戲——會讓它們的設計者驚恐地發現，竟然不小心就成了圖靈完備。
Wildly different models -- one shared class of computable functions:
MODEL its primitive move built around
--------------------- ---------------------------------- -----------------
Turing machine write a cell, step L/R a tape + head
Lambda calculus beta reduction (substitute) functions only
Recursive functions compose / recurse / minimise numbers only
Register / counter m. inc, dec, jump-if-zero registers + lines
Cellular automaton update every cell by a local rule a grid of cells
Real prog. language run one statement whatever it has
Each pair has been PROVEN able to simulate the other:
TM <--> lambda <--> recursive fns <--> register m. <--> ...
so all of them recognise/compute the SAME set. Equivalence, not coincidence.這場匯流意味著什麼——又證明不了什麼
退一步，感受它的力道。懷著不同目標的人——研究函數的邏輯學家、把算術形式化的數學家、構想機器的工程師、觀看格網自我組織的科學家——從毫不相干的起點出發，而每一條路都抵達了同一個終點。這些不是鬆散的家族相似；每一個等價關係都是一條硬邦邦的定理、一份在某模型內模擬另一模型的具體配方。這張由證明織成的網，正是我們所說的等價的計算模型，也是支撐一個大想法、我們手上最強的證據。
- 從清單裡挑任意兩個模型——比方說 lambda 演算和圖靈機。
- 示範如何把每一台圖靈機編碼成一個逐步模仿它的 lambda 運算式，使得圖靈機能算的，lambda 演算也能算。
- 再示範反方向：寫一台對編碼後的 lambda 運算式執行 beta 歸約的圖靈機，使得 lambda 演算能算的，圖靈機也能算。
- 兩個模擬、一個方向各一，逼使這兩個可計算函數類別完全相同——而把這些成對的模擬串接起來，就把所有模型連成同一個類別。
那個大想法就是邱奇-圖靈論題：凡是能被「任何」機械的、有效的程序計算出來的東西，都能被一台圖靈機計算出來。我們所能構想的每一個形式模型都匯流於此，正是它的佐證。但這裡有個關鍵的老實話、也是下一篇導引的整個主題：這個論題「不是」一條定理。上面那些等價關係才是定理——它們連結的是形式模型與形式模型。論題連結的，卻是「圖靈可計算」這個精確的想法，與「能被任何有效方法計算」這個模糊、直覺、前數學的想法。你無法證明一個精確的東西等於一個不精確的東西；你只能蒐集排山倒海的證據、然後拒絕押注它會失敗。至今九十年來，沒有人造出過任何一個哪怕勉強說得通的物理或形式程序，能算出圖靈機算不出的東西。