第四百九十六章 停机问题

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

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

首当其冲的是停机问题。

令z表示一个简单图灵机。

关于z，有如下判定：

对于一个给定的瞬间描述a，判定是否存在一个以a开始的对z的计算。

也就是说，我们希望如果给定初始状态，那么z会不会最终停止？这就是z停机问题。

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

一秒记住新域名 https://www.d9zw.net

本章未完，点击下一页继续阅读