作者：silverxz
校对：时光

许多年后，确认Hilbert第十问题已尘埃落定时，Martin Davis准会想起他老师说「Hilbert第十问题亟待证明不可解」的那个遥远的下午。

我们已经看到，Hilbert纲领中的完备性、一致性、可判定性被Gödel和Turing等人打破了。而Hilbert第十问题无非是判定问题的一个特例。因此，判定问题可解性的否定答案，让人们对Hilbert第十问题的乐观态度在10年内几乎完全转变为悲观。

Post是可计算理论的奠基人之一。他的运气实在不太好：12岁车祸失去左臂，导致放弃天文学转而研究数学。23岁获得数学博士学位，来到普林斯顿读博士后，患上躁狂，一天只能研究三个小时。他在普林斯顿就读期间几乎发现了Gödel的不完备性定理，比Gödel早了十年，只是他觉得需要更完善的分析，没有发表。最后，他57岁死于抑郁症电击治疗诱发的心脏病。倘若他的运气能再好一些，或许如今在历史上的名字会更响亮。

回到正题。1944年，在Hilbert提出这个问题44年后，时任纽约市立学院数学系主任的Post发表了他对Hilbert第十问题的看法，他说：「Hilbert第十问题亟待证明不可解」。

他或许只是在随口发表他的观点。但他没有想到，某种程度上，正是这句话导致了Hilbert第十问题的解决。Martin Davis，一位就读于纽约市立学院的本科生，听到了Post的这句话。而这，成为了Davis投身Hilbert第十问题的开端，也让他成为了这个故事的主人公之一。

Davis：丢番图集

从今天来看，解决Hilbert第十问题的关键首先在于引入丢番图集的概念，并注意到它的重要性。这是一个和丢番图方程可解性相关联的概念，是自然数集的子集，于是我们可以用可计算理论发展出的内容考察它。简单来说：若能找到某个丢番图集不可判定，就能推导出Hilbert第十问题不可解。

这一部分的内容还并不复杂，即便是只关心历史的读者也可以尝试理解什么是丢番图集。所以我们在历史中插入一小段数学，读者亦可跳过：

还记得丢番图方程是整系数多变量多项式方程，我们将丢番图方程记作的形式，其中是这个方程的变量。按理来说它们的取值是整数，不过经过一些技术处理可以让它们等价为取自然数值，这里暂略去。

所谓丢番图集，是指一个 n 元自然数序对构成的集合。它需要满足：存在一个丢番图方程，使有解。

稍微解释一下。首先这里的顺序，丢番图方程 D 是选好了就不能变的，对于每个都只能用相同的 D。而是把变元替换为常量之后得到的 m 元丢番图方程。

乍一看好像不知道在干什么。这里的关键在于，D 是自然数集的子集，于是我们可以使用可计算理论中的工具来研究它。

我们回忆一下什么样的自然数集的子集 S 叫做可判定的（或者也叫可计算的、递归的）：当且仅当存在一个图灵机 M，给定自然数 a，M 可以在有限时间内判断 a 是否属于 S。

如果Hilbert第十问题可解，我们就可以得到一个“判断一切丢番图方程是否有解”的图灵机 M′。这样，对于丢番图集 S，我们只要询问 M′ 这个图灵机如下的问题：丢番图方程是否有解？这样就可以判断是否属于 S，从而所有丢番图集 S 都是可判定的。

反过来说，它的逆否命题就是：如果我们能找到一个丢番图集 S 不可判定，那么也就不存在这样的 M′，即Hilbert第十问题不可解。而研究集合是否可判定的问题是可计算理论相对熟悉的问题，也就有更丰富的入手点和工具。这就是为什么说丢番图集很重要（当然，这也是事后诸葛亮）。

第一个从丢番图集的方向做出推进的人就是Davis，希望读者没有在读了一小段数学之后就把他忘掉。Davis本科毕业后师从Church读博士，做的课题是超算数分层(hyperarithmetic hierarchy)，是Kleene的算术分层(arithmetic hierarchy)成果的推广。这是一个还没人做过的新领域，很有趣，而且肯定能出成果。对于科研人来说，没有比这更好的方向了。

