從一堆定義到一趟旅程
在前面四篇導覽裡，你蒐集了整門學科的原始詞彙：一個字母表 Sigma（希臘大寫字母 Σ，也就是你固定下來、被允許使用的符號集合）、由串接建出的字串、由每個有限字串構成的巨大宇宙 Sigma 星號，以及一個形式語言——它不過就是從那個宇宙中雕出來的一個字串集合。你也看到了那個關鍵的重新框架：一個是非問題可以編碼成一個語言，於是「解決問題」就變成「判斷哪些字串屬於這個集合」。本篇不再多加一個工具，而是退後一步，讓你看見前方一切的整體形狀。
這裡是整門課最重要的一個想法：並非所有語言都一樣難描述。有些語言能被幾乎不需要記憶體的機器識別；有些需要一點點記帳；有些需要一台完整的通用電腦；而有些——驚人地——根本沒有任何機器能識別。把語言依「需要多少機械力」加以組織的這張地圖，就叫做喬姆斯基階層。一旦這張地圖進到你腦中，後面每一篇導覽都會像是在探索一塊你早已知道輪廓的疆域中的某個區域。
四個層層相套的語言環
想像四個一個套一個畫出來的環，像樹的年輪。最內圈最小、最溫馴；每個較大的環都包含內側的一切，再加上嚴格更多。最內圈是正規語言：簡單到一台只有固定有限記憶體的機器就能識別的模式——想像一座旋轉閘門，它永遠只記得自己目前處在哪個狀態。往外一圈是上下文無關語言：需要一疊只能從最上面動手的盤子的模式，那剛好足夠用來配對像成對括號這種有巢狀結構的東西。再往外是需要一台完整通用機器的語言，而最外圈裝著沒有任何機器能完全應付的語言。
關鍵字是層層相套：每個正規語言也是上下文無關的，而每個上下文無關語言也能被更大的機器處理。但每一圈都嚴格更大——確實有些語言住在某一圈裡，卻無法被任何屬於內側某圈的機器表達。教科書上的見證者是「等量計數」語言 a^n b^n（若干個 a 後面恰好接同樣多個 b）。它是上下文無關的（一個堆疊可以數 a，再用它去和 b 對消），但它不是正規語言，因為固定的有限記憶體記不住一個無上限的計數。誠實地證明這道鴻溝，正是日後一個工具——幫浦引理——的用途。
每一圈都有一台配對的機器
這個階層的美妙之處在於：每一圈不只是一個模糊的難度概念——它恰好被某一種機器精確地捕捉。一台有限自動機就像一台販賣機或一座旋轉閘門：它有少數幾個狀態，一次讀入一個符號，每讀一個符號就依規則 delta(q, a) = p（在狀態 q、讀到符號 a 時，前往狀態 p）跳到新狀態。它沒有草稿紙——它的全部記憶體「就是」自己正處於那有限多個狀態中的哪一個。那恰恰是正規語言所需要、且不多不少的能力。
再加一塊記憶體——一疊盤子，你只能往最上面放或從最上面拿——你就得到一台下推自動機，它恰好識別上下文無關語言。這個堆疊剛好夠用來配對 a^n b^n：每讀一個 a 就推入一個盤子，再為每個 b 彈出一個盤子，只有在輸入結束的同時堆疊恰好清空才接受。把記憶體上的所有限制都拿掉——給機器一本無盡的筆記本，它可以在任意位置讀、擦、重寫——你就抵達了圖靈機，也就是通用電腦的模型。它的語言構成最外側的兩圈。
RING LANGUAGE FAMILY MATCHING MACHINE MEMORY
-------------- ----------------------- ----------------------- -------------------
innermost regular finite automaton (DFA) finite states only
| context-free pushdown automaton one stack (top only)
v decidable Turing machine (halts) unbounded tape
outermost recursively enumerable Turing machine (may loop) unbounded tape
example that escapes each inner ring:
a^n b^n regular? NO context-free? YES
a^n b^n c^n cf? NO decidable? YES最外圈，以及一道爬不上去的牆
最外側的兩圈很微妙，值得停下來想想。一個語言是可判定的，若存在某台圖靈機總是停機並給出正確的是非答案——它永不無限運行。一個語言是遞迴可枚舉的（也稱為圖靈可識別的），若存在某台機器會接受每個屬於該語言的字串，但對「不」屬於它的字串，機器被允許永遠繞圈，而不說否。所以一個識別器可能讓你苦等而得不到答案；一個判定器則一定會回來。這意味著圖靈可識別嚴格弱於可判定：確實存在你能識別、卻永遠無法判定的語言。
而在更外側還有一道硬牆。停機問題——給定一個程式的程式碼與一個輸入，它最終會停機還是永遠繞圈？——是不可判定的：沒有任何圖靈機能對所有輸入正確回答它。這不是「太慢」或「目前太難」，而是一個被證明的數學不可能，由一個叫做對角線化的自我指涉技巧所確立。它的概要很短，值得看一次。
- 為了導出矛盾，假設存在一個程式 H，它接受任何程式 P 與輸入 x，並總是正確回答 P 在 x 上會不會停機。
- 造一個狡猾的程式 D：它接受一個程式 P，對 (P, P) 這一對跑 H，然後做相反的事：若 H 說「P 在 P 上會停機」，則 D 永遠繞圈；若 H 說「P 會繞圈」，則 D 停機。
- 現在把 D 自己的程式碼餵給它：問 D 在 D 上會不會停機。若 H 說它停機，D 卻被造成會繞圈——矛盾；若 H 說它繞圈，D 卻被造成會停機——兩種情況都矛盾。
- 既然假設 H 存在會逼出矛盾，這樣的 H 就不可能存在。停機問題沒有通用的求解器——句點。
為什麼一切都回到同一個問題
無論你身在哪一圈，所做的事永遠是你在「問題變成語言」時遇到的那一件：判定成員資格。這個字串在這個語言裡嗎？有限自動機靠讀完字串、檢查是否停在接受狀態來回答；下推自動機靠它的堆疊來回答；圖靈機靠在紙帶上計算來回答。整個階層其實是一個「回答這一個問題有多昂貴」的階層，而那道不可判定的牆，正是這個問題根本沒有演算法答案的地方。
越過可判定的界線之後，問題換了風味，但精神不變。一旦我們同意只研究電腦「能」解決的問題，就開始追問「有多有效率」——這便開啟了複雜度類別的世界，例如 P（能在隨輸入大小僅以多項式增長的時間內解決）與 NP（答案像一幅拼好的拼圖般容易檢查，即使很難找到）。這裡有兩個誠實的提醒：NP 並不表示「非多項式」，事實上 P 包含於 NP 之中；而 P 是否真的等於 NP，是尚未解決的重大難題之一——未被證明，而非暗地裡早已知道。地圖告訴你某問題住在哪塊疆域，但它不會假裝最難的那些疆域之間的邊界都已勘測完畢。