24

在亚马逊上阅读 Stephen Wolfram 的“A New Kind of Science”的评论时，我发现了以下声明：

每个计算机科学 (CS) 学生都知道 dovetailer，这是一个非常简单的 2 行程序，它系统地列出并执行通用计算机（例如图灵机 (TM)）的所有可能程序。

有人可以给出一个“简单的两行程序”来说明“鸽派”吗？

4

2 回答 2

29

CS学生通常手头有图灵机到整数的编码，当他们编写他们的软件图灵机模拟器时需要它，该模拟器将图灵机作为输入，并将指定机器的输出作为输出写入。可以安排这种编码具有每个整数都是不同的有效程序的属性。

因此，列出和执行所有程序的天真的两行代码将是：

for (int i = 0; ; ++i) 
    printf("%d: %d\n", i, universal_turing_machine(i));

这忽略了 Cint中的固定宽度类型。

现在，显然该程序并没有走得太远，因为很快它就会遇到i相应的图灵机不会停止的情况。所以“燕尾”技巧是从第一台机器运行一条指令，然后从第二台机器运行一条指令，从第一台机器运行一条指令，然后从第三台机器运行一条指令，第二台，第一台，依此类推。当每台机器停止时（如果它停止了），您当然可以停止处理它，或者在它的“时间片”中什么也不做。

考虑到每一步图灵机之间必要的上下文切换，我不太清楚这是一个“双线”。但是dovetail程序有理论上的用途（在实践中可能没有用处）。关于它的一件有趣的事情是它具有以下属性：

如果存在P在多项式时间内解决问题 X 的程序（并提供证明解决方案所需的信息），则燕尾程序在多项式时间内解决 X。

证明是相当简单的（它需要恒定的时间，相当于执行P*(P-1)/2图灵指令到达正确程序的开始P[*]，然后执行它的多项式时间比单独执行该程序所需的时间更短）。我觉得最有趣的财产的重新陈述是：

如果 P=NP，那么我们已经知道所有 NP 完全问题的多项式解。

我们只是还没有证明它们是多项式的。P=NP 的证明将完成该证明，而无需实际展示解决问题的子程序。燕尾程序本身可以在运行过程中计算出来——当每台机器停止时，使用多项式时间“这是原始输入的 X 的解决方案吗？” X 是 NP 所暗示的算法。如果是解决方案，则输出并停止。如果不是，请继续。

[*] 好吧，也许是线性时间，因为当你创建每个新的虚拟图灵机时，你需要给它一个输入的副本来处理。同样在实践中，上下文切换可能不是恒定时间，所以称之为二次。Hand-wave-hand-wave 它是多项式的好吗？

于 2011-02-24T16:34:02.867 回答
2

好吧，图灵机程序实际上是一个表（状态 x 磁带符号），因此该程序将枚举所有此类可能的表。像那样：

for(int symbol_count = 1; true; symbol_count++)
{
    for(int state_count = 1; state_count <= symbol_count; state_count++)
    {
        gen_table(symbol_count, state_count);
    }
}

其中 gen_table 枚举了所有这种大小的动作表（例如，将表视为一个大数字，将状态视为数字）。这比 C 语言中的两行要长，Wolfram 可能使用了其他更强大的语言。

于 2011-02-24T16:16:10.177 回答