图灵机中的递归和递归可枚举语言？

Question

我们说语言 L 是递归如果它是由 TM 决定。

L 是 递归可枚举的 (r.e.) 如果它被识别通过TM.

假设，enumerator (en-r) 是一个带有打印机的确定性图灵机，它以空白纸带开始，可以打印字符串 s1, s2, s3, s4... sn... 如果语言是无限的，则永远持续下去。

程序需要生成正在打印的字符串，所以这是一个图灵机，可以在磁带上的某个地方生成语言中的所有字符串。我也可以在磁带上存储其他东西。

en-r 的语言是它打印的所有字符串的集合。 en-r是生成机，不是识别机。

对于枚举数 EN，我们说 L(EN) = {s| EN 打印 s}.

关于这种情况，我有 3 个问题：

谢谢

Answer 1

我将在最后解决问题 (1)，因为它可能是其中最棘手的。

对于 (2)，假设您有一个以递增顺序打印集合的枚举器。要从中构建决策程序，请执行以下操作。获取您的输入字符串 w，然后是运行枚举器，直到发生以下情况之一：

枚举器打印您输入的 w。那样的话，你输入的w肯定是语言
枚举器打印字符串 x，其中 w < x。在这种情况下，枚举器不会打印您的字符串，并且由于此时枚举器的所有输出 z 都满足 w < x < z，因此它永远不会打印您的输入。然后你就可以拒绝了。
枚举器停止而不打印您的输入字符串 w。那样的话，肯定是语言不通，你可以拒绝。

这三个选项中的一个肯定会发生，因此您可以保证该过程在所有输入上停止，因此是一个决策者。

对于 (3)，假设 D 是您的语言的决策者。下面是一个枚举器的伪代码，它以递增的顺序打印语言中的字符串：

for each string w, in increasing order:
    run D on w.
    if D accepts w, print w.

你明白为什么这会按排序顺序打印集合 S 了吗？

现在，回到 (1)。有几种方法可以证明这一点。传统的是用相吻合的思路。想象一下，以某种顺序按 w0、w1、w2、w3……的顺序写出所有字符串。然后，执行这段代码，假设 R 是 L 的识别器：

for i = 1 to infinity
    for j = 0 to i:
        run R on w_j for i - j steps.
        if R accepted, print w_j.

想法是对于 L 中的每个字符串 w_j，有一些 i 的选择，其中 R 在 i - j 步骤中接受 w_j，所以这最终将打印 L 中的每个字符串。

Recursive vs recursively enumerable language in Turing Machines?