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

我们已经看到的最先进的机器——图灵机，似乎拥有我们需要的一切：拥有无限制的存储，这个存储能以任何顺序、在任意的循环中、在任意的条件语句以及子例程中访问。

我们也看到了极小编程语言 lambda 演算，被证明也出奇得强大：稍加精心设计，它就允许我们把简单的值和复杂的数据结构都表示成纯代码，还能实现操纵这些表示的运算。我们看到了许多简单的系统，就像 lambda 演算一样，它们也与图灵机有着同样的通用能力。

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

基本事实

能执行算法的通用系统

通常说来，使用像图灵机、lambda 演算和部分递归函数这样的通用系统我们能干什么呢？如果我们能恰当理解这些系统的能力，那就可以考察一下它们的限制。
计算机的实际目的就是执行算法。算法是一个指令列表，指令描述把一个输入值转成一个输出值的过程，但必须满足某些条件：有限，简单，终止，正确。

比如我们把欧几里得算法的自然描述转换成形式化的机器指令，而且没有歧义。但是，任何算法都能转换成适合一台机器执行的指令吗？表面上看，这个问题似乎不值一提——如何把欧几里得算法转换成一个程序相当明显。而作为程序员，我们有天然的倾向会把两者看成可互换的——但在一个计算系统中，一个算法抽象的、直觉的思想与具体的、逻辑上的实现是存在实质差别的。是否存在一个算法，它大、复杂而且不同寻常以致于其本质无法被一个没有思想的机械过程捕捉呢？

最终可能没有严谨的答案，因为这个问题是哲学层面的而非科学层面的。一个算法的指令一定要“简单”而且“不精巧” ，以便它“能由一个人计算” ，但这些对人类的直觉和能力来说都是不严密的，这并不是能用来证实或者推翻一个假设的数学化断言。

不管怎样，我们都可以通过提出大量算法并观察我们选择的计算系统（图灵机、lambda 演算、部分递归函数，或者 Ruby）是否能够实现它们来收集证据。数学家和计算机科学家差不多从 20 世纪 30 年代开始就已经在这么做了，但到目前为止还没有人成功设计出这些系统不能执行的算法。因此我们可以对经验上的直觉相当自信：一台机器肯定能执行任何算法。

另一个比较强的证据是这些系统中大多数都是为了尝试捕捉和分析一个算法的非形式化思想而独立发展的，只是后来才被发现彼此之间恰好等价。每一次对算法思想的建模尝试都产生了一个系统，这个系统的能力与一台图灵机的能力等价，而这是对一台图灵机足够表示一个算法的很好暗示。

任何算法都能被一台机器（特别是一台确定型的图灵机）执行的思想叫作邱奇 - 图灵论题（Church–Turing thesis） 。尽管这仅仅是一个猜想而不是一个被证明的事实，但有足够的证据让它成为广泛接受的真理。

图灵机能执行任何算法”是个哲学层面的断言，说的是算法的直观感觉和用来实现算法的形式系统之间的关系。它实际的含义是一个解释的问题：我们可以把它看成关于什么能计算以及什么不能计算的命题，或者作为单词“算法”的更严格的一个定义。

不管怎样，它都叫“邱奇 - 图灵论题” ，而不是“邱奇 - 图灵定理” 。因为它是一个非形式化的断言而不是一个可证明的数学断言——它没法用纯数学化的语言表达，因此没有办法构建数学证明。因为它与我们对计算本质的直觉判断和算法能做事情的证据相符，所以被广泛认为是真的，但我们仍旧称它为“论题” ，以便提醒自己它的状态与毕达哥拉斯定理这样的可证明思想不同。

邱奇 - 图灵论题表明，图灵机尽管简单，但拥有执行任何计算所需要的所有能力，而这些计算原则上可以由一个人按照简单的指令执行。许多人比这更进一步，他们认为，既然所有对算法编码的尝试都归结到了与图灵机能力等价的通用系统上，那也就不可能做得更好了：任何现实世界中的计算机或者编程语言只能做到与图灵机做的一样多的事，不能再多了。是否最终有可能构建一台比图灵机更强大的机器——能使用外来的物理法则执行超越我们对“算法”想象的任务——现在还不能确切知道，但可以肯定的是我们现在不知道如何做。

能够替代图灵机的程序

图灵机的简单性使得为一个特定任务设计一个规则手册非常困难。为了避免对可计算性的研究被图灵机编程烦琐的细节干扰，我们将使用 Ruby 程序作为替身，就像处理欧几里得算法那样。

