作者：silverxz
校对：时光

上回说到 Hilbert 和他的 23 个问题。接下来，我会用两篇来回顾历史。本篇回顾的是第十问题所需要的背景，包括丢番图方程的历史和算法与可计算的历史；下一篇真正进入到 Hilbert 第十问题解决的历史。如果对于本篇的内容已经熟悉，可以直接进入下一篇。

丢番图方程：从Diophantus到Hilbert

这个故事有一个经典开头：

很久很久以前，或者说，1800 年前，古希腊数学家 Diophantus（丢番图）研究了一大堆代数方程，那个时候的代数方程指的是由有理系数多项式构成的方程。他的研究很丰富，其中一项重点是：一个方程有没有整数解。

对于一个有理系数方程，比如，我们可以把它的系数通分，两边相乘，分母去掉，从而变成一个整系数的方程。这不改变解。所以，研究就转变成了整系数多项式方程整数解的存在性。这个问题是 Diophantus 最先着重研究的，所以人们把整系数的多项式方程称作丢番图方程。

请允许我使用“丢番图方程”而不是Diophantine方程，因为这个词我总是打错，而且我总不能写“Turing机”，那太奇怪了

笔者没有考证 Diophantus 研究整数解的动机是什么，或许是受到勾股数的影响，或许他只是觉得有趣。毕竟，Diophantus 是被一些人称为“代数之父”的代数学先驱，他的著作*《算术》(Arithmetica)，从名字就能看出是奠基性的人物——这很容易让人联想到 Euclid 与《几何原本》，Newton 与《自然哲学的数学原理》*等等直白的名字。总之对于 Diophantus，研究整数解存在性或许确实不需要什么理由，他同时也研究很多其他东西。数学本身就是一门兴趣使然的艺术。

随着数学发展，丢番图方程的研究产生了更丰富的动机。但这种研究往往是针对某个或某类特定的丢番图方程去做的，而不是全部丢番图方程。这是因为特定的丢番图方程往往更有具体意义，或更具数学上的美感。

比如，Fermat（费马）会研究形式的丢番图方程的解并留下一句著名的*“我确信我想到了一种美妙的证明，可惜这里空白太小，写不下”；但他恐怕不会特意去研究这种“奇形怪状”的丢番图方程。类似地，线性丢番图方程对应于初等数论中的最大公因子和 Bézout 定理；是勾股数；Pell 方程对应于双曲线；对应于 Ramanujan（拉马努金）的一则经典轶事“taxicab number”*……丢番图方程绝对比你想象的多得多，但大多数数学家关心的总是其中的一些特例。

注意这里的用词是“大多数”。然而世界上还有 Hilbert 这样的数学家存在：他的野心更大，关心全部的丢番图方程，也就是我们要讨论的 Hilbert 第十问题。

科普往往更喜欢强调个人英雄主义，喜欢突出人物的某种特质。许多科普这时候就应该说：“是 Hilbert 比其他人更有雄心壮志，更具胆量与气魄，敢于直面这样庞大的问题。”这样或许也是读者喜闻乐见的，也会为后来Hilbert的期望落空感到分外惋惜。

然而我们得实事求是地说：Hilbert能提出包括第十问题在内的 23 个问题，固然因为他是视野开阔的顶尖数学家，也因为他有相当的雄心壮志，但这同样也要考虑到历史的行程。那个时代对数学的公理化推动、对元数学和数学哲学的讨论即将进入空前的盛况。倘若读者对这一部分历史感兴趣，我或许会单独写一篇附录（挖坑.jpg）。

算法：从Euclid到Hilbert

我们已经提过Hilbert第十问题的陈述：

给定一个丢番图方程，带有任意数量的未知数：设计一个过程，在有限次运算内确定这个方程是否有整数解。

今天我们知道，这可以换成更简练的陈述：

设计一个算法，判断任意给定的丢番图方程是否有整数解。

