第18章

长眠的丢番图

图灵和邱奇证明了，不存在通用的过程来判定任一命题在一阶谓词逻辑系统是否可证。然而，这之后很久，最初的判定性问题依然没有解决。这就是著名的希尔伯特第10问题，它是大卫·希尔伯特于1900年在巴黎国际数学大会的演讲中提出的20世纪数学家面临的最重要数学问题中的一个：

10．丢番图方程可解性的判定。

给定一个包含任意个未知数的有理整系数不定方程，试推导一个过程，通过有限步运算判定该方程是否存在有理整数解。^［1］

公元3世纪，亚历山大数学家丢番图在他的《算术》中所提到的代数问题，都可以用一些整系数多变量多项式来描述。希尔伯特的第10问题就是要求一个通用过程来判定某个特定的丢番图方程是否有整数解。

诚然，在哥德尔的不完备性定理以及邱奇和图灵的不可判定结果诞生以后，很少有数学家还期望有人能达成希尔伯特的愿望，“设计一个过程”来判定丢番图方程的可解性。很多人其实期望的是一种相反的结果：不可能有这种通用过程的证明。

很多数学家深深着迷于希尔伯特的第10问题，其中有一个人，她将自己整个职业生涯都投入到了追寻第10问题不可解的证明中。这个人就是朱莉亚·罗宾逊。

朱莉亚·罗宾逊最早的记忆，是她在亚利桑那州家附近的巨型仙人掌边摆弄鹅卵石。

我想我天生就喜欢研究自然数。对我来说，它们就是实实在在的事物。我们可以想象与我们现在迥然不同的化学或生物学科，但是无法想象另一个跟现在不同的数字数学。在任一宇宙中，数字的定理都是通用的。^［2］

朱莉亚·罗宾逊于1919年出生在圣路易斯州，原名朱莉亚·鲍曼。她有一个大她2岁的姐姐康斯坦斯。当朱莉亚·罗宾逊2岁的时候，她的妈妈去世了，她们搬到了凤凰城附近的祖母家里，后来又搬到了圣迭戈湾附近的洛马岬，与父亲及继母一起住。

朱莉亚9岁的时候，得了猩红热，然后又是风湿热，因此休学了2年。为了帮她赶上学业进度，父母聘请了家教，让朱莉亚在一年内补习了从5年级到8年级的功课。

有一天她告诉我，无法将2的平方根计算到小数点后的某一位起开始循环。她知道，这已是证明过的，虽然她不知道是如何证明的。我不明白这是怎么证明的，所以回到家，利用新学到的一些开平方的技巧试图自己证明它，但是到那天下午最终放弃了。^［3］

1933年，朱莉亚进入了圣迭戈高中。这一年，大批的数学家开始陆续逃离哥廷根和其他德国高等学府。朱莉亚童年时的疾病让她变得害羞、安静、自卑，但也造就了她独自工作时的耐心和坚毅。

上到高年级的时候，她成了班上唯一既选修物理又选修数学的女生，而且这些科目她都能获得好成绩。她收到的高中毕业礼物是一把计算尺。1936年秋，未满17岁的朱莉亚去了圣迭戈大学（现更名为圣迭戈州立大学），主修数学。那时，她的学费是每学期12美元。朱莉亚希望自己将来成为一名教师，“那时我没想过要当数学家（数学家毕竟和数学教师完全不同）”。^［4］

1937年，Simon & Schuster公司出版了一本非常有名的书《数学精英》（Men of Mathematics），作者是数学家E. T. 贝尔（1883—1960）。读了这本书，朱莉亚才知道数学家是什么，他们真正做的是什么。虽然这本书在历史和人物个性方面有虚构的成分，但是给了朱莉亚从未有过的鼓舞，就像此后它给其他很多同样处于豆蔻年华的数学家带来的一样。

1939年，朱莉亚离开了圣迭戈州立大学，去了加州大学伯克利分校。当时伯克利正在筹建一个强大的数学系。在第一学年，她的数论老师是拉斐尔·罗宾逊，仅大她8岁。“第二学期，我们仅有4名学生，同样，我是唯一的女生。拉斐尔让我陪他散步……在一次清晨散步的路上，他向我介绍了哥德尔的研究成果。”^［5］

也许他们还谈论了很多其他理论。1941年，拉斐尔·罗宾逊和朱莉亚·鲍曼结婚了。由于有避免裙带关系的规定，因而朱莉亚不能在伯克利的数学系任教，虽然她已经在统计系得到了助教一职。（当她申请这份工作时，人事部门问她每天都做什么。她写道：“星期一——证明命题，星期二——证明命题，星期三——证明命题，星期四——证明命题，星期五——命题是错的。”^［6］

