第14章：停！发生什么了？

如果你一直读到了这里，就会对现代逻辑的基本思想有一个不错的理解。不过，也仅限于入门。现代逻辑的内容远胜于此，包含极为深刻而优美的结果。当然，我们不可能在这样一本书中全面评述这些结果。但本章和下一章，我们至少对它们提供一瞥。我们将看看一些关于形式推理哪些可以做哪些不能做的结果，以及这些结果的哲学意味。警告：这两章可能比前面的章节更难一点。我已竭力简单化处理，但我们涉及的是一些复杂的数学问题。说完这些，让我们继续本章的主题。

莱布尼茨——我们在第 6 章和第 9 章碰到的那个莱布尼茨——有一个梦想，一个终结争论之梦。每当我们有一个富有争议的论断，我们就可以用一种被称为普遍文字（characteristica universalis）的恰当语言把它写出来。然后，为了判定该论断的真假，我们演算（calculemus）就行。这种语言使得有一个计算过程（calculus ratiocinator）可以被用于判定该论断是否为真。

尽管莱布尼茨对于实现该计划确实建议了一些步骤，但它一度只是一个梦想。莱布尼茨时代的数学还没有达到可以处理其设想的程度。

我们时代的数学达到了。我们在前面的章节中看到的符号语言可以表达（至少一大类）真假未知的论断。剩下的问题就是，是否存在一个合适的计算过程。

答案（不幸）是，不存在——即使对范围十分有限的数学论断也是如此。该结果由英国数学家阿兰·图灵（1912-1954）于 1936 年证明。图灵是现代计算机科学的奠基者之一。当然，在图灵时代，没有任何为现在多数人所熟知的现代计算机这样的东西。但这些机器的理论远在计算机出现之前就已被图灵和其他人发明，剩下那些人只是去寻找如何在实践中实现这些想法——尽管图灵本人在实际构建计算机器方面（例如在破解二战中德国海军电报密码的Enigma项目中），也取得过令人瞩目的进展。正如所料，图灵在计算上的兴趣与莱布尼茨之梦的联系并非巧合。

什么是计算机？最简单的情况下，计算机就是某种接收一个或多个输入，执行某个过程——数学家称之为算法（algorithm），该名称来自波斯数学家 Al Khwārizmī（780-850）——然后（如果运气好的话）给你一个输出的装置。

现代计算机的输入和输出有不同种类：数、文本、图片、声音。但对机器而言，这些都是数，这是它所能作用的全部对象。计算机的输入装置将输入转换成一串算法能作用的数。输出装置则将这一过程倒转过来。

不过，计算机存储数的形式并非我们在小学算术中熟知的那些。计算机的存储单元只能是两个状态中的某一个：开或关。因此，计算机只有两个基本字节的信息可以使用。人们可以把它们想成 1 和 0。任何数都可以用这两个数字表达。这是由二进制算术完成的。（即，如果你只有两个指头你会如何计数。）在标准（十进制）算术中，数实际上是一种表达 10 的幂之和的方式。比如，4302 就是：

$4\times 10^3+3\times 10^2+0\times 10^1+2\times 10^0$

（$10^0$——实际上任何数的 0 次幂——就是 1）。类似的，二进制数也是一些幂之和，只是这次是 2 的幂。于是，1011 就是：

$1\times 2^3+0\times 2^2+1\times 2^1+1\times 2^0$

下表给出了前几个十进制数与二进制数之间的转换。

十进制	二进制
0	0
1	1
2	10
3	11
4	100
5	101

所以我们可以将计算（算法）看作某种作用在这种二进制数上的东西。

输入和输出就讲这么多，但什么是计算？计算由一组在标准计算机程序中可找到的那类规则给定。这些程序由很多不同的语言写成，其精确细节在这里并不重要。一个相当无趣的程序可能长下面这个样子：

1. 若 $x=0$ 则输出 $x$；否则跳至第 2 行
2. 令 $x:=x-1$
3. 跳至第 1 行

左边的数是行号。输入是某个数 $x$。第 1 行测试这个数是否是 0，如果是，就输出这个数。否则跳到下一行。这一行将 $x$ 减 1，然后计算又回到第1行。稍微思考一下就会发现，这个程序所做的就是把任何输入的数不断减 1，直至减到 0 作为输出。