我们已经回顾了丢番图方程的简要历史，现在的关键是：「算法」是什么？我们看到，Hilbert 把它粗略地描述成一个在有限次“运算”内终止的“过程”。

这种朴素的直觉其实由来已久。我们会在数学学习中发现，某一类问题似乎有一套固定的解决方法，而我们只需要「机械地」执行这一套方法，就可以解决这一类问题。比如你肯定知道的：解一元二次方程的方法，只需要计算

这就是一个非常机械的方法，如果要说的详细些，你可以说：第一步，移项；第二步，合并同类项，找到 a, b, c 三个量；第三步，计算 2a；第四步，计算……用这个方法，你可以机械地解出世界上所有的一元二次方程。

另一个古老的例子来自 Euclid 的时代：计算两个数的最大公因子的方法。这是一个非常好用的算法，直到今天也在使用，一般称为欧几里得算法或辗转相除法——它不仅出现在 Euclid 的《几何原本》中，也出现在《九章算术》中。这个方法同样也可以机械地计算两个数的最大公因子，只需要不断按一定规则加减乘除，如果满足某些条件就停止，然后就可以得到想要的结果。

我们今天使用的算法(algorithm)一词来自于9世纪数学家 al-Khwarizmi（花拉子米）的名字，他有一系列的关于代数方程系统求解的成果。他的求解方法可以看出很明显的「机械化」（或者程式化、系统化，随你们喜欢）的思想，给出的是“一步一步”的求解规则。这大致就是最朴素的算法观念。

但毕竟那个时代并不存在真正可以实现算法的“机械”，人们也就不会有明确提出「算法」这个概念的动机，也不会尝试研究它。这是现实世界带来的制约。

变化发生在17世纪。Leibniz（莱布尼茨）和Pascal（帕斯卡）分别发明了他们自己的机械计算器。顺便一提，Leibniz 还是最先深入研究二进制的人，而且受到了《易经》的启发（我之前一直以为这是地摊文学，但好像是真的）。机械计算好像要成为现实了。Leibniz 有一个大胆的想法：能不能搞一台机器，给它一个数学命题，它就告诉我这个命题是真是假？

这确实有点太跃进了，Leibniz 想弄出一个能解决所有数学问题的算法。这里的问题不止是“算法是什么”，还有一个更直接的问题：我们怎么把数学命题表述成机器可以理解的样子？这就又被时代限制住了，能算加减法的机器和能处理命题的机器显然还有很大差距。更关键的是，那个时代还完全没有形式逻辑、形式化推导的概念，Leibniz知道他需要把口语中的数学命题转换成更精确、更形式化的样子，但是他做不到。

直到19世纪末，Frege（弗雷格）和Russell（罗素）发展出了数理逻辑，把 Leibniz 缺失的数学工具补上了。这的确是一种非常好用的工具，它本身是用来阐述 Frege 和 Russell 等人的「逻辑主义」的，但它同样也被吸收进数学本身，也为Hilbert的「形式主义」提供了土壤。

我们略去过多关于数学哲学的内容，感兴趣的读者同样可以参考附录（如果我写了的话）。Hilbert的形式主义立场让他关心很多很大的问题，他的主张和目标在 1920-1930 年已经不再局限于丢番图方程那样“小”的问题，而是发展为所谓的“Hilbert 纲领”，包含如下 4 条（我们忽略了其中一条关于有限主义的内容）：

形式化：所有数学命题都应该能使用精确的形式化语言来表达。
完备性：证明「每个真命题都能被形式化证明」。
一致性：证明「形式化的数学没有矛盾」。
可判定性：找到一个算法，能够判定任何数学命题的真假。

可以看到，Hilbert 纲领形成了一个闭环，其中的可判定性就是当年 Leibniz 设想的“旧事重提”，现在称之为 Entscheidungsproblem。这个冗长德语词汇的意思是「判定问题」。

