枚举器是带有打印机的图灵机。 图灵机可以使用该打印机作为输出设备来打印字符串。 每次图灵机要向列表中添加一个字符串时，它都会将该字符串发送到打印机。 枚举器是图灵机的一种变体，与图灵机等价。
枚举器 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个磁带中的输入进行比较。 如果匹配，则我们接受输入，否则拒绝。
内容由匿名用户提供，本内容不代表vibaike.com立场，内容投诉举报请联系vibaike.com客服。如若转载，请注明出处：https://vibaike.com/198235/
