什么是可以计算的,只要把不可以计算的全部排除,剩下的就是全部可以计算的了。
马丁·戴维斯《可计算性和不可解性》开始研究什么样的计算是可计算的。
那什么又是不可以计算的?
首当其冲的是停机问题。令z表示一个简单图灵机。关于z,有如下判定:
对于一个给定的瞬间描述a,判定是否存在一个以a开始的对z的计算。也就是说,我们希望如果给定初始状态,那么z会不会最终停止?这就是z停机问题。
最后戴维斯说:“存在一种图灵机,其停机问题是递归无解的。”
状态提示: 停机问题
本章阅读结束,请阅读下一章
本章阅读结束,请阅读下一章
TXT下载地址:http://www.77kshu.top/txt/xiazai208161.html
手机阅读:http://m.77kshu.top/208161/
发表书评:http://www.77kshu.top/book/208161.html
为了方便下次阅读,你可以在顶部"加入书签"记录本次(停机问题)的阅读记录,下次打开书架即可看到!请向你的朋友(QQ、博客、微信等方式)推荐本书,蔡泽禹谢谢您的支持!!
手机阅读:http://m.77kshu.top/208161/
发表书评:http://www.77kshu.top/book/208161.html
为了方便下次阅读,你可以在顶部"加入书签"记录本次(停机问题)的阅读记录,下次打开书架即可看到!请向你的朋友(QQ、博客、微信等方式)推荐本书,蔡泽禹谢谢您的支持!!