一堆要求被解釋的巧合
回頭走過前三篇，注意那個模式。一台只有一條紙帶的圖靈機，和一台有五十條紙帶的圖靈機，計算出來的語言一樣（多紙帶頂多買到多項式級的加速，從不帶來新能力）。一台非確定型圖靈機，算不出任何確定型算不出的東西——確定型機器只是付出指數級的減速，去搜尋那棵猜測之樹。接著 lambda 演算、遞迴函數、暫存器機或計數器機、甚至細胞自動機與你最愛的程式語言，結果界定出的，竟是同一類可計算函數。這些模型沒有一個是為了配合別的而設計的。它們在不同年代、由不同的人、帶著全然不同的直覺被發明出來。
當對同一個模糊想法、各種天差地別的形式化嘗試，不斷落在一模一樣的答案上，那就不是運氣——那是證據，說明那個模糊想法是真實的、而且我們抓住了它。這裡的模糊想法，是整門學科裡最古老的一個：「用一套機械程序去計算某樣東西」究竟是什麼意思？在 1930 年代之前，「演算法」是個非正式的概念——一份書記員能拿紙、筆、不靠任何創意就照著做的食譜。上面那些模型，都是把這個概念弄精確的嘗試。它們全都吻合這件事，是計算理論裡最核心的經驗觀察，而它在呼喊一個名字。
論題究竟主張什麼
邱奇–圖靈論題主張：這些形式模型完整地捕捉了那個非正式概念——凡是能被「任何」機械的、有限的、一步接一步的程序所計算的東西——不論是由一個有無限紙與時間的書記員、由任何想像得到的機器、由任何語言裡的任何演算法——都能被一台圖靈機計算。一句話：直覺上可計算的函數，恰恰就是圖靈可計算的函數。正是這一點，讓我們不必再寫「可被圖靈機、或暫存器機、或……計算」，而能直接寫可判定或「可計算」，篤定這個詞在每一個合理模型底下都指同一件事。
仔細看這道等式的兩邊。一邊，「圖靈可計算」，是個精確的數學對象——我們有定義，能對它證明東西。另一邊，「直覺上可被機械程序計算」，則是刻意保持非正式的——它是個關於真實世界、關於「有效程序」這個詞對數學家而言一向意味著什麼的主張。論題是一座架在「形式概念」與「非形式概念」之間的橋。正是這個結構，讓它佔據一個奇怪的地位，那正是下一節要談的。
為什麼它是論題，而不是定理
這裡是幾乎每個人第一次都會絆倒的微妙處。我們已經「證明」了——帶著完整的數學嚴謹——lambda 演算、圖靈機、暫存器機界定出同一批函數；那些是貨真價實的定理，因為三者都是你能拿來比對的精確定義。但邱奇–圖靈論題不是其中之一。它無法被證明，因為它的一邊——「每一種可能的機械程序」——並不是一個數學對象。你沒辦法對一個模糊的直覺概念作量化、再對它證一條定理。要證明它，你得先把「機械程序」形式化，可那個形式化又不過是「再多一個模型」，你還得從頭再用非正式的方式論證它的等價性。那份非正式性，從來不會完全消失。
那它到底是什麼樣的陳述？它更接近一條自然律，而非一條定理——一個關於現實的主張，我們因累積的證據而壓倒性地相信它，但它原則上是可被否證的。證據浩如煙海：九十年來，人們努力想打破這個模式，所提出過的每一個「有效計算」模型，結果不是與圖靈機等價，就是嚴格地更弱。要反駁這論題，只需有人拿出一套真正機械的程序——某樣拿紙的書記員照著清楚的有限規則就能執行的東西——去計算一個沒有任何圖靈機算得出來的函數。從來沒人辦到。這就是我們接受它的原因。但「因壓倒性證據而接受」並不等於「證明」，一門誠實的課程從不把兩者攪混。
圖靈完備：把那份能力借過來
一旦你接受圖靈機標出了機械計算的天花板，一個極其實用的詞就掉了出來。一個計算模型若能模擬任何一台圖靈機——等價地說，若它能計算每一個圖靈可計算的函數——它就是圖靈完備的。依論題，圖靈完備就是一個模型所能達到的最強：它能算出一切「根本算得出來」的東西。這就是為什麼我們能隨口卻準確地說，Python、C、Java、lambda 演算，甚至一些沒人會拿來寫程式的玩具，「能力全都一樣強」。它們在便利與速度上天差地別，可在「終究能計算什麼」上，一分一毫都不差。
證明某樣東西圖靈完備，通常是一個模擬論證，而那套配方正是貫穿整個這一階梯的那一套。要顯示模型 M 圖靈完備，就顯示 M 能模仿一台圖靈機：把紙帶表示出來（常用兩個堆疊、或一個串列、或一個大數），把讀寫頭的位置與目前狀態表示出來，並顯示對每一條圖靈轉移 delta(q, a) = (p, b, 方向)，M 裡都有一個對應的步驟，以同樣的方式更新那個被表示的組態。若 M 能忠實地一步步推進一台被表示的圖靈機到永遠，M 就能算出那台圖靈機算得出的任何東西。同一招反過來跑，正是我們當初證明那些競爭模型「等於」圖靈機、而不只是在例子上湊巧吻合的方法。
Turing machine M simulated inside model X
------------------ --------------------------
tape ... a b | c d ... -> leftpart = [b, a, ...] (a stack)
head over c current = c
rightpart = [d, ...] (a stack)
state q -> state = q
one TM step delta(q,c) = (p, x, RIGHT):
write x at head, go right, enter p
becomes in X:
current := x ; push current onto leftpart
current := pop(rightpart) ; state := p
X is Turing-complete <=> it can keep doing this forever, faithfully.兩條論題，以及通往通用機器的橋
把兩個聽起來相似、其實不同的主張分開來，是值得的。邱奇–圖靈論題談的是「根本上」什麼可計算，不理會效率。另有一條更強、且分開的猜想——延伸（或強）邱奇–圖靈論題——它額外加上一個關於代價的主張：任何合理模型都能被一台圖靈機以「至多多項式時間的減速」模擬，因此「可有效率地計算」也是與模型無關的。普通版論題立足極穩；延伸版則確實有爭議。量子電腦是那個著名的壓力點：它們似乎能比任何已知古典演算法更快地解某些問題（如質因數分解），這會損及「延伸」版——但很重要地，量子電腦並不被認為能算出任何圖靈機算不出的東西，所以普通版論題毫髮無傷，而且量子電腦也不被認為能有效率地攻破 NP 完全問題。
- 看見一堆等價模型（紙帶、非確定性、lambda 演算、暫存器機、真實語言）全都計算同一批函數——這由前幾篇的證明確立。
- 把那個觀察提升為一個關於「所有」有效程序的主張：邱奇–圖靈論題。基於壓倒性證據（而非證明）接受它，因為它的一邊是非正式的。
- 把它兌現成一個可用的詞：一個模型若能模擬圖靈機，便是圖靈完備的，而那是任何模型所能達到的最強。
- 把效率分開來看：延伸版論題（多項式時間模擬）是另一個、有爭議的主張，量子計算對它構成真實的壓力。
還有一個後果重要到足以在下一篇獨佔一席。若每一個合理模型都能被模擬，那麼特別地，一台圖靈機就能模擬一台圖靈機。這不是廢話——它意味著我們能造出「一台」固定的機器，它接收任何別的機器的一份描述，外加那台機器的輸入，然後忠實地把它跑起來。要做到這點，我們得先把一台圖靈機寫成一個字串，就像我們寫資料那樣，這正是把機器編碼的想法。其成果就是通用圖靈機——每一台儲存程式電腦在理論上的祖先，是那個把「一個任務一台機器」變成「一台機器、依任務寫程式」的東西。邱奇–圖靈論題告訴你這種通用性根本是可能的；第 5 篇則把那台機器造出來。