希尔伯特第十问题

在上面几章我们比较详细地介绍了一次不定方程（一次同余）及二次不定方程中的佩尔方程的解法及求解的历史。在这些介绍中，我们可以注意到古代与现代研究的一个差别。在古代，人们一般热衷于寻求不定方程的一个求解方法。而在现代，人们对不定方程的研究则细致得多：一般要从考虑要研究的不定方程是否有解开始，如果无解，证明为什么无解。如果有解，则考虑解的情况。

判断一个不定方程是否有解有些时候比较容易。如二元一次不定方程。但对绝大多数不定方程而言，判断它是否有解并不是容易解决的事情。如佩尔方程的有解性直到拉格朗日才得以完成。而著名的费马方程xn+yn=zn，n>2的无解性则经过了300多年后才得到解决。

最一般的问题是由希尔伯特于20世纪初提出的：

长期以来，人们对丢番图方程是否有整数解的研究都是针对特定形式的丢番图方程进行的。那么有没有办法对一般的丢番图方程是否有整数解进行研究呢？或者具体地说，是否可以找到一种普遍的算法，可以用来判定一个任意的丢番图方程是否有整数解，从而一劳永逸地解决这类问题呢？这便是著名的希尔伯特第十问题。在本章中，我们将对这一问题的解决历程做一简单的介绍。

2000年8月6日上午，第二次国际数学家大会在巴黎召开。8日上午，一位外表朴素无华的数学家登上讲台，缓慢地、审慎地开始了自己的演讲。这位不到40岁的数学家在当时已经开始享有一个数学家所能享有的最高声誉。他就是德国著名数学家大卫·希尔伯特（1862～1943）。

希尔伯特从小喜爱数学，在威廉预科学校读书时，他数学获最高分“超”。老师在毕业评语中写道：“该生对数学表现出强烈兴趣，而且理解深刻，他用非常好的方法掌握了老师讲授的内容，并能有把握地、灵活地应用它们。”

1880年秋，希尔伯特进柯尼斯堡大学攻读数学。在大学期间，对科学的共同爱好把希尔伯特与比他年长三岁的副教授胡尔维茨和比他高一班的闵可夫斯基（日后做过爱因斯坦的数学老师）紧密联系在一起。希尔伯特后来曾这样追忆他们的友谊：“在日复一日无数的散步时刻，我们漫游了数学科学的每个角落。”后来，把数学融入谈论成为他特有的风格。一则与之有关的轶事发生在多年之后：人们看到希尔伯特日复一日地穿着破裤子，这对许多人而言是令人尴尬的，把这种情况得体地告诉希尔伯特的任务落在他的助手柯朗（也是一位极著名的数学家）身上。柯朗知道希尔伯特喜欢一边谈论数学，一边在乡间漫步。于是便邀请他一同散步。柯朗设法使两人走过一片多刺的灌木丛，这时柯朗告诉希尔伯特他的裤子被刮破了。“哦，不是，”希尔伯特回答说，“它几星期前就是这样了，不过还没有人注意到。”

1888年秋，希尔伯特解决了代数不变量中著名的“哥尔丹问题”，这使他声名初建。他的证明是纯粹的存在性证明，这使它在发表之初遭到了包括哥尔丹本人在内的一批数学家的非议。

哥尔丹宣称“这不是数学，而是神学！”但希尔伯特充分相信存在性证明的深刻意义和价值：“在我们这门科学的历史发展中，纯粹的存在性证明始终是最重要的里程碑。”他的存在性数学思想方法产生的巨大影响，使人们逐渐认识并接受了这种纯存在性证明。哥尔丹后来向希尔伯特的成功表示了敬意，针对以往的怀疑和否定态度，他优雅地说：“我终于相信神学也有其优点。”

1895年，一直想把哥廷根大学建成世界第一流数学中心的数学领袖F·克莱因动员希尔伯特到哥廷根去。希尔伯特接受了邀请，并在那里一直待到48年后去世。正是通过两人联手，开创了哥廷根学派的全盛时期，使其成为世界数学的中心。世界各地的学生把哥廷根当做数学圣地，打起背包，来到这里。直到1933年纳粹统治德国所导致的大批流亡为止，哥廷根神话保持了30多年。而希尔伯特的学术成就、教学活动及其个性风格，使他成为这一强大学派的领头人。

希尔伯特本人是20世纪前后世界最伟大的数学家之一（另一位与他并驾齐驱的是法国数学家庞加莱）。希尔伯特属于这样的数学家，竭尽全力打开一座巨大的矿藏后，把无数的珍宝留给后来人，自己却兴趣盎然地去勘探新的宝藏。他在数学上是个“多面手”，在数学几乎所有领域都作出巨大的贡献。他去世时，著名的美国《自然》杂志上写道：“希尔伯特就像数学世界的亚历山大，在整个数学版图上，都留下了他那巨大显赫的名字！”

希尔伯特同时是一位杰出的教师。这位平易近人的教授周围，聚集起一批有才华的青年。得到他直接指导或受其教诲的著名数学家数不胜数：外尔、柯朗、埃米·诺特（数学史上最著名的女数学家）、冯·诺依曼、策梅罗，等等。他对整整一代学生产生了强大、神奇、罕见的影响。“希尔伯特就像一位穿杂色衣服的风笛手，用甜蜜的笛声引诱一大群老鼠跟着他走进数学的深河。”“一旦一帮学生围绕着希尔伯特，不被杂务所打扰而专门从事研究，他们怎能不相互激励……在形成科学研究这种凝聚点时，有着一种雪球效应。”哥廷根大学的黄金时代正是如此开辟出来的。可惜，在希尔伯特晚年，他的学生大都被迫离开，他于1943年2月14日在孤寂中逝世。在他的墓碑上，人们镌刻下体现他身上那种极富感染力的乐观主义的名言“我们必须知道，我们必将知道”。这种乐观主义，将在哥廷根希尔伯特墓碑上发出回响，只要石碑犹存，它就永远不会停息。正如柯朗在纪念希尔伯特诞生100周年的演说中指出的：“希尔伯特那有感染力的乐观主义，即使到今天也在数学中保持着他的生命力。唯有希尔伯特的精神，才会引导数学继往开来，不断成功。”

