枚举器

枚举器是带有打印机的图灵机。 图灵机可以使用该打印机作为输出设备来打印字符串。 每次图灵机要向列表中添加一个字符串时，它都会将该字符串发送到打印机。 枚举器是图灵机的一种变体，与图灵机等价。

枚举器 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个磁带中的输入进行比较。 如果匹配，则我们接受输入，否则拒绝。