第三百五十二章 停机问题
  什么是可以计算的，只要把不可以计算的全部排除，剩下的就是全部可以计算的了。

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

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

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

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

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



更多完整内容阅读登陆

《墨缘文学网，https://wap.mywenxue.org》