兩個看起來很像、意思卻南轅北轍的詞
你來到這裡時，已經知道一台圖靈機——那本可讀、可擦、可重寫的無盡筆記本——對任何輸入恰有三種可能命運：它可以停機並接受、停機並拒絕，或永遠跑下去、絕不停止。前兩種乾淨俐落；第三種才是麻煩製造者，而這一整階都圍繞著它打造。問題問起來簡單、答起來卻很深：當我們說一台機器「解決」某語言的成員問題時，我們是指它總是給我們一個答案，還是只指它在真正答案恰好為「是」時才作答？這兩種讀法把宇宙中每個語言切成兩堆彼此重疊的東西，而它們的名字就是可判定與可識別。
一個語言 L 是圖靈可識別的（Turing-recognizable），若存在某台圖靈機 M，恰好接受 L 中的字串。陷阱在於 M 對不屬於 L 的字串會怎麼做：它可以拒絕它們，也可以永遠迴圈下去——兩者都行。所以若你餵 M 一個字串而它接受了，你便得知「是的，這在 L 裡」。但若 M 跑了一百萬步還在跑，你什麼也不能斷定：也許它正要拒絕、也許它會在第十億步拒絕、也許它根本永不停止。一台識別器是個樂觀主義者，一旦「是」為真便立刻喊出「是！」，卻可能在答案為「否」時索性永遠不開口。你會在較舊的書上看到的同義詞是遞迴可枚舉（recursively enumerable），通常縮寫成 r.e.。
一個語言 L 是圖靈可判定的（Turing-decidable；舊書稱遞迴的，recursive），若存在某台圖靈機——現在叫做判定器（decider）——接受 L 中的每個字串，而且拒絕不屬於 L 的每個字串，並對每一個輸入都總是停機。那被禁止的第三種命運消失了：判定器絕不迴圈。它不是樂觀主義者，而是一位裁判，對任何輸入，最終都會朝某一方吹哨。在日常說法裡，「對一個是非問題擁有演算法」通常指的就是判定——一個保證會終止並給出正確裁決的程序。識別則是那較弱、較滑溜的表親。
那個漏洞，正是「迴圈」本身
差異的核心就在這裡，值得慢慢說：每個可判定語言都是可識別的，反過來卻不成立。先講簡單的方向。若你有一台判定器，你就已經有了一台識別器——一位總會回答是或否的裁判，特別地，正是一台接受所有「是」實例的機器。丟掉「而且它在『否』實例上也會停機」這個保證，只是削弱了承諾；它從不違背承諾。所以可判定是可識別的子集。全部的戲劇張力，都在於這個子集是否為真子集——是否存在某個可識別卻不可判定的東西。下一階先劇透：有的，而那著名的見證者就是停機問題。
為何識別器會無法成為判定器？想像兩台機器都在某語言裡找一個字串。判定器搜的是一間有限的房間：它能掃遍每個角落，找不到便宣告「不在這裡」。識別器搜的是一條無盡的走廊：若那東西在，它終會絆到它並喊出來；但若那東西不在，識別器就只是一直走下去，在任何有限的時刻，它都無法誠實地說「我現在已經到處都查過了」。這種永遠無法下結論說「否」的無能，並非懶惰或慢——它是一道邏輯的牆。迴圈不是換台更快的電腦就能修補的臭蟲；對某些語言來說，迴圈是無可避免的，而證明這件事，是再下一階的震撼彈。
把答案翻面：余可識別語言
如果識別器擅長確認「是」的答案，那麼擅長確認「否」的答案的機器呢？那正是余可識別語言（co-recognizable language）的點子。一個語言 L 是余可識別的，當它的補集——字母表 Sigma（寫成 Σ，即允許符號的集合）上所有不屬於 L 的字串所成的集合——是可識別的。等價地說，存在一台機器恰好對 L 之外的字串停機並接受，而可能在 L 之內的字串上迴圈。它是那位鏡像中的樂觀主義者：一旦「否」為真便立刻喊出「否！」，卻在答案為「是」時保持沉默（或迴圈）。
把這兩幅圖像並排端詳，一種優美的對稱便浮現了。識別器是一個「是」偵測器，可能在「否」時永不啟動。余識別器是一個「否」偵測器，可能在「是」時永不啟動。各自單獨都是半盲的。接下來顯而易見的念頭——而且它是對的——是：如果你同時擁有兩者、針對同一個語言呢？若你能同時跑一個「是」偵測器與一個「否」偵測器，那麼對任何輸入，必有其中之一最終會啟動（畢竟真正的答案非「是」即「否」），而它一啟動，你就拿到裁決並停機。這個夥伴關係，就是從識別回到判定的橋樑，也是你在這一階接下來會遇到的核心定理的主題。
那條定理，以及它所解釋的封閉律
這是本階的核心結果，乾淨地陳述出來，好讓它在日後某篇給出完整證明之前就能指引你：一個語言 L 是可判定的，若且唯若 L 同時是可識別的而且是余可識別的。這就是那條著名的可判定＝可識別＋余可識別刻畫，它恰好捕捉了那個夥伴關係。其中一個方向是我們已經看過的簡單方向：判定器給出一台識別器（並且，因為它在「否」實例上也停機，同時也給出一台余識別器）。另一個方向才是巧妙的，而訣竅在於把兩台機器一起跑，而不是先跑一台再跑另一台。
- 假設 L 可被機器 M 識別（在「是」時啟動），且 L 余可識別，意即它的補集可被機器 N 識別（在「否」時啟動）。我們要替 L 造一台判定器 D。
- 對輸入 w，D 並行模擬 M 與 N——跑 M 一步、再跑 N 一步、再各跑下一步，永遠交替下去。（天真地先把 M 跑到底，會冒著在 N 還沒輪到之前就先迴圈的風險。）
- 若 M 曾接受，則 w 屬於 L，於是 D 停機並接受。若 N 曾接受，則 w 屬於補集，於是 D 停機並拒絕。
- 由於每個 w 不是屬於 L 就是屬於它的補集，M、N 中恰有一台保證最終會接受。所以 D 總會停機並給出正確裁決——D 是一台判定器，而 L 是可判定的。
這條定理也解釋了一條讓初學者吃驚的封閉律。可識別語言對聯集與交集封閉——並行跑兩台識別器，在適當時接受——但它們對補集不封閉。若它們封閉，則每個可識別語言都會自動也是余可識別的，於是（由該定理）就是可判定的，而我們知道那是假的。所以「可識別，取補集後仍可識別？」對某些語言必然失敗——確實，停機問題那個語言的補集，正是「余可識別卻不可識別」之語言的標準例子。相對地，可判定語言對補集確實封閉：把一台判定器的接受與拒絕狀態對調，你就得到補集的判定器，不必擔心迴圈，因為判定器絕不迴圈。
枚舉器觀點，以及我們永遠能判定的問題
還有第二種同樣鮮活的方式來描繪可識別性，它解釋了「遞迴可枚舉」這個舊名。不是一台拿字串來作答的機器，而是想像一台沒有輸入、只是把某語言的字串一個接一個印出來的機器——一台枚舉器（enumerator），一位不知疲倦的列舉者。一個語言可識別，恰好等於存在某台枚舉器最終能印出它的每一個成員（以任何順序，可能有重複）。微妙之處在此：要列舉一個成員來自無限多台候選機器或計算的語言，你不能在開始下一項之前把每項計算跑到底——其中一項可能迴圈，把整張清單凍住。解法是對角穿插（dovetailing）：像洗牌一樣把諸計算交錯進行，先做第 1 項工作的第 1 步；再做第 1、2 項工作的第 1 步；再做第 1、2、3 項工作的第 1 步；如此下去，讓每項計算都能拿到無上限多的步數，而沒有任何單獨一項會卡住其餘的。
DOVETAILING the jobs J1, J2, J3, ... (each Ji may loop): round 1: J1 step1 round 2: J1 step2 J2 step1 round 3: J1 step3 J2 step2 J3 step1 round 4: J1 step4 J2 step3 J3 step2 J4 step1 ... - whenever some Ji ACCEPTS / produces output, record it. - no single looping Ji ever starves the others of attention. - every Ji eventually receives any finite number of steps you like.
在講了這麼多可能永遠迴圈的機器之後，能在堅實的土地上收尾真是鬆一口氣：許許多多自然的問題就是乾脆而可靠地可判定的。尤其是關於有限自動機，幾乎一切都可判定，因為一台 DFA 是個有限、可完全攤開描繪的物件。「這台 DFA 接受字串 w 嗎？」（接受問題）只要把 DFA 在 w 上跑一遍就判定了——它沒有迴圈，所以總會停機。「這台 DFA 的語言是空的嗎？」則藉由檢查是否有任何接受狀態可從起始狀態抵達來判定，那是一次有限的圖搜尋。「這兩台 DFA 接受相同的語言嗎？」（等價）則藉由為對稱差造一台 DFA、再測試它是否為空來判定——若差集裡什麼也沒有，兩者就相等。即使對於上下文無關文法，成員性（「這文法產生 w 嗎？」）與空性（「它究竟產不產生任何東西？」）也都可判定，儘管兩個文法是否等價則不可判定。
留意這個規律，並把它帶上階梯：一個模型在喬姆斯基層級裡坐得越低，我們能判定關於它的事情就越多。有限自動機受限得如此之深，以致空性、等價與成員性全都可判定。文法放棄了等價，卻保住成員性與空性。而那無所不能的圖靈機——正因它能做任何電腦做得到的事——放棄的最多：甚至連問「這台機器在這個輸入上究竟停不停機？」都根本沒有判定器。能力與可預測性彼此抵換。那個抵換，就是你會在緊接著的下一階走到的懸崖邊，而你現在握著的可判定／可識別之分，正是你藉以閱讀它的地圖。