这个方法可行要归因于通用性：原则上，我们可以把任何的 Ruby 程序转换成一个等价的图灵机，反之亦然。因此一个 Ruby 程序与一台图灵机相比不多不少正好能力相当，从而我们发现的关于 Ruby 能力的任何限制都应该可以同样适用于图灵机。

代码即数据

程序有两种身份。除了把程序当作控制一个特定系统的指令之外，我们还把程序看成是纯数据：一个表达式树，一个原始字符串，或者甚至一个大的数。这种双重性通常会被程序员认为理所当然，但程序能够被表示成数据以便它们能用做提供给其他程序的输入，对通用计算机来说是至关重要的。正是代码和数据的统一才使得软件成为可能。

我们在通用图灵机的讨论中已经看到了作为数据的程序，它期望另一台图灵机的规则手册能作为字符序列写到它的纸带上。像 Lisp 和 XSLT 这样奇特的同体异构编程语言（即程序与数据由同样的结构存储） ，程序被显式地写成语言本身可以操纵的数据结构：每一个Lisp 程序是一个称为 s 表达式的嵌套列表，而每一个 XSLT 样式表是一个 XML 文档。

可以永远循环的通用系统

我们已经看到通用目的的计算机是通用的：可以设计一台能模拟其他任何图灵机的图灵机，或者写一个能对其他任何程序求值的程序。通用性是个强大的思想，这样不同的任务只用一台可改写的机器而不是很多专门机器就可以完成。但它也有不方便的地方：任何强大到足以通用的系统，都不可避免地允许我们构建永不停机一直循环的计算。

那么为什么每个通用系统都把非终结作为属性呢？有没有什么天才的方法能限制图灵机以便它们总是能停机，而不必在它们的用处上做出妥协呢？怎么知道我们某一天不会设计出一种编程语言，它与 Ruby 一样强大但不包含无限循环呢？

被仔细地设计以保证它们的程序一定总是能停机的语言叫作完全编程语言。与之相对的是更常见的部分编程语言，这样语言的程序有时候能停机给出答案，有时候不能。完全编程语言仍然非常强大，能表达许多有用的计算，但它们不能做到的就是解释自身。

能引用自身的程序

让一个程序从标准输入读取它自己的源代码只不过是一个对所有通用系统都能完成的某个事情的为简化，而且与它们的环境和其他特性无关。这是一个叫作 Kleene 第二递归定理的推论（Kleene’s second recursion theorem） ，它保证了任何程序都可以转换成能计算自身源代码的等价物。

可判定性

到目前为止我们已经看到图灵机有非常多的能力和灵活性：它们可以执行编码成数据的任意程序，执行我们能想出来的任意算法，运行无限长时间，对它们自身的描述进行计算。尽管它们很简单，可这些小的假想的机器都已经被证明能表示一般的通用系统。

如果它们这么强大而灵活，那是否存在图灵机乃至真实世界的计算机和编程语言不能做的事情呢？

在回答这个问题之前，需要让这个问题更明确一些。我们可以让一台图灵机做什么样的事情呢？怎么识别它已经干完了呢？需要研究每一种可能的问题吗？或者只考虑其中一部分问题是否足够呢？我们只是在寻找解法超越自己当前理解的问题，还是在寻找已经知道永远不能解决的问题呢？

如果存在一个算法，对任何可能的输入都能保证在有限时间内解决一个判定性问题，那么这个问题就是可判定的（或者叫可计算的） 。邱奇－图灵论题认为每一个算法都能由图灵机执行，所以对于一个可判定性的问题，我们需要设计一台总是产生正确答案的图灵机，并且如果运行足够长的时间，它总是能停机。把一台图灵机的最终配置解释成“是”或者“否”的答案是很简单的：例如可以检查在当前纸带的位置上是否写有 Y 或者 N，或者完全忽略纸带内容，而只是检查它的最终状态是接受状态（ “是” ）还是非接受状态（ “否” ） 。

有许——无限多——多判定性问题而且大量的问题是不可判定的：没有保证能停机的算法能解决它们。这些问题中每一个都是不可判定的，不是因为我们还没有找到合适的算法，而是因为问题本身从本质上就对某些输入不可能解决，而我们可以证明永远也不会找到合适的算法。

停机问题

大量的非判定性问题是关于机器和程序执行过程中的行为的。这其中最著名的就是停机问题，停机问题要解决的是对拥有一条特定纸带的特定图灵机判定它的执行是否能够停机。