但是Davis陷入了纠结。Hilbert第十问题太迷人，他知道自己很可能没法在这么难的问题上有所建树，但他实在控制不了自己不去想它。最后，他同时做了两方面研究，学位论文也同时包含超算数分层和Hilbert第十问题两方面内容。

我们主要关心Davis那篇论文中关于Hilbert第十问题的部分，让我们看看这篇1953年的论文都做了些什么。

那篇论文中，Davis说明了有限个丢番图集之间的交和并仍然是丢番图集，但丢番图集的补则不一定是丢番图集。这种性质恰好对应了可计算理论中的“递归可枚举集”。这让Davis很自然地猜想：会不会丢番图集恰好就等价于递归可枚举集？如果答案是肯定的，那么根据可计算理论中的一个基本事实：存在一个不可判定的递归可枚举集，就能得知存在不可判定的丢番图集，这就意味着Hilbert第十问题不可解。

这个猜想很简洁漂亮，但它的证明很困难。Davis论文中取得的成果看起来离成功只有一步之遥。为了理解这一点，我们再插入一段数学。

我们的目标是证明丢番图集与递归可枚举集等价。递归可枚举是可计算理论中的一个概念，它和我们刚才介绍过的“递归集”（可判定集）的概念非常相似。递归集 S 要求存在一个图灵机 M，使对于给定的，可以用 M 在有限时间内判断是否成立。即，时 M 要给出肯定的回答，否则给出否定的回答。而递归可枚举集 S′ 则只需要“满足一半”：当时，M 必须正确回答 a 确实属于S′；但当时，M 虽然不能答错，但允许“不停机”，即可以一直运行下去、不给出答案。因此，过去人们也使用“半判定”(semidecidable)来描述递归可枚举的概念。

根据这种定义，丢番图集一定是递归可枚举集。因为，对于丢番图集 S，我们只需要让图灵机 M 不断枚举，判断是不是的解。假如，那么一定有这么一组解，总有一天会被枚举到；如果不存在这样的解，那么图灵机 M 就会一直枚举，停不下来。从而 S 是一个递归可枚举集。（这里有一个之前没提的细节：虽然是中的 n 元组，但可以被编码为中的元素，所以可以视 S 为的子集。这是小小的技术细节，这里暂时不用关心。）

因此，证明真正困难的地方在于，如何证明所有递归可枚举集都是丢番图集。我们先把（一元）丢番图集的定义形式化地写出来：

如果我们能证明，递归可枚举集也能写成这样的形式，那就大功告成了。Davis没有做到这一点，而是证明了一个相似的形式。他证明，如果 S 是递归可枚举集，那么:

可以看出，这里多了一个有界全称量词，即。如果换成，那就和上面的形式一样了。递归可枚举集的这种表示形式也就称为Davis正规形式(Davis normal form)。

看似Davis距离解决这个问题只有一步之遥，只差一个字符而已。然而咫尺天涯，往后几十年，人们都在为去掉这个有界全称量词而努力。

Robinson：关于指数丢番图方程的猜想

让我们转头看看别处。考虑丢番图集的并非只有Davis一人，Tarski也是其中之一。1948年，Tarski猜测，所有2的幂构成的集合不是丢番图集。换言之，Tarski认为丢番图方程不具有表达指数的能力。

Tarski是能在数学史上留下浓重数笔的大数学家，对数学的众多分支都有贡献。读者或许听说过著名的Banach-Tarski分球悖论：选择公理下，把一个球“切”成若干部分，竟然能拼出两个球，并且这两个球都和原来的球一样大（这是一个略吸人眼球的说法，实际上有严格的数学陈述和背景）。而这只是Tarski在1924年的工作，时年23岁。

话归正题，Tarski猜想丢番图方程不具备表达指数函数的能力，并让他的学生Julia Robinson尝试对此进行证明。Robinson是一位命途多舛的女性，自幼丧母，体弱多病，18岁时父亲由于经济困难自杀。但艰难的命运掩盖不了Robinson的数学才华，这位女数学家就是这个故事的第二位主人公。

