或者可能存在用于关机问题的通用算法。
但是,一如既往,有细微差别。
如果有兴趣,我要猫。
引言
1936年,艾伦·图灵(Alan Turing)证明,没有通用的算法可以分析其他算法并指出程序是否会挂起。
我想立即在所有e上加点并描述我使用的术语,以便不加理解。
程序冻结 -无论命令的执行速度和并行计算的速度如何,该算法将无限期地工作。 无论我们有多大的超级计算机,该算法都将始终运行无限量的时间。
在有限的时间内执行程序 -任何计算机上的算法都将完成其计算,无论其数量如何。 例如,如果一个算法运行了3亿年,这并不意味着它就挂起了,只需要在当前资源上运行3亿年,它就永远结束了。
现在您可以继续。
图灵的证明可以描述如下:在输入处有一个特定的oracle S(算法),其中提供了对算法N和输入数据X的描述;如果算法N没有停止,则程序停止并返回1,并在输入处接收X。
否则程序不会停止,如果算法N在收到输入X后停止。如果我们将自己的描述输入到oracle中,将会出现矛盾,并且算法本身也会矛盾。 可以在
Wiki上找到详细信息。
甲骨文存在但他需要一个兄弟
如果甲骨文应该停止分析它的算法,那么您就不会感到困惑,我直接为这个事实感到困惑,因此为证明起见,我们将略微纠正甲骨文的结论。 让oracle返回1或0。那么,请问,如果我们使用伪代码编写,则什么都没有改变:
If ((N)==0){
While (true){
}
}
, , :
, , :
S1 0 1 0 1 , .
S2 0 1 , . 1 1 , 0 . 0 , 1 .
, . .
, , . , , .
, . , .
:
If ((N)==0){
While(true){
}
}
If ((N)==0){
While(true){
}
}
.
.
, . , . - , .
, , . , .