虽然拉斐尔和朱莉亚都想要个孩子，但是朱莉亚的童年疾病让她的内心变得十分脆弱。她有过一次流产，医生强烈建议她打消要孩子的念头。^［7］

在1946～1947这一学年，拉斐尔以访问学者身份去了普林斯顿大学。他和朱莉亚上了由邱奇主讲的课程，还在纪念普林斯顿大学二百周年期间听了哥德尔关于数学基础的课。

回到伯克利后，朱莉亚在著名的波兰裔犹太逻辑学家阿尔弗雷德·塔斯基（1902—1983）指导下攻读博士，并在1948年拿到了博士学位。就是在那时，她的博士论文揭示了“她的主要学术兴趣在逻辑学和数论交织的领域”。^［8］

1948年，塔斯基让她研究一个问题，这个问题牵涉到另一个问题，而这就是决定了她作为数学家的职业生涯的希尔伯特第10问题。

就像大多数数学家一样，朱莉亚并没指望第10问题存在令希尔伯特满意的解。在第一篇关于丢番图方程的论文^［9］中，她写道：

鉴于针对很多经典的带一个未知数的丢番图方程，还没有有效的方法判定其对于任意参数值的可解性，因而很可能不存在一个判定过程。例如，还没有方法判定以下丢番图方程是否可解：

x² + ay² = s², x ² – ay² = t²,

（早在中世纪，阿拉伯人就研究过这个丢番图方程。）

一些数学家倾向于迂回解决丢番图方程。他们定义了丢番图集合，集合包含了某一特定丢番图方程的所有解。例如，在下面的丢番图方程中，所有偶数的集合就是该方程所有整数解x的集合：

x – 2y = 0

这个方程有2个变量，但是丢番图集合只由x的取值构成。如果x和y都是整数，那么x一定是偶数。

对于含有多变量的丢番图方程，可以定义一个丢番图关系（Diophantine relation）。例如，假设你想表达x比y小这一关系，满足这个关系的x和y的取值就是下面丢番图方程的解：

x – y + z + 1 = 0

朱莉亚的论文并没有证明这些集合与关系就是所谓的丢番图集合与丢番图关系，但她指出这些集合和关系可以用指数来定义，也就是x^y，其中x和y都是变量。

将指数引入丢番图方程的讨论中一开始看上去并不相关。丢番图方程中不允许指数出现。丢番图方程可以包含变量的整数次幂，但是不能包含变量的变量次幂。

不过，这篇论文指出指数是一个很重要的关系，因为二项式系数、阶乘函数和素数集合都可以用指数来定义。指数关系有没有可能就是丢番图关系，因为它可以定义为丢番图关系？答案并不肯定，但是朱莉亚的论文还证明了，指数可以用任何一个有着近似指数级增长的丢番图关系来定义。虽然目前还未发现这样的丢番图关系，但她说“非常有可能”^［10］存在这样的丢番图关系。

严格来说，费马的最后定理（也称费马大定理）并不是一个丢番图方程：

xⁿ + yⁿ = zⁿ

费马定理声称这个方程在n大于2时没有整数解，也就是说，n在这里被视为变量。将n替换成任意一个大于2的整数，这个方程就变成了一个丢番图方程。如果指数关系确实是一种丢番图关系，那么费马的这个方程就成为一个标准的丢番图方程，虽然它比一般形式更为复杂。

朱莉亚的论文发表在1950年的国际数学家大会上。那届大会在哈佛召开，也是在那里，朱莉亚第一次遇见了马丁·戴维斯。

马丁·戴维斯早在纽约城市学院读本科的时候，就为希尔伯特的第10问题所着迷。纽约城市学院数学系的教授埃米尔·波斯特写过一句话，大意是第10问题“正乞求人们证明它是不可解的”。^［11］

戴维斯在普林斯顿读研究生的时候，发现自己“完全没办法不想希尔伯特的第10问题，我认为，对于这个如此困难的问题我几乎不可能看到出路，我试着将自己的注意力从它身上移开，却发现做不到”，虽然戴维斯的博士论文确实涉及了这个主题。

马丁·戴维斯参加国际数学大会时刚刚拿到博士学位。朱莉亚还记得马丁·戴维斯当时对她论文的反应有点让人费解：“我记得他说过，他并不觉得我的论文对解决希尔伯特问题有什么帮助，因为论文里只是一系列的例子。我说，好吧，我已经尽力了。”^［12］戴维斯后来承认：“我确实跟她说过我怀疑她的做法偏离了目标，这是我一生中说过的最愚蠢的话之一。”^［13］