即便是大数学家，也不意味着他的猜想都是对的——我们已经看到了Hilbert纲领全面失败的例子。事实上，Tarski的这个猜想也是错的，因此Robinson自然证不出来。她尝试无果，于是转而考虑：丢番图方程会不会其实具备表示指数的能力？她大胆地猜想：指数丢番图方程会不会总能等价于某个丢番图方程？这里的指数丢番图方程的意思是，变量可以出现在指数中，比如这样的方程。

平心而论，我们也不能怪Tarski“猜错”。一个多项式方程不具备表达指数的能力，这是很自然的猜测；反倒是Robinson的猜测着实大胆。但是，Hilbert第十问题的解决就是离不开Robinson数次对解决方向的敏锐。

顺着这一猜想，Robinson继续研究。1952年，她发表了相应的研究成果。论文中，她虽然没有证明这一猜想，但构造出了用指数丢番图方程表达二项式系数、阶乘、质数的方法，说明指数丢番图方程表达能力之强。然后，她找到了指数丢番图方程可以表示为丢番图方程的一个充分条件，这个条件后来称为“J.R.假设”。这些研究更多是在探索丢番图集和丢番图方程的性质，还和Hilbert第十问题本身没有太直接的关系，或许也没人能意识到这些内容对Hilbert第十问题的解决非常重要。

读者可能会期待，Davis和Robinson相遇，汇总两人的成果，一起解决Hilbert第十问题。其实他们确实遇见了。就在Robinson的论文发表之前，1950年在剑桥举办的国际数学家大会上，两人见过一面，彼此交换了各自的研究内容。Robinson表示她正在尝试给各种特定的集合“丢番图定义”，尤其是给关于指数函数的，还介绍了那条J.R.假设。但有趣的是，Davis当即表示，他认为Robinson的这条路走不了多远；而Robinson心里其实也觉得Davis的路不行——或许这也是一种“文人相轻”。后来Davis说，“这绝对是我人生中特别蠢的论断之一”。

Davis, Putnam, Robinson：合作

1957年夏，康奈尔大学举办了一场持续五周、汇集全美国几乎所有逻辑学家的大会。在这里，Davis遇到了这段历史的第三位主人公，Hilary Putnam，一位逻辑学家兼哲学家。会议期间他们住在一块儿，两人很投缘，几乎想都没想就决定一起合作，这是他们共事的开始。

我们还记得前面提到的Davis正规形式，那个“只差了一个有界全称量词”的形式。这个形式的构造是Davis仿照Gödel使用中国剩余定理的编码方法得到的。这时，Putnam提出再用一次中国剩余定理编码的想法。

Davis起初对此表示怀疑，毕竟他肯定已经思考过很多次了。但最终，他们成功沿着这条路推进。随后的三个夏天，他们进一步合作，用Davis的话评价，「we had a wonderful time.」他回忆说，「我们无话不谈。Hilary教了我一点欧洲古典哲学，我教了他泛函分析。我们谈论弗洛伊德心理学、谈论时政、谈论量子机制的基础，但我们主要谈数学。」

1959年夏，他们做出了最关键的成果。他们对Davis正规形式应用中国剩余定理，同时吸收了Robinson的方法，进行了许多繁杂的分析和处理……最终，去掉了Davis正规形式中的有界全称量词——但是代价是引进了两条新条件。第一个条件就是指数丢番图方程能被表示为丢番图方程，也即Robinson的猜想；第二条则是一条关于质数性质的猜想：质数列2,3,5,7,11,…中存在任意长的等差子数列。

实际上，第二条猜想在2004年才被Ben Green和Terence Tao(陶哲轩)证明，如今称为Green-Tao定理，Davis和Putnam当然是没有解决。但这就是合作的价值：他们把研究的成果寄给了Robinson。或许他们也没想太多，只是因为恰好用到了Robinson的猜想，双方的研究意外地交汇了。

但他们没想到的是，Robinson带来了关于第二条猜想的突破。她巧妙地修改、扩展了Davis和Putnam的证明，用了一些数论中的技巧，绕过了第二条猜想。Robinson的数论功底应当不弱。一则趣事是：此时Robinson已经结婚很久，她的爱人Raphael Robinson正是她当年教她数论的老师。