目前都没有问题。接下来——这是现代计算机真正聪明之处——当计算进行时，计算机不必等待人输入每一行程序。程序本身就存储在计算机中。当然，是存储成一个数。计算机没法存储任何其他东西。（事实上，我们可以把计算机在任何时刻的整个状态想成一个巨大的 0、1 字符串——一个庞大的二进制数！）我们可以把存储在计算机中代表程序的数看作程序的"编码"。若 $n$ 是任何一个数，则令 $P_n$ 为编码为 $n$ 的程序。（若由于计算机中的编码方式，$n$ 恰好不是任何程序的编码，我们就让 $P_n$ 默认为上面那个简单的程序。）严格来说，程序本身不关心它运行的算法有多少个输入。它只是当它被告知时，取用任何位于计算机中的信息。不过，作为约定，我们可以假定，除了那些相干的信息被合适的比特填充，所有输入的信息比特都为 0。

现在，有时一个给定输入的程序会产生一个输出；但有时它会永远运行下去。比如，考虑下面这个程序：

1. 令 $x:=x+1$
2. 若 $x=0$ 则输出 $0$；否则跳至第 1 行

该程序将某个输入加 1，然后测试它是否为 0，如果是，则输出 $x$。但它当然不是 0（我们的二进制数总是大于等于 0），因此我们跳回第 1 行，然后重复这一过程。加1我们永远也得不到 0，因而计算永不停止，就这样以无限循环的方式一直运行（现实中，计算会在机器报废时，或在 $x$ 大到超出计算机能处理的范围时停止）。为将来讨论方便，我们称这个程序为 $L$（表示循环，looping）。

良好构造的程序会被设计成这绝不会发生。程序员通过分析程序，保证它永远不会进入这种无限循环。但这总是能做到吗？是否有算法可以对任何程序和输入，判定该程序和输入下的计算是否会终止？

答案是：没有。这就是图灵所证明的。这是一个相对简单，但却十分精巧的证明。它使用了归谬法（reductio ad absurdum），先假定和我们希望证明的结论相反的情况成立，然后表明这会导致某种不可接受的结果。

假定有一个这样满足要求的算法，称之为 $A$。于是，当 $A$ 应用于两个输入 $n$ 和 $i$，它输出 1 或 0。1 意味着程序 $P_n$ 输入 $i$ 的计算终止；0 意味着它不终止。

现在考虑下面这个算法。让我们称之为 $T$（表示图灵，Turing）：

• 运行算法 $A$（输入 $x$ 和 $x$）。该算法终止并给出 1 或 0 的结果。
• 若结果是 0，则输出 1

• 若结果是 1，则运行 $L$（输入 $x$）。

该程序输入 $x$ 会做什么呢？本质上，它相当于运用 $A$ 判定程序 $P_x$ 输入 $x$ 是否会停止。若计算不会停止，则该程序输出 1。特别的，该程序会停止。但若计算确实停止了，则整个计算会跳至一个无限循环并永不停机。

我是用一种颇为"高层次"的术语来描述程序 $T$ 的。但这并不会产生特殊难题。任何理解信息如何编码并存储于计算机，使用一种可以直接利用这些数据的语言的娴熟程序员，都能写出这样一个程序。

现在，为了完成证明：$T$ 自身也有一个编码，称之为 $t$。我们可以运行 $T$ 并以 $t$ 自身作为输入。如果计算停止，则运行 $A$（输入 $t$ 和 $t$）的计算停止并输出 1。但这样运行 $T$ 的计算就会陷入无限循环而不会停止。反之，若运行 $T$（输入 $t$）的计算不停止，则运行 $A$（输入 $t$ 和 $t$）的计算停止并输出 0。这样，运行 $T$ 的计算就停止并输出 1。因此，若计算不停止，则它停止！无论哪种情况，我们都得到某种不可能的结果。因此我们最初有一个算法 $A$ 的假设必定为假。

图灵证明的精巧之处是某种自指。（我们在第5章碰到过自指。）它让某个假定的程序应用于它自身的编码。这有时被称作对角化（diagonalization），一种由伟大的德国数学家康托（Georg Cantor, 1845-1918）在研究无穷时发明的方法。考察下表你就会明白它为何叫对角化。

	0	1	2	3	4	$\cdots$
