Question

世界上最幸运的事，是人脑无法把自身的内容全部关联起来。

——霍华德·菲利普·洛夫克拉夫特

本书中，我们已经探索了不同的计算机和编程语言模型，其中包括几种抽象机器。这些机器中有一些更强大，特别是有两种机器有相当明显的限制：有限自动机无法解决涉及无限制计数的问题，例如判定一个括号组成的字符串是否平衡；下推自动机无法处理任何信息需要在多处重用的问题，例如判定一个字符串是否含有同样数目的字符 a、b 和 c。

但我们已经看到的最先进的机器——图灵机，似乎拥有我们需要的一切：拥有无限制的存储，这个存储能以任何顺序、在任意的循环中、在任意的条件语句以及子例程中访问。第6 章中的极小编程语言 lambda 演算，被证明也出奇得强大：稍加精心设计，它就允许我们把简单的值和复杂的数据结构都表示成纯代码，还能实现操纵这些表示的运算。而在第 7 章，我们看到了许多简单的系统，就像 lambda 演算一样，它们也与图灵机有着同样的通用能力。

我们还能将系统不断增强的过程推进多少？或许并不是不确定的：我们通过增加特性让图灵机做更强大的尝试，但没有取得任何进展，这表明计算能力可能存在着一种硬性的限制。那么计算机和编程语言的基本能力是什么呢？有什么它们做不到的事情吗？存在不可能的程序吗？