Robinson绕开第二条猜想之后，实际上他们就已经证明了：所有递归可枚举集都是指数丢番图集。之后，三人于1961年联合发表了相应成果。这次合作对于他们来说是一次“重新认识”。以前Davis觉得Robinson的路行不通，但做着做着发现——诶，还真需要Robinson研究的这一套东西，而且Robinson本人也的确是水平很高的数学家；Robinson之前也不觉得Davis的想法很有未来，而这一次，用她的原话，「I am very pleased, surprised, and impressed with your results on Hilbert’s Tenth Problem.」，也算是令她刮目相待。

也让我们来整理一下目前为止的进展：我们已经知道，证明Hilbert第十问题不可解，只需要证明丢番图集等价于递归可枚举集。而根据刚才的结果，这就等价于证明丢番图集等价于指数丢番图集。而根据Robinson的已有研究，它的一个充分条件是“J.R.假设”。总的来说，只要证明J.R.假设，就证明了Hilbert第十问题不可解。由此，Hilbert第十问题的研究进入了新的阶段。

Matiyasevich：迷雾与最后一块拼图

接下来的几年里，三人一直在尝试证明J.R.假设，但没有成功。整个六十年代，他们找到了许多能推出J.R.假设的新条件，但始终没有办法真正解决问题。这让提出了J.R.假设的Robinson本人都一度陷入了巨大的悲观之中，乃至于转而尝试证明Hilbert第十问题其实是可解的。

8年过去了。没有进展。

实际上，一直有不少同行并不看好Davis等人的工作。就连1961年那篇重要结果的审稿人都说，「作者的证明很巧妙，但完全没有使用深刻的数论或可计算理论知识，因此不太可能与Hilbert第十问题有密切关联。关于指数丢番图方程的猜想也不太可能成立。」

的确，正如我们提到过的，Tarski那样的认为指数丢番图方程的“表达能力”严格强于丢番图方程的直觉，才是更符合常人直觉的。Davis他们坚持自己的主张，毫无疑问是出于对自己研究课题的更深刻的洞见。但现在，连他们自己都开始怀疑自己了。

1968年，Davis做出了一点“小东西”。从Robinson的回应我们就能看出她有多么悲观了：「很高兴看到你的成果，我对J.R.假设的信心仍没有恢复。不过，这是我第一次看到它得证的可能性。你的方法可能确实能奏效，但似乎需要无穷多的运气。」——当一位研究判定性的数学家需要诉诸“无穷多”的时候，这显然只是她毫无信心的委婉说法。

这些年间，Davis常常去做关于Hilbert第十问题的报告。每当人们问到他对后续工作的展望时，Davis或许也只能在心底暗自苦笑，给出一个诙谐的回答避而不谈。他说，「我相信J.R.假设会被一个聪明的苏联青年(a clever young Russian)证明」。

这话或许有两层原因。一个是苏联式教育确实容易出“少年天才”，一定程度上这一传统也延续到了今天的俄罗斯和中国。另一方面由于冷战，苏联在学术上一直处于相对孤立的地位，数学虽是少数交流比较好的学科，但也有诸多困难。这导致Davis这样的美国人很少能与苏联同行交流。“被苏联人证明”这种话，或许只是无奈地期待一个意料之外的奇迹吧。

然而，苏联数学界并非没有人关注Hilbert第十问题。我们把时间倒退一些。

Matiyasevich，17岁的IMO(国际数学奥林匹克竞赛)金牌，同年(1964年)保送圣彼得堡国立大学——几乎是“少年天才”中最符合刻板印象的一位了。或许是Davis在研究受挫之余苦修了预言术，Matiyasevich就是这个故事的最后一位关键角色。

大二时，Matiyasevich已经做出了一些关于数理逻辑的成果——足以在1966年的国际数学家大会上展示的那种。随后，他被Sergei Maslov建议去研究Hilbert第十问题，话是这么说的：「去试试证明没有算法能判定丢番图方程的可解性。这个问题有个名字叫Hilbert第十问题，但你不用管。」

「啊……但我还没学过判定问题不可解的任何证明方法……」Matiyasevich说。

「没关系」，Sergei Maslov说，「一般就是把它规约到另一个已知的不可解问题上，而你对规约的技术已经很熟悉了。」这话说的倒没错，Davis试图证明“丢番图集等价于递归可枚举集”，本质上也是基于“已知递归可枚举集不可判定”的一种规约。