0	$\mathbf{a_{00}}$	$a_{01}$	$a_{02}$	$a_{03}$	$a_{04}$	$\cdots$
1	$a_{10}$	$\mathbf{a_{11}}$	$a_{12}$	$a_{13}$	$a_{14}$	$\cdots$
2	$a_{20}$	$a_{21}$	$\mathbf{a_{22}}$	$a_{23}$	$a_{24}$	$\cdots$
3	$a_{30}$	$a_{31}$	$a_{32}$	$\mathbf{a_{33}}$	$a_{34}$	$\cdots$
4	$a_{40}$	$a_{41}$	$a_{42}$	$a_{43}$	$\mathbf{a_{44}}$
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$

最左列是程序的编码。最上面一行是输入。表格中的项 $a_{xy}$ 是编码为 $x$ 的程序输入 $y$ 后的输出。若该计算不终止，则我们可以用符号 $\infty$ 表示。算法 $A$ 所做的——假定它存在——就是计算 $a_{xy}$ 的值是否为 $\infty$。$T$ 作用于该计算在对角线上的结果（粗体显示） ，确保它的行为与 $P_x$ 作用于 $x$ 不同。这样 $T$ 就不可能出现在最左列。但每个程序都出现在这一列。因而 $T$ 不存在。而 $T$ 是由算法 $A$ 定义的，该定义并无问题，因此 $A$ 也就不可能存在。

这个结果称为停机定理（Halting Theorem）。它表明，没有算法可以判定任何给定的程序在给定的输入下是否停机（当然，我们尽可在特殊情形做到这一点）。现在回到莱布尼茨之梦。我们看到的是，有一些数学问题，比如这个停机问题，并没有算法判定其真假。莱布尼茨之梦无法实现。

我在结束前面的章节时会指出，为何其中的看法可能存在争议。让我以同样的方式结束本章。在标准数论假设下，图灵的证明是无可辩驳的。这是足够好的数学。但在我给的上述证明中，有一个到现在我还未作评论的假设。该假设就是，任何我们能看作算法的东西都能写成计算机程序。如果并非如此，则图灵的证明只是表明了没有计算机程序能判定任何计算是否停止。但或许存在某种其他的算法——一种或许能在莱布尼茨的计划中有效使用的算法。

每个算法都能写成计算机程序，这一论断被称为丘奇-图灵论题（Church-Turing Thesis），以图灵和美国数学家Alonzo Church（1903-1995）命名。它本身不能进行数学证明，因为证明只能作用于被精确定义的概念，而尽管什么是计算机能做的可以被精确的数学语言定义，算法却只是一个非形式的直观概念。粗略而言，算法是可以无需猜测和创造性的逐步完成的过程——而这或多或少是模糊概念。

长期以来，丘奇-图灵论题都被数学家所接受。曾有一段试图反驳它的历史。这些反驳都试图构造某种直观上可以被看作算法，但却不能在计算机上编程的东西。这些尝试都失败了。因此，丘奇-图灵论题就被普遍接受了。

然而，现在也有研究领域研究除了那种运用于台式计算机中的计算的计算方法。这些计算有时被称作超计算（hypercomputation）。一个例子是：有些涉及的方法使用模拟量，而不是数字量。（模拟量是连续的，如长度；而数字量则是离散的，如二进制数。）另一个例子是：有些涉及的方法诉诸于广义相对论中的时空性质，其中时间会"加速"。不过，现在谈这些研究的最终结果如何还为时尚早。

本章要点

• 算法可以被编码。

• 假若有算法 $A$，可以判定编码为 $x$ 的算法（即 $P_x$）输入 $y$ 是否终止，则我们可以定义算法 $T$，它计算 $A$ 输入 $x$ 和 $x$ 得到的值，并利用该结果确保它自身的输出“在对角线上”不同于每个 $P_x$。
• $T$ 自身必定有一个编码 $t$。运行 $T$（输入 $t$）将产生一个不可能的结果。
• 因此没有这样的算法 $T$，因而也就没有这样的算法 $A$。