基本機器留給你的那個疑慮
到了這個地步，圖靈機粗陋得幾乎讓人不敢信任。它只有一條無窮長的紙帶、一個一次只能左右挪動一格的讀寫頭；要比對輸入的兩半，它得在整條紙帶上來回跋涉，活像一個只有一張紙的人，靠著反覆走過整張紙的長度，去核對一筆很長的加總。一種很自然的擔憂悄悄浮現：說不定這東西就是太弱了。說不定一個更聰明的設計——更多紙帶、會猜的能力、乾脆換一個完全不同的小機關——能解出這台可憐機器永遠解不了的問題。
本篇導讀回應這份擔憂，而答案正是整個段落的主標題：那無所謂。你可以堆上一大疊紙帶、賦予機器猜測的能力，或乾脆把紙帶丟掉、改用一套天差地遠的形式系統，但它能解的那一族問題卻維持得分毫不差。機器會變得更快、更方便，卻從不變得更有能耐。這份令人意外的不可撼動性有個名字——圖靈機的穩健性——而接下來好幾篇導讀，講的就是如何誠實地把這份穩健性掙到手。
更多紙帶：更快的機器，而非更強的機器
先從最親切的升級開始。一台多帶圖靈機擁有某個固定數目 k 條紙帶，每條都有自己獨立的讀寫頭；它在一步之內同時讀取 k 個讀寫頭底下的格子，然後分別寫入、分別移動每個讀寫頭。這帶來莫大的便利：要檢查輸入的左半是否等於右半，你只要把其中一半複製到第二條紙帶上，再讓兩個讀寫頭齊步並進、逐格比對——再也不必在單一紙帶上累死人地來回奔波。
現在來看關鍵主張：每一台多帶機器都能被一台普通的單帶機器模擬。訣竅是把全部 k 條紙帶並排攤在這條單一紙帶上、一軌一軌交錯排列，並在每個讀寫頭當前所在的格子上點一個記號。要模仿多帶機器的一步，單帶模擬器先掃過整片已寫入的區域一次，讀出全部 k 個被標記的格子，再掃回來更新每一個並移動那些記號點。這台單帶機器最終做的事，正是多帶機器所做的——接受相同的輸入、產生相同的輸出。
這個模擬的代價是什麼？每模擬一步，單帶讀寫頭要掃過的區域，最長可達「到目前為止的步數」那麼長，所以模擬 t 步要花約 t^2 步的數量級——一個多項式級的膨脹（此處為 O(t^2)）。而這正是全部的寓意所在：額外的紙帶換來速度，頂多差一個多項式因子，卻從不換來新的解題能力。單帶機器在排序與比對上比較慢，但 k 帶機器能判定的問題，沒有一個是單帶機器判定不了的。
Multitape machine, 2 tapes: Encoded onto ONE tape (interleaved):
tape 1: a a b a
^ a . a a b a # b . a c #
tape 2: b a c | ^ ^
^ (dot = where each head sits)
One simulated step = sweep right to read both dotted cells,
sweep left to rewrite + move both dots.
Simulating t steps ~ O(t^2) steps on the single tape.免費的猜測？非確定性只花時間
下一個升級更大膽。回想有限自動機那幾階裡，一台 NFA 如何能分裂成許多副本、同時探索每一條路徑——對精簡度來說純粹是魔法，但它是一個數學裝置，從來不是隨機的，也從來不是免費的。一台非確定型圖靈機在紙帶上做的是同一件事：在某些步驟，它的轉移規則提供好幾個可能的動作，而只要「有任何一條」選擇序列通往接受狀態，這台機器就接受。把它想像成這台機器抽出一棵分岔的可能計算之樹，只要其中哪怕一條枝椏喊出「是」，它就成功。
這份幸運的猜測，能讓它判定任何新東西嗎？不能。一台確定型機器可以靠著有系統地探索那整棵選擇之樹，來模擬非確定型機器——關鍵在於要用「廣度優先搜尋」，而不是深度優先。為什麼廣度優先要緊：某一條枝椏可能永遠跑不完，若你一頭栽到底，就會卡死、再也試不到其他枝椏；正確的做法是把所有枝椏「一次多走一步」地交替推進，像在它們之間分時共享，這就保證了任何「有限長」的接受路徑終究會被找到。
誠實的價碼如下。一棵深度為 t 的計算樹，最多可有約 b^t 個節點（b 是每步選擇數的上限），所以確定型的模擬可能要花指數時間——大約 2^(O(t))。因此在圖靈機上，非確定性的代價是模擬時的「指數級減速」，卻多判定不了哪怕一個語言。請把它和有限自動機那段故事鮮明對照：當年子集構造法把一台 NFA 壓平成一台 DFA，只在狀態數上付出指數級的膨脹，表達能力同樣毫無改變——同一個教訓，講了兩遍：非確定性是便利，而不是能力。
為什麼這個指數在這裡無關痛癢，卻讓複雜度領域的人人魂牽夢縈？因為談可計算性時，我們只問「到底存不存在一條會停機的接受計算」，而指數時間終究會停。可是一旦我們要求模擬必須維持在多項式內，這同一道指數鴻溝就化身為大名鼎鼎的 P 對 NP 問題——至今懸而未決。同樣的非確定性，依你是否計較時間，賭注卻天差地別。
把紙帶丟掉：打成平手的對手模型
到目前為止，我們只是在「拉伸」圖靈機。更深的震撼在於：一些彼此毫不相干的形式系統，由不同的人為了不同的理由發明出來，竟然全都抵達了「完全相同」的那一組可計算問題。這些就是等價的計算模型，而它們看起來和「一條紙帶配一個讀寫頭」毫無相似之處。邱奇的 lambda 演算把一切化約為「建構並套用無名函數」；哥德爾與克萊尼的遞迴函數，則從少數幾個基本函數，加上複合、原始遞迴與一個無界搜尋運算子，搭起整個計算；暫存器機（或計數器機）更貼近真實的組合語言，無非是加一、減一與跳躍；而一維的細胞自動機，則靠一條固定的「局部規則」去更新一整列細胞來進行計算。
我們怎麼知道它們打成平手？靠的是雙向、具體、不厭其煩的模擬。你寫一台圖靈機，讓它一步一步地執行 lambda 演算的化約；你也寫出一些 lambda 項，把一條紙帶、一個讀寫頭與一張轉移表編碼進去，再硬生生地碾過一整段圖靈計算。每一對這樣的互譯，都證明了兩個模型恰好辨認相同的語言。對每一對都這麼做，整座動物園就坍縮成「可計算性」這個單一的概念——而這也正是為什麼，你最愛的那個真實程式語言同樣名列其中。
論題、編碼，與那台萬用機器
這一切的趨同，壯了膽提出一個著名主張：邱奇—圖靈論題。它說，凡是我們直覺上會稱為「能用機械程序有效計算」的東西，恰好就是圖靈機所能計算的東西。請仔細留意這是「哪一種」陳述。它在一個非形式的、直覺的概念（「演算法」、「機械程序」）與一個精確的數學概念（圖靈機）之間搭橋，所以它無法像定理那樣被證明——因為直覺那一側根本沒有形式定義，可供你拿來對照證明。它是一個「論題」：數十年來每一個被提出的模型都打成平手，給了它壓倒性的支持，但它是一個關於現實的主張，而不是一條演繹。一個未來能勝過圖靈機的模型將駁倒它，但九十年來沒有任何東西接近過。
相信這個論題，立刻就有紅利可領：圖靈機本身是一個「有限」的物件——一份有限的狀態與轉移規則清單——所以我們能把這份描述寫成某固定字母表上的一個普通字串。這就是把機器編碼成字串：挑一套方案，把狀態編號，把每條規則照「delta(q1, a) = (q2, b, R)」這樣拼寫出來，再串接起來。如今一台機器 M 有了一個文字化的名字，記作 <M>，這個名字能被當作輸入餵給另一台機器——當年讓我們把「問題」視為字串集合的同一招，現在讓「程式」成為了資料。光是這一個想法，就交到我們手上一顆鑲在王冠上的寶石：萬用圖靈機 U。把這一對 (<M>, w) 餵給 U——也就是任意機器 M 的編碼描述，後面接著一個輸入 w——U 就會模擬 M 在 w 上的執行，並且「恰好在 M 會接受 w 時」接受。一旦編碼就位，這些步驟就相當直觀了。
- 在它的紙帶上，U 保存三樣東西：規則手冊 <M>、M 那條被模擬之紙帶的內容，以及一個記號，存放著 M 的當前狀態與讀寫頭位置。
- 要模擬一步，U 先讀出 M 那個被標記的讀寫頭底下的符號，接著掃過 <M>，找出相符的規則 delta(當前狀態, 那個符號)。
- U 在被模擬的紙帶上執行那條規則：寫下新符號，把被標記的讀寫頭向左或向右移動，並更新所存放的狀態。
- U 不斷重複，直到被模擬的 M 停機；假如 M 在 w 上會永遠繞圈，U 也就老老實實地跟著永遠繞圈——它只能映照 M，無法預知 M。
停下來想想 U 究竟是什麼。它是一台固定的機器，卻能執行任何被當作資料交給它的機器——一件單一的硬體，其行為由儲存在紙帶上的程式所決定。這正是每一台真實電腦核心處的儲存程式概念：你的手機是一台裝置，卻能單憑載入其中的位元組，搖身變成計算機、相機或遊戲。萬用機器，正是這套設計在數學上的直系祖先。而結尾藏著一根刺：正因為 U 能模擬任何機器、包括它自己，它恰恰就是下一階用來搭建自我指涉、並證明停機問題不可判定的那根槓桿——讓電腦得以萬用的那份穩健性，也正是讓關於電腦的某些問題永遠無解的緣由。