「那我需要额外读点什么资料呢？」Matiyasevich问。

「呃……是有一些美国人搞的东西，但你没必要读。」

「为什么？」

「他们折腾了那么久还没做出来，估计方法肯定不对。」Sergei Maslov说。

也不能怪Maslov看轻Davis他们、低估了Hilbert第十问题的难度。在没有真正做过某个问题之前，错估问题的难度是常态。正如一则经典但无切实依据的传言：Minkowski曾断言“四色定理没有被证明，无非是因为只有三流数学家在它上面浪费过时间”——然后他自己尝试了几周，也没有做出来。

并且我们也提到过，这种不看好的观点并非Maslov独有。J.R.假设无非是“指数丢番图方程等价于丢番图方程”的充分条件；而后者又只是Hilbert第十问题不可解的充分条件。就算Hilbert第十问题真的不可解，也不一定代表J.R.假设成立。几年没有进展，或许，真的错了。

更重要的是，摆在人们面前的从来不只有证明J.R.假设这一条路。于是，1965年，Matiyasevich真的完全没读Davis, Putnam, Robinson他们的工作，他按照Maslov的建议，从“自由半群上的词方程判定问题”入手。如果读者学过抽象代数，大概能理解这是个什么问题，不知道也不重要，这里就不过多介绍了。

总之，这是一个有明确的代数背景和语言学意义的问题。和它类似的问题此前已经得到了Post, Tarski, Markov……等许多知名数学家的一系列研究，可以说这个问题“研究圈子”比Hilbert第十问题的研究圈子要大得多。更关键的是，它的不可判定可以直接推导出Hilbert第十问题不可判定。这就是J.R.假设之外的解决Hilbert第十问题的路径之一。

如果我们不站在上帝视角，恐怕也不得不承认，这似乎是一条更有前景的道路。或许我们也会觉得，Davis等人是在一条狭窄崎岖的路上“死磕”。但是事后来看，词方程判定问题的这条路反而才是行不通的，因为这个问题其实是可判定的，而且在Hilbert第十问题被解决之后才得证。

三年过去了，Matiyasevich沿着这个方向尝试了许多，也考虑了一些词方程判定问题的扩展版本，但并没有什么好的结果。最后，他也只能放弃这条路，去看看那些“美国人搞的东西”。一开始，他觉得这种指数增长的丢番图集的记号“很不自然”，但他非常敏锐，很快就意识到这家伙在Hilbert第十问题中的重要性。

这之后，Matiyasevich几乎全身心地投入到Davis等人的这条解决路线中。他组织过一些讨论班，请了5位逻辑学家、5位搞数论的专家，一起讨论现有的结果。但很快，那些人都不来参加了，他只能自己一个人研究。

他几乎遇到了和当年Davis一样的困境：知道Hilbert第十问题很困难，但就是没法放弃。Davis还是比较幸运的，他比Matiyasevich要早个十几年，且手握一个容易出成果的方向。Matiyasevich就更“窘困”一些。Matiyasevich回忆说甚至有教授取笑(laughed at)他，“Hilbert第十问题做出来了吗？还没？那你可就没法毕业喽！”

Matiyasevich确实在毕业之前都没做出这个问题。但他还是毕业了，靠他大二之前弄出来的那些成果。随后他进了研究所读博，研究方向也与Hilbert第十问题无关。那之后，他“认清现实”，彻底把Hilbert第十问题放在一边。

倘若这是个虚构的小说或影视作品，这里应当是颇有张力的一小段，主角正处于低谷，饱受挫败。看客也当为之牵动，或共鸣，或同情。“史实”反倒缺乏这种感觉，因为你们都确凿知晓，Matiyasevich最后会成功的。然而须知，失败的“Matiyasevich”们千千万万，科普却只会讲这位成功的Matiyasevich。这也不算“有失偏颇”，或许该说是诗意的英雄叙事——人们愿意且需要传颂这样的史诗。

