Question

不可判定性是生命中麻烦的一个事实。停机问题令人失望，因为它表明我们无法拥有一切：我们想要的是能力不受限制的通用编程语言，但还想要写出程序产生一个不会陷入无限循环的结果，或者至少是子例程作为某个更大的长期运行任务的一部分能停机（参见8.1.4 节“超长时间运行的计算”部分）。

2004 年的一篇经典论文对此做出了简要总结：

由于停机问题，语言设计中存在着二分法。根据编程规范，我们必须在这两者间选择。

A. 安全——在这种语言中所有知道的程序都要终止。

B. 普遍性——在这种语言中，我们可以写：

i. 所有结束的程序；

ii. 不能结束的病态程序。

并且，给出一个任意的程序，我们一般无法说出它是（i）还是（ii）。 50 年前，在电子计算发展初期，我们选择（B）。

——David Turner，Total Functional Programming（完全函数式编程，http://www.jucs.org/jucs_10_7/total_functional_programming）

是的，我们不愿意写出病态的程序来，但那仅仅是运气不好。没法识别任意的一个程序是否病态，因此我们不可能在不牺牲通用性的前提下完全避免写出病态程序。18

18完全编程语言是对这个问题的潜在解决方案，但到目前为止它们还没有开始应用，或许是因为它们比起通常的语言更难理解吧。

Rice 定理的暗示也是令人沮丧的：不止“程序是否会停机”这个问题是不可判定的，“程序是否做了我想让它做的”也是不可判定的。我们生活的宇宙当中，没法构建一台机器能准确预测一个程序是否能输出hello world，是否会计算一个特定的数学函数或者是否能做一个特定的操作系统调用，而这就是它的运行方式。

那是令人沮丧的，因为能够机械地检查程序性质实在是非常有用的；有了一个工具能判定程序是否遵守它的规范或者含有任何的 bug 之后，现代软件的可靠性将会提高。那些性质可能对于个体程序是可以机械地检查出来的，但除非它们通常都能检查出来，不然我们将永远不能信任机器来做这些工作。

例如，假如我们发明了一个新的软件平台，并且决定通过在线商店——一个“应用程序的超市”卖兼容程序来赚钱，如果你喜欢——代表我们平台的第三方开发者。我们想要顾客能充满自信地购物，因此决定只买满足某些条件的程序：它们一定不能崩溃，它们一定不能调用私有的 API，并且它们一定不能执行从网上下载的任意代码。

成千上万的开发者开始向我们提交代码的时候，我们如何检查每一个应用是否满足要求呢？如果我们使用自动系统检查每一个提交的规范程度，那将会节约大量的时间和金钱，但感谢不可判定性，不可能构建一个准确完成这个任务的系统。我们只能雇用一小队人运行这些程序、反编译并且检测操作系统来测量程序的动态行为，除此之外别无他法。

人工检查速度慢，成本高，容易出错，而且每个程序只能运行一小段时间，提供自己动态行为的有限片段。因此即使没人犯错误，通常一些不可预计的东西也会出现，然后我们就会有大量气愤的顾客。多谢了，不可判定性。

在所有这些不便之下有两个基础问题。第一个是我们没有能力预测程序执行的时候会发生什么；弄清楚一个程序做什么的唯一通用方法就是真正运行它。尽管一些程序足够简单，行为直接是可预测的，但仅仅通过分析它们的源代码，通用语言总是会允许行为不可预测的程序存在。19

19Stephen Wolfram 为这种不运行程序就无法预测程序行为的思想起名叫计算不可约。

第二个问题是，在我们确实决定运行程序的时候，没有可靠的方式知道它多久能运行完。唯一通用的解决方案是运行程序然后等它执行，但既然我们知道通用语言的程序有可能不停机永远循环下去，那么总是存在一些程序无论等待多久都运行不完。