返回

数学心

首页
关灯
护眼
字体:
大
中
小
第四百九十六章 停机问题
存入书签 我的书架 返回目录
亲爱的书友,您现在访问的是转码页面,可能导致更新不及时,访问最新更新请点击


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

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

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

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

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

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

上一章 目录 下一章