交錯運行要解決的問題
前面幾篇留給你一個令人不安的事實：一台識別器是被允許永遠繞圈的。對在它語言裡的字串，它最終必須接受；但對語言之外的字串，它可能無止境地跑下去，永遠不說「不」。正是那一條允許——那個「迴圈漏洞」——把僅僅是識別器的東西，與一台必須永遠停機並給出裁決的判定器區分開來。到目前為止，我們把它當成一個必須忍受的限制。現在我們要把它變成必須繞道工程化處理的東西，因為我們即將讓好幾台會繞圈的機器並排運行。
這裡有一個陷阱，把它說具體。假設你想知道字串 w 是否屬於兩個可識別語言的聯集，L1 或 L2。最直覺的計畫是：先在 w 上跑機器 M1；若它接受，就接受；否則再在 w 上跑 M2。這個錯誤是致命的——如果 w 在 L2 裡但不在 L1 裡，那麼 M1 可能在 w 上永遠繞圈，於是你根本到不了 M2。你被卡在第一台機器上，等一個永遠不會來的答案，儘管真正的答案（透過 M2 接受）就在那裡。一台接一台地跑之所以失敗，正正是因為那個迴圈漏洞。
交錯運行：每樣東西都跑一點點
交錯運行就是解法，而其想法美妙地簡單：絕不在你查看其他計算之前，讓任何一個計算跑到結束。反之，用公平的輪轉給每個計算一小片時間。想像一位家長同時念睡前故事給好幾個坐不住的孩子聽——與其念完一整本書（而且若有孩子一直喊「再來一次！」，可能永遠念不完），你念一頁給孩子 A、一頁給孩子 B、一頁給孩子 C，然後回到 A 念第二頁，如此類推。沒有任何孩子被餓著，而任何真的會結束的故事，都會在有限時間內結束。這名字來自木工：燕尾榫把它們的齒交錯起來，好讓兩塊木頭咬合在一起——在這裡，我們把許多計算的步驟交錯起來。
讓我們修好先前那個壞掉的聯集。要在輸入 w 上識別 L1 或 L2，就讓 M1 與 M2 步調一致地跑：先做 M1 的一步，再做 M2 的一步，接著 M1 的第二步、M2 的第二步，如此交替下去。若任一機器曾進入它的接受狀態，就停機並接受。現在這論證滴水不漏：若 w 在 L1 裡，M1 在某個有限步數後接受，而交錯運行會抵達那一步；若 w 在 L2 裡，M2 會接受，我們同樣會抵達那一步。另一台機器永遠繞圈再也無所謂了，因為我們從不等它——我們始終只一次等一步。這正是可識別語言對聯集封閉的真正證明。
交錯運行可以從兩台機器擴展到無窮多台，而那正是它真正發揮價值之處。假設你必須為 Sigma-star（字母表上所有有限字串的集合）裡的每一個字串各跑一個計算——那是無窮多個。你不能把第 1 號計算跑到底、再跑第 2 號，因為第 1 號可能繞圈。反之，你走一張三角形的排程表：在第 k 輪，你把前 k 個計算各多推進一步。於是第 1 號計算在每一輪都拿到步數、第 2 號從第 2 輪開始、第 3 號從第 3 輪開始，而任何單一的「（計算，步數）」配對，只需有限多輪就會被抵達。沒有任何無窮的東西被等待；每一件有限的事最終都會被服務到。
Naive (BROKEN): finish each computation before the next C1: step1 step2 step3 ......(may loop forever)..... <-- stuck here C2: never reached C3: never reached Dovetailed (FAIR): advance the first k computations in round k round 1: C1.step1 round 2: C1.step2 C2.step1 round 3: C1.step3 C2.step2 C3.step1 round 4: C1.step4 C2.step3 C3.step2 C4.step1 ... Every pair (Ci, step j) occurs by round i+j-1 -> finite wait. If ANY Ci ever accepts, we see it in finite time, even if every other computation runs forever.
列舉機：一台把語言列出來的機器
交錯運行現在解鎖了一種全然不同——但完全等價——的方式來想像可識別語言。到目前為止，識別器一直是個裁判：你遞給它一個字串，它（也許）說「是」。一台列舉機把這個關係翻轉過來。它是一台完全沒有輸入、卻外接了一台印表機的圖靈機。你把它打開，就讓它跑；只要它高興，它就印出一個字串，然後繼續。一台列舉機的語言，就是它曾經印出的所有字串所成的集合，順序不拘，允許重複。別把它想成在門口查證件的保鑣，而要想成一位不知疲倦的作者，永遠一個接一個地出版這個語言的成員。
這條招牌定理——列舉機刻畫——說的是：這兩幅圖像描述的是同一類：一個語言是圖靈可識別的，當且僅當有某台列舉機把它列舉出來。（這正是為何這一類又叫做遞迴可列舉——「可列舉」就字面而言正是列舉機的承諾。）這證明的兩個方向都很短，而且都倚賴交錯運行、或它的近親：對所有字串作一次系統性的走訪。一旦你看懂它們，這個等價就不再像個巧合，而開始像是必然。
- 由列舉機造出識別器（簡單的方向）。給定一台列舉機 E，為同一個語言造一台識別器 M：在輸入 w 上，跑 E 並盯著它的印表機；每當 E 印出一個字串，就把它與 w 比對；若相符，M 就接受。若 w 在語言裡，E 最終會印出它，於是 M 接受；若不在，M 就一直盯著看（它可能永遠跑下去——而這沒關係，識別器是被允許繞圈的）。
- 由識別器造出列舉機（交錯運行的方向）。給定一台識別器 M，造一台列舉機 E。天真地先在第 1 號字串上跑 M、再跑第 2 號，會在 M 於第 1 號繞圈時卡住。所以 E 改用交錯運行：它把 Sigma-star 的所有字串 s1, s2, s3, …… 依序列出，並對其中前 k 個各跑 M 跑 k 步，讓 k 永遠增大。每當這個交錯運行看到 M 接受了某個字串 si，E 就印出 si。
- 驗證它確實奏效。M 所接受的每個字串，都在某個有限步數內被接受，而交錯排程在有限多輪後就會抵達那個「（字串，步數）」配對，於是 E 印出它。M 從不接受的字串（它在那些字串上拒絕或繞圈）則永遠不會被印出。所以 E 印出的恰好就是 M 的語言——兩台機器一致，等價於是得證。
若能「依序」列舉，你就能「判定」
列舉機這幅圖像，回報給我們一個關於「可判定 vs 可識別」鴻溝的鋒利洞見。一台普通的列舉機可能以任意雜亂的順序印出，還會重複。但假設有一台列舉機能以嚴格遞增的順序印出它的字串——短的先印、長度相同時按字母序、且不重複。那麼一件強而有力的事就跟著成立了：這個語言不只是可識別，而是可判定的。原因在於，有序的輸出讓你能夠放棄。要判定 w 是否為成員，就跑這台有序列舉機並盯著看：當它印出 w 的那一刻，接受；當它印出任何在順序上排在 w 之後的字串那一刻，你就知道 w 永遠不會出現，於是拒絕。順序把那個沒完沒了的「繼續等」，轉換成了一個確定的「它早該出現了」。
這與上一篇的定理交錯得（容我玩個雙關）漂亮：一個語言是可判定的，當且僅當它與它的補集都是可識別的。「有序列舉機」這個條件，不過是同一枚硬幣的另一面。一台判定器總能被轉成一台有序列舉機（依「先長度後字母序」對每個字串跑判定器，把被接受的印出來），而一台有序列舉機也總能被轉成一台判定器，正如我們剛剛所見。所以「可判定」、「可識別且補集可識別」，以及「能依遞增順序列舉」，是同一類東西的三種等價描述。
為何可識別語言對「補集」不封閉
交錯運行替可識別語言買到了一些慷慨的封閉性，但它買不到一切——而它無法填補的那道鴻溝，正是這一階最有教育意義的部分。我們剛看到，可識別語言對聯集封閉（把兩台識別器交錯運行，任一接受就接受），同樣對交集也封閉（把兩台都跑到結束，這裡循序跑也無妨，唯有兩台都接受才接受）。它們對串接與克林星號（Kleene star）也封閉，全都透過交錯運行或猜測達成。可判定語言對以上全部也封閉，而且對補集也封閉（一台判定器總會停機，所以只要把它的接受狀態與拒絕狀態對調即可）。
但可識別這一類不對補集封閉，原因在於那個「對調」的把戲失靈了。如果 M 只是一台識別器，把接受與拒絕對調是無望的：原本 M 永遠繞圈（不給答案）之處，對調後的機器仍舊永遠繞圈，所以它也不接受補集。這裡沒有交錯運行能來搭救，因為那些缺席的答案根本從未被產生過——你無法去交錯一個不存在的步驟。這不是聰明才智的失敗；它是關於這一類的、一個真真切切的結構性事實。
最乾淨的證明把整個這一階串在一起。為了導出矛盾，假設可識別語言確實對補集封閉。那麼對任何可識別的 L，它的補集也會是可識別的——意思是 L 同時是可識別與補集可識別的，而依上一篇的定理，這會讓每一個可識別語言都變成可判定的。但下一階將會展示一個語言（圖靈機的接受問題），它是可識別卻可被證明不可判定的。矛盾。所以「可識別但不可判定」的語言確實存在，而它們的存在，恰恰就是擋住「對補集封閉」的那道牆。迴圈漏洞不是怪癖；它是承重結構。