枚舉器是帶有打印機的圖靈機。 圖靈機可以使用該打印機作為輸出設備來打印字符串。 每次圖靈機要向列表中添加一個字符串時，它都會將該字符串發送到打印機。 枚舉器是圖靈機的一種變體，與圖靈機等價。

枚舉器 E {\displaystyle E} 可以定義為 2-tape 圖靈機（Multitape 圖靈機，其中 k = 2 {\displaystyle k=2} ），其語言為 ? {\displaystyle \emptyset } 。 最初，E {\displaystyle E} 沒有接收到任何輸入，所有的磁帶都是空白的（即，填充有空白符號）。 新定義的符號 # ∈ Γ ∧ # ? Σ {\displaystyle \#\in \Gamma \land \#\notin \Sigma } 是標志 S {\ 顯示樣式 S}。 第二條磁帶可以看作是打印機，上面的字符串之間用# {\displaystyle \#} 分隔。 由 L ( E ) {\displaystyle L(E)} 表示的枚舉器 E {\displaystyle E} 枚舉的語言被定義為第二個磁帶（打印機）上的字符串集。

當且僅當它可以被枚舉器枚舉時，有限字母表上的語言是圖靈可識別的。 這表明圖靈可識別語言也是遞歸可枚舉的。

證明

枚舉器可以枚舉圖靈可識別語言

考慮一個圖靈機 M {\displaystyle M} 并且它接受的語言是 L ( M ) {\displaystyle L(M)} 。 由于輸入字母表 Σ {\displaystyle \Sigma } 上所有可能字符串的集合，即 Kleene Closure Σ ? {\displaystyle \Sigma {*}} 是一個可數集，我們可以將其中的字符串枚舉為 s 1 , s 2 , … , s i , {\displaystyle s_{1},s_{2},\dots ,s_{i},} 等。然后枚舉器枚舉語言 L ( M ) {\displaystyle L(M)} 將遵循以下步驟：

1 for i = 1,2,3,...2 使用輸入字符串 s 1 , s 2 , … , s i {\displaystyle s_{1},s_{2},\ 運行 M {\displaystyle M} dots ,s_{i}} for i {\displaystyle i} -steps3 如果接受任何字符串，則打印它。

現在的問題是 L ( M ) {\displaystyle L(M)} 語言中的每個字符串是否都會被我們構造的 Enumerator 打印出來。 對于語言 L ( M ) {\displaystyle L(M)} 中的任何字符串 w {\displaystyle w} TM M {\displaystyle M} 將運行有限數量的步驟（假設它是 k {\displaystyle k} for w {\displaystyle w} ) 接受它。 然后在第 k {\displaystyle k} 枚舉器的第 w {\displaystyle w} 步將被打印出來。 因此，枚舉器將打印 M {\displaystyle M} 識別的每個字符串，但單個字符串可能會打印多次。

可枚舉語言是圖靈可識別的

構造一個識別可枚舉語言 L {\displaystyle L} 的圖靈機 M {\displaystyle M} 非常容易。 我們可以有兩盤磁帶。 在一盤磁帶上，我們獲取輸入字符串，在另一盤磁帶上，我們運行枚舉器以逐一枚舉語言中的字符串。 一旦在第二個磁帶中打印了一個字符串，我們就將它與xxx個磁帶中的輸入進行比較。 如果匹配，則我們接受輸入，否則拒絕。