如果语言L由 TM决定,我们就说它是递归的。
如果L被TM识别,则它是递归可枚举(re) 的。
假设,枚举器( en-r ) 是一个确定性图灵机,其打印机从空白磁带开始,可以打印字符串 s1, s2, s3, s4... sn... 如果语言是无限的,则永远继续。
程序需要生成正在打印的字符串,所以这是一个图灵机,它在磁带上的某个地方生成语言中的所有字符串。我也可以在磁带上存储其他东西。
en-r 的语言是它打印的所有字符串的集合。En-r 是生成器机器,而不是识别器机器。
对于枚举器 EN,我们说 L(EN) = {s| EN 打印 s}。
关于这种情况,我有 3 个问题:
假设 L 是一个重集,那么我们如何使用识别器为 L 创建一个枚举器?
如果 L 是一种语言,并且有一个枚举器按升序枚举 L,那么为什么 L 是递归的?
为什么如果 L 是递归的,那么有一个 en-r 以递增的顺序枚举它?
谢谢