有些问题，虽然有客观答案，但却无法被计算机解决。这个问题与我们目前的计算水平无关。将来无论出现多快多强大的计算机，也永远不能解决这些问题。
到最后，我们自我感知、自我发明、狭隘固执的海市蜃楼不过是自我指涉的小小奇迹。
——道格拉斯·R.霍夫施塔特（Douglas R.Hofstadter），《我是一个奇异的环》（I Am a Strange Loop）
我喃喃自语：“我还太年轻。”
转念又一想：“我已不算小。”
为此我抛起一枚便士
占卜恋爱是否还嫌早。
“去爱吧，去爱吧，小伙子，
如果那姑娘年轻又俊俏。”
啊，便士，便士，铜便士，
我陷入了她的卷发的圈套。
噢，爱情是狡猾的东西，
没有谁足够聪明
能窥透其中的全部奥秘，
因他会思念着爱情，
直到天上看不见星星，
阴影把月亮吞掉。
啊，便士，便士，铜便士，
开始恋爱从来都不嫌早。
——威廉·巴特勒·叶芝（William Butler Yeats，1865—1939），《铜便士》
发现可能之局限的唯一方式是比可能走得更远，进入不可能的疆域。
——亚瑟·C.克拉克（Arthur C.Clarke，1917—2008）
计算机可以做很多奇妙的事。然而有很多任务是它们无法完成的。计算机不能判断一幅画是否美丽；它们不“理解”道德问题；而且它们不会坠入爱河。这些“人性的”过程超出了运算的范畴。一幅画是否美丽取决于你的审美品位，而计算机没有品位可言。它们没有处理道德问题所需的伦理准则。所有这些问题都是主观的，而计算机不能良好地处理主观问题。在这一章，我们将探讨一些虽然有客观答案，却无法被计算机解决的问题。
需要注意的是，这些任务并不是需要很长时间才能完成计算（就像在上一章中提到的一样），而是永远也无法完成。这个问题与我们目前的计算水平无关。将来无论出现多快多强大的计算机，也永远不能解决这些问题。
本章第1节简短地讨论了程序、算法和计算机。第2节介绍了任何计算机都无法解决的问题，停机问题（halting problem）。我将解释为什么任何计算机都无法解决它。我们不能不加怀疑地相信这个结论。相反，我将仔细审视任何计算机在这个问题面前都无能为力的证明。知道停机问题不可解决之后，我又在第3节中指出其他许多问题也是不可解决的。第4节描述了不可解决问题的层级或分类。我用第5节作为结论，并探讨了更富哲学意味的问题，如大脑、思维和计算机的关系。
再也跳不出的死循环
我们都有计算机突然“卡死”或者陷入“死循环”（infinite loo，又称无限循环）的经历。我们的计算机陷进了它们的程序的循环里。一旦进入死循环，它们就再也出不来了。微软的Windows系统此时会提醒我们计算机“未响应”，好像在嘲弄我们似的。为什么不买一种能够确保这种情况永远不会发生的软件呢？如果有某种方法能够判断一个程序是以正常方式停机（或终止）还是进入死循环的话，那就太好了。哎，可惜这样的方法并不存在。这是人们发现的第一批计算机无法解决的问题之一。尽管某个程序是否停机这个问题是客观的而非主观的，但计算机却没有办法解决它。
在我们开始之前，需要先了解一些术语。计算机是一种运行算法的实体机器。程序是对算法的确切描述。当我们说解决某一特定问题的算法不存在时，我们的意思就是没有任何程序、计算机或机器能够执行该任务。我们描述的是机械化过程的局限性，所以这四个词在使用时是可以互换的。
在我对某个程度是否停机的讨论中，我没有讨论所有程序，而是局限于特定类型的程序，这些程序只处理整数。如果你怀疑我试图通过只查看这个有限的程序集合来骗你的话，你应该记住两件事。第一，我将要指出的是，即使对于这些有限定条件的程序，计算机也无法判断这些程序是否停机。当然也就没有计算机能够对所有程序做出同样的判断。第二，处理实数、图形、机器人技术以及由计算机操作的所有令人赞叹的机器程序，都可以通过操纵整数的方式运行。可以使用整数为不同类型的更复杂的数字和对象编码。所以如果我们指出只处理整数的程序存在局限的话，更复杂的其他类型的程序一定也存在局限。
我使用的程序任何人都很容易读懂，只需要从上到下简单地分析。不同变量如x，y或z代表整数。程序中的语句写得很清楚。例如，可能会有这样一句
x=y+1。
这意味着变量x的赋值等于y与1之和。我们还可以写
x=x+1。
这意味着x的值应该增加1。由于某些程序需要一个输入，我们会写x=?
此时计算机应该停止，等待用户输入一个数字。变量x将会得到用户输入的数值。有些行带有A、B或C这样的标签。这些标签是用来控制程序的运行的。仅仅从上到下的程序不是很有趣。我们需要让程序能够重复执行一系列循环动作。标签让我们可以通过使用跳转（goto）指令制造循环。
为了更直观地理解程序，让我们来看一些例子：
这个程序执行的是什么任务呢？如果在这个程序中输入15，那么x在第一行就是15。接下来的三行每一行都会给x加1，相当于一共给x加3。然后计算机会将x的最终值打印出来，即18。完成这一步之后，计算机就会停机。如果输入的是56，程序就会打印出59。总而言之，这个程序计算的函数是f（x）=x+3。
这很有趣！让我们尝试更多例子吧。
先看左边的程序。如果用户输入23，会发生什么呢？变量x的值会是23，变值y的值会是10。接下来的两行语句是串联工作的：x增加到24，y减小到9。下一行是条件语句。由于y是9，因此大于0，计算机会返回有标签A的那一行。这一次x会增加到25，y减小到8。这个循环重复数次，直到x等于33，y减小到0。此时条件语句失效，运行打印指令。数字33将被输出，因为这是x的值。如果x的输入值是108，那么打印的数字将是118。总而言之，这个程序计算的函数是f（x）=x+10。
现在来看右边的程序。除了一处差别，它几乎和左边的程序一样。它用y=?替换了左边的y=10。左边的程序只需要一个输入，而这个程序需要两个。它不再从10往下数y，而是从y的任意初始值向下数。不难看出这个程序计算的是双值函数f（x,y）=x+y。不需要太多论证就能看出，用这种编程语言写出的程序可以执行大部分计算机能够执行的任务。事实上，只要有足够的编码，这样的程序可以执行任何计算机可以执行的任何任务。
让我们再来查看一些程序。
如果在左边的程序中输入5，条件语句就会失效，于是这个程序会立即终止。相比之下，如果输入15，程序就会进入死循环。事实上，为x输入任何小于或等于9的数字都会让程序停机，而对数字10或更大的任何数字，程序都会进入死循环。
右边的程序呢？你能判断这个程序在什么时候停机，在什么时候陷入死循环吗？我也不能！何不找一台计算机来解决这个问题。
Mac或Linux用户会发现这些概念抽象得无法理解。他们真是幸运。
不能解决的问题
让我们来清晰地描述停机问题。对于任意程序和它的某一个输入，判断该程序在该输入下运行是会停机还是会陷入死循环。这是一个判定问题，也就是说，它会给出“是”或“否”的答案。计算机能解决停机问题吗？
这个问题是阿兰·M.图灵（Alan M.Turing，1912—1954）提出的，他在1936年给出了绝对否定的答案：没有程序能够解决停机问题。一台计算机无法判断对于任意程序的任意输入，该程序是否会在该输入下停机。如果计算机可以解决某个判定问题，我们说该问题是可判定的（decidable）。相反，如果计算机不能解决这个问题，我们说该问题是不可判定的（undecidable）。停机问题是不可判定的。
我们在这里需要几分钟的深思。我们首先要将上一章主要关注的不可行的问题与不可判定的问题区分开来。在上一章，问题可以被解决，但是对于较大的输入，解决问题需要一段极其不合理的时间。我们在这里遇到了不一样的情况。停机问题无论在多长时间内都无法被解决。它不是一个难的问题；它是一个不可能解决的问题。
此外，值得注意的是，某一程序在运行某一输入时是否停机是存在客观答案的。它不像艺术品位或道德感那样是一种模棱两可的主观概念。该程序要么最终停机，要么陷入死循环，然而计算机不能判定这个客观问题。即使人类也会很难判断这个问题（关于这一点的更多内容见第6章第5节）。然而这个问题存在一个真实、客观的答案。
值得注意的另一点是，图灵说的不是他自己不能写出解决停机问题的程序。他说的也不是其他人不够聪明，发现不了这样的程序。他证明的是，这样的程序不可能存在。困难不在于缺少技术或巧思。图灵指出，任何程度的技术创新或机智多谋都不可能解决这个问题。在更深的层次上，他说的是计算机和其他任何遵循理性的实体设备都无法解决停机问题。
你也许认为有一种简单的方法能够证明停机问题是可判定的：用给定的输入运行程序，看看该程序是停机还是陷入死循环。哎，可惜这个方法并不管用。如果程序运行了10分钟然后停机了，你可以很肯定地说，该程序运行该输入时会停机。但是如果10分钟后程序仍然在运行呢？这并不意味着程序进入了死循环，因为许多程序都需要超过10分钟的时间才会终止。或许你应该让程序运行20分钟。如果它停机了，问题就解决了。然而，如果它没有停机，我们又能知道什么呢？我们还是不能确定它是否陷入了死循环。我们应该将这程序运行多久呢？在任意有限的时间内，总有一些程序需要再多一些的时间才能终止。我们判断某个程序是否陷入死循环的唯一方法是等待无限长的时间，看它是否还在运行。但谁有那么多时间啊。
图灵的答案最令人惊叹的一点是，它是在1936年提出并证明的，比任何一台计算机问世的时间都早得多。作为一名杰出的理论数学家，图灵在工程师刚刚知道如何制造计算机之前很多年就阐释了计算机能力的局限。给理论家点赞！
经过思考，我们已经充分认识到为什么停机问题的不可判定如此有趣，而且它值得我们进行更深入的探讨，现在就让我们来证明它吧。要想证明停机问题的不可判定性，我们使用了计算机可以谈论自身这一事实。也就是说，计算机可以自我指涉。既然程序可以讨论程序，计算机就存在自我指涉的元素，局限也就由此产生了。到目前为止，我们已经在这本书里多次见到自我指涉的例子——例如，在说谎者悖论中有一些讨论自身的自我指涉语句：
这个句子是假的。
我们指出，当且仅当此句为假的时候，它才是真的。在这里，我们将创造出一个自我指涉的程序，它本质上是这样的：
当该程序被问到它会停机还是会陷入死循环时，该程序会给出错误的答案。
我们将会看到，这样一个程序的存在会导致矛盾的产生。这样的矛盾在计算机的真实世界里是不被允许的，于是我们有了局限：停机问题无法解决。这种证明是一种反证法。假设停机问题不是不可判定的（即计算机可以判定这个问题）；在这样的假设下，我们推导出了矛盾：
停机问题可判定⇒矛盾。
我们不得不断定，我们的假设一定是不正确的。
值得注意的是，我们在上一节谈论的程序都非常简单。它们很容易被描述，而且我们可以用整数来为这些程序编码。对于任意一个程序，都有一个独一无二的数字与其对应。对于某个程序，与其对应的数字称为“程序号”（program number）。我们也可以反其道而行之：从一个数字得到与其对应的程序。对于数字x，我们将与之相应的程序称为“程序x”。这些程序处理数字，而数字代表这些程序；于是我们将会得到处理程序的程序，如图6.1所示。这是自我指涉的核心。
图6.1 程序的自我指涉
让我们假设停机问题可判定，而且我们可以创造出一个判定它的程序。
这意味着我们可以写出下面这样一个计算机程序：输入程序号y和数字x，然后计算机会根据程序y在输入为x时是否停机输出是或否的答案。我们将这个函数写成
判定停机（y,x）函数的程序是一个黑箱，它需要两个输入，然后输出一个是或否的答案，如图6.2所示。
我们将运行这个函数的（不存在的）程序表示为Halt（y，x）。既然我们现在有了对程序和数字编号的能力，不妨让我们将这个假定的程序当作下面这个更大的程序的一部分：
图6.2 （不存在的）停机问题判断机
这个程序非常重要，将被称为程序D［“diagonal”（对角线）的首字母大写］。让我们用一张图来看看这个程序。程序D的构造见图6.3，图6.2是它内部的一个黑箱。
图6.3 （不存在的）程序D
该程序接受一个输入，该输入既是程序号，也是输入数字（自我指涉）。如果该程序在运行它自己的输入时停机，它就会陷入死循环。相反，如果该程序在运行输入时陷入死循环，它就会停机并打印出“否”的答案。所以该程序在被问到关于输入x的问题时，总是会给出错误的答案。
正式地说，程序D在输入为x时的行为如下：
当且仅当程序x在输入为x的情况下陷入死循环时，程序D才在输入为x的情况下停机。
等一下！下面就是有趣的部分了：如果停机程序是真正的程序，我们就可以放心地将它用作另一个程序的一部分，创造出程序D。如果程序D是真正的程序，那么它就有一个与之对应的编号数字。我们不知道这个数字是什么，但这并不妨碍我们将它表示为d0。现在让我们将数字d0输入程序D。也就是说，让我们看看程序D会对自身说些什么。
当且仅当程序d0在输入为d0的情况下陷入死循环时，程序D才在输入为d0的情况下停机。
但是程序d0就是程序D，所以我们可以将这句话重新表述为：
当且仅当程序D在输入为d0的情况下陷入死循环时，程序D才在输入为d0的情况下停机。
这便产生了矛盾。我们可以说：
当程序D被询问自身将停机还是陷入死循环的时候，程序D给出了关于自身的错误答案。
我们一下子回到了说谎者悖论。我们来到了这样一个时刻，当且仅当某个程序不停机时，该程序才停机。人类语言和人类思维或许会有矛盾，但计算机不会。一定是在什么地方出了问题。我们只做了一个假设：有可能写出一个判定停机问题的程序。这个假设让我们推导出了矛盾，因此它一定是错误的。使用计算机解决停机问题是不可能的。
上述对停机问题不可判定性的证明有一点复杂，我们还可以从另一个视角看待这个问题。用对角线证明的方式将它直观地呈现出来就更容易理解了（如果你已经读过第4章，就会更轻松地接受这种证明方式）。假设某一天，我们得到了能够判定停机问题的程序。我们可以将该程序的输出写成一个无限矩阵（见图6.4）。
最左边一列的数字是程序号。最上面一行的数字对应的是该程序的输入。里面的是或否表示该程序在相应的输入下是否停机。例如，程序7在输入2下的结果为“否”。这意味着如果你将数字2输入到程序7中，该程序会陷入死循环。与之相反，程序4在输入为8时会停机。我们通过对角化的方式利用这个（想象中的）程序创造出一个新程序。程序D只有一个输入，它的值取决于图6.4矩阵中对角线的元素。该程序以某个数字为输入。对于输入x，程序D先判断程序x在输入x下是否停机，然后给出完全相反的答案。如图6.5所示。
图6.4 （不存在的）停机程序及其对角线
边上的数字是该程序的输入，而里面的是和否告诉我们该程序在这些输入下是停机还是陷入死循环。
图6.5 （不存在的）程序D
虽然这个新的（想象中的）程序D很容易从停机程序中构建出来，但我们却能够指出程序D不存在。如果它真的存在，就会有一个与其对应的数字。但这个数字会是什么呢？
●它不可能是程序0，因为程序0在输入为0时陷入死循环，而程序D在输入为0时停机。
●它不可能是程序1，因为程序1在输入为1时停机，而程序D在输入为1时陷入死循环。
●它不可能是程序2，因为程序2在输入为2时陷入死循环，而程序D在输入为2时停机。
●……
●它不能是程序d0，因为程序d0在输入为d0时是“这样的”，而程序D在输入为d0时是“那样的”。
●……
换句话说，程序D不可能存在，因为当我们询问关于它自身的问题时，它总是对自己将要做什么给出错误的答案。我们的结论是不存在这样的程序D，所以我们最初的假设——存在停机程序——一定有问题。
总而言之，我们指出如果停机问题存在，程序D就存在，而既然程序D不可能存在，那么停机程序也不可能存在。用我们的逻辑符号来表示这个过程：
停机程序存在⇒程序D存在⇒矛盾。
这意味着停机问题是不可判定的。
有趣的是，这只是微软用来对付停机问题的一种解决方案。当某个程序运行一段略长的时间时，一条“未响应”信息就会出现在窗口的顶部栏上。然后用户应该采取措施终止这条信息提示的死循环。遗憾的是，计算机并不清楚程序是否真的陷入了死循环。它可能只是运行得比Windows操作系统期望的更久而已。
很容易看出程序和数字之间的这种对应：每个程序在计算机中都被储存为某个独一无二的0和1的序列。这个序列其实是个非常大的二进制数字。一个典型的程序通常储存为数百万个0和1。对应的数字将会非常庞大，但我们不必为此担心。
超过计算边界的程序
停机问题不是唯一不可判定的问题。我将指出还有许多其他问题是无法被计算机解决或判定的。
思考打印42问题（printing 42 problem）。对于某给定程序，判断是否存在任何输入令该程序打印数字42。让我们来看看一个样本程序。
这个程序在一个循环里面还有一个循环。里面的循环将z中的数字加到x上。在外面的循环里，z设定为10，而这个循环会运行三次。综上所述，这个程序会将10×3=30加到x上。所以要想让该程序输出42，唯一的方法是输入12。我们的结论是存在一个输入令输出等于42。然而判断这个程序的行为是相当简单的。对于某些非常复杂的程序，很难判断该程序是否可能输出42。
打印42问题也是不可判定的。虽然我们不在本书列出证明，但我们可以从直觉上知道这个问题比停机问题更难。我们对停机问题的目标是判断是否存在某个输入令该程序停机。而对于打印42问题，我们问的是是否存在任何输入，令该程序停机且输出42。我们将不得不搜索所有输入。
让我们思考零程序问题（zero program problem）。查看下面两个程序：
无论输入什么，这两个程序都总是打印0。还有其他数百万个程序也总是执行同样的操作：不管输入的是什么，该程序总是输入0然后停机。这样的程序称为零程序（zero programs）。如果能够判断一个程序在什么情况下是零程序就好了。零程序问题问的就是某个既定程序是否为零程序。也就是说，我们希望某台计算机在输入某个程序时，能够根据该程序是否总是输出0的结果输出是或否的答案。这个问题也是无法解决的。要想证明这个结果，我们要走的路实在是太远了。这个问题的解决要求我们知道该程序在每一个输入下都会停机。这可比停机问题难多了。
我们有必要在这里强调打印42问题和零程序问题之间的不同之处。在打印42问题中，我们问的是是否存在至少一个输入令相关程序输出42。相比之下，零程序问题问的是，是否每个输入都令相关程序输出0。无论是哪种方式，这两个问题都是不可判定的。
一旦我们指出某个问题不可解决，就不难指出另一个问题同样不可解决。这里使用的方法是归约，也就是将一个问题归约到另一个问题。假设有两个判定问题：问题A和问题B，再假设有一种方法可以将问题A的一个例子转化成问题B的一个例子，令答案为“是”的问题A的例子转化为拥有同样答案的问题B的例子，对于答案为“否”的例子也是一样。（我们没有像上一章那样要求转化过程必须在多项式次数的操作步骤内完成。在这里，我们并不在意这种转化过程要花多长时间，只关心这种转化能否发生。）我们可以用图6.6直观地表示这一转化过程。
图6.6 将一个问题转化成另一个问题
如果能够建立这样的转化，那么：
如果问题B是可判定的，那么问题A也是可判定的。
要想判定问题A，只需要将问题A的一个例子进行转化，然后查看相应的问题B的例子的结果如何。如果问题A是不可判定的呢？那样的话，问题B一定也是不可判定的。
如果问题A不可判定，那么问题B也不可判定。
如果有这样的转化过程，我们可以说问题B和问题A一样难或者比问题A更难，并将其写作：
问题A≤问题B。
在上一节，我指出了停机问题的不可判定性。现在我们有可能描述出这样的转化过程，这种转化过程表明：
停机问题≤42问题
及
停机问题≤零程序问题。
我们就能得出结论，这两个过程也是不可判定的。
让我们继续下去，证明我们可以将零程序问题转化为另一个问题。思考下面两个程序：
虽然这两个程序看起来不一样，而且有不同的变量，但很容易看出只要输入相同，它们一定会产生相同的输出。执行相同任务的程序称为等效程序（equivalent program）。如果能够知道两个程序是否等效就好了。等效程序问题（equivalent program problem）需要这样一台计算机，它以两个程序作为输入，并判断这两个程序是否等效。此时你大概已经猜到，等效程序问题是无法解决的。通过如下归约实际上很容易看出这一点：
零程序问题≤等效程序问题。
我将指出
等效程序问题可判定⇒零程序问题可判定。
我们在之前指出（但没有证明）
零程序问题可判定⇒矛盾。
将这两个过程放在一起，我们就可以站在此前的结果上，指出等效程序问题是不可判定的。
在我们论述这种归约过程之前，先思考下面这个简短的程序：
该程序总是输出0，无论输入的值是多少。让我们将该程序称为程序Z［zero（零）的首字母大写］。
（错误地）假设有一种方法能够判定两个程序是否等效。然后假设你想要判定一个程序是否是零程序。
你只需要将该程序和程序Z一起发送到设想中的等效程序判断机中，如图6.7所示。如果该程序与Z等效，那么等效程序判断机就会如是告诉我们。使用这样的程序，我们创造出了一个零程序判断机。但我们知道这样的判断机不可能存在。总而言之，存在等效程序判断机这个假设是站不住脚的。
你或许已经注意到，我们目前为止指出的所有不可判定的问题都和判断程序的不同性质有关。换句话说，我们指出没有程序能够判断关于程序的某些性质。这与我们的主题十分相符，即存在自我指涉时就会产生局限。1951年，亨利·莱斯（Henry Rice）证明了所有这些定理的源头。莱斯的发现后来被称为莱斯定理（Rice’s theorem），根据该定理，关于程序的有趣性质不能被任何程序判定。要想证明这个相当复杂的结论，只需指出对于任何一种有趣的性质P，
图6.7 零程序问题到等效程序问题的归约
停机问题≤性质P问题。
既然停机问题不可判定，那么性质P问题也同样不可判定。
在其他领域如数学和物理学工作的计算机呢？还有没有其他计算机在其中有所局限的客观领域？在第9章第3节中，我们将看到在数学领域还有其他很多问题是计算机无法胜任的。
读者可能会对本章漠然视之。毕竟这里指出的是，存在几个很容易描述的问题是计算机无法解决的。你可能会据此认为，计算机不能解决的只是少数奇怪的病态问题，它们能够解决的问题才是多数。让我们更谨慎地思考这一点。
思考一下某个数字是否属于某个集合的判定问题。对于下列集合，这个问题很简单：
●奇数集合。
●偶数集合。
●质数集合。
●可以写成5个平方数之和的数字组成的集合。
我们可以针对上述每一个集合编写出一个程序，该程序接受某个整数为输入，并根据该输入是否在相应的集合中输出“是”或“否”的答案。
然而还存在其他类型的集合。本章已经指出，对于某些特定的整数集合，无法编写出判断某些整数是否在相应集合中的计算机程序。例如：
●在某些输入下会输出42的程序的编号的集合。
●总是输出0的程序的编号的集合。
所以，某些整数集合是可判定的，其他整数集合则不可判定。
现在让我们来做一些计算吧。我们在第4章第3节中见到，存在整数的不可数无限子集。这些集合中多少是可判定的，又有多少是不可判定的呢？我在第6章第2节的开头提到过，每一个程序都有一个独一无二的整数代表它。因此，程序的数量是可数无限的。由于每个可判定的集合都需要一个程序来判定它，所以可判定整数集合的数量也是可数无限的（见图6.8）。所有其他整数集合都是不可判定的，所以不可判定集合的数量是不可数无限的，可判定集合的数量是可数无限的。第4章指出了可数无限和不可数无限之间的巨大差别。
图6.8 性质以及能够判定其中某些性质的程序
在本章开头，我们提出的问题是什么任务是计算机能够执行的，什么任务超出了计算机的能力。我们发现计算机只能解决所有问题中所占极少的一部分。事实上，所占比例极大且计算机不能完成的任务超出了理性的边界。
42是关于生命、宇宙和所有一切的终极问题的答案（注：42的出处是《银河系漫游指南》。——译者注），除此之外这个数字没有什么特殊之外。
上一章提出了非常相似的概念。然而由于我没有想当然地假设上一章的知识，我就在这里将它重复了一遍。
计算机的“神谕”
到目前为止，本章指出许多问题超出了任何计算机的解决能力。呼之欲出的疑问是，在可计算性的屏障之外是什么。图灵在他关于停机问题的原始论文中提出了这个问题并给出了天才的答案，这个答案赋予了那些无法解决的问题以结构。
我们不能解决停机问题。然而不妨想象我们在某个时刻能够解决它。解决停机问题的过程不可能是一台普通计算机完成的，因为我们已经证明没有任何普通计算机能够做到这一点。相反，它一定存在某种非机械之处，某种“诡秘的”气质。在古希腊（以及几乎所有其他类型的社会中），有一些特殊的人可以通神，传达神的信息。这些人被称为神谕（oracle，源自拉丁语单词“说话”）。在被询问某个问题时，这些神谕会陷入精神恍惚的催眠状态，然后给出回答，这些答案据说来自神明。
为了对无法解决的问题进行分类，图灵使用了神谕的概念。假设有某种类型的神谕可以解决停机问题。在某台计算机中使用这个“诡秘的”停机神谕。在一次计算过程中，让这台计算机询问神谕某些特定程序是否停机的问题。我们可以在图6.9中将该过程形象地表示出来。
输入从左边进入，然后计算机执行某种常规计算。在这个过程中，常规计算机可以向停机神谕询问一个“是”或“否”的问题，然后根据答案进行不同的计算。随着计算的继续，计算机可以向神谕询问数个问题。可以将这种额外提问的特征增添到我们的编程语言中，只需要添加像下面这样的命令：
图6.9 一台可以向神谕提问的计算机
这样的命令可以在一个程序里出现几次，而且可以令z取不同值。拥有这种能力的计算机不仅能够解决停机问题，还能解决我们见到过的常规计算机不能解决的许多其他问题。
在停机神谕的帮助下，就连计算机科学领域之外的问题也可以得到解决。关于数字的最难的开放式问题之一称为哥德巴赫猜想（Goldbach conjecture）。这个问题可以追溯到18世纪中期，目的是证明或证伪一个关于数字的猜想：
每个大于2的正偶数都是两个质数之和。对于较小的数字，很容易看出这个命题是成立的：
●4=2+2。
●18=5+13。
●220=23+197。
●8206=59+8147。
实际上，数学家已经发现这个猜想对所有小于1017的偶数都是成立的。然而这还不够。这个猜想说的是它对每一个偶数都适用。250多年过去了，这个形式非常简单的问题依然困扰着数学家们。
如果我们能够使用停机神谕，判断这个猜想是否为真就会变得非常简单。思考下列程序：
这个简单的程序搜索的是哥德巴赫猜想的反例。如果不存在这样的反例，这个程序就会永远运行下去。相反，如果的确存在某个反例，该程序就会停机。所以你要做的就是询问停机神谕这个程序是否停机。注意声称哥德巴赫猜想目前没有反例不会为你赢得太多名声。问题在于证明该猜想是正确的。
如果能够使用神秘的停机神谕，我们还能解决数学领域的其他许多问题。我们将在第9章第3节中见到一部分这些问题。
除了停机神谕之外，还可能存在其他类型的神谕。对于任意神谕X，所有可向该神谕提问的程序称为X神谕程序（X oracle program）。向停机神谕提问的程序就称为停机神谕程序（halt oracle program）。在停机神谕程序的帮助下，许多不可解决的问题都能得到解决。那么问题就出现了：停机神谕程序能解决所有无法解决的问题吗？图灵指出它们不能。我们已经指出每个常规程序都有一个独一无二的数字与其对应，所以每个停机神谕程序也有一个独一无二的数字。有这些数字在手上，我们就可以问问某个既定数字对应的停机神谕程序是否会停机。这个判定问题称为停机神谕程序的停机问题（halting problem for halt oracle programs）。使用和第2节中类似的论证过程，可以看出停机神谕程序的停机问题不能被任何停机神谕程序解决。这个问题也是无法解决的问题，而且即使在停机神谕的帮助下也不能计算。
图灵还没有结束。假设我们有一种神谕可以解决停机神谕程序的停机问题。将这种神谕称为停机′神谕（halt′ oracle）。有了这个神谕，我们就能解决多得多的问题了。使用这种神谕的任何程序都称为停机′神谕程序（halt′ oracle program）。再一次地，我们又可以提出类似的问题，是否所有问题都能被停机′神谕程序解决。此时你大概已经猜到了，答案是否定的。我们可以指出没有任何停机′神谕程序能够解决停机′神谕程序的停机问题。要想做到这一点，需要停机″神谕。这个过程可以无限持续下去……
我们描述出了无法解决的问题的层级。可以说某些无法解决的问题比其他问题更难，而某些问题比其他问题更容易。计算机科学家们已经能够将某些问题定性为停机′–可计算问题而不是停机″–可计算问题。他们描述了位于该层级结构不同部位的不同问题。我们一直在关心理性的边界，如今我们在理性的边界之外建立起了清晰的结构。
第5章的图5.18现在可以将不可计算的问题包含进来，如图6.10所示。
简单的、困难的和更难的问题的集合可以全部看成是一个集合，将其称为“可计算的问题”。本节讲述的是，不可计算的问题的集合也拥有层级结构。将这些信息融为一体，我们就得到了图6.11。
在第5章第3节，我们介绍了P=?NP，并指出它为什么是重要且令人兴奋的问题。如果我们将神谕纳入考虑，这个问题能否解决呢？
图6.10 问题的层级
图6.11 无法解决的问题的层级
首先需要明确一些定义。P是这样一些问题的集合，这些问题都可以使用一台常规计算机在多项式次数的操作步骤内解决。让我们对此进行推广。思考任意神谕X。将可以在多项式次数的操作步骤内完成的X神谕问题的集合定义为PX。NP是这样一些问题的集合，这些问题都可以使用一台常规计算机在最多指数或阶乘次数的操作步骤内解决。用NPX表示可以在最多为指数或阶乘次数的操作步骤内解决的X神谕问题。
1975年，T.P.贝克（T.P.Baker）、J.吉尔（J.Gill）和罗伯特·索洛韦（Robert Solovay）三位研究者发表了一篇论文，其中包括两个非常有趣的结果。他们描述了两个神谕A和B，令
第一个结果表明有一个神谕A，难题可以在较少的操作步骤内解决。第二个结果表明有一个神谕B，令一个困难的问题需要非常多的操作步骤。所以只要假定不同的神谕，就能解决长久以来悬而未决的P=?NP这一难题。
沿着这些路径继续发展出了其他结果。1976年，朱里斯·哈特马尼斯（Juris Hartmanis）和约翰·E.霍普克罗夫特（John E.Hopcroft）指出有神谕C存在，令问题
无法被常规的数学公理解决。现在还不十分清楚这些定理和最初的P=?NP问题有什么关联，但它仍然是一个有趣的主题。
目前最难的数学问题是黎曼假设（Riemann hypothesis）。它是克雷数学研究所在2000年提出的七大千年难题之一。如果你解决了这个问题，就能获得一百万美元。这个问题比哥德巴赫猜想更难陈述，所以我不会深入探讨它。然而对于专业人士，如果存在寻找哥德巴赫猜想的反例的程序，那么同样存在系统地搜寻其黎曼函数的实数部分不是1/2的零点的程序。
用正式的语言表述，他们指出这个问题独立于策梅洛–弗兰克尔集合论。第4章第4节和第9章第5节还有更多关于这种独立性的讨论。
如何让机器拥有思维
本章讨论的是超出计算机能力之外的事物。我们可以问问人类思维是否能完成计算机不能完成的任务。人类思维不仅仅是一台机器吗？它会像一台计算机那样受限吗？
我们指出计算机不能解决停机问题。那么人类能解决它吗？毕竟人的大脑不就是某种类型的计算机吗？面临较小的程序时，人类通常可以解决停机问题。确切地说，我们可以观察程序，看它是否会停机。但是对于大型程序呢？停机问题涉及的是任意程序。有几千个非常聪明的人在微软公司工作，但他们当中的许多人在检查他们制造的大型程序时都没能发现有时候这些程序会陷入死循环。这是否意味着人类无法发现所有这样的无限循环呢？其他计算问题又如何呢？
这些问题与人类大脑和人类思维之间关系的问题有关。人的大脑是一台高度复杂的实体机器。实际上，它很可能是整个宇宙中最复杂的实体机器。人类的思维毫无疑问以某种方式与大脑相关。无论大脑发生了什么，都肯定会影响到思维。如果你怀疑这一点，试试喝几杯龙舌兰再来阅读这一章的内容！然而两者之间的关系却并不明朗。我们的思维和我们的想法似乎不止于此。我们感觉自己不仅仅是一大束活跃的脑神经元突触。在我们的想象中，我们远不只是遵循物理定律的实体机器。人类似乎更像是拥有自由意志和独立思维的有意识的生物。但我们真的自由吗？我们真的能掌控自己吗？安布罗斯·比尔斯对大脑的定义是“一种设备，我们以为我们是用它思考的”。我们真的在自由思考吗，还是我们的思维受过训练后认为自己是自由的，摆脱了大脑的束缚。
如果人类思维只是遵循物理过程的实体大脑，那么人类思维也无法解决这里提出的任何问题。相比之下，如果思维不仅仅是实体大脑，那么或许思维能做到更多。是哪种情况呢？
库尔特·哥德尔感到人类思维不仅仅是机器。他感到有些特定的命题无法被任何机械系统证明，但这些结果却仍然能被人类知道/理解。哥德尔说这表明人类思维不会仅仅是有限的机器。如果我们的大脑不是有限的机器，那它们是什么？
著名数学教授罗杰·彭罗斯爵士（Sir Roger Penrose）提出了类似的观点，他也认为大脑不仅仅是一台机器。彭罗斯还做了进一步的推测，大脑或许使用了神秘的量子引力的概念，因此人类才能执行那些机器不能执行的任务。他声称使用量子引力的计算机或许能解决停机问题。彭罗斯还说这也许有助于解释意识的存在。
美国研究人员道格拉斯·R.霍夫施塔特（Douglas R.Hofstadter）推测，人类的思维之所以拥有意识，是因为它有自我指涉的能力。由于我们可以思考我们自身，还能思考思考着我们自身的我们自身，……所以我们会产生我们是一个“我”的感受。将这一点和我们在本章学到的内容进行比较。本章试图指出计算机执行自我指涉的能力是它遭遇局限的原因。我们可以说自我指涉给计算机带来了限制，而在人类中产生了意识吗？或许可以。人类真的有自我指涉吗？我们真的知道我们的思维内部正在发生什么吗？
许多伟大的头脑都思索过这些问题，但并没有得到任何清晰的共识。
对于上面提出的问题，我们可以从相反的角度思考。与其问人类思维是否不仅仅是机器，不如问我们是否能让机器表现得更像人类思维。计算机科学中有一个领域致力于解决这个问题，即人工智能（artificial intelligence）。如果人类思维不仅仅是机器，就没有办法让机器真正拥有思维。另一方面，如果思维只是一种高级机器，只是它看起来超出机器的范畴，那么我们就能指望将来有了足够的时间和才智之后，我们就能制造出一台看起来不仅仅是机器的计算机。人工智能可能吗？即使我们有了一台行为方式和人一样的计算机，那就意味着这台计算机有意识吗？
对于制造人工智能的努力而言，问题在于如何意识到是否已经达成了目标。这需要对智能下一个合适的定义。如今的计算机可以做到30年前它们做不到的令人惊叹的事情。在当时，大多数人都相信计算机永远无法在对弈中击败国际象棋大师。1997年5月，这个预言被打破了。IBM公司（国际商业机器公司）开发的超级电脑深蓝（Deep Blue）在一场共六局的比赛中击败了世界冠军加里·卡斯帕罗夫（Garry Kasparov）。计算机可以在国际象棋比赛中击败人类，然而目前没有机器人能够在网球比赛中击败人类。如果我们向未来再看30年呢？如果我们有机会知道那时候计算机能做的事情，毫无疑问我们将非常震惊。随着技术的进步，计算机会获得更多技能，我们不再那么惊奇于它们的成就，说它们只是“运行着某个程序”。我们总是希望我们的机器能够做到更多事情。“只要它能做到这件事”，那就说明它们拥有了“真正的智能”。随着时间的推移，“只是运行某个程序”和“真正的智能”之间的分界线似乎也在改变。或许我们已经达成了人工智能。
和深蓝处于同一条发展路径上的是沃森（Watson）。2011年，IBM公司让他们的一台名为沃森的语言识别计算机在电视竞赛节目《危险边缘》（Jeopardy）中与人类选手一较高下。这台计算机以明显的优势击败了人类。与其询问计算机能否达到人类的水平，或许我们应该问的是计算机是否已经超越了人类。毕竟如今一台典型的个人计算机能够在国际象棋比赛中击败99.99%的人类。正如许多公司已经演示的那样，计算机在接电话和处理其他曾经只有人才能执行的任务时比人效率高得多。我们不应将这看作人类地位的下降，而应该将它看成是人类才智的胜利。人类为机器编程，让机器超越了人类的局限。
本节包含的问题多于答案。对于大多数这些问题，笔者没有仓促地给出任何所谓的答案。问题本身就足够有趣了。
Bierce,1906/2010,21。
人类能判断关于自身思维的众多事实吗？我们的潜意识呢？心理学是人类思维研究人类思维尤其是潜意识的学科。和其他人相比，心理学家拥有对自身更深入的见解吗