什么是"鸠尾"？

Question

在阅读亚马逊上Stephen Wolfram的"新种科学"评论时,我发现了以下声明:

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

有人能给出"简单的2线程序",说明"dovetaling"吗？

Answer 1

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

因此,列出并执行所有程序的天真双线将是:

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

这忽略了C int中的固定宽度类型.

现在,很明显,程序并没有走得太远,因为它很快就会遇到i相应的图灵机没有停止的程序.因此,"燕尾"技巧是从第一台机器运行一条指令,然后从第一台机器运行一条指令,从第一台机器运行另一条指令,然后从第三台,第二台,第一台运行一条指令,依此类推.当每台机器停机(如果它停止),当然你可以停止处理它或只是在它的"timeslices"中无所事事.

考虑到图灵机在每一步所需的上下文切换,我不知道这是一个"双线".但燕尾计划具有理论用途(在实践中可能没有用).关于它的一个有趣的事情是它具有以下属性:

如果存在一个P在多项式时间内解决问题X 的程序(并提供证明解的必要信息),则燕尾程序在多项式时间内求解X.

证明相当简单(它需要恒定的时间等同于执行P*(P-1)/2图灵指令才能到达正确的程序P[*]的开始,然后只有多数时间来执行它比执行该程序所花费的更多时间).我发现最有趣的财产的重新声明是:

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

我们还没有证明它们是多项式的.P = NP的证明将完成该证明而不实际展示解决问题的子程序中的哪一个.燕尾程序本身可以解决这个问题 - 当每台机器停止时,使用多项式时间"这是原始输入的X解决方案吗？" X是NP的算法.如果是解决方案,则输出并停止.如果不是,继续前进.

[*]好吧,也许是线性时间,因为当你创建每个新的虚拟图灵机时,你需要给它一个输入的副本来处理.同样在实践中,上下文切换可能不是恒定时间,因此将其称为二次方.手波手动它的多项式好吗？