枚举器

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

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