我需要帮助来理解这个证明。
“首先我们证明如果我们有一个枚举器 E 来枚举 语言 A，TM M 识别 A。TM M 按以下方式工作。
PROOF M = "输入 w:
1.运行E，E每输出一个字符串，就与w进行比较。
- 如果 w 出现在 E 的输出中，则接受。”
- 显然，M 接受 E 列表中出现的那些字符串。 ”
如果 w 没有出现在 E 的输出中，那么它也不会出现在 E 的列表中。 他想说什么？
最佳答案
你必须证明这两个部分，因为它包含“当且仅当”短语。
首先，你应该证明，如果存在一个枚举器 E 枚举语言 L 中的所有字符串，我们就可以为该语言 L 构造一个识别器。
该识别器使用输入 w(字符串)并在内部运行 E。 E是一个枚举器，它一一生成L中的所有字符串。如果输入字符串等于这些生成的字符串之一，则接受。如果这种语言是无限的，那么识别器可能不会停止，这对于识别器来说不是问题，因为它不是决策器。
第二部分是，如果 L 是图灵可识别的，那么一定存在一个可识别 L 的图灵机 M。 枚举器可以构造如下；
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.
我们以有限的步骤并行运行它们的原因与我们更喜欢深度有限搜索而不是深度优先搜索的原因相同。它可以在搜索图上经历无限的死路径。
关于computation-theory - 部分定理: "A language is Turing-recognizable if and only if some enumerator enumerates it"，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31860681/