希尔伯特是善于提出重要数学问题的真正大师。希尔伯特认为，科学在每个时代都有它自己的问题，而这些问题的解决对于科学发展具有深远意义。他指出：“只要一门科学分支能提出大量的问题，它就充满着生命力，而问题缺乏则预示着独立发展的衰亡和终止。”

在1900年巴黎第二届国际数学家大会上，希尔伯特所做的演讲题目就是“数学问题”。在这一数学史上最重要的演讲中，他不仅对各类数学问题的意义、源泉及研究方法发表了精辟见解，而且根据过去特别是19世纪数学研究的成果和发展趋势，向国际数学界提出了23个数学问题。这23个问题通称“希尔伯特问题”。一位大数学家曾对希尔伯特说：“你使得我们所有的人，都仅仅在思考你想让我们思考的问题。”

希尔伯特问题涉及现代数学的大部分领域，在日后的岁月中，这些问题就像一张航图，数学家总是按照它们来衡量数学的进步。而对它们的探讨则刺激了广泛的数学研究，对20世纪数学产生了持久的影响。在解决这些问题的过程中源源不断地产生出的“金蛋”也为20世纪的数学发展注入了极大的生机。贯穿20世纪，当每一个希尔伯特难题被征服时，都会引起整个国际数学界的关注。任何解决希尔伯特问题的人，哪怕是其中一部分的人都将被永彪数学史册。著名数学家外尔称这类人为数学家中的“荣誉阶级”。

在本章中，我们准备对“希尔伯特问题”清单上涉及丢番图方程的第十个问题——以希尔伯特第十问题著称——的解决历程做一简单的介绍。

希尔伯特第十问题在数学上被称为判定问题，因为它寻求的是对数学命题进行判定的算法。它的陈述非常简洁：

10.丢番图方程可解性的判别

设给了一个具有任意多个未知数的整系数丢番图方程，要求给出一个可行的方法（verfahren），使得借助它，通过有穷次运算可以判定该方程有无整数解。

这里的德文verfahren，就是英文所谓的algorithm（算法）。这一数学名词的来由与花拉子密有关。825年左右，阿拉伯数学家花拉子密完成了《印度的计算术》，书中介绍了如何使用印度数码进行算术运算。这本书的一个拉丁文稿是以“花拉子密说”开始的，后来经过讹传，这位数学家的名字演变成英文的“al-gorithm（算法）”。

算法的概念我们在前面已经多次使用过。但什么是算法呢？我们可以给出它的一个描述性定义：所谓算法可理解为求解某类问题的完全机械的、统一的方法。它由有限多个明确的步骤组成，对于一类问题中的每一个给定的具体问题，只要机械地执行这些步骤就能得到问题的解答。由于算法具有明确性、有限性及“按部就班”的特点，因此现在算法通常可以编成计算机程序，让计算机执行并解决。

可以说，算法思想与算法实例源远流长。从古代开始人们就已经掌握了一些算法。比如我们前面介绍过的求两个整数最大公因数的辗转相除法就是一个典型的算法。其他如整数、普通分数和小数的加减乘除运算，方程的求根公式等，都是数学中最基本的算法。正如我们已提到的，我国古代数学在算法方面有悠久的历史，并取得了许多伟大成就。如我国著名数学家吴文俊指出的：“我国传统数学在从问题出发以解决问题为主旨的发展过程中建立了以构造性与机械化为其特色的算法体系。”

在希尔伯特第十问题提出前，因为存在算法的问题一般是通过构造出算法来确证的，因而有算法的直观理解就可以了。然而，希尔伯特第十问题的提出则使人们意识到，当涉及抽象地证明某类问题存在算法时，仅有对算法的朴素理解就不够了。实际上，如果没有算法的精确定义，人们对希尔伯特第十问题的可解与不可解究竟是什么含义都无法弄清楚。因此，为了解决希尔伯特第十问题，首要的事情是必须对算法给出更严格的、精确化的数学定义。对此，直到20世纪30年代，随着数理逻辑发展成为一门成熟的数学学科及一批逻辑学家和数学家的杰出工作，这一问题才通过算法概念的形式化得到圆满解决。这种形式化是把算法与某类计算的“模型”联系起来。

最早的这类形式化是由美国逻辑学家丘奇（1903～1995）与他的学生克林（1909～1994）做出的。1933年，在从事逻辑及算法的研究中，他们给出了λ—可定义函数。其后各种计算模型纷纷问世。1934年，著名数学家及逻辑学家哥德尔在法国数学家埃尔布朗（1908～1931）的启发下，提出一般递归函数的定义，随后克林在1936年把它具体化。同年，丘奇证明了他提出的λ—可定义函数与一般递归函数是等价的。丘奇同时提出算法可计算函数等同于一般递归函数或λ—可定义函数，这就是著名的“丘奇论题”。差不多同时，一种更符合人们直观经验的算法定义由英国数学家图灵引入。

图灵（1912～1954），科学史上罕见的具有非凡洞察力的天才。1935年，当还是剑桥大学的学生时，图灵旁听了数理逻辑学家纽曼开设的一组课程。在课程中纽曼提到了希尔伯特于1928年提出的一个有关一阶逻辑的判定问题。图灵立即被这一未解之谜迷住了。在经过深入思考后，他于1936年5月完成了他最重要的数学论文“论可计算数及其在判定问题中的应用”，该文于1937年发表后，立即引起广泛的注意。

