三種命運，以及那個躲起來的
到了現在，你已認得圖靈機是一本可讀、可擦、可重寫的無盡筆記本，也知道它在某個輸入上的計算可以用三種方式之一結束。它可以在接受狀態停機。它可以在拒絕狀態停機。或者——而這正是在這一階裡惹出一切麻煩的命運——它可以永遠繞圈，根本不停下。一台 DFA，那個只記得當前狀態的旋轉閘門，從不會有這種問題：它把每個輸入符號恰好讀一次，字串一用完就立刻停下。而圖靈機，能隨它高興在紙帶上來回走動多少次都行，真的可以一直跑到天荒地老。
上一篇釘死了恰好在這第三種命運上不同的兩個類別。一個語言是可判定的（也叫 遞迴的，recursive），若存在某台圖靈機——一台判定器——對語言中的每個字串都接受、對不在語言中的每個字串都拒絕，而且關鍵在於它對每一個輸入都會停機，永不繞圈。一個語言是可辨識的（也叫 遞迴可枚舉的，recursively enumerable，或簡稱 r.e.），若存在某台圖靈機恰好接受語言中的那些字串——但對不在語言中的字串，它被允許做那件鑽漏洞的事：它可以拒絕，也可以乾脆永遠跑下去、永不作答。判定器對一切事物承諾一個裁決；辨識器只承諾對成員最終說「是」。
迴圈究竟從何而來
人們很容易以為迴圈只是個臭蟲——某個人設計得草率的機器。有時候確實是。但這一階深層的重點是：對某些語言而言，繞圈是無可避免的——無論你把機器設計得多巧妙，都沒辦法既辨識該語言又總是停機。要感受迴圈從何而來，想像辨識一個語言最自然的辦法：試東西，看哪個行得通。假設你的語言是「所有字串 w，使得某處某個計算最終會做 X」。顯然的辨識器就去搜尋：試第一個候選、再第二個、再第三個。若答案存在，搜尋會找到它並接受。但若答案不存在，搜尋永不結束——總還有下一個候選要試。迴圈不是馬虎；它是一場沒有內建停止點的無界搜尋的形狀。
這裡有個陷阱，使它在一般情況下真正無法修補。要把那台搜尋型辨識器變成判定器，你會需要偵測「我已經搜尋得夠久了；答案永遠不會來」並以拒絕停機。但對最難的語言來說，判定「這場搜尋永遠不會成功」本身就是一個不可判定的問題——它正是你將在下一階遇到的那個停機問題的化身。於是你卡住了：你能辨識該語言（找到答案就接受），卻在一般情況下無法在有限時間內辨識答案的不存在，而那恰恰是一個乾淨的拒絕所需要的。「找到一個是」與「確定一個不是」之間的這道鴻溝，正是「可辨識」嚴格弱於「可判定」的全部原因。
為何你不能就加個逾時
新手最常見的反射動作是：「那好——就讓機器跑個比方說一百萬步之後停下，若還沒接受就拒絕。」這修補了某個特定輸入，卻弄壞了整個語言。語言中一個真正的成員，也許真的需要兩百萬步才接受；你在一百萬步把它砍斷，就錯誤地拒絕了一個本該屬於語言的字串。無論你挑哪個有限的截斷點，總有某個合法的計算需要更多。沒有哪個單一數字對所有輸入都「夠用」，因為那些成員的執行時間沒有有限的上界。逾時把迴圈換成了不正確，這根本不是修補。
還有一個更微妙的錯覺：「只要偵測機器何時重複了一個組態，重複了就宣告迴圈。」記得一個組態是「（當前狀態、整條紙帶內容、頭的位置）」的完整快照。若一台決定性機器曾回到它先前到過的某個組態，那麼是的，它注定要永遠重複那個循環，你可以安全地拒絕。問題在於紙帶是無界的：一台機器可以永遠繞圈卻從不精確重複任何組態，做法就是每一趟都往新的空白紙帶寫上新符號——像一名永不停手的書記，因為帳本永遠用不完空白頁。不重複並不蘊含終止。所以組態循環偵測抓得到某些迴圈，卻永遠抓不到全部。
這漏洞讓封閉性付出什麼代價
這漏洞在「兩個類別能挺過哪些集合運算」上留下了精確的指紋。回想正規語言那幾階：若把某運算套在類別中的語言上，結果總是回到該類別之內，就說這個類別在該運算下封閉。可判定語言封閉得很漂亮：在聯集、交集、補集、串接與克林星號（Kleene star）之下，結果總是又可判定。補集行得通的理由很簡單，且立足於停機：拿一台判定 L 的判定器，跑它，把它的答案翻轉——接受變拒絕、拒絕變接受。因為那判定器總會停機，翻轉後的機器也總會停機，所以它判定 L 的補集。
現在看同樣的翻轉把戲在辨識器上如何失靈，並看那漏洞如何當破壞者。可辨識語言在聯集與交集下封閉——以聯集為例，平行地跑兩台辨識器（交錯它們的步驟，這個動作你會在後面一篇以 交織（dovetailing）來研讀），任一台接受就接受。但它們在補集下不封閉。試試翻轉：拿一台辨識 L 的辨識器，把接受與拒絕對調。問題就在那個迴圈。對一個不在 L 中的字串，原本的辨識器可能永遠繞圈——而一台從不停機的機器，根本沒有可供翻轉的答案。翻轉只在機器停機時有效，而辨識器恰恰就是那種可能不停機的機器。於是「翻轉一台辨識器」造出的機器在那些同樣的字串上仍然繞圈，對它們什麼也不接受，因此辨識不了補集。
Operation Decidable (recursive) Recognizable (r.e.) ------------- --------------------- ------------------- union closed (yes) closed (yes) intersection closed (yes) closed (yes) complement closed (yes) NOT closed <-- the loophole concatenation closed (yes) closed (yes) Kleene star closed (yes) closed (yes) Why complement splits the two classes: decider for L --> always halts --> FLIP accept/reject --> decides complement. works. recognizer for L --> may LOOP on non-members --> nothing to flip --> fails.
補集才是真正的獎品
補集封閉性的失靈不是枝微末節——它是下一篇的整個樞紐，所以讓它好好落地。可辨識語言的補集有自己的名字：若一個語言的補集是可辨識的，就說這個語言是 可餘辨識的（co-recognizable）。把一個可餘辨識語言想成這樣：你能可靠地確認「非成員」，但成員那邊的「是」可能繞圈。它是可辨識圖像照進鏡子裡的樣子：不再是可信的是配上不可靠的不是，而是可信的不是配上不可靠的是。
現在說出你下次會證明的那句重點，先放在這裡讓你看見漏洞通往何方。一個語言是可判定的，恰好當它既可辨識又可餘辨識：可判定等於可辨識加上可餘辨識。這個直覺美極了。如果你有一台「是」可信的機器（L 的辨識器），又有第二台「不是」可信的機器（L 補集的辨識器），就把兩台同時跑起來。對任何輸入，它們之中恰好會有一台最終停機並作答——誰先開口，誰就給你正確的裁決，毫無永遠繞圈的可能。兩個各自不可靠的半邊，各自蓋住對方的盲點，合成一台可靠的判定器。
退一步，把這三個類別放上一張你可以一直留著的地圖。每個可判定語言都是可辨識的（判定器尤其就是一台碰巧從不繞圈的辨識器），所以可判定是可辨識的嚴格子集。同樣的翻轉論證也顯示可判定是可餘辨識的子集。而兩者的交疊——可辨識且可餘辨識——恰恰就是可判定，不多也不少。在兩者之外，還躺著一些狂野到連辨識都辨識不了的語言。那幅乾淨的三環圖就是目的地，而把這些環切開的，唯獨那個微小、無法修補的「允許永遠繞圈」。