朱莉亚和她的姐姐康斯坦斯自从长大后就很少在一起，但在1950年，康斯坦斯嫁给了内尔·雷德，旧金山大学的法律系学生。从此她们住得很近并经常来往，关系变得非常密切。在罗宾逊夫妇的鼓励下，康斯坦斯写了她的第一本书《从0到无穷》（From Zero to Infinity，1955）。在她们姐妹去了哥廷根“朝圣”后，康斯坦斯又写了一本关于希尔伯特的传记（1970）。我在本书的第3章中大量参考了这本传记。康斯坦斯随后又写了几本传记，她笔下的人物有理查德·柯朗（1976）、奈曼（1982）、 E. T. 贝尔（1993）。后来，她专门写了一本书献给妹妹：《朱莉亚：数学人生》（Julia: A Life in Mathematics，1996）。

在1958年、1959年和1960年的夏天，马丁·戴维斯与希拉里·普特南（1926—）一起共事。普特南更为人们熟知的身份是哲学家，但是他在数学和哲学方面的造诣都很深。1959年夏，他们开始将朱莉亚的方法引入到工作中。最后，他们寄给朱莉亚一份其论文的草稿。朱莉亚改进了其中的一部分，三个人联名完成了这份新的论文“指数丢番图方程的判定问题”（The Decision Problem for Exponential Diophantine Equations），并于 1961年发表。^［14］

就如论文标题，这篇论文是关于指数丢番图方程的，即丢番图方程的一种变形，它允许指数以几种形式出现：变量的变量次幂，常数的变量次幂，变量的常数次幂（也就是一般的丢番图方程）。戴维斯戴普特南普朱莉亚合作的这篇论文，在第二句话提到：证明的结果是“并没有一般的算法来判定指数丢番图方程是否有正整数解”。

现在，离否定希尔伯特第10问题仅一步之遥，这关键的一步就是戴维斯称之的“朱莉亚·罗宾逊假定”。^［15］这个假定是说存在近似指数级增长的丢番图关系，这也蕴涵了指数关系本身就是丢番图关系，也就是说，指数丢番图方程可以表示为一般的丢番图方程。

20世纪60年代，朱莉亚一直是伯克利的讲师，讲授数学（其中一个学期讲授的是哲学），偶尔从事和发表一些希尔伯特第10问题的研究。在1969年的《数论的研究现状》（Studies in Number Theory）中，她写了40页篇幅的一章来总结当时数论研究的进展，这章提出了一个最为重要的难题：

关系 r = S^t 是丢番图关系吗？如果是，所有的指数丢番图方程都可以替换成等价的有更多变量的丢番图方程。另外，所有的递归可枚举关系也都是丢番图关系，因此希尔伯特的第10问题不可判定。目前为止，我们依然不知道是不是这样。^［16］

20世纪60年代，戴维斯在雷舍利尔理工学院和纽约大学授课，经常有机会讲授希尔伯特的第10问题。如果有人请他预测这个问题的可解性或不可解性，他就会像希伯来圣经里的先知那样，说出早已准备好的回答：“我认为朱莉亚·罗宾逊假定是成立的，而且它会被一个聪明的年轻俄国人证明。”^［17］

尤里·马蒂亚塞维奇于1947年出生在俄罗斯的圣彼得堡（即前苏联的列宁格勒），他高中时候的学校很注意学生数学和科学素质的培养。马蒂亚塞维奇17岁的时候进入国立列宁格勒大学学习，1966年就在莫斯科进行的国际数学家大会上发表过演讲。1970年，他从斯捷克洛夫数学研究所列宁格勒分部（也就是著名的LOMI）取到了博士学位。

马蒂亚塞维奇第一次听说希尔伯特第10问题是在1965年，当时他在国立列宁格勒大学读本科二年级。他的导师马斯洛夫（1939—1981）轻描淡写地告诉他：“试着去证明丢番图方程的不可解性。这个问题也叫做希尔伯特第10问题，但你不必理会这些。”他还向马蒂亚塞维奇推荐了一种研究方法：“现在，不可解证明的通常途径是，将需要证明的问题规约到已知证明的其他不可解的问题上。”马斯洛夫不推荐马蒂亚塞维奇看关于希尔伯特第10问题的相关研究文献，他说：“关于这个问题，现在只有几个美国数学家发表了一些研究成果，你不需要看……美国人至今还没证明这个问题，所以他们的方法很可能不恰当。”^［18］