在这篇思想深刻而丰富的论文中，图灵的贡献之一是引入了一种“理想计算机”即著名的图灵机。在此基础上，图灵从一个全新的角度定义了可计算函数：可计算函数就是图灵机能计算的函数，一个算法就是一个能够被图灵机执行的有限操作集。这给计算下了一个完全确定的定义，从而将计算的概念放在了一个坚实的数学立足点上，使含糊的、直觉的思想过渡到精确的、数学上明确定义的算法概念。1937年，图灵又在他的“可计算性与λ—可定义性”一文中证明了图灵机可计算函数与λ—可定义函数是等价的。这进一步拓广了丘奇论点：算法（能行）可计算函数等同于一般递归函数或λ—可定义函数或图灵机可计算函数。之后，1943年波斯特提出“首尾算法”；1947年马尔可夫又提出“正规算法”。同样的，这两种算法定义虽然是从完全不同的角度提出的，但它们与其他的算法定义也是彼此等价的。在现在的计算机时代，人们还可以将“算法”定义为用计算机语言编写的一套计算机程序。而且若通过取消对数据大小的所有限制而使问题理想化，那么不管用什么语言和机器，所产生的可计算函数集都相同：一种计算能够在一种机器上用一种语言进行，当且仅当它能在任何其他机器上用任何其他语言进行。也就是说，语言和机器的选择对于“算法”的最终定义来说是无关紧要的。

在有关算法的研究中，数学家们提出了一个重要的概念：递归可枚举集。它指的是由可以有效计算的函数所生成的自然数的集合。在对它的研究中，数学家还得出一个重要结果：对于某些递归可枚举集来说，我们无法判定一个自然数是否属于该集合！换句话说，有些递归可枚举集是不可判定的。这一结果把对算法的研究与判定问题联系起来，为后来解决希尔伯特第十问题埋下了重要的伏笔。

在希尔伯特第十问题提出后的最初一段时间中，数学家还根据拉格朗日定理得到一个比较容易的结论。拉格朗日定理是说任一自然数可表示为四个整数的平方和。根据这一定理，有自然数解等价于有整数解。这意味着，讨论一个丢番图方程有无整数解可归结为讨论方程有无自然数解。在这一结论基础上，人们讨论希尔伯特第十问题时，只需看是否存在一个算法判定丢番图方程有无自然数解就可以了。

除此结果外，在希尔伯特第十问题提出后的前30多年中，由于人们只有关于算法的直观、朴素认识，因此研究毫无进展。但随着20世纪30年代从不同途径出发得到的若干种完全等价的算法精确定义的提出，数学家们在一片黑暗中摸索的岁月终于过去了。在探求希尔伯特第十问题的道路上，数学家开始迈出了重要而基础的第一步。

随后的一次突破主要是观念上的。在20世纪以前，人们普遍认为，所有的问题都是有算法的，人们的计算研究就是找出算法来。当希尔伯特在1900年提出第十问题时，他对问题存在一个肯定的答案怀有期待，他与其他数学家都倾向于认为：所要寻找的一般算法是存在的。然而，在1944年，最早意识到希尔伯特第十问题可能会有否定答案的美国数学家波斯特（1897～1954）发表了一篇关于希尔伯特第十问题的论文“寻求一个不可解的证明”。他的这一观点一发表就产生了影响。而受影响者中的一位后来走上钻研希尔伯特第十问题的征途，并成为解决第十问题的关键人物之一，他的名字叫马丁·戴维斯。

戴维斯1928年出生在纽约。1944年，戴维斯进入纽约市立大学学习，当时波斯特正好在这里任教。于是，戴维斯得以在1944年看到了波斯特的论文。论文中的观点深深打动了戴维斯，从此他开始了自己“对这一问题的终身迷恋”。

1948年，在纽约市立大学毕业后，戴维斯去普林斯顿跟随丘奇从事进一步的研究。他选择了一个有趣而且当时尚未被开发的领域作为自己的研究方向，这是一个可以确保有研究成果出现的稳妥做法。但在研究自己的这一课题之余，戴维斯仍念念不忘思考希尔伯特第十问题。结果，毕业时他得到了双重收获。他不仅完成了自己的选题，而且在希尔伯特第十问题研究方面也获得了可观的成果。在1950年的博士论文中，他不仅介绍了自己研究的选题，而且还特意增添了一个章节，简单叙述了自己在希尔伯特第十问题方面的研究。3年后，他发表了一篇更详细的论述。

戴维斯在研究中，一方面巧妙应用中国剩余定理处理编码问题（著名数学家哥德尔最先使用中国剩余定理处理这类问题，戴维斯改进了哥德尔的工作），得到了递归可枚举集的戴维斯范式。更重要的一方面是，戴维斯在他的研究中开辟了一条解决希尔伯特第十问题的新途径，为此戴维斯运用了一个重要的概念：丢番图集，这是一类可以通过丢番图方程生成的自然数集。我们举个例子解释一下这个概念。

设集合S表示被4除余数不为2的所有自然数，则S={1，3，4，5，7，8}，……。下面我们说明S是一个丢番图集。

显然，如果一个元素n属于集合S，则n可表示为4k，4k+1，4k+3这三种形式之一。在第一种情形下有，。在后两种情形中有：。这说明，S中的每一个数都可以表示成两个自然数的平方差形式。

反过来，如果一个数具有a2-b2的形式，那么它也一定属于S。原因在于：a2或者是4的倍数（a为偶数），或者是4的倍数加1（a为奇数）。同样的，b2也或者是4的倍数（b为偶数），或者是4的倍数加1（b为奇数）。这样a2-b2只可能具有4k，4k+1，4k+3三种形式之一，而不可能出现4k+2的形式。

把上面两点合起来，可知：集合S中的自然数，与能表示成a2-b2形式的自然数是对应的。现在，引入多项，让集合S与这一多项式联系在一起。

可以验证，一个自然数k属于S等价于丢番图方程P S（k, y1，y2）=0有解，也就是说一个自然数k属于S当且仅当丢番图方程有整数解。这意味着，集合S可以通过一个丢番图方程生成，因此它是一个丢番图集。

一般地，如果对于由自然数构成的集合S，有一个相应的整系数多项式PS（x, y1，y2，……，yn），使得正整数k属于S当且仅当丢番图方程P S（k, y1，y2，……，yn）=0有整数解，则称S为一个丢番图集。

