每个计算机科学(CS)学生都知道 dovetailer,这是一个非常简单的两行程序,可以系统地列出并执行所有可能的程序,用于通用计算机,如图灵机(TM)。
有人能给出一个“简单的两行程序”,以说明“dovetaling”吗?
一个计算机科学专业的学生通常手头都有将图灵机转换为整数的编码,这是他们在编写软件图灵机仿真器时所需的,该仿真器接受一个图灵机作为输入,并将指定机器的输出作为输出。可以安排使得此编码具有每个整数都是不同的有效程序的属性。
因此,列出并执行所有程序的天真两行代码如下:
for (int i = 0; ; ++i)
printf("%d: %d\n", i, universal_turing_machine(i));
在 C 语言中,int
是一种固定宽度的类型,这一点被忽略了。
显然,该程序无法运行得很远,因为很快它就会遇到一个相应的图灵机不会停机的 i
。那么“鸽尾式”技巧是:先运行第一台机器的一条指令,然后运行第二台机器和第一台的一条指令,接着依次运行第三、第二、第一台的指令,以此类推。当每台机器(如果它停机)停机时,你可以停止处理或者只是在其“时间片”中坐着什么也不做。
我不知道为什么这是“两行代码”,考虑到每次需要在图灵机之间进行上下文切换。但是鸽尾程序具有理论用途(可能在实践中没有用处)。关于它的一个有趣之处是它具有以下性质:
如果存在一个程序
P
,可以在多项式时间内解决问题 X(并提供证明解决方案所需的信息),那么鸽尾程序可以在多项式时间内解决问题 X。
证明非常简单(它需要常数时间等价于执行 P * (P-1) / 2
图灵指令来到达正确的程序 P
的开始位置 [*],然后执行它比在其自身上执行该程序所需的时间多项式恶劣)。我认为最有趣的属性重新陈述是:
如果 P = NP,则我们已经知道所有 NP 完全问题的多项式解。
我们尚未证明它们是多项式的。如果 P=NP 的证明完成,而无需展示解决问题的子程序是哪一个,鸽尾程序本身可以在运行过程中找出答案—当每个机器停机时,使用隐含于 X 是 NP 的事实的多项式时间“这是原始输入 X 的解吗?”算法。如果它是解决方案,则输出并停止。如果不是,继续执行。
[*]好吧,也许是线性的时间,因为当你创建每个新的虚拟图灵机时,你需要给它一份要处理的输入的副本。而且在实践中,上下文切换可能不是固定时间,所以把它称为二次的。大概就是这样,它是多项式的,好吗?
图灵机程序实际上是一个表格(状态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可能使用了其他更强大的语言。