接上線索：兩種命運與那一塊缺角
到現在你已從這一階帶著兩個事實。第一，一個可判定語言有一台機器——一台判定器——它永遠停機：對每個輸入它最終都會停下並說是或否，絕不會卡在原地空轉。第二，一個僅僅可辨識的語言有一台機器，它對語言中的每個字串都說是，但對語言之外的字串，它被允許做比說否更弱的事：它可以永遠繞圈。那道漏洞——一台永不停機之機器的沉默——正是「判定」與「辨識」之間的全部落差，而第二篇正是細談了為什麼辨識器被准許保持沉默而非拒絕。
於是空中懸著一個自然的問題。如果辨識器唯一的弱點是它對非成員可能沉默，那要怎樣才能補上那個洞、把一台僅僅的辨識器升級成完整的判定器？你也許會猜「加個計時器就好」，但那行不通：沒有通用的辦法知道多久才算夠久，因為一台尚未停機的機器，可能恰好在下一步停機，也可能永不停機。真正的答案出奇地乾淨，正是本篇的主題：一個語言可判定，恰恰就在它以及它的補集兩者都可辨識的時候。我們稱之為可判定 iff 可辨識且可餘辨識定理。
「可餘辨識」是什麼意思
先談補集。一個語言 L 在字母表 Σ（sigma，那個固定的合法符號集合）上的補集，是 Σ 上所有不在 L 中的字串所成的集合，記作「非 L」或加一條上槓。若 L 是「所有能編譯的 C 程式」，它的補集就是「所有不是可編譯 C 程式的字串」——其中也包含每一個亂碼字串，而不只是壞掉的程式。當一個語言的補集可辨識時，我們稱它可餘辨識。所以「可餘辨識」不是一種新機器；它不過是這句話：「存在一台辨識不在 L 中之字串的辨識器」。
把這兩半並排來讀，圖像就清晰了。L 的辨識器是一台擅長說是的機器：它恰好對 L 的成員停機並接受，而被允許對非成員繞圈。非 L 的辨識器則是一台對 L 擅長說否的機器：它恰好對 L 的非成員停機並接受（而對成員繞圈）。一台可靠地確認「在 L 中」，另一台可靠地確認「不在 L 中」。各自單獨都是半盲的；問題是當你同時擁有兩者，會得到什麼。
定理，以及證明它的並行運行訣竅
這個主張有兩個方向，而一條乾淨的定理把兩邊都證了。容易的方向：若 L 可判定，則 L 與非 L 兩者都可辨識。這幾乎是免費的——L 的判定器永遠停機並給是／否，所以它尤其是 L 的一台辨識器；而要辨識非 L，就跑同一台判定器並把它的答案反轉。一台會停機的機器反轉後仍是會停機的機器，所以非 L 甚至是可判定的。於是可判定語言理所當然地既可辨識又可餘辨識。有趣的內容在另一個方向。
困難的方向：若 L 可辨識且可餘辨識，則 L 可判定。這裡有個讓它不顯然的疑慮。你手上有辨識 L 的機器 M1，與辨識非 L 的機器 M2。給定輸入 w，何不先跑 M1，若它拒絕就跑 M2？因為 M1 可能對 w 永遠繞圈——你會永恆地等在 M1 的門口，連 M2 都到不了。一前一後地跑，會繼承我們正想治癒的那個繞圈病。解法是讓它們同時跑、輪流推進，這樣兩者都困不住你。
- 建一台 L 的新判定器 D。它的輸入是一個字串 w。
- D 同步在 w 上模擬兩台機器：先做 M1 的一步、再做 M2 的一步、接著 M1 的下一步，如此永遠交替——這種交錯，與你下一篇會再遇到的「並行交織」是同一個點子。
- 最終必然恰好發生兩件事之一。若 M1 停機並接受，則 w 在 L 中，於是 D 停機並說是。
- 若反過來是 M2 停機並接受，則 w 在非 L 中，所以 w 不在 L 中，於是 D 停機並說否。
- D 永遠停機。為何？每個 w 恰好屬於 L 與非 L 之一，所以 M1、M2 中保證有一台會接受 w。並行地跑兩者，意味著我們絕不會卡著等那台繞圈的——那台註定會接受的，在有限多步之後就會輪到它。
這就是全部的證明，而它的引擎是並行模擬訣竅：交替推進步數，好讓一台繞圈的機器永遠餓不死它那台會停機的夥伴。D 之所以是全函式——對所有輸入停機——的深層原因，是這個邏輯事實：「w 在 L 中或 w 在非 L 中」永遠為真。「是否屬於 L」是個貨真價實的是非題；我們只是缺一個辦法去逼兩台辨識器之一在有限時間內表態，而把它們一起跑恰恰做到了這點。注意，全程從未需要任何計時器、也從未需要對運行時間設限。
封閉性：對稱在哪裡成立、又在哪裡斷裂
這條定理把一切重整成一張俐落的三區地圖。可判定語言坐在正中央，那片機器永遠停機的平靜核心。圍著它們，可辨識語言往「是的一側」鼓出去，可餘辨識語言往「否的一側」鼓出去。定理說那兩塊鼓包的重疊區，恰好就是正中央那塊可判定的——不多也不少。這就是可判定／可辨識／可餘辨識圖像，值得把它牢牢釘在腦中，因為下一階會用具名的例子把每個區域填滿。
現在談封閉性，這裡冒出一個美麗的不對稱。可判定語言對補集封閉：如我們所見，只要把判定器的答案反轉，你仍然永遠停機。它們對聯集與交集也封閉——跑兩台判定器，兩台都會結束，再用「或」或「且」把它們的裁決合起來。所以可判定語言構成一個舒適、對稱的世界：可判定語言的每一種布林組合都可判定。這正是你直覺上會盼望的封閉行為。
可辨識語言則不同。它們確實對聯集與交集封閉——把兩台辨識器並行跑（聯集：兩者任一接受就接受；交集：唯有兩者都接受才接受，這裡前後接連跑也行，因為都得停機才能接受）。但可辨識語言對補集不封閉。倘若封閉，那每個可辨識的 L 也都會有一個可辨識的補集，使每一個可辨識語言都可餘辨識——再依我們剛證的定理，那就會讓每個可辨識語言都可判定。我們會在後面一篇看到，某些可辨識語言可被證明不可判定（著名的就是接受問題 A_TM）。所以補集封閉不可能成立；假設它成立會直接導出矛盾。
枚舉器觀點，與對 DFA 的一行心算檢查
「可辨識」還有第二種同樣鮮活的想像方式，下一篇會把它完整展開。想像一台機器，它不是被問某一個字串，而是就坐在那裡，一個接一個地印出 L 中所有的字串——一種不知疲倦的列表製造者，叫做枚舉器。一個語言可辨識，恰恰就在某台枚舉器能印出它每一個成員的時候（順序任意、可重複、想花多久就花多久）。「可餘辨識」於是意味著存在一台枚舉器，能列出每一個不在 L 中的東西。同時擁有兩張列表，直覺上就是擁有了完整的答案卷——這再次說明了為何兩者合起來給你可判定性。
人很容易得出「可辨識但不可判定」是常態的印象，所以讓我們用具體而令人安心的東西錨定另一個極端。拿任何關於一台固定的確定性有限自動機的尋常問題——比方說一台 DFA 的空語言問題：這台 DFA 是否一個字串都不接受？你可以用一個永遠停機的、樸素的有限程序解決它：從 DFA 的起始狀態出發，沿著轉移把每個可到達的狀態標記起來（一次圖搜尋）；唯有當沒有任何接受狀態被標記到時，這台 DFA 的語言才是空的。這裡沒有輸入字串可繞圈——那台自動機本身就是整份有限的輸入——所以這個問題乾脆俐落地可判定。
EMPTINESS of a DFA (does it accept nothing?)
input: a DFA M = (Q, Sigma, delta, q0, F)
1. mark q0
2. repeat until no change:
if state q is marked and delta(q, x) = p,
then mark p (for every symbol x in Sigma)
3. if NO state in F got marked -> ACCEPT (L(M) is empty)
else -> REJECT (L(M) is nonempty)
This loop must stop: there are only finitely many states
to mark, so it always halts. A genuine DECIDER, no looping.這是地圖平靜的核心，而接下來兩篇探索它的外緣。把那條中心等式帶在身上：可判定 = 可辨識且可餘辨識。它告訴你，「僅僅辨識」與「真正判定」之間的落差，恰恰就是少了一台補集辨識器——而把兩台普通辨識器並行跑、絕不讓任一台的繞圈卡住另一台，就足以補上那道落差。要記住的誠實提醒是：這並不讓每個可辨識語言都可判定。許多語言可辨識，而它們的補集不可辨識，正是那些頑固的單側語言，讓下一階找到了計算的極限。