在对丢番图集的探讨中，戴维斯发现丢番图集与递归可枚举集之间有某些类似处，于是他做出了一个大胆猜测：丢番图集与递归可枚举集是等价的。如果这一推测成立，那么一条通往证否希尔伯特第十问题的道路马上可被打通。因为在此之前，人们已经证明了，某些递归可枚举集是不可判定的。因此，由两者等价，可以直接推出某些丢番图集不可判定，即不存在一般的算法来确定一个自然数是否属于某些丢番图集，也即不存在一个算法来判定所有丢番图方程是否有解。于是，按这个思路即可完成对希尔伯特第十问题的否定解决。

这样，整个问题变成：戴维斯的大胆猜测是否成立？

戴维斯当时在一个额外的假设下，证明这个猜测是成立的。但去掉这个额外的假设是极其困难的。1957年，戴维斯结识了普特南（1926～）并开始了两人的合作。1959年，两人在引入一条不同的额外假设的前提下，证明了一条重要结论：递归可枚举集都是指数丢番图的。

两人的这一新成果后来被证明是迈向成功解决希尔伯特第十问题的重要一步。为得到这一结果，两人证明中又一次应用了中国剩余定理。特别地，他们的研究是在另一位研究希尔伯特第十问题的重要人物的基础上迈出的，因此在发表自己的论文之前，戴维斯与普特南决定先听一听这位重要人物的看法。也许会出乎许多人意料之外，这位重要人物是一位女性。她的名字叫朱丽亚·罗宾逊。

朱丽亚·罗宾逊1919年出生于美国一个普通的商人家庭。1925年上小学。但幼时的朱丽亚体弱多病。9岁时，因为猩红热她不得不被隔离了一个月。第二年，严重的风湿热又使她不得不在一家护理院休养了一年。病愈后，她跟着家教学习，一周学习3个上午。结果一年之内，她成功地掌握了五～八年级的课程。在回忆这一段时光时，朱丽亚说“我认为在那几年病床上的岁月中，我学会了顽强。我的妈妈说我是她见过的最顽强的儿童。我必须说正是我的顽强，才能让我在数学中取得成功。而顽强是所有数学家共有的特性。”也正是在这一时期，数学第一次点燃了朱丽亚的热情。而其对数学热衷的起点是2的平方根。她后来曾写道：“在我七、八年级时，我们的课本上说无论怎样写√2的小数展开式，它绝不会变成循环小数。我不明白，一个人怎么会知道这一点的——他们所能知道的一切就是算出来的部分展开式并不循环。回家后，我决定将它展开得更长一些，希望能够找到一个循环。但不久算术就打败了我，尽管我和多数数学家一样十分固执。”这次失败，使朱丽亚开始认识到数学论证的力量，因为它能让你确信，无论计算到小数点之后多少位，2的平方根的小数展开永远不会出现循环。

重返学校就读于九年级时，朱丽亚发现自己已经走到了同学的前面，而且当其他许多女孩子开始逃离数学之时，她却对数学的兴趣越来越浓厚，为数学深深着迷。1936年，高中毕业时，朱丽亚获得了学校的数学奖、生物奖、物理奖以及科学通才奖。16岁她进入圣迭戈州立学院，并选择了数学作为主修专业。因为当时的学院侧重于师资力量培养，因此罗宾逊最初只希望获得数学教师资格。然而，在数学史课上，她读到了贝尔的《数学精英》一书，由此她开始着迷于数学研究。但在这所学校，她却没有志趣相投的人。18岁时，她转到了加利福尼亚伯克利分校读高年级。在伯克利，从前羞怯的丑小鸭发觉自己竟变成了白天鹅。在这里，无论是老师还是学生，对数学都与她一样兴奋痴迷。她结识了许多数学学生和教授。其中一位教数论的教授拉菲尔·罗宾逊不仅激发了朱丽亚对数论的兴趣，后来还成了她的丈夫。当两人还在交往时，拉菲尔·罗宾逊就发现数学可以打动朱丽亚的心，于是他开始向她介绍最新的数学发展。他谈到的关于哥德尔和图灵的研究，引起了朱丽亚格外的关注。“有关数的结果竟然能通过符号逻辑得到证明，这令我十分震惊和兴奋”。

1940年，朱丽亚获得数学学士学位，并进入伯克利研究生院。1941年，她取得了数学硕士学位。同年，她还通过了公务员考试。这些使她可以有资格去做一名初级统计员。但是她决定继续深造。1941年12月，她和拉菲尔·罗宾逊结婚。因为学校不允许夫妻在同一院系任教，朱丽亚不得不去伯克利统计实验室做一名研究助手，但对数学研究的热情促使她继续旁听研究生院的数学课。1948年，朱丽亚发表了第一篇论文，这是她在统计实验室研究的成果。

1946～1947年，她丈夫到普林斯顿做访问教授，她跟随前往。在那里，她对数学逻辑产生了兴趣。1947年，她回到伯克利，在20世纪最著名的逻辑学家塔斯基（1902～1983）指导下开始博士研究。1948年，她发表了一篇有深度的论文，并由此获得博士学位。在其后几年中，她继续研究，发表了3篇关于数学逻辑方面的重要论文。1949～1950年，罗宾逊作为初级数学家在兰德公司工作。并于1951年发表《求解博弈问题的重复方法》，这篇她在博弈论方面的唯一文章也是博弈论的奠基作之一。

虽然兴趣很广泛，但在罗宾逊的数学研究生涯中，数理逻辑和数论一直是她首要的关注点。也主要是这方面的研究结果，为她赢得了众多荣誉。1976年，她入选美国国家科学院，成为第一位入选的女数学家。1982年，她被选为美国数学学会会长，成为第一位担任美国数学学会会长的女性。1983年，由于对数学作出的贡献，她被授予约翰·D和凯瑟琳·T·麦克阿瑟基金奖，成为第一位获得这一奖的女数学家。在接踵而至的荣誉面前，她写道：“事实上，我只不过是一名数学家，并不想被人看成是开创了这个或那个记录的第一位女性。我宁可作为数学家被人们记得，仅仅是因为我证明过的那些定理和解决过的那些问题。”

