希尔伯特第十问题
希尔伯特第十问题作者：卢昌海 来源：数学大院 2023-12-14 07:01 发表于北京
数学问题是数学中最具魅力的部分之一，也是数学史上许多重要思想的源泉。据说，有人曾建议德国著名的数学家希尔伯特（David Hilbert，1862～1943）去解决费马猜想，以夺取为这一猜想而设的沃尔夫斯凯尔奖金（Wolfskehl Prize），希尔伯特笑笑说：“我为什么要杀掉一只会下金蛋的鹅呢？”
在希尔伯特看来，一个像费马猜想这样的数学问题对数学的价值是无可估量的。希尔伯特不仅舍不得“杀鹅”，还怀着极大的热诚为 20 世纪的数学界做了一回“寻鹅之人”。1900 年，在巴黎举行的第二届国际数学家大会上，希尔伯特做了一次堪称数学史上影响最为深远的演讲，题目是“数学问题”。在演讲中，希尔伯特列举了 23 个他认为最具重要意义的数学问题，这些问题被后人称为“希尔伯特问题”。解决希尔伯特问题成了许多数学家终生奋斗的目标，在解决这些问题的过程中，源源不断地产生出的“金蛋”为 20 世纪的数学发展注入了极大的生机。
什么是希尔伯特第十问题
希尔伯特第十问题是一个与解方程有关的问题。在中学时我们就解过许多简单的方程，比如 2x－2y＝1 ，x^2＋y^2＝z^2 。这两个简单方程有一个共同特点，只包含未知数的整数次幂，系数也都是整数，这类方程被称为整系数代数多项式方程。数学家们对这类方程的研究有着漫长的历史。
公元 3 世纪，希腊数学家丢番图（Diophantus，200？～284？）发表了一部长篇巨著《算术》。这部 13 卷的著作，经过 1700 多年的漫长岁月，流传至今的只有六卷。丢番图在这部著作中对整系数代数多项式方程进行的大量研究，对代数与数论的发展有着先驱性的贡献。后人为纪念他，把整系数代数多项式方程称为丢番图方程（Diophantus Equation）。
对于丢番图方程，数学家们最感兴趣的是它是否有整数解（或自然数解）。对于简单的方程这是很容易找到答案的，比如 x^2＋y^2＝z^2 有整数解（早在 3000 多年前，我国古代的数学家就知道这个方程的一组解：即勾三股四弦五）；2x－2y＝1 则没有整数解（因为方程的左边为偶数，右边却为奇数）。但对于一般的丢番图方程来说，判断它是否有整数解却是件极困难的事，其中最著名的例子就是费马猜想，即 x^n＋y^n＝z^n 在 n＞2 时没有非零整数解，直到 300 多年后才得到证明。
长期以来，人们对丢番图方程是否有整数解的研究都是针对特定形式的丢番图方程进行的。有没有办法对一般的丢番图方程是否有整数解进行研究呢？或者，是否可以找到一种普遍的算法，用来判定一个任意的丢番图方程是否有整数解，从而一劳永逸地解决这类问题呢？这便是著名的希尔伯特第十问题。这样的问题在数学上被称为判定问题（Decision Problem），因为它寻求的是对数学命题进行判定的算法。
希尔伯特是一位对数学充满乐观信念的数学家。他提出这一问题时，没有用“是否存在这样的算法”作为问题的表述，而是直接要求数学家们寻找这样的算法，可见他对存在一个肯定的答案怀有期待。这种期待与他在其他方面对数学的乐观看法一脉相承。
不可判定命题的启示
希尔伯特第十问题要求寻找判定丢番图方程是否有解的算法。究竟是什么算法呢？当时没有明确的定义。这一困难使希尔伯特第十问题在提出后整整 30 年没有取得任何实质性进展。
直到 20 世纪 30 年代，对算法的研究才逐渐深入。
数学上，算法是（通过有限多的步骤）对数学函数进行有效计算的方法。因此算法研究的一个重要的切入点，是寻找可以有效计算的函数。到底什么样的函数是可以有效计算的呢？数学家们开始并没有普遍的结论，只知道一些最简单的函数，以及用这些函数通过若干简单规则组合出的函数是可以有效计算的。数学家们把这类函数叫做递归函数（Recursive Function）。
1931 年，年轻的法国数学家赫尔布兰德（Jacques Herbrand，1908～1931）对递归函数进行了研究，并给著名逻辑学家哥德尔（Kurt Gdel，1906～1978）写信叙述了自己的研究结果。哥德尔当时正处于自己一生中最重大的成果——哥德尔不完全性定理——的研究时期，没有立即对赫尔布兰德的工作做出回应。那一年的夏天，年仅 23 岁的赫尔布兰德在攀登阿尔卑斯山时不幸遇难，他的工作因此被暂时埋没了。
与赫尔布兰德的研究差不多同时，20 世纪 30 年代初，普林斯顿大学的美国逻辑学家丘奇（Alonzo Church，1903～1995）也在积极从事逻辑及算法的研究，并且发展出了一种新的逻辑体系。他让自己的两个学生克林（Stephen Kleene，1909～1994）与罗瑟（John Rosser，1907～1989）对这一体系做细致的研究。两个学生都是一流好手，克林后来还成为一流的逻辑学家。他们的研究很快就有了结果，但这结果大大出乎丘奇的意料。他们发现丘奇的那套体系竟然是自相矛盾的！命运似乎只有一个：放弃。幸运的是，丘奇的那套体系中有一个组成部分是自洽的，因此可以保留下来，这部分叫做兰姆达运算（λ－calculus）。
这种兰姆达运算可以用来定义函数，而所有用兰姆达运算定义的函数都是可以有效计算的。在对兰姆达运算做了研究之后，丘奇提出了一个大胆的猜测，他猜测所有可以有效计算的函数都可以用兰姆达运算来定义。
1934 年，丘奇向到普林斯顿大学访问的哥德尔介绍了这一猜测，哥德尔却不以为然。丘奇不服气，请哥德尔给出一个他认为合适的描述。一两个月后，哥德尔就给出了一种完全不同的描述，这种描述的基础正是 3 年前赫尔布兰德在给他的信中叙述的结果。哥德尔对这一结果进行了完善，这一结果被人们称为赫尔布兰德－哥德尔递归函数。
这样，丘奇与哥德尔各自给出了一种体系，描述可以有效计算的函数。丘奇与克林很快证明，这两种看上去完全不同的描述方式实际上是彼此等价的。两位著名逻辑学家的工作殊途同归，大大增强了丘奇的信心。他相信人们已经找到了可以有效计算的函数的普遍定义。但哥德尔及其他一些人对此却仍然怀有疑虑。最终打消这种疑虑的是英国数学家图灵（Alan Turing，1912～1954）。
图灵当时对丘奇及哥德尔在这方面的研究并不知情。他所研究的课题是什么样的运算可以用机器来实现。他的这一研究对后来计算机科学的发展起到了深远的影响。在图灵的研究接近完成的时候，他的导师注意到了丘奇与哥德尔的工作。于是图灵对彼此的工作进行了比较，发现丘奇与哥德尔所定义的那些函数与他的抽象计算机可以计算的函数恰好吻合！图灵把这一结果作为附录加进了自己的论文。这下就连哥德尔也心悦诚服了，毕竟，有什么能比在计算机上计算更接近“可以有效计算”以及算法的基本含义呢？
在这些有关算法的研究中，数学家们还提出了一个重要的概念：递归可枚举集（Recursively Enumerable Set）。即由可以有效计算的函数所生成的自然数的集合。对于一个集合来说，一个很基本的问题就是判断一个元素是否属于该集合。递归可枚举集也不例外。当数学家们研究递归可枚举集的时候，发现了一个十分微妙的结果：对于某些递归可枚举集来说，我们无法判定一个自然数是否属于该集合！换句话说，有一些递归可枚举集是不可判定的。这一结果把对算法的研究与判定问题联系了起来，为后来解决希尔伯特第十问题埋下了重要的伏笔。
这一系列结果出现在 1936～1937 年间。那时候，在数学中存在无法判定的命题已经不是一件新鲜事了。早在 5 年前哥德尔就已经证明了他的不完全性定理，即任何足够复杂并且自洽的数学体系都必定包含不可判定的命题。当时已知的不可判定命题大都集中在逻辑领域内。在数学的其他领域中，究竟哪些命题是不可判定的呢？这个问题在整整 10 年之后才开始有答案。
1947 年美国数学家波斯特（Emil Post，1897～1954）找到了第一个逻辑领域以外的不可判定命题。波斯特是一位有着深刻洞察力的逻辑学家，7 岁时随父母从波兰移民到美国，是美国逻辑学的先驱之一。他早将近 10 年就得到了与哥德尔不完全性定理相似的结果，由于想对结果作更全面的分析而没有及时发表。1936 年，几乎与哥德尔、丘奇及图灵同时，波斯特独立提出了类似于图灵的结果，他也是最早意识到希尔伯特第十问题可能会有否定答案的数学家之一。1944 年，他在一篇文章中明确提出希尔伯特第十问题“期待一个不可解性证明”。当时波斯特在纽约市立大学任教，他的这一观点深深打动了一位学生，使后者走上了毕生钻研希尔伯特第十问题的征途。这位学生名叫戴维斯（Martin Davis，1928～），是解决希尔伯特第十问题的关键人物。
戴维斯的努力——一个麻烦变成两个麻烦
戴维斯的父母从波兰移民美国，戴维斯本人则出生在纽约。1944～1948 年间，戴维斯在纽约市立大学学习，波斯特对希尔伯特第十问题期待一个否定答案的看法，用戴维斯本人的话说是开始了他“对这一问题的终身迷恋”。从纽约市立大学毕业后，戴维斯来到了美国逻辑学的中心普林斯顿，跟随丘奇从事进一步的研究。戴维斯在普林斯顿研究的是一个冷门的课题，对于研究生来说，研究这样的课题最容易出成果。但戴维斯无法抵御希尔伯特第十问题的魅力，在研究自己课题的同时，分出精力继续思考希尔伯特第十问题。他甚至在博士论文上特意增添了一个章节，叙述了自己在希尔伯特第十问题上“不务正业”的结果，那是在 1950 年。这一增添的章节使戴维斯的那篇原本会像多数研究生一样被人遗忘的博士论文名垂史册。3年后，戴维斯发表了一篇更详细的论述。他的这一工作标志着数学家们正式开始解决希尔伯特第十问题。
戴维斯在他的研究中引进及运用了一个重要的概念―――丢番图集（Diophantus Set）。和上面提到的递归可枚举集一样，丢番图集也是一些由自然数组成的集合。不同的是，递归可枚举集是由可以有效计算的函数生成的，丢番图集则是通过丢番图方程生成的。戴维斯的重要发现就在于找到了这两类集合之间的一种关联。
这两类集合之间的关联之所以重要，是因为倘若希尔伯特第十问题具有肯定的答案，即存在一个算法来判定丢番图方程是否有解，那么我们就可以用这一算法来确定一个自然数是否属于某个丢番图集，这表明所有丢番图集都是可判定的。反之，倘若我们可以证明某些丢番图集是不可判定的，也就证明了希尔伯特第十问题具有否定的答案，而这正是戴维斯想要做的。
证明某些丢番图集是不可判定的，最好的办法就是设法把它与某一类已经知道是不可判定的集合联系在一起，递归可枚举集就正是这样的一个角色。如果有人可以证明所有的递归可枚举集都是丢番图集，也就等于证明了某些丢番图集是不可判定的，从而也就完成了对希尔伯特第十问题的否定解决。
不幸的是，在戴维斯找到的关联中用到了一个被称为有界全称量词（Bounded Universal Quantifier）的逻辑算符。如果没有这个有界全称量词，他就可以证明所有的递归可枚举集都是丢番图集，大功也就告成了。可是数学证明是差不得分毫的，因为有了这个有界全称量词，戴维斯的逻辑链条中断了。尽管如此，戴维斯仍然相信所有的递归可枚举集都是丢番图集，他把这一点作为一个猜测提了出来。在当时，这是一个很大胆的猜测。
要证明戴维斯的猜测，关键得把那个有界全称量词去掉，这是件非常困难的事。直到 9 年以后的 1959 年，戴维斯才在与哲学家普特南（Hilary Putnam，1926～）的合作中有条件地做到了这一点。做到这一点所付出的代价是不得不引进两条额外的假设。初看起来，这像是不进反退，原本只有一个麻烦，现在反而变成了两个。但数学假设的证明难度不是用数量来衡量的，戴维斯与普特南所引进的那两条额外假设比那个有界全称量词来得具体，因而处理起来要容易一些。在发表这一研究的全文之前，戴维斯与普特南决定听一听研究希尔伯特第十问题的另一位重要人物罗宾逊夫人（Julia Robinson，1919～1985）的看法，他们把结果寄给了罗宾逊夫人。这一寄揭开了一段新的合作，把他们的结果又大大向前推进了一步。
罗宾逊猜想——距解决只剩一步之遥
罗宾逊夫人是数学界少有的女数学家之一。与其他女数学家一样，她一生在追求学术的过程中遇到过许多坎坷。这些坎坷既有来自社会的，也有生活上的不幸。罗宾逊夫人幼年时屡患疾病，导致身体虚弱，无法生育，这一点曾使酷爱家庭的她陷入极度的痛苦之中。后来，在她同为数学家的丈夫的引导下，是数学的力量让她渐渐摆脱了痛苦的阴影。罗宾逊夫人的丈夫早年曾是她的数论教授，帮助她打下了非常扎实的数论基础。罗宾逊夫人自 1948 年起开始研究希尔伯特第十问题，并曾经与戴维斯有过交流。当她收到戴维斯与普特南寄来的结果时，凭借自己的数论功底很快发现，他们所作的两个假设中有一个可以去掉，同时整个证明也可以作极大的简化。1961 年，戴维斯、普特南及罗宾逊夫人合作发表了这一简化后的结果。这一结果是戴维斯、普特南的逻辑技巧与罗宾逊夫人的数论功底的完美结合，也是希尔伯特第十问题研究中的又一个重要的进展。
但是在戴维斯与普特南所作的两个假设中仍有一个连罗宾逊夫人也无法去除。那便是在他们的结果中用到了一种被称为“指数丢番图集”的集合，这种集合类似于丢番图集，但却涉及指数函数。倘若有人可以证明“指数丢番图集”实际上就是丢番图集，那么戴维斯、普特南及罗宾逊夫人的工作就完全了，希尔伯特第十问题也就被证明具有否定的答案了。但“指数丢番图集”究竟是不是丢番图集却困住了这三个人。
对罗宾逊夫人而言，“指数丢番图集”其实并不陌生。早在 1948 年，她刚刚涉足希尔伯特第十问题的时候，就研究过由著名逻辑学家塔尔斯基（Alfred Tarski，1901～1983）提出的一个猜测。这一猜测认为“指数丢番图集”不是丢番图集。经过一段时间的研究后，罗宾逊夫人开始怀疑塔尔斯基的猜测，因为她找不到任何证据可以支持这一猜测，于是转而猜测与塔尔斯基猜测相反的命题，即“指数丢番图集”实际上就是丢番图集，这个命题被称为罗宾逊猜想。这也正是戴维斯、普特南及罗宾逊夫人 1961 年的工作中惟一缺失的环节。他们距离希尔伯特第十问题的解决只剩下一步之遥，但这一步却难似登天。
在罗宾逊夫人沉醉于希尔伯特第十问题的那些年里，幼年患病所留下的后遗症一再困扰着她。当年的一位医生甚至预言她的心脏机能受损严重，也许活不过 40 岁。这一预测虽然很幸运地由于后来的一次成功的心脏手术而没有成为事实，但每一年的生日，罗宾逊夫人都要在吹熄蜡烛的时候许愿，希望能够看到希尔伯特第十问题的解决。无论谁来解决都可以，但一定要在她有生之年解决。“我无法忍受在不知道答案的情况下离开人世。”这是罗宾逊夫人的话。
时光一年年流逝，罗宾逊夫人的愿望一次次落空。那手握最后一把钥匙的人究竟在哪里呢？
那个时候，戴维斯也常常被人问到这一问题。当时正是冷战时期，对美国人来说世界上最遥远的地方莫过于俄国。戴维斯调侃地回答：“那会是一位聪明的俄国年轻人。”他说对了！一个名叫马蒂亚塞维奇（Yuri Matiyasevich，1947～）的俄国年轻人将从世界的另一端走上数学舞台。
马蒂亚塞维奇——为智慧链条扣上最后一环的人
马蒂亚塞维奇，1947 年出生在俄罗斯圣彼得堡（当时称列宁格勒），12 岁时父亲去世。凭借优异的成绩，家境贫寒的马蒂亚塞维奇在数学竞赛中脱颖而出，获得了各种教育机会。1965 年，在他念本科的时候，他的导师马斯洛夫（S. Yu. Maslov，1939～1982）建议他证明丢番图方程的不可判定性。马斯洛夫轻描淡写地说：“这个问题也被称为希尔伯特第十问题，但你不必理会这个。”马蒂亚塞维奇表示他对研究这类不可解问题没有经验，马斯洛夫补充道：不可解问题没什么大不了的，无非就是把它约化成一个已知是不可解的其他问题。他还告诉马蒂亚塞维奇，有几个美国人曾做过一些研究，但不必理会那些研究，因为它们“很可能是不充足的”。
马蒂亚塞维奇的研究开始并不顺利，他曾一度以为自己已经解决了问题，甚至开始准备作报告了，结果却发现自己犯了一个错误。一段时间的徒劳无功之后，他开始阅读“几个美国人”的“很可能是不充足的”研究成果，但依然没有获得实质性进展。随着毕业时间的临近，他只好把这个问题放在了一边。
1969 年，顽强的罗宾逊夫人又向希尔伯特第十问题做了一次冲击。虽然这一次仍然没有成功，但她为证明罗宾逊猜想提出了一条非常巧妙的思路。罗宾逊夫人的结果发表后，很快有同事把这一消息告诉了马蒂亚塞维奇。这时的马蒂亚塞维奇已决定不再把时间浪费在希尔伯特第十问题上了，于是没有理会。事情接下来的发展极富戏剧性，用马蒂亚塞维奇自己的话说：“在数学天堂的某个角落里，必定存在着一位数学之神，不想让我错过罗宾逊夫人的新论文。”由于他此前对希尔伯特第十问题的研究，苏联的一份数学评论杂志把罗宾逊夫人的论文寄给了他，让他加以评论。这一看，马蒂亚塞维奇立即被罗宾逊夫人的思路吸引住了，他重新投入到希尔伯特第十问题的研究上来。
接下来的几个月，马蒂亚塞维奇一直在思索罗宾逊猜想。1969 年的除夕派对上，马蒂亚塞维奇由于过分专注，走的时候竟然错穿了他叔叔的衣服。全神贯注的投入终于让他获得了巨大的成功。1970 年新年过后第四天，马蒂亚塞维奇成功地证明了罗宾逊猜想，从而一举解决了希尔伯特第十问题。有了几年前误以为解决希尔伯特第十问题的教训，这次他把文章交给了马斯洛夫及另一位数学家栗弗席茨（Vladimir Lifshits），请他们检验，自己携未婚妻出外滑雪度假。两个星期后当他回到学校，一切都变了。他的论文经受住了以眼光犀利著称的数学家法蒂夫（D. K. Faddeev，1907～1989）与马尔科夫（A. A. Markov，1903～1979）的检验，他成为希尔伯特第十问题的解决者。
1 月 29 日，马蒂亚塞维奇作了有关他研究成果的第一次公开演讲。那次演讲中的一位听众把这一成果带到了不久之后在西伯利亚诺沃斯比尔斯克（Novosibirsk）举行的一次数学会议上，会议的出席者中恰好有一位罗宾逊夫人的同事。就这样，马蒂亚塞维奇解决希尔伯特第十问题的消息很快传遍了数学界。当时马蒂亚塞维奇还不满 23 岁，正是一位“聪明的俄国年轻人”。
2 月 15 日，罗宾逊夫人接到了同事的电话，告知她这一消息。那一年的生日，当罗宾逊夫人将吹熄生日蜡烛时，她停了下来，忽然意识到自己许了这么多年的愿望已经成为了现实，那是一种美妙的感觉。虽然她曾经那么接近答案，却还是失之交臂，但她没有觉得遗憾。对罗宾逊夫人来说，对数学真理的欣赏远远超越了任何个人的荣誉。她在给马蒂亚塞维奇的祝贺信中这样写道：“让我特别高兴得是，当我想到我最初提出那个猜想的时候，你还是个孩子，而我不得不等待你的长大。”戴维斯也非常兴奋，他在自己的经典著作《可计算性与不可解性》的平装本序言中写道：“我一生最大的快乐之一是 1970 年 2 月读到马蒂亚塞维奇的工作”。年轻的马蒂亚塞维奇同样对戴维斯、罗宾逊夫人以及在解决希尔伯特第十问题的漫长征途中作出贡献的所有前辈数学家表达了深深的敬意。
在 20 世纪六七十年代那个寒冷的政治冬天里，这些第一流的数学家们以他们的探索精神划开了冷战的冰层，让世人看到了科学的伟大人文力量。按照罗宾逊夫人的说法，这是一种存在于科学家心中的观念，它跨越地理、种族、意识形态、性别、年龄甚至时代而存在，过去、现在及未来的所有数学家们彼此都是同事，他们献身于一个共同的目标，那便是最美丽的科学与艺术。
来源：中国青年报
页:
[1]