如果它们都能实现，那就可以直接造一个机器，把任意一个数学命题形式化之后喂给它就可以了，所有数学家都可以转行研究怎么量产这个机器去了。然而这样的机器不存在，因为 Hilbert 的纲领除了形式化以外，全面失败了。

完备性和一致性是 Gödel 动的手，我们略去不谈，只看我们关心的可判定性。当年Leibniz提出这种想法时，大概没有多少人关心；如今Hilbert把这个设想再拿出来，时机已经趋于成熟，人们终于有能力开始回答这个问题了：「算法」是什么？或者说，「计算」是什么？

可计算性：Gödel, Church, Turing

所谓算法，无非是从一些给定的量出发“按部就班”执行一些操作，最后得到一个结果，而且这些操作得是人类或者机械能够完成的。在这种情景下，我们可以把它抽象成形如的函数。我们考虑，哪些 f 是「可计算」的，给定一个输入就能切实地计算出一个输出？

率先动手的还是其实还是 Gödel，他在“杀死”完备性和一致性的两年后写了一篇论文，弄出了所谓的一般递归函数的概念。这个概念其实很复杂抽象，与我们编程时写的递归函数完全不同。Gödel 猜想“有限计算过程”等价于“递归过程”，但是他不太相信自己提出的一般递归函数确实囊括了所有可能的递归。也就是说，他对一般递归函数是否完全刻画了“可计算函数”的概念表示怀疑。

紧随其后的是Church，他弄出了一个叫「lambda演算」的东西，并且他又证明了两件事：第一，lambda演算和 Gödel 的一般递归函数本质是是等价的；第二，如果我们认为一般递归函数和 lambda 演算确实刻画了可计算，那么 Hilbert 的可判定性就不能达成。

所以这里的问题就是：这两个概念确实成功刻画了可计算吗？这是一个非常主观的、哲学上的问题。因为我们现在就是在尝试定义什么是可计算，所以，一个定义是否符合我们对于可计算的朴素认同，这是一个无法证明的主观问题。

Church 认为答案是肯定的，任何人类能实现的计算过程都可以由 lambda 演算实现，人们称这个观点为「Church议题」（thesis，这里表示的应该是观点、假设的意思，但是一般翻译成议题）。但是 Gödel 并不认同，他仍然保持怀疑态度，认为需要更多的证据来支持。

最后一锤定音的人是 Turing。差不多同一时间，Turing 发表了他最重要的论文 On Computable Numbers，提出了他自己对可计算的刻画方式：「图灵机」。最重要的是，这是一种完全从人类角度出发的构造，他将人类的演草纸抽象成一维的条带，将人类的注意力和行为抽象成图灵机内部的状态机。一切的思考包含于论文的第九章，如 Soare 所说，他推荐每一位学习可计算理论的学生都读一读。

图灵机的诞生立刻说服了 Gödel，他觉得这是对可计算非常恰当的刻画。随后，图灵机被证明为和一般递归函数、lambda 演算均等价。最后，人们对「可计算」的概念有了共识：能被图灵机、lambda 演算、一般递归函数等等价概念所刻画的函数就是可计算函数，它符合我们直觉上对计算的观念。这个观点后来被称为 Church-Turing 议题。在这种观点下，Hilbert 的可判定性完全宣告破产，不存在一个万能的机器告诉我们一个命题是真是假。

然而，Hilbert 第十问题这种更“弱”的问题还是悬而未决的。虽然我们不能一劳永逸解决所有数学问题，但或许的确存在一个算法（在这种语境下，一个可计算函数，或者说一个图灵机，就可以叫做一个算法）可以一劳永逸解决所有丢番图方程呢？此时，问题的一切概念都已经明晰，终于可以迈出解决它的步伐了。下一节我们会看到这个问题是如何被逐步解决的。

笔者注：上述这些工作中还有 Kleene 等人的参与，只提及 Gödel, Church, Turing 是为了方便叙事。