1985年7月30日，在和白血病进行了长期的搏斗后，朱丽亚·罗宾逊去世，享年65岁。圣迭戈高中设立了纪念她的朱丽亚·罗宾逊数学奖，奖励那些毕业班数学成绩优异的学生。她的丈夫设立了朱丽亚·罗宾逊奖学基金，奖励伯克利的数学系研究生。这些奖项鼓励和帮助那些有天赋的人在数学领域从事他们感兴趣的工作。这位天才女数学家的成功同时还激励了更多的女性走向数学研究。

罗宾逊的名字与希尔伯特第十问题是分不开的，她在数学方面最重要的成就也是与希尔伯特第十问题连在一起的。有意思的是，她与这一问题的结缘起始于一个很偶然的机会。这个问题实际上是她的导师塔斯基在一次教师的聚会上向她的丈夫提出的。由于罗宾逊对数论的热情很早就被点燃了，后来在普林斯顿又被数理逻辑所深深吸引，于是代表数理逻辑和数论两个领域完美结合的希尔伯特第十问题在极长的岁月里，牢牢吸引了她，成了她一直关注的焦点。她自1948年开始着手研究这一问题，直到1976年还发表了关于这个问题的最后一篇论文。在这期间，她为解决这个问题作出了不可替代的一系列重大贡献，在解决希尔伯特第十问题中扮演了关键角色。

与戴维斯的研究方向不同，罗宾逊选择了另外的思路着手对这一问题的探索。她所做的是为一些特殊且重要的函数构造丢番图表示。

1950年，当国际数学家大会在美国召开时，罗宾逊与戴维斯两人第一次见面了。在会议上，戴维斯报告了自己的研究结果，罗宾逊也做了10分钟报告，宣读了自己的发现。会后，戴维斯对罗宾逊说，自己看不出有什么希望能将她所列举的例子推广到一般情况。而罗宾逊则认为戴维斯无法去掉自己的困难假设。事实上，两人都认为自己行进在正确的道路上，而对方的方向是错误的。

在这次会议后，罗宾逊继续沿着自己开辟的道路前进。她敏锐地察觉到佩尔方程对冲击第十问题具有举足轻重的作用。从1952年开始，她对一类特殊的佩尔方程x2-（a2-1）y2=1进行了系统而深入的研究。利用其丰富的性质，罗宾逊在自己的道路上取得了重大进展。在1952年发表的对解决希尔伯特第十问题有重要影响的论文“代数中存在判断的可定义性”中，罗宾逊把研究范围从多项式丢番图方程扩大到求幂丢番图方程。其中她所得到的一个对希尔伯特第十问题解决具有决定性的结果是：在罗宾逊假设下，指数丢番图集（以丢番图方程所定义的集合，但其中指数可以是未知数）是丢番图集。

戴维斯与普特南在寄给罗宾逊的论文中，也研究了指数丢番图集，他们把中国剩余定理应用于戴维斯范式，并在一个数论假设下，证明了每一个递归可枚举集都是指数丢番图的。这个数论假设表述的内容是：存在任意有限长度的全由质数所组成的等差数列。这一假设现在已由格林和陶哲轩于2004年证明。但在当时却因尚未证明而只能当做一条假设。

1959年，当收到戴维斯、普特南寄来的论文草稿后，罗宾逊说自己看到这一结果“很高兴，感到惊讶，并留下了深刻印象”。然后，凭借自己深厚的数学功底，她很快发现自己可以做得更好。她指出，可以用其他途径绕过上述的数论假设，也就是说这一假设是不必要的。此外，罗宾逊还用自己的方法大大简化了戴维斯、普特南的证明，使最后的证明既通俗易懂又优雅简洁。当收到罗宾逊的证明后，轮到戴维斯、普特南“很高兴，感到惊讶，并留下深刻印象”了。

1961年，三人合作的成果《指数丢番图方程的判定问题》发表在《数学年刊》上。在这篇标志着希尔伯特第十问题得到重大进展的论文中，他们证明了：每一个递归可枚举集都是指数丢番图的。

与罗宾逊早先关于指数丢番图的工作相结合，我们可以得到一个解决希尔伯特第十问题的逻辑链条：每一个递归可枚举集都是指数丢番图的；指数丢番图集就是丢番图集。于是每一个递归可枚举集是丢番图集，而反过来，丢番图集都是递归可枚举集是容易证明的。这样，戴维斯的大胆假设（递归可枚举集与丢番图集等价）成立。而在此之前，人们已经发现某些递归可枚举集是不可判定的，因此某些不定方程也是不可判定的，即对任意丢番图方程不存在一般算法判定其是否有解。由此，希尔伯特第十问题在否定意义上可以得到完全解决。

然而，还不到欢庆的时候。因为在这一美妙的逻辑链条中还有缺失的一环：罗宾逊所证明的“指数丢番图集就是丢番图集”依赖于一个假设。这一著名假设现在称为罗宾逊假设。简单而言它是说，存在一个满足如下两个性质的丢番图方程G（u, v，z1，……，zn）=0。

在这个方程的任一个解中皆有v≤uu；对任何k都存在满足v>uk的解。

满足罗宾逊假设的这种方程称作有指数增长性。于是到1961年为止，沿着这几个美国人的思路，所有的工作就是寻找一个有指数增长性的丢番图方程。对于他们构建的数学墙而言，整个理论完全依赖于是否能够证明其中一块砖头的存在。如果它存在，第十问题就可画上一个圆满的句号，但如果事实证明不存在这样的方程，那么他们耗费这么长时间建造起来的数学之墙将在瞬间崩塌。

在随后的几年，戴维斯、罗宾逊等人一直寻找缺失的最后一环——寻找一个满足罗宾逊条件的丢番图方程。然而，看上去找到一个这样的方程是非常困难的。一年一年过去了，没有新的大进展。一种普遍的看法是，它不大可能存在。几年后，甚至罗宾逊也开始对自己的假设变得相当悲观，以至于在一个短暂的时期，她实际上是朝着希尔伯特第十问题可解的方向工作。许多数学家也怀疑这一思路并不是攻克希尔伯特第十问题的正确道路，他们认为沿着这一方向行进只会被引入歧途。

