部分定理："A language is Turing-recognizable if and only if some enumerator enumerates it"

Question

我需要帮助来理解这个证明。

如果 w 没有出现在 E 的输出中，它就不会出现在 E 的列表中。他想说什么？

Answer 1

你的定理有两个方向：如果"if"和"only if"。证明是针对"if"方向的。

假设你有一个针对语言L的枚举器E，你能构造一个图灵机M 识别 L？是的你可以。只需定义一个图灵机 M，在输入字符串 w 上，检查 w 是否曾经在 E 的输出中（可能是无限的）。如果是，接受。如果不是reject.

由于 E 是 L 的枚举器，对于 w 中的任何 w =]L, E 最终在停止之前输出 w（如果它曾经停止）。因此，M 对 L 中的每个字符串停止。如果 w 不在 L 中，则 M 永远不会停止，或者 M 拒绝 w.

此外，M 是决策者，而不仅仅是 L 的识别者，M 必须总是停止。

Answer 2

你必须证明这两个部分，因为它包含 "if and only if" 短语。

首先，你应该证明，如果存在一个枚举器E，它枚举了语言L中的所有字符串，我们就可以为这种语言L构造一个识别器。

此识别器使用输入 w（字符串）和运行s 中的 E。 E 是一个枚举器，它一个一个地生成 L 中的所有字符串。如果输入字符串等于这些生成的字符串之一，则接受。如果这种语言是无限的，那么识别器可能不会停止，这对识别器来说不是问题，因为它不是决策器。

第二部分是，如果L是图灵可识别的，那么必须有一个图灵机M可以识别L。枚举器可以构造如下；

for k=1,2,3...
    Run M on w1,w2,w3... in parallelized for k steps
        if M accepts any of the wi then print wi on the printer.

我们运行以有限的步骤将它们并行化的原因与我们更喜欢深度限制搜索而不是深度优先搜索的原因相同。在搜索图上可以走无限死路

Part of the theorem: "A language is Turing-recognizable if and only if some enumerator enumerates it"