math - 使用图灵机实现枚举器 - 冗余打印

Question

在以下算法中：

我们使用图灵机实现了一个枚举器，枚举器应该输出图灵机接受的语言。来自 Σ* 的接受词被打印多次（每次迭代之前打印的词将被再次打印）。

为什么我们不能只说 - “对 Σ* 中的每个单词运行 M。如果它接受则打印，如果拒绝则继续下一个单词”。然后我们不会多次打印每个单词。

为什么不必要的打印？

图像中的算法是：

如果 TMM识别一种语言A，我们可以为A. 假设s1, s2, s3, ... 是Σ*.

E=“忽略输入

i1) 对= 1, 2, 3, ...重复以下操作

2)在每个输入, , , 上M运行步骤。. . .is1s2s3si

3）如果任何计算接受，打印出相应sj的。”</p>

如果M接受一个特定的字符串，它将出现在生成的列表中E（实际上是无限多次）

谢谢

Answer 1

如评论中所述：问题是某些计算可能不会终止。因此，如果您按顺序执行它们，则永远不会执行第一个非终止计算之后的那些。

给定的算法使用标准技术来解决这个问题：dovetailing。

您可以将第 3 步更改为“如果任何计算在i步骤后接受，则打印” - 这样就没有不必要的打印了。但是你必须在每次模拟期间计算步骤，这意味着一些额外的工作。作者选择了一个编程简单但效率不高的选项。