在那个时候，戴维斯常常被人问到这一问题。他回答说：“我认为朱丽亚的假设是正确的，而且它将被一位聪明的俄罗斯年轻人所证明。”

戴维斯是如此走运。1970年，一位聪明的俄罗斯年轻人马蒂亚塞维奇登上数学舞台，在解决希尔伯特第十问题的道路上迈出了最后一步，戴维斯的预言丝毫不差地实现了。

马蒂亚塞维奇，1947年出生在俄罗斯的圣彼得堡（即前苏联的列宁格勒），12岁时父亲不幸去世，家境贫寒。但凭借优异的数学成绩，马蒂亚塞维奇在数学竞赛体系中脱颖而出。1964年，在莫斯科举行的国际数学奥林匹克竞赛中他获得金奖。也因此，他跳过高中最后一年的学习，免试进入列宁格勒国立大学数学与力学系就读。1965年，作为大学二年级学生的马蒂亚塞维奇得到了关于波斯特典范系统的一批成果，并参加了当年在莫斯科举行的国际数学家大会。也是在这一年，希尔伯特第十问题进入了他的视野。当他去问自己的导师马斯洛夫（1939～1982），自己下一步该做些什么时，马斯洛夫回答说：“尝试证明丢番图方程不存在一般算法。这个问题也被称为希尔伯特第十问题，但你不必理会这个”。马蒂亚塞维奇说他对研究这类不可解问题没有经验，马斯洛夫回答说不可解问题没什么大不了的，无非就是把它约化成一个已知是不可解的其他问题。当马蒂亚塞维奇询问应该先阅读些什么资料时，马斯洛夫告诉他，几个美国数学家在这方面写过几篇论文，但也不必太理会那些研究，因为“到目前为止美国人没有成功，所以他们的方法很可能是不充足的”。马斯洛夫并不是唯一低估几个美国人关于希尔伯特第十问题工作的人。事实上，由于多年来没有新的重要进展，当时许多人已对由戴维斯、普特南、罗宾逊开辟的道路持怀疑态度。

接受导师的建议，马蒂亚塞维奇开始卷入到希尔伯特第十问题中。但由于导师的影响，马蒂亚塞维奇最初几年是在一条后来证明根本不可能结出果实的道路上白费工夫。直到1968年，在经过长时间的徒劳无功之后，他开始阅读起“几个美国人”的那些工作来。这使他了解了戴维斯、普特南、罗宾逊所开辟的研究途径。于是，马蒂亚塞维奇决定组织一次关于希尔伯特第十问题的研讨会。然而他发现，其他数学家对此并没有这么大的兴趣：“在我概述已知结果的首次会议上，只有5位逻辑学家和5位数论家参加，接着，与会人数按指数减少，不久就剩下我自己一个人了。”

此后一段时间，马蒂亚塞维奇自己仍然坚持在这一问题上投入大量的精力。他花费几乎所有空闲，试图找到满足罗宾逊假设的丢番图方程。然而，时间一天天过去了，他依然没有获得实质性进展，倒是作为“研究希尔伯特第十问题的本科生”的名声传遍了校园。一位教授开始嘲笑他。每一次见面，他会问：“你已经证明了希尔伯特第十问题无解？还没有？这样，你将无法从大学毕业！”

马蒂亚塞维奇当然没有沦落到如此悲惨的境地。1969年，他顺利毕业了，但因为没有做出更出色的结果，他的论文是他所做的关于波斯特典范系统的早期研究。同年，他成为列宁格勒部的斯捷克洛夫数学研究所的研究生。但他所研究的题目不再是希尔伯特第十问题了。

1969年秋的一天，他的一位同事对他说：“快到图书馆去。在美国数学学会学报最新一期上有朱丽叶·罗宾逊的新论文！”但马蒂亚塞维奇当时已经决定把希尔伯特第十问题搁置一边了，“朱丽亚继续研究这个问题，这很不错。但我不打算再在这个问题上浪费时间了。”所以他没有急着去图书馆。

事情接下来的发展变得极富戏剧性，用马蒂亚塞维奇自己的话说：“在数学天堂的某个角落里必定存在着一位数学之神（或女神），不想让我错过罗宾逊夫人的新论文”。由于他此前对希尔伯特第十问题的研究，他已被视为这方面的专家。结果，苏联的一份数学评论杂志把罗宾逊夫人的论文寄给了他，让他加以评论。就这样，马蒂亚塞维奇并非情愿地读到了罗宾逊的论文。然而，这一读之下，希尔伯特第十问题就重新俘获了他。

罗宾逊新奇和美妙的想法，涉及的仍是特殊类型的佩尔方程x2-（a2-1）y2=1，在论文中罗宾逊探讨了这一方程的一些新性质。这使马蒂亚塞维奇马上联想到自己在1966年开始研究第十问题时所使用的一个著名数列：斐波那契数列。

斐波那契数列以数学家斐波那契命名。斐波那契（约1170～1250），中世纪欧洲最卓越的数学家。他既在欧洲数学的复兴中起到先锋作用，又在东西方数学的交流中起到了桥梁作用。16世纪意大利数学家卡尔丹评价他说：“我们可以假定，所有我们掌握的希腊以外的数学知识都是由于斐波那契的出现而得到的。”斐波那契之所以取得如此高的成就，重要原因之一是他如饥似渴地汲取外来的文化。

斐波那契出生于意大利的商业城市比萨，现在那里还有他的一座雕像。他的父亲曾作为比萨共和国的官员于1192年左右被派往布日伊（今属阿尔及利亚）管理比萨的商业侨民。斐波那契早年受过良好的教育，约22岁时随父亲到布日伊，在那里学会了用当时的阿拉伯数码进行计算。后来又随父亲到过埃及、叙利亚、希腊等多个国家。在旅行中他广泛接触和认真研究，熟练掌握了多种计算技巧。大约在1200年，斐波那契回到比萨。此后的25年，他潜心写作，完成多本数学著作。在第一编第二章中，我们曾简单提到过他在求三次方程数值解方面的工作。但其最主要的成就是在数论和不定方程方面。这方面的研究主要记载在他的一部重要著作《平方数书》中。其书中涉及的不定分析和数论成果远远超过了前人，成为此后400多年间数论中最领先的作品。这书奠定了斐波那契作为数论家的地位，使他成为介于丢番图和费马之间最有影响的数论家。

