turing-machines - 图灵机中的递归与递归可枚举语言？

Question

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

如果L被TM识别，则它是递归可枚举(re) 的。

假设，枚举器( en-r ) 是一个确定性图灵机，其打印机从空白磁带开始，可以打印字符串 s1, s2, s3, s4... sn... 如果语言是无限的，则永远继续。

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

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

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

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

谢谢

score 0 · Accepted Answer

我将最后解决问题（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 中的每个字符串。

1 回答 1