枚舉器（enumerator）

替派對指定賓客名單有兩種方式。一種是門口的守衛，逐一核對到場者是否在名單上、回答是或否，這是識別器（recognizer）。另一種是大廳裡的印表機，讓它一直跑，就會一個接一個印出每位賓客的名字，直到所有名字（可能有無窮多個）都出現為止，這就是枚舉器（enumerator）。枚舉器是圖靈機的一種變體：它不接收輸入並做判斷，而只是把某語言的成員一一列在輸出上。

形式上，枚舉器是一台帶有特殊「印表」輸出（以及一條工作帶）但沒有輸入的圖靈機。它從空白帶開始永遠運行，偶爾發出訊號「這個字串完成了，印出來」。枚舉器 E 的語言恰好是它曾印出的所有字串所成的集合。字串可以任意順序出現，也可以重複；重要的只是最終出現的那個集合。讓這套機制能處理無窮語言而不卡住的關鍵技巧是交錯執行（dovetailing）：機器不在完整處理完一個候選之前就絕不碰下一個，而是交織地推進許多候選，各推進一點，於是沒有任何單一的難纏字串能凍結整個列舉。

枚舉器給了一個重要類別的另一種刻畫：一個語言是圖靈可識別的，若且唯若有某個枚舉器能列舉它。這正是可識別語言又被稱作「遞迴可枚舉（recursively enumerable，常簡寫為 r.e.）」的原因——它們恰好就是某物能枚舉出來的語言。誠實的微妙之處：枚舉器不必按排序印出，而且你一般無法判斷某個特定字串會在何時出現、甚至會不會出現。若你總能把列舉強制成遞增順序、並偵測到「我已越過 w 應該出現的位置」，那麼該語言就會是可判定的，而可判定嚴格強於僅僅可識別。