斐波那契最有影响的著作却是回国后不久即完成出版的名著《算盘书》（1202年初版）。在这本中世纪欧洲最重要的数学著作中，他向欧洲介绍了印度—阿拉伯数码。这对于改变欧洲数学的面貌起了极为重要的作用。这书留给数学的另一宝贵遗产则是斐波那契数列。

在1228年出的这一传世之作的修订版中，斐波那契提出了以下饶有趣味的兔子问题：某人有一对兔子饲养在围墙中，如果它们每个月生一对兔子，且新生的兔子在第二个月后也是每个月生一对兔子，问一年后围墙中共有多少对兔子。

逐月推算，我们可以得到数列：1，1，2，3，5，8，13，21，34，55，89，144，233。这个数列产生的规则很简单，即开头两个数1以后的每个数都是由它前面两个数相加而得，因此它可用递推式表示为：F1=1，F2=1，Fn=Fn-1+Fn-2（n≥3）。

1876年，法国数学家卢卡斯出版了一部四卷本的有关娱乐数学方面的著作，把斐波那契的名字加到问题的解答和所出现的数列上面。从此，这一数列就正式命名为斐波那契数列。数列中的每一项，则称为“斐波那契数”。

斐波那契数列自提出后，在后来的岁月中，似乎和题中的高产兔子一样，引发了为数众多的数学论文和介绍文章。使其成为数学中著名且有趣的数列的一方面原因在于，斐波那契数（列）出现在自然界各种各样的场合，特别是植物学领域。事实上，在植物的花、枝条、叶、种子等形态特征中都可发现使人感兴趣的斐波那契数（列）的迷人踪迹。

另一方面原因则在于，斐波那契数列具有极其多的性质，其中一些非常奇妙。

1730年，英国数学家棣莫弗（1667～1754）在其名著《分析杂论》中给出斐波那契数列的通项公式。1843年，这一公式最早由法国数学家比内（1786～1856）证明，因此这一结果又被命名为“比内公式”。这一公式令人惊奇的一点是，所有斐波那契数都是整数，但它们却可以通过无理数的幂表示出来。

斐波那契数列有一个重要性质与黄金分割有关。考察斐波那契数列中相邻两项的比，会发现，前一项与其相邻的后一项的比值越来越接近著名的黄金数！事实上，。因为斐波那契数列与黄金数间具有这一分不开的联系，所以只要斐波那契数列出现之处，黄金数也就会自动地出现。

再举几个有趣的斐波那契数的性质，其中后两个性质被马蒂亚塞维奇在证明中所使用。

，有些悖论如“魔术师的剪刀”悖论的构造即依赖了斐波那契数列的这一性质。

1953年，有人发现，，这里89是斐波那契数列中第11项，且为一素数。这个结果是十分意外的。数学家认为这是这一数列古怪的性质之一。

比利时医生、业余初等数论家爱德华·齐肯多夫（1901～1983）在1939年得出著名的齐肯多夫定理：任何正整数都可以用唯一方法表示成若干个不连续的斐波那契数之和。这种和式称为齐肯多夫表述法。比如说，对数30，它有几种方法表示成斐波那契数之和：30=21+8+1=21+5+3+1=13+8+5+3+1=13+8+5+2+1+1。但这些表示中有且只有一种表示30=21+8+1，其中没有使用连续斐波那契数。而这一表示就是数30的齐肯多夫表述法。在1939年发表的文章中，齐肯多夫证明了这对任何一个正整数都是成立的。

1969年，一位前苏联数学家在自己一本书的修订版中首次公开发表斐波那契数列的一个性质：若，则Fn｜m。这一关于斐波那契数的美丽性质一旦被发现不难证明，但奇怪的是，它被发现得如此迟。

可以说，斐波那契数列的性质，难以计数，而且还在增加。1963年，有一群斐波那契数列迷们，在小霍加特医生的倡导下，建立了国际性的斐波那契学会，并开始出版杂志《斐波那契季刊》，专门介绍有关这个数列的研究。杂志的前三年发表了这个特殊研究领域的近1000页成果。1968年，为了处理大量积压的稿件，杂志又发行了三期增刊。

斐波那契数列具有的各种性质还使它成为解决一些数学问题的有用工具。比如，19世纪中叶法国数学家拉梅（1795～1870）用斐波那契数列证明：在应用辗转相除法求两个数的最大公约数时，所用步数不大于较小数位数的5倍。令人深感意外的是，在解决希尔伯特第十问题的过程中，这一数列又发挥了决定性作用。

马蒂亚塞维奇在1966年开始研究希尔伯特第十问题时，曾得到一些有关斐波那契数列的研究结果。在看到罗宾逊的论文后，他马上意识到罗宾逊研究中涉及的佩尔方程的一个性质与自己曾探讨过的斐波那契数列的一个结果非常相像。

前景看上去很乐观，马蒂亚塞维奇重新投入到希尔伯特第十问题的研究上。在随后的日子里，马蒂亚塞维奇一直沿着这一新方向思索。对此的沉迷，使他在得出结果之前先书写了一出心不在焉的数学家故事：1970年除夕夜的派对上，由于过于出神，他在离开舅舅家时竟然错穿了舅舅的衣服。

全心的投入这次开始结出果实。1970年1月3日上午，他相信自己已经成功。但这天结束的时候他却发现自己的想法有一个漏洞。不过，在第二天早上，漏洞就被补上了。此前，马蒂亚塞维奇曾有过一次尴尬的经历。他声称自己证明了希尔伯特第十问题不可解，但在演讲中却发现了一个错误。这次，他不想再次体验这种尴尬，于是他把完成的论文交给了马斯洛夫及另一位数学家请他们检查，没有再对任何其他人谈这件事。在等待判决的时间里，他离开列宁格勒，携未婚妻去滑雪度假。两个星期后当他回到学校时，他兴奋地看到他的论文经受住了以眼光犀利著称的两位数学家的检验，他的证明是正确的也不再是秘密，他成为希尔伯特第十问题的解决者。