感谢通用性，我们可以把同样的问题用更实际的名词重讲一遍：给定一个包含 Ruby 程序源代码的字符串，还有一个数据的字符串可以让程序从标准输入中读取，那么运行这个程序最终会得到一个答案作为结果还是只会无限循环下去呢？

完全解决停机问题是不可能的，而且既然 Ruby 程序与图灵机等价，所以图灵机也是不可能的。邱奇－图灵论题说的是所有的算法都能由一台图灵机执行，因此如果不存在能解决停机问题的图灵机，也不会存在算法；换句话说，停机问题是不可判定的。

其他不可判定问题

停机问题不是唯一的不可判定问题。我们日常构建软件的过程中可能想要解决大量问题，而它们的不可判定性对于自动化工具和过程的实际限制非常重要。

Rice 定理：程序行为的任何非平凡性质都是不可判定的，因为停机问题总是能被规约成判定这个属性是否为 true 的问题；如果我们能发明一个算法来判定那个属性，就能使用它来构建另一个算法来判定停机问题，而这是不可能的。

令人沮丧的暗示

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

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

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

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

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

发生上述情况的原因

我们已经看到所有通用系统都足够强大，可以引用自身。程序对数字进行运算，数字可以表示字符串，而一个程序的指令只用字符串写下来的，因此程序完全能够对它们自己的源代码进行运算。

自引用能力使得写出能准确预测程序行为的程序成为不可能的事情。一旦一个特别的行为检查程序写完了，我们总是能构建一个更大的程序打败它：新程序把这个检测器当作一个子例程，检查它自身的源代码，然后立即做与检测器要做的相反的事情。这些自我矛盾的程序比我们实际写出来的一些东西更奇特，但它们只是一个征兆，而不是潜在问题的根因：通常，程序行为过于强大而无法准确预测。

一言以蔽之，程序行为这么难预测有两个原因：

  1. 任何拥有足够能力引用自身的系统，都无法正确回答每一个关于自身的问题
  2. 但是对于通用编程语言，不存在更强大的系统供我们升级。邱奇－图灵论题表明我们发明的对程序行为进行预测的任何可用算法，都能由一个程序执行，因此我们无法超越通用系统的能力。

处理不可计算性

写一个程序的所有要点就是让计算机做有用的事情。作为程序员，我们该如何应对无法检测程序是否正确工作这个事实呢？

拒绝是一个吸引人的选择：忽略整个问题。如果能自动校验程序行为当然好，但我们不能，所以只是期望做到最好，而永远不要检查一个程序在正确地完成它的工作。

但这属于反应过度，因为情况没有听起来那么坏。Rice 定理并不意味着分析程序不可能，而只是我们不可能写出一个不平凡的总是停机并产生正确答案的分析器。

没有什么可以阻止我们写一个工具来为某些程序给出正确答案，只是我们得承认总是会存在其他程序要么给出错误答案要么永远循环不返回任何东西。

不考虑不可判定性，下面是一些分析和预测程序行为的实用方法。

  • 问一些不可判定的问题，但如果找不到答案就放弃。
  • 把所问的几个小问题答案汇总起来，就能为一个更大的问题提供经验性的证据。在执行自动化验收测试时，我们通常不能为每一个可能的输入检查程序是否做了正确的事情，但我们可以尝试为有限的输入样本运行这个程序来看会发生什么。每一个测试运行都对那个特例程序如何运行给出了信息，并且我们可以使用这个信息提高对程序通常可能行为的信心。有可能还有未测试的输入，这会引起完全不同的行为，但只要测试用例为大多数现实输入的表示完成了工作，我们就可以坦然生活。 这个方法的另一个例子是单元测试的使用，单元测试是为了验证小段程序行为，而不是把程序作为整体来验证。一个良好分离的单元测试专注于简单单元代码的性质，并通过把程序的其他部分表示成测试替代物（存根和模拟对象）来做出假设。使用小段容易理解代码的单个单元测试可能会简单而且快速，把任何一个将会永远运行或者给出误导答案的测试风险最小化。
  • 问可判定的问题，在必要的时候要保守一些。上面的建议通过实际运行一个程序的很多部分来看发生了什么，它总是会引入无限循环的风险，但有的问题可以只通过静态检查源代码就能回答。最明显的例子是： “这个程序含有任何的语法错误吗？”但万一真正的答案是不可判定的，我们也准备接受近似安全的话，就可以回答更有意思的问题。
  • 通过把程序转换成更简单的东西来近似它，然后问关于近似的可判定问题。