《计算复杂性：现代方法》——1.5　不可计算性简介

本节书摘来自华章计算机《计算复杂性：现代方法》一书中的第1章，第1.5节，作者 ［美］桑杰夫·阿罗拉（Sanjeev Arora），博阿兹·巴拉克（Boaz Barak），译 骆吉洲，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

1.5　不可计算性简介

下面的事情看起来似乎很“显然”：只要时间充分，任何函数均是可被计算的。然而，这已被证明是错误的。因为，存在这样的函数，它们在无穷步骤内不能被计算！本节简要介绍这一事实和由此引出的学科分支。21尽管严格地讲不可计算性对复杂性而言不是必需的，但它却构成了复杂性的知识背景。

下面的定理证明了不可计算函数的存在性。（事实上，该定理证明了值域为{0,1}的不可计算函数（即语言）的存在性。值域为{0,1}的不可计算函数也就是众所周知的不可判定语言。）定理的证明用到了对角线方法，这种方法在复杂性理论中也很有用；参见第3章。

1.5.1　停机问题

读者可能不禁要问，为什么我们要研究上面定义的函数UC是不是可计算的呢？什么样的人会关心到底如何计算这种刻意构造的函数呢？

现在我们展示一个更自然的不可计算函数。函数HALT以序对〈α,x〉为输入，它输出1当且仅当α表示的图灵机Mα在输入x上会在有限步骤内停机。这肯定是我们需要计算的函数。因为，给定一个计算机程序和输入之后，我们肯定希望知道该程序在该输入上是否会陷入无限循环。如果计算机能够计算函数HALT,则设计无bug的计算机软件和硬件将变得容易得多。遗憾的是，现在我们可以证明计算机计算不了这个函数，即使运行时间允许任意的长。

定理1.11证明过程中的技术称为归约。定理的证明已经表明，如果假设存在计算HALT的算法，则必存在计算UC的算法；这就将对UC的计算归约到了对HALT的计算。在本书中，我们将遇到许多归约。通常，归约技术用于证明问题B至少同问题A一样难，这正是通过证明“如果给定求解问题B的算法，则存在求解问题A的算法”来完成的。

还有许多有趣的不可计算（也称不可判定）函数，参见习题1.12。甚至，还有一些不可计算函数，它们看起来似乎与图灵机或算法毫无关系。例如，下面的问题不能被任何图灵机在有限时间内求解：给定一族整系数的多项式方程，问这些方程是否存在整数解（亦即，是否存在变量的整数赋值满足所有方程）。这就是著名的丢番图问题。1900年，希尔伯特曾将寻找丢番图方程的求解算法这一问题作为最难的23个开放数学问题之一提出。本章的注记提到了更多关于可计算理论的资源。

1.5.2　哥德尔定理

1900年，当年最卓越的数学家戴维·希尔伯特提出了一项雄心勃勃的研究计划。该计划旨在为所有数学建立严格的公理系统，以最终确保所有为真的结论均能被严格地证明。罗素(Russell)、怀特黑德(Whitehead)、策梅洛(Zermelo)、弗兰克尔(Fraenkel)等数学家在接下来的数十年中各自提出了自己的公理系统，但他们谁也不能证明他们的公理系统既是完备的（亦即，能证明所有正确的数学结论）又是可靠的（亦即，不会证明出错误的结论）。1931年，库尔特·哥德尔证明了所有这些努力都注定要失败，这震惊了整个数学界。因为他证明了：对于任意可靠的公理和推理规则的系统，23必存在正确的数论结论不能在中被证明。下面，我们给出这个结果的证明概要。注意，我们给出的讨论并不针对哥德尔的更强结论；亦即，数学上任何一个足够强的公理系统均不能证明其自身的一致性。采用下面的思想，要证明这个更强的结论也不是很难。

注意，上述构造最早是由图灵给出的。该构造过程还表明，所有正确数学结论构成的集合是不可判定的。这同时还表明，希尔伯特著名的判定问题无解。（希尔伯特曾提出用“机械过程”（现译作“算法过程”）来判定数学结论的真伪。）