1970年1月29日，马蒂亚塞维奇做了有关他研究成果的第一次公开演讲。演讲后，一位听众得到他的允可，复制了他证明的手稿并带到不久之后在西伯利亚举行的一次数学会议上，而会议的出席者中恰好有一位是罗宾逊夫人的同事。2月15日，罗宾逊夫人接到了同事的电话，告知了她这一消息。

1970年2月，马蒂亚塞维奇的著名论文“可枚举集是丢番图的”发表在科学院院报上。论文中，他利用斐波那契数列的一系列性质，用初等方法完成了一个重要的定理：一个集合是递归可枚举的当且仅当它是丢番图的。其关键之处就是找到了一个满足罗宾逊假设的丢番图方程。他证明了“偶角标斐波那契函数是丢番图的”，即若F（2x）是第2x个斐波那契数，则y=F（2x）是丢番图的，而且容易证明F（2x）满足罗宾逊假设。这样，马蒂亚塞维奇构造的例子对罗宾逊假设提出了必要的存在性定义。最后的砖头找到了。希尔伯特所期望的一般算法是不存在的。

随着论文的发表，马蒂亚塞维奇解决希尔伯特第十问题的消息很快传遍了数学界。此时，马蒂亚塞维奇还不满23岁，正是一位“聪明的俄国年轻人”。

这位年轻人的工作令戴维斯非常兴奋，在自己的经典著作《可计算性与不可解性》的平装本序言中他写道：“我一生最大的快乐之一是一九七零年二月读到马蒂亚塞维奇的工作”。几个月后，在国际数学家大会上，戴维斯告诉马蒂亚塞维奇，自己曾一直预言他的出现。

回顾马蒂亚塞维奇的成功，人们意识到，事实上，罗宾逊曾离完成希尔伯特第十问题无解证明相当近。问题是，她为什么没有做到这一点呢？马蒂亚塞维奇认为，关键原因可能在于，在自己的证明中使用了斐波那契数列的一个性质“若，则Fn｜m”。一位苏联数学家在1942年就已发现这一性质，但直到1969年他才在自己出版的一本介绍斐波那契数列的畅销书的第三版中正式公开了这一结果。

由于前期的工作，马蒂亚塞维奇已经认识到斐波那契数列对解决希尔伯特第十问题的重要性。因此当1969年夏天看到这本书时，他马上带着浓厚的兴趣读了此书，并对这一结果留下了深刻的印象。当他看到罗宾逊的论文时，他立即意识到它可能是非常有用的，事实也是如此，为了完成自己的证明，马蒂亚塞维奇使用了斐波那契数列的这一结果。马蒂亚塞维奇由此推测说：如果这一结论更早被发表并被罗宾逊看到，那么希尔伯特第十问题有可能在他之前很早就解决了。

多年致力于希尔伯特第十问题的研究，而且曾经那么的接近答案，却还是失之交臂，但罗宾逊却没有觉得遗憾，对她而言，对数学真理的欣赏远远超越了任何个人的荣誉。当问题最终解决时，罗宾逊对希尔伯特第十问题在自己一生中的重要性做了十分感人的叙述：

在整个20世纪60年代，除了发表几篇其他方面的论文外，我一直在研究第十问题，但我感到十分失望。我们家有个习俗，每逢谁过生日，都要有一个聚会。年复一年，当轮到我吹灭生日蛋糕上的蜡烛时，我总是许愿，第十问题会被解决——不是说我解决它，而只是说它会被解决。我觉得，如果不知道它的答案，我会死不瞑目的。

1970年1月4日，马蒂亚塞维奇在他23岁生日前的两个月，终于成功地给出证明……希尔伯特第十问题的这个人们期待已久的答案，结果是否定的。我听到这个消息时十分兴奋，很想立即打电话到列宁格勒，核实证明是否真的是正确的……在我第一次听到这个消息之后一个星期，我写信给马蒂亚塞维奇：“……现在，我知道它是正确的，它是漂亮的，它是精彩的。如果你真的是22岁，那么我感到特别高兴的是，当我初次作出这个猜想时，你还只是个婴儿，我只得等你长大成人！”那年，当我吹生日蛋糕上的蜡烛时，吹了半口气便停住了，我突然意识到，我许了这么多年的愿已经变成现实了。

年轻的马蒂亚塞维奇同样对罗宾逊表达了深深的敬意。问题圆满解决后，两人还为证明的归属产生了争论，只不过并不为了自己的名誉——他们都坚称是对方做出了最关键的一步。后来，两人结下了深厚的友谊，并进行了卓有成效的合作。

回顾希尔伯特第十问题由提出到解决的漫长历程，可以确定地说它的解决是集体智慧的结晶。从希尔伯特1900年提出这一问题后，70年中有许多数学家都为此作出了贡献。美国数学家戴维斯、普特南、罗宾逊作了突出的贡献，罗宾逊的成果距最后的证明极为接近，而且她的工作对马蒂亚塞维奇有至关重要的影响，为他提供了坚实的基础并且触动了他的灵感。而最终的一步由马蒂亚塞维奇完成，他找到了拼图的最后一块，从而完成了整个证明。事实上，戴维斯、普特南、罗宾逊、马蒂亚塞维奇在解决希尔伯特第十问题上所做的工作，已经都获得了数学界的广泛承认，并被一起列为“荣誉阶级”数学家成员。

（照片摄于1982年底，图中自左至右依次为戴维斯、罗宾逊、马蒂亚塞维奇）

“数学家应该是这样一个团体，不分地域、种族、信仰、性别、年龄甚至时代，将自己的一切奉献给艺术和科学中最美丽的部分——数学。”

让我们引用罗宾逊的这句话作为全书之结语吧。