枚舉器刻劃（the enumerator characterization）

為什麼可識別語言又叫做遞迴可枚舉（recursively ENUMERABLE）？因為有第二種同樣有效的方式來描述「完全相同的那些語言」：一個語言可識別，恰好等於存在某台機器能把它的成員一個接一個地列出來，像一台不知疲倦的目錄印表機，不停地印出圖書館擁有的每一個書名。它不必結束（清單可能無限，順序與重複都無所謂），但每個成員最終都會被印出，而任何非成員都不會出現。這台列舉裝置就叫枚舉器（enumerator）。

枚舉器是一台帶印表機（輸出通道）、沒有輸入的圖靈機；它就只是運轉並吐出字串。它所枚舉的語言，就是它曾印出的所有字串所成的集合。定理說：一個語言圖靈可識別，若且唯若存在某台枚舉器枚舉它。由識別器造枚舉器：對所有字串 s1, s2, s3, ... 交錯執行識別器，只要某個 si 的模擬接受就印出它。由枚舉器回到識別器：對輸入 w，跑這台枚舉器，一旦它印出 w 就接受（若 w 永遠沒被印出，你就乾脆永遠迴圈——而這正是識別器被允許做的事）。

這就是那個歷史名字的由來，也是一個真正好用的工具。它讓你能藉由展示一個「列舉過程」來證明某語言可識別，而不必造一台接受／拒絕的機器；也讓 RE 語言的封閉性證明變得自然（要枚舉聯集，就交錯執行兩台枚舉器）。一個誠實的細微之處區分了這兩類：一個語言可判定，恰好等於它能以嚴格遞增（已排序）的順序被枚舉——因為這時要測 w，你只要列舉到越過 w 就停。僅僅可識別的語言能被枚舉，但不一定能照排序順序枚舉，這正是它們不必可判定的原因。