书城现实数学大帝
57676100000099

第99章 停机问题

什么是可以计算的,只要把不可以计算的全部排除,剩下的就是全部可以计算的了。

马丁·戴维斯《可计算性和不可解性》开始研究什么样的计算是可计算的。

那什么又是不可以计算的?

首当其冲的是停机问题。令Z表示一个简单图灵机。关于Z,有如下判定:

对于一个给定的瞬间描述α,判定是否存在一个以α开始的对Z的计算。也就是说,我们希望如果给定初始状态,那么Z会不会最终停止?这就是Z停机问题。

最后戴维斯说:“存在一种图灵机,其停机问题是递归无解的。”