几年里，马蒂亚塞维奇尝试了一些不同的方法解决希尔伯特第10问题，但都陷入了死胡同。他对这个世界难题的痴迷逐渐传遍了国立列宁格勒大学的校园。一位教授嘲笑他：“你证明了希尔伯特第10问题不可解了吗？还没有？那么你将无法从这里毕业！”^［19］马蒂亚塞维奇最后决定读一读美国人的论文，这其中包括了最重要的1961年戴维斯年普特南普朱莉亚合著的论文。

1970年新年刚过，马蒂亚塞维奇找到了一个与斐波那契数有关的满足朱莉亚·罗宾逊假设的丢番图关系。他当年只有22岁。他在1月底做了关于希尔伯特第10问题不可判定的第一次公开报告，很快传遍了世界。朱莉亚·罗宾逊写信给他：“让我特别高兴的是，如果你真的才22岁，那当我最初提出那个猜想的时侯，你还是个孩子，而我不得不等你长大! “^［20］

朱莉亚和拉斐尔·罗宾逊于1971年前往列宁格勒，拜访了马蒂亚塞维奇夫妇。在接下来的几年间，他们通过邮件在丢番图方程的问题上又合作出了几篇文章。

马丁·戴维斯在《科学美国》杂志^［21］上就希尔伯特第10问题写了一篇脍炙人口的文章。1982年，多佛出版社再版经典著作《可计算性和不可判定性》时，他又写了一篇更有技术性的文章作为这本书的附录二。1974年5月，美国数学学会在北伊利诺伊斯大学举行了一场纯数学的座谈会，这次会议专注于希尔伯特问题。戴维斯、马蒂亚塞维奇和朱莉亚共同呈现了一篇文章：”丢番图方程：负面解的积极因素“（Diophantine Equations: Positive Aspects of a Negative Solution）^［22］，在其中探讨了从丢番图方程不可解的证明中推导出来的几个有用结论。

由于在解决希尔伯特第10问题中起到的杰出作用，朱莉亚·罗宾逊广为人知。1976年，她终于在伯克利晋升为正教授，并成为美国科学院第一位女性数学家。1982年，她成为美国数学学会第一位女主席。她还被《家庭妇女期刊》（Ladies Home Journal）列入百位美国最杰出女性的名单。^［23］

1983年，朱莉亚·罗宾逊被授予麦克阿瑟奖（也称为“天才奖”）。她匿名捐赠了部分奖金，用来支持牛津出版社出版《哥德尔文集》。这本书现在是每一个研究数学逻辑和可计算性的学者必参考的一本图书。

1984年，朱莉亚·罗宾逊被诊断出患有白血病。她于次年逝世，享年65岁。她的丈夫拉斐尔·罗宾逊在1995年去世，享年83岁。

马蒂亚塞维奇现在已是花甲之年。本书出版时，马丁·戴维斯也有80岁了。他们两个人现在仍然活跃在数学界。

1993年，马蒂亚塞维奇写了《希尔伯特的第10问题》（Hilbert’s Tenth Problem），很快被麻省理工出版社译为英文出版。虽然希尔伯特第10问题不可解的证明占据了这本书的前一百页，但马蒂亚塞维奇重写了证明，而这个重写后的证明自成体系，几乎无需引用任何之前的研究。

《希尔伯特的第10问题》的第5章提到了图灵机。作为计算机时代的产物，马蒂亚塞维奇用现代编程语言的专业术语描述他的机器的工作原理，并阐述了它们和程序设计语句的关系。他证明了“图灵机不能判定某一类丢番图方程是否有解，更不要说任意丢番图方程了”。^［24］

那个古老的谜语告诉我们：丢番图的童年占一生的六分之一；过了十二分之一，两颊长须；又过了七分之一，找到了终生伴侣；五年之后，婚姻之神赐给他一个儿子，可儿子享年仅是其父的一半就进入了冰冷的坟墓；悲伤只有靠研究数学问题去消解，又过四年，他也走完了人生的旅途。

17个世纪后，阿兰·图灵在与丢番图儿子相似的年纪，溘然长逝。后人借助他用无与伦比的想象力创造出来的翅膀才得以继续探索人类智慧的潜力和局限，并追求人类智慧在逻辑和数学上的意义。

丢番图和图灵死后都留下了谜题。就像人类的动机一样，一些丢番图方程有解，一些没有，而许多其他事情，我们永远都不知道。