把舊超能力裝到新機器上
回到有限自動機那階梯時，你見過一台會分身的機器。一台非確定型有限自動機讀到一個 `a` 時，不必只挑一個下一狀態——它可以分裂成許多副本，每個允許的選擇一個，平行地探索每一條分支，只要有任何一個副本最後落得開心就接受。一台非確定型圖靈機（NTM），正是把這同一項超能力，栓到一台普通圖靈機那本無盡的可讀可寫的筆記本上。它的轉移規則不再交還一個動作；它交還一組動作，而我們想像機器把它們全部同時試一遍。
具體說，確定型機器有像「delta(q, a) = (p, b, R)」這樣的規則——在狀態 q 讀到 `a`，就寫 `b`、右移、進入狀態 p——非確定型機器則有形如「delta(q, a) = 一組這樣的三元組」的規則。在狀態 q 讀到同一個 `a`，它可以寫 `b` 右移到 p，「或者」寫 `c` 左移到 r，「或者」做第三件事。我們說當「某一條」選擇序列把這台 NTM 帶到接受狀態時，它就接受這個輸入。一條幸運的分支就夠了；不幸的分支無關緊要。這就是你在 NFA 那裡見過的「先猜、再查」形狀，只是現在有一整條可讀可寫的紙帶可以拿來查。
圖像：一棵不斷分岔的格局之樹
想像一台 NTM 的運轉，最乾淨的方式是把它當成一棵樹，而不是一條線。確定型機器在固定輸入上描出一條單一路徑：一個格局接一個格局，每一步都被規則逼出來，一路向前直到停機（或永不停機）。把機器在某一瞬間的完整快照——狀態、紙帶內容、讀寫頭所在位置——稱作一個格局（configuration）。對 NTM 而言，每個格局都可能有好幾個合法的後繼者，所以我們得到的不是一條路徑，而是一棵樹，每當有選擇可挑時就分岔一次。
樹的根是起始格局。每個節點的子節點，就是一步之內可達的所有格局。某個副本抵達接受狀態的那條分支，是一條接受分支。當這棵樹包含「至少一條」接受分支時——不管在哪裡、不管多深——這台 NTM 就接受整個輸入。所以「這台 NTM 接受 x」的意思，其實是一句關於「樹中是否存在某條路徑」的陳述，而真的去跑它這件差事，就是去搜尋那棵樹這件差事。
[ start config ] depth 0
/ | \
cfg A cfg B cfg C depth 1
/ \ | / \
... cfg cfg ... ACCEPT <-- one lucky branch
| | (the whole NTM accepts)
REJECT loop...
accept x <=> SOME leaf in the tree is an accept state
branching factor b, depth up to t => up to b^t configurations確定型追了上來——靠著搜尋那棵樹
這裡是頭條結論，而它該讓你覺得似曾相識：一台非確定型圖靈機並不比一台確定型的更強。NTM 能做的任何事，一台普通的確定型圖靈機也都做得到。這是上一階梯 NFA 與 DFA 等價的深層回聲：在那裡，子集構造法把「試遍所有分支」變成了「追蹤你『可能身處』的那組狀態」。這裡的把戲甚至更直截了當——我們就讓確定型機器系統性地探索 NTM 那棵格局之樹，盯著看有沒有一條接受分支。
唯一的微妙處在於「怎麼」探索那棵樹。最天真的想法——沿著第一條分支一路走到底，再換下一條——是致命的，因為那第一條分支可能永遠迴圈，於是你會卡在一條非接受路徑上，而一條接受路徑就在隔兩條分支處等著、永遠到不了。所以模擬器必須以廣度優先來探索：先檢視所有深度 1 的分支，再所有深度 2 的分支，再深度 3，依此類推。這樣一來，若有任何接受分支存在於某個有限深度 d，搜尋就保證在做完所有深度 d 的工作後抵達它。用多條紙帶的佈局能把記帳弄得乾淨：這正是上一篇那台多帶圖靈機生來就擅長收拾整齊的活兒。
- 用「抵達某節點所走的選擇序列」來為樹中每個節點編址，例如字串「2-1-3」表示「第一個分岔取選擇 2、接著選擇 1、再選擇 3」。把這個地址記在一條專用的「選擇」紙帶上。
- 要測試一個地址，就把原始輸入複製到一條工作紙帶上，然後確定型地重跑這台 NTM，每到一個分岔就服從選擇紙帶上的下一個數字。若某個數字要求的是個不存在的選擇，就把這個地址當成無效並放棄。
- 若這條被模擬的分支抵達接受狀態，就停機並接受整個輸入。若它拒絕、或選擇用光了，就換下一條。
- 以最短長度優先的字典序產生這些地址——先所有長度 1 的字串，再所有長度 2 的，依此類推——這恰恰就是對樹的廣度優先搜尋，所以一條有限深度的接受分支總會被找到。
等價——但代價是什麼？
於是 NTM 算不出任何確定型機器算不出的東西。這是圖靈機模型穩健性的又一根支柱：正如加上許多條紙帶並未改變「能算什麼」（只改了速度），加上非確定性也同樣沒改變它。一台 NTM 能辨識的語言類別，恰恰就是圖靈可辨識的語言；它能判定的類別，恰恰就是可判定的語言。非確定性，和額外的紙帶一樣，是一種方便——一種讓設計與描述機器更輕鬆的辦法——而不是一種算出真正新東西的辦法。
但留意這感覺和多帶那個結論有多不一樣。把一台多帶機器轉成單帶，只付出了多項式級的拖慢——是慢了，沒錯，但只是輕微地慢。上面那場樹搜尋則昂貴得多。若 NTM 的樹有分岔度 b、而接受分支在深度 t，要檢視的格局可能多達「b^t」這個量級，所以確定型模擬器可能花掉以 t 計的指數級時間。目前已知最好的一般上界是：模擬一台 NTM 的 t 步，要花確定型機器大約「2^(O(t))」步。我們能廉價地對上「能力」；而對上「速度」，就目前所有人所知，可能得付出指數級的爆炸。
這個虛構為何重要：先猜、再驗證
即便沒有任何 NTM 存在於硬體之中，這個模型仍是整門理論裡最有用的工具之一，理由和 NFA 當年一樣：「猜了再驗」的機器，遠比一台從零開始的確定型機器好「設計」。配方是先猜、再驗證：在分岔那一步，讓機器非確定型地寫下一個候選答案——一個可能的因數分解、一條可能的走遍圖的路線、一種可能的著色——然後跑一個普通的確定型檢查，看這個候選是否真的行得通，只有行得通才接受。因為機器在「某一條」分支成功時就接受，這在邏輯上完全等同於說「存在一個能通過檢查的候選」。
這個「猜了再驗」的形狀不只是設計上的方便——它幾乎逐字就是計算機科學裡最重要類別之一的定義。NP 這個類別，是一台 NTM 能在多項式時間內判定的問題之集合；等價地，它是那些「是」答案附帶一張簡短憑證、且一台確定型機器能快速檢查該憑證的問題之集合。那個非確定型的猜測「就是」憑證；那個確定型的檢查就是驗證器。NP 正是拼圖問題的正式家園：難以完成，但一旦有人把解遞給你，就容易檢查。
現在迴圈合攏了。上一節那句「只不過是指數級拖慢」，恰恰就是「是否每個 NP 問題都能確定型地在多項式時間內解出」這個問題——也就是 P 是否等於 NP。當心這個名字：NP 代表「非確定型多項式時間」，「不是」「非多項式」；事實上每個能在確定型多項式時間內解出的問題，理所當然都在 NP 裡，所以 P 是 NP 的子集。這兩個類別究竟是否真的相等，尚未有解、尚未被證明，而且誰擺平它就值大量名聲。再往上兩階你會與它正面相遇；今天，只要看出這台貌不驚人的非確定型圖靈機，正是長出那整個問題的種子，就夠了。