在阅读亚马逊上斯蒂芬·沃尔夫拉姆(Stephen Wolfram)的“一种新型科学”的评论时，我遇到了以下说法:
有人可以给一个“简单的两行程序”来说明“燕窝”吗？
最佳答案
CS学生通常手头上将Turing机器编码为整数，这是他们编写软件Turing机器模拟器时需要的，该软件将Turing机器作为输入，并将指定机器的输出作为输出。可以安排这种编码具有每个整数都是不同的有效程序的属性。
因此，列出并执行所有程序的幼稚的两层代码将是:
for (int i = 0; ; ++i)
printf("%d: %d\n", i, universal_turing_machine(i));
这忽略了C语言中的
int是固定宽度的类型。现在，该程序显然不会走得太远，因为很快它会命中一个
i，因此相应的Turing机器不会停止运行。因此，“燕尾”技巧是从第一台机器运行一条指令，然后从第二台机器运行一条指令，然后从第一台机器运行另一条指令，然后从第三台机器开始运行第二条指令，第二台，等等，依次类推。当每台机器停止(如果停止)时，您当然可以停止对其进行处理，或者只是在其“时间片”中不做任何事情。考虑到在图灵机每一步之间必须进行上下文切换，我不太清楚这是“两层的”。但是燕尾榫程序在理论上有用(实际上可能没有用)。关于它的一件有趣的事是它具有以下属性:
证明非常简单(花费恒定的时间等同于执行
P*(P-1)/2 Turing指令才能到达正确程序P [*]的开始，然后执行该程序的时间要比单独执行该程序所花费的时间多很多) 。我发现最有趣的属性重述是:我们只是尚未证明它们是多项式。 P = NP的证明可以完成该证明，而无需实际展示解决问题的子程序。燕尾榫程序本身可以解决问题-当每台机器停止运行时，使用多项式时间“这是对原始输入的X的一种解决方案吗？” X表示NP所暗示的算法。如果是解决方案，请输出并停止。如果不是，继续前进。
[*]好吧，也许是线性时间，因为在创建每个新的虚拟图灵机时，需要给它一个输入副本以进行处理。同样在实践中，上下文切换可能不是恒定的时间，因此将其称为二次方。手波手波是多项式好吗？