图灵可识别=>枚举

Question

我得到了从枚举器到图灵计算机的证明（继续运行枚举器，看看它是否与输入匹配），但我看不出另一种方法的工作原理。

根据我的笔记和书籍（计算理论的介绍 - sipser），以获取图灵机器的图灵枚举者，我们基本上写下了字母的所有组合。然后，您在此输入上运行TM，如果它接受打印出来，请用新的字符串重复AD Infinitum替换。

我遇到的问题肯定是要求该语言可决定的。否则，它可能会陷入某些无限的循环中的第三个单词，从来没有接受或拒绝，肯定永远不会打印出整个语言。

我想念什么？

Answer 1

缺少的是您在字符串上运行Turing Machine $ m $以获取枚举者的方式。与其生成每个字符串，运行$ m $，然后如果$ M $接受（您确定的无效），则输出此字符串，您会执行以下操作，该操作采用了模拟$ M的许多实例的策略$在不同的字符串上“并行”。

假设磁带具有内容$ langle w_1，s_1 rangle ＃ cdots cdots ＃ langle w_n，s_n rangle $，其中$ w_i $是您正在考虑的一句话，$ s_i $是$ m $运行的当前状态在$ w_i $上。这表示正在模拟$ m $的$ n $副本。 $ w_i $存储了，因此我们知道原始输入是什么。

现在运行以下循环

1. 最后，磁带将下一个字符串从$ w in sigma^*$，以及$ m $的初始配置$ s $，也就是说，写成$ ＃ langle w，s rangle $。
2. 模拟磁带上$ m $的每个副本一步。 （大概是使用另一胶。）
3. 如果任何$ m $ s进入接受状态，请将相应的字符串放在输出胶带上。从磁带中删除$ m $的实例。
4. 如果任何$ m $ s进入拒绝状态，请从磁带中删除$ m $的实例。
5. Goto步骤1。

不难说，$ m $接受的所有字符串$ w in sigma^*$最终将在磁带上输出。