可識別語言的封閉性（closure of the recognizable languages）

可識別語言仍然相當穩健，但它帶著一道著名的傷口。因為識別器能可靠地喊「是」，卻可能在「否」上沉默（永遠迴圈），所以任何「只需要確認『是』」的組合方式都行得通——但任何「需要確認『否』」的組合就出問題。於是可識別類別對那些「用一堆『是』拼出一個『是』」的運算封閉，而恰好在那個「需要把『是』翻成『否』」的運算上失敗。

它們對哪些封閉：聯集、交集、串接、Kleene 星號。需要小心的是避免被某台迴圈的子機器卡住。對 L1 與 L2 的聯集，在輸入 w 上你不能先把 R1 跑完再跑 R2——即使 w ∈ L2，R1 也可能永遠迴圈。要改用交錯執行（dovetail）：交替跑 R1 與 R2 的步驟，任一台接受的瞬間就接受。交集較簡單，因為兩者都必須接受：先把 R1 跑到接受、再跑 R2（若 w 在交集裡兩者都會接受；若不在，反正允許迴圈）。串接與星號則靠「對 w 的有限多種切法做交錯執行」搭配跑識別器來處理。每一種情形，接受都恰好在『該接受時』於有限時間內達成。

它們『不』對哪個封閉：補集。這就是那道招牌不對稱。假如可識別語言對補集封閉，那麼每個可識別語言 L 都會有可識別的補集，依「可判定 ⟺ 可識別且共可識別」定理，這會使『每一個』可識別語言都可判定。但 A_TM 可識別卻不可判定——矛盾。所以可識別類別不可能對補集封閉。具體地說，A_TM 可識別而它的補集不可識別：沒有任何機器能可靠地確認「M 不接受 w」，因為確認「不接受」等於要在有限時間內偵測出一個無窮迴圈。