言归正传。Matiyasevich注定不能离开Hilbert第十问题。1969年，在Matiyasevich放弃Hilbert第十问题没多久后，Robinson发了一篇新论文。Matiyasevich知道了这件事，但不打算去读。但命运偏要他去读——那时候苏联会挑选一些外面的研究成果翻译到国内的期刊上，而Matiyasevich作为这一领域的专家，被选定为Robinson论文的审稿人。这下，他不得不读了。

众所周知，某些事情戒掉是很难的，而重新沾上只需要一个契机——数学就是这种东西。Robinson提出的一些新想法立刻激起了Matiyasevich的兴趣，她考虑了一类特殊的Pell方程，而这与Matiyasevich几年前做过的关于Fibonacci数列的尝试有些类似——我们知道，Fibonacci数列也是指数增长的。Matiyasevich又回到了那个整天思考Hilbert第十问题的疯狂状态，他参考Robinson的方法，回顾自己过去的研究……甚至连1970年的跨年夜都停不下来。直到1970年的1月3日，他，真的，把这个问题做出来了。

然而我们都知道，比证明更常见的是伪证。事实上，Matiyasevich已经有过一次“以为自己解决了Hilbert第十问题，但其实没有”的经历，那种尴尬让他永远也忘不了。他内心一定特别激动，但仍然努力冷静下来，特别仔细地核验了整个证明，并请身边的人帮忙检查——都没有发现问题。

终于在1月29日，他做了公开报告，展示了他的成果。参会者有Robinson的同事。成果很快传到Robinson、Davis……传到数学界。这时候我们终于可以说：据问题提出70年后，Hilbert第十问题已经被证明不可解了。

尾声

杀死魔王不会是战斗的结束。解决Hilbert第十问题也并非这个问题的结束。正如著名的比喻：数学问题是下金蛋的鹅，关键不在于这个问题的答案本身，而在于解决它所使用的方法，以及它衍生出的种种其他问题和结果。

Matiyasevich最后使用了一个丢番图方程来表达或者说编码所有的递归可枚举集。于是可以自然地提出其他问题：这样的方程最少需要多少变量？Matiyasevich刚开始给出的上界是200，后来一路被Robinson等人降低到14，再降到9。这不仅仅是“善后工作”，而是属于从Hilbert第十问题发展出的新问题。除此之外，解决Hilbert第十问题的工具和方法也被应用于处理数论、分析学（一些微分方程问题和积分问题）、博弈论中的一些判定问题，这在Matiyasevich的著作Hilbert’s Tenth Problem中都可以看到。

对于Hilbert第十问题本身来说，也可以有其他的推广问题：加上什么样的限制之后，可以让丢番图方程保持不可解或变得可解？不再要求整数解，推广到上或其他更大的域上，是否能让它变得可解？这些问题中的一大部分都是open的。不过，那是交给其他“勇者”去做的事，我们的Matiyasevich, Robinson, Davis, Putnam的故事，就该在这里停步了。他们的功业浓缩入一句话当中:

MRDP定理(Matiyasevich-Robinson-Davis-Putnam). 递归可枚举集等价于丢番图集。

Matiyasevich是唯一至今仍在世的人。后来他去研究了一些关于四色定理、黎曼函数的问题，虽然没做出什么太大的成果，但始终不曾离开数学，去年仍以76岁高龄作为唯一作者投稿了文章。

Putnam或许是这个故事中最没有存在感的一位，因为他算是其他剧场来客串的。他的本职是哲学家，与Davis的合作是他不多的数学成果之一，但他在哲学中成果的地位和重要性很高。

Robinson在70年代和Matiyasevich做了许多关于Hilbert第十问题的后续工作。她被认为是美国本土第一位在数论上取得重大成果的女数学家，1975年当选美国国家科学院院士。

1982年，她被提名为美国数学学会的会长(任期1983-1984)。她完全明白，这种当选并不仅仅因为她的数学贡献，还因为她的女性身份——正如她也不会忘记，几十年前求学求职时女性身份带来的不利影响，虽然她几乎不会主动抱怨。如她所说，她“别无选择”，只得接受了这个职位，承担她的责任，为未来的女性数学家提供更好的环境。

1984年的会长任期内，Robinson诊断出白血病。暂时好转后，她的姐姐以Robinson自己口吻撰写了Robinson的自传。随即Robinson于1985年去世。自传的最后一段写道：