回顧：一個定義，多種偽裝
你帶著前四篇傳來的一個悄然驚人的事實來到這一篇。多帶圖靈機只比單帶機器快上多項式倍，從不更強。非決定性圖靈機可以被一台決定性機器以至多指數級的減速來模擬，所以它辨識的語言也完全相同。而那些彷彿來自另一顆星球的競爭模型——λ 演算、遞迴函式、暫存器與計數器機器、細胞自動機，以及每一種真實的程式語言——結果計算出來的，恰恰是同一套函式。這張彼此呼應的網就是模型的等價性，也是邱奇-圖靈論題的實證骨幹。
回想一下，這個論題不是你能證明的定理。它主張「直覺上可計算」——凡是人或機器原則上能透過遵循某個有限程序算出來的東西——與「圖靈可計算」是同一回事。右邊是一個精確的數學物件；左邊是一個關於「有效程序」本質的非形式觀念，所以沒有任何證明能架起兩者之間的橋。我們手上有的，是壓倒性的證據：任何人曾提出的每一個模型，都落在同一個地方。本篇補上那份證據的拱頂石，並在這麼做的同時，把整個電腦科學中最實用的觀念交到你手上。
機器只是資料：把 M 編碼成字串
改變一切的這一步在此。一台圖靈機是一個有限的物件：一個有限的狀態集合、一個有限的帶字母表、一個起始狀態、接受與拒絕狀態，以及一張有限的轉移規則表，每條形如 delta(q, a) = (p, b, D)。凡是有限的東西都能寫下來。所以挑一個固定的方案，把整份描述拼寫成某個字母表上的單一字串——這就是機器的編碼，通常用角括號寫成 <M>。機器 M 是那個抽象的小裝置；<M> 是它的原始碼，一個你可以用電子郵件寄出去的純字串。
你究竟怎麼編碼並不重要，而這份自由本身就是一課。把狀態編號為 q1、q2、q3……；把帶符號編號為 a1、a2……；把每條規則寫成那些編號組成的一個元組，比方說用二進位，規則之間加上分隔符。只要這個方案是一個合理的編碼——能用一個簡單程序解碼，而非被人為灌水到浪費的長度——那選擇就可以互換，正如同一支程式不論存成 UTF-8 還是 ASCII 都還是「同一支」。一個微小卻誠實的細節：我們通常還會固定一個慣例，讓每一個字串都解碼成某台機器（亂碼字串對應到一台立刻拒絕的平凡機器），這樣「字串 <M>」就永遠有意義。
一台機器跑遍所有機器：通用機器
如果一台機器只是個字串，何必為每件工作打造一塊新硬體？造一台機器，把別的機器的原始碼當作輸入。通用圖靈機——傳統上叫做 U——接受的輸入是一對東西：一台被編碼的機器，加上給它的一個輸入字串，寫成 <M, w>。U 接著做 M 在 w 上會做的事——M 接受 w 它就接受、M 拒絕 w 它就拒絕、M 在 w 上繞圈它就繞圈。一句話：U 是一台直譯器。它不把任何特定工作烤進去；它讀取工作，然後執行它。
- 把工作鋪在幾條軌道上（或幾條帶上，反正多餘的帶不增加能力）：一條存著從 <M> 解碼出來的固定轉移表，一條存著 M 的工作帶內容，再用一小塊區域存「M 當前的狀態」。
- 初始化：把輸入 w 複製到被模擬的工作帶上，把記下的狀態設為 M 的起始狀態，並把被模擬的讀寫頭放在 w 的左端。
- 模擬一步：讀取被模擬讀寫頭下的符號與記下的狀態，然後在轉移表裡查這個（狀態、符號）對，找出相符的規則。
- 套用它：用規則的寫入符號蓋掉原符號、更新記下的狀態，並挪動工作帶內容以模仿讀寫頭向左或向右移動。
- 從第三步重複。若記下的狀態變成 M 的接受狀態，U 就接受；變成 M 的拒絕狀態，U 就拒絕；若 M 會繞圈，U 也忠實地跟著繞圈。
第五步那個誠實的微妙處值得停一下。U 不能往前偷看、預先判定 M 會不會停機；它只能像 M 那樣一步步把 M 跑出來才知道。所以 U 所辨識的語言——所有「M 接受 w」之對 <M, w> 構成的通用語言——是圖靈可辨識的，卻不是可判定的。若 M 在 w 上繞圈，U 也跟著繞圈；它從不說謊，只是永遠不返回。這不是 U 的瑕疵；它是上一階的停機問題披著通用機器這身戲服。通用性替你買到一台能跑一切的直譯器，卻買不到一條繞過不可判定性的路。
儲存程式的觀念，以及「圖靈完備」是什麼意思
退一步，注意剛才發生了什麼。我們不再為每個問題接一台獨立的機器，而是把程式放在與資料同一條帶上，在那裡它像任何其他符號一樣被讀取。這就是儲存程式的觀念——程式與資料住在同一份統一的記憶體裡——而通用圖靈機正是它的直系數學祖先。你正用來讀這篇文章的筆電，在精神上就是一台又快又方便的 U：它的 CPU 是那台固定的直譯器，而它跑的應用程式，就是與其輸入存在同一份記憶體裡、被編碼過的機器 <M>。理論在工程存在之前，就先畫好了藍圖。
這終於讓我們能定義一個你聽人隨口說過的詞：當一個系統能模擬任何圖靈機時，它就是圖靈完備的——等價地說，當它能計算每一個圖靈可計算函式時。圖靈完備這個標籤，恰恰就是 U 跨過的那道門檻。而整個這一階出人意料的妙處，在於那道門檻有多低。你不需要一門花俏的語言；少少幾個運算——一種迴圈的方式、一種測試的方式，以及讀寫無界記憶體的能力——就已經跨過它了。λ 演算跨過它；遞迴函式跨過它；甚至一些小得驚人的規則集與玩具機器都跨過它。能力，在這裡，便宜得令人吃驚。
不只是能否，還有多快：延伸論題
目前為止講的都是什麼可計算。還有一個更強、各自獨立的主張，關於多有效率：延伸邱奇-圖靈論題說，任何合理的計算模型都能被一台圖靈機以只有多項式的減速來模擬——所以「有效率」在多項式時間的意義下，跨所有合理模型都是同一回事。正是這一點，讓我們得以只在圖靈機上研究多項式時間問題的類別 P，並信任答案與模型無關。你帶進來的那些早先事實在此完美吻合：多帶只花一個多項式因子，所以多帶仍在這個界限之內。
要小心：這條延伸論題比原版站得更不穩。非決定性圖靈機是那個著名的問號——我們對它最好的決定性模擬要付出指數級的爆炸，而非多項式級，而那個指數代價是否真的必要，正是無人解開的開放問題 P 對 NP。量子電腦帶來第二個疑慮：它們似乎只用多項式的額外開銷就能模擬量子物理，而一台古典圖靈機看來需要指數級的開銷，這將推翻延伸論題（不過並不知道量子機器能攻破 NP 完全問題）。關於可計算性的樸素邱奇-圖靈論題依然堅如磐石；效率版本則是真正有爭議的。
於是這一階把整個迴圈閉合了。你現在懂得圖靈機為何配當「計算」的那個定義：它在各種變體下的穩健性、那一眾等價模型的齊聲合唱、把它們繫於我們直覺的那條論題，以及那台從一串儲存的程式碼就能跑遍它們全部的通用機器。把這一幅圖像帶在最前面：程式即資料，而單單一台機器就能讀一支程式並化身為它。從這裡起你遇到的每一個問題——什麼是沒有機器能判定的、什麼是每台機器都覺得慢的——都是關於那一個通用招數的觸及範圍與代價的問題。