|
站长在 Bluesky 新开了微博帐号
▷▷▷ 敬请关注 ◁◁◁
手机版
Hilbert 第十问题漫谈 (下)
- 卢昌海 -
上一篇 | 返回目录
3. 丢番图集
戴维斯的父母也是从波兰移民来美国的， 戴维斯本人则出生在纽约。 1944-1948 年间，
戴维斯在纽约市立大学学习， 波斯特对希尔伯特第十问题 “期待一个不可解性证明” 的看法用戴维斯本人的话说是开始了他
“对这一问题的终身迷恋”。 从纽约市立大学毕业后， 戴维斯来到了美国逻辑学的中心普林斯顿，
跟随丘奇从事进一步的研究。 戴维斯在普林斯顿研究的是一个冷门课题——别小看这种课题， 对研究生来说，
研究那样的课题往往最容易出成果， 且不容易被别人抢先或与人 “撞车”。 但戴维斯无法抵御希尔伯特第十问题的魅力，
在研究自己课题的同时， 还分出精力来继续思考希尔伯特第十问题。 最后他甚至在博士论文上特意增添了一个章节，
简单叙述了自己在希尔伯特第十问题上 “不务正业” 的结果， 那是在 1950 年。
这一增添的章节使戴维斯的那篇原本会象多数研究生工作那样被人遗忘的博士论文变得重要起来， 甚至可以名垂史册。
3 年后， 戴维斯发表了一篇更详细的论述。 他的这一工作标志着数学家们正式开始解决希尔伯特第十问题。
戴维斯在他的研究中引进及运用了一个很重要的概念， 叫做 “丢番图集” (Diophantine set)。
和我们在前面提到过的递归可枚举集一样，
丢番图集也是一些由自然数组成的集合。 所不同的是， 递归可枚举集是由可以有效计算的函数生成的，
而丢番图集则是通过丢番图方程生成的。 戴维斯的重要发现就在于找到了这两类集合之间的一种关联。
戴维斯为什么要引进丢番图集的概念呢？ 是因为倘若希尔伯特第十问题具有肯定的答案，
即存在一个算法来判定丢番图方程是否有解， 那么我们就可以用这一算法来确定一个自然数是否属于某个丢番图集，
这表明所有丢番图集都是可判定的。 反过来说， 倘若我们可以证明某些丢番图集是不可判定的，
也就等于证明了希尔伯特第十问题具有否定的答案。 因此，
丢番图集的可判定与否跟希尔伯特第十问题具有肯定还是否定答案有着密切关系，
这正是戴维斯引进丢番图集这一概念的价值所在。
受波斯特影响， 戴维斯倾向于认为希尔伯特第十问题具有否定答案， 因此， 他想要证明的是某些丢番图集是不可判定的。
那么， 怎样才能证明某些丢番图集是不可判定的呢？
最好的办法就是设法把它与某一类已经知道是不可判定的集合联系在一起[注一]。
而什么样的集合是已经知道是不可判定的呢？ 正是前面提到过的递归可枚举集。 因此在这两类集合之间建立关联是非常重要的。
尤其是， 如果能证明所有递归可枚举集都是丢番图集， 那就等于证明了某些丢番图集是不可判定的，
从而也就等于证明了希尔伯特第十问题的否定答案——即波斯特所说的 “不可解性证明”。
这正是戴维斯寻找希尔伯特第十问题否定答案的思路。
不幸的是， 在戴维斯找到的丢番图集与递归可枚举集的关联中用到了一个被称为 “有界全称量词” (bounded universal quantifier)
的逻辑算符。 如果没有这个有界全称量词， 他就可以证明所有递归可枚举集都是丢番图集， 一切也就大功告成了。
可是数学证明是差不得分毫的， 因为有了这个有界全称量词， 戴维斯的逻辑链条中断了， 从而无法对希尔伯特第十问题作出解答。
但尽管如此， 戴维斯仍然相信所有递归可枚举集都是丢番图集， 他把这一点作为一个猜测提了出来。
在当时， 这是一个很大胆的猜测。
很明显， 要证明戴维斯的猜测， 关键就得把那个有界全称量词去掉， 这是一件非常困难的事情。
直到 9 年之后， 即 1959 年， 戴维斯才在与美国哲学家普特南 (Hilary Putnam, 1926-) 的合作中有条件地做到了这一点。
他们为做到这一点所付出的代价， 是不得不引进了两条额外假设。
初看起来， 这像是不进反退： 原本只有一个麻烦 (即 “有界全称量词”)， 现在反而变成了两个 (即 “两条额外假设”)。
但数学假设的证明难度不是用数量来简单衡量的， 戴维斯与普特南所引进的那两条额外假设比那个有界全称量词来得具体，
因而处理起来要容易一些。 在发表这一研究的全文之前，
戴维斯与普特南把自己的结果寄给了研究希尔伯特第十问题的另一位重要人物——美国数学家罗宾逊夫人
(Julia Robinson, 1919-1985)， 想先听听她的看法。
这一寄揭开了一段新的合作， 把他们的结果又大大向前推进了一步。
4. 罗宾逊猜想
数学是一个性别比例相当失调的领域，
罗宾逊夫人是该领域中为数不多的女数学家之一。 与其他一些女数学家一样， 她一生在追求学术的过程中遇到过许多坎坷。
这些坎坷既有来自社会的， 也有来自自己生活的。 罗宾逊夫人幼年时屡患疾病， 导致身体虚弱，
无法生育， 这一点曾使酷爱家庭的她陷入极度的痛苦之中。
后来， 在她那同为数学家的丈夫引导下， 是数学的力量让她渐渐摆脱了痛苦的阴影。 罗宾逊夫人的丈夫早年曾是她的数论教授，
帮助她打下了非常扎实的数论基础。
罗宾逊夫人自 1948 年起开始研究希尔伯特第十问题， 并曾与戴维斯有过交流。
当她收到戴维斯与普特南寄来的结果时， 凭借自己的数论功底， 很快就发现了他们所作的两个假设中有一个可以去掉，
同时整个证明也可以作极大的简化。 1961 年， 戴维斯、 普特南及罗宾逊夫人合作发表了这一简化后的结果。
这一结果是戴维斯、 普特南的逻辑技巧与罗宾逊夫人的数论功底的完美结合，
也是数学家们在希尔伯特第十问题的研究中所取得的又一个重要进展。
在这一进展中戴维斯与普特南所作的两个假设只剩下了一个。 但这剩下的一个却是连罗宾逊夫人也无法去除的。
这个假设涉及到一种被称为 “指数丢番图集” (exponential Diophantine set) 的集合，
这种集合类似于丢番图集， 但却涉及到指数函数。 倘若有人能证明指数丢番图集实际上就是丢番图集——这也正是那剩下的假设之所在，
那么戴维斯、 普特南及罗宾逊夫人的工作就完全了， 希尔伯特第十问题也就被证明具有否定答案了。
但指数丢番图集究竟是不是丢番图集呢？ 却困住了这三人。
对罗宾逊夫人来说， 指数丢番图集其实并不陌生。 早在 1948 年， 当她刚刚涉足希尔伯特第十问题的时侯，
就研究过由著名波兰逻辑学家塔尔斯基 (Alfred Tarski, 1901-1983) 所提出的一个猜测。 该猜测认为指数丢番图集不是丢番图集。
经过一段时间的研究后， 罗宾逊夫人开始怀疑起了塔尔斯基的猜测， 因为她找不到任何证据可以支持这一猜测。
于是她转而作出了一个与塔尔斯基相反的猜测， 即指数丢番图集实际上就是丢番图集，
这个命题被称为罗宾逊猜想。 这也正是戴维斯、 普特南及罗宾逊夫人
1961 年的工作中唯一缺失的环节。 他们距离希尔伯特第十问题的解决只剩下了一步之遥， 但这一步却难似登天。
在罗宾逊夫人沉醉于希尔伯特第十问题的那些年里， 幼年患病留下的后遗症一再困扰着她。
当年的一位医生甚至预言她的心脏机能受损严重， 也许活不过 40 岁。
这一预测虽然很幸运地由于后来的一次成功的心脏手术而没有成为事实， 但每一年的生日，
罗宾逊夫人都要在吹熄蜡烛的时侯许愿， 希望能够看到希尔伯特第十问题的解决——无论谁来解决都可以，
但一定要在她有生之年解决。 “我无法忍受在不知道答案的情况下离开人世”——这是罗宾逊夫人的话。
时光一年一年地流逝， 罗宾逊夫人的愿望一次一次地落空。 那手握最后一把钥匙的人究竟在哪里呢？
在那些年， 戴维斯也常常被人问到这一问题。 当时正是冷战时期， 对美国人来说世界上最遥远的地方莫过于是俄国。 因此，
戴维斯总是戏剧性地回答说： “那会是一位聪明的俄国年轻人”。 如果戴维斯是一位占星师的话， 这句回答足可让他震动天下，
因为他每一个字都说对了！ 一位聪明的俄国年轻人从世界的另一端走上了数学舞台，
他的名字叫做马蒂亚塞维奇 (Yuri Matiyasevich, 1947-)， 他将为这根长长的智慧链条扣上最后一环。
5. 解决
马蒂亚塞维奇于 1947 年出生在苏联的列宁格勒 (俄罗斯的圣彼得堡)。 他 12 岁时父亲就不幸去世，
但家境贫寒的马蒂亚塞维奇凭借优异的数学成绩在苏联的数学竞赛体系中脱颖而出，
获得了良好的教育机会。 1965 年， 在他还在念本科的时侯， 他的导师马斯洛夫 (S. Yu. Maslov, 1939-1982)
就建议他去证明丢番图方程的不可判定性。 马斯洛夫在建议时轻描淡写地补充说 “这个问题也被称为希尔伯特第十问题，
但你不必理会这个”。 马蒂亚塞维奇说他对研究这类不可解问题没有经验， 马斯洛夫回答说不可解问题没什么大不了的，
无非就是把它约化成一个已知是不可解的其它问题。 他还告诉马蒂亚塞维奇说有几个美国人曾做过一些研究，
但不必理会那些研究， 因为它们 “很可能是不充分的”。
带着马斯洛夫的建议， 马蒂亚塞维奇开始研究起了希尔伯特第十问题。
但他的研究并不顺利， 他一度误以为已解决了问题， 甚至开始准备做报告，
结果却发现自己犯了一个错误。 经过了一段时间的徒劳无功之后， 他开始阅读起 “几个美国人” 的那些
“很可能是不充份的” 工作来， 但依然没有获得实质性进展， 倒是他作为 “研究希尔伯特问题的本科生”
的名声走红了校园， 不时遭来一些善意的取笑。 毕业的时间渐渐临近，
他只好把这个艰深的问题放在一边， 以便可以有时间做一些其他的工作——比如应付毕业论文。
一晃又是几年， 到了 1969 年， 顽强的罗宾逊夫人又向希尔伯特第十问题发起了一次冲击。
这一次虽然还是没有成功， 但她为证明罗宾逊猜想提出了一条非常巧妙的思路。 罗宾逊夫人的结果发表后，
很快有同事把这一消息告诉了马蒂亚塞维奇。 但这时的马蒂亚塞维奇早已决定不再把时间浪费在希尔伯特第十问题上了，
于是没有理会这一消息。 不过， 事情接下来的发展变得很富有戏剧性， 用马蒂亚塞维奇自己的话说：
“在数学天堂的某个角落里必定存在着一位数学之神 (或女神)，
不想让我错过罗宾逊夫人的新论文”。 由于他此前对希尔伯特第十问题的研究，
苏联的一份数学评论杂志把罗宾逊夫人的论文寄给了他， 让他加以评论。 就这样， 马蒂亚塞维奇终于还是看到了罗宾逊夫人的论文。
这一看之下他立刻被罗宾逊夫人的思路所吸引，重新投入到了希尔伯特第十问题的研究上来。
在接下来的几个月时间里， 马蒂亚塞维奇一直在思索罗宾逊猜想。 1969 年在不知不觉间落下了帷幕。
在除夕夜的派对上， 马蒂亚塞维奇因过于出神， 走的时侯竟错穿了他叔叔的衣服离去。
这样全神贯注的投入终于获得了巨大的成功。 1970 年新年到来后的第 4 天， 马蒂亚塞维奇成功地证明了罗宾逊猜想，
从而一举解决了希尔伯特第十问题。 但有了几年前误以为解决希尔伯特第十问题的教训，
这一次他把文章交给了马斯洛夫及另一位数学家栗弗席茨 (Vladimir Lifshits)，
请他们检验， 然后携未婚妻出外滑雪度假。 两个星期后当他回到学校， 一切都变了，
他的论文经受住了以眼光犀利著称的数学家法蒂夫 (D. K. Faddeev, 1907-1989) 与马尔科夫
(A. A. Markov, 1903-1979) 的检验。
马蒂亚塞维奇成为了希尔伯特第十问题的解决者。
1 月 29 日， 马蒂亚塞维奇做了有关他研究成果的第一次公开演讲。
那次演讲中的一位听众把这一成果带到了不久之后在新西伯利亚 (Novosibirsk)
召开的一次数学会议上， 而那次会议的出席者中恰好有一位是罗宾逊夫人的同事。
就这样， 马蒂亚塞维奇解决希尔伯特第十问题的消息很快传遍了数学界。
那时候马蒂亚塞维奇还不满 23 岁， 正是一位 “聪明的俄国年轻人”。
2 月 25 日， 罗宾逊夫人接到了同事的电话， 告知她这一消息。 那一年的生日，
当罗宾逊夫人又将吹熄生日蜡烛时， 她停了下来， 忽然意识到自己许了这么多年的愿望已经成为了现实，
那是一种美妙的感觉。 虽然她自己曾经那么地接近答案， 却还是失之交臂， 但她没有觉得遗憾，
因为对于像她那样真正热爱数学的人来说， 对数学真理的欣赏远远超越了任何个人的荣誉。 在给马蒂亚塞维奇的祝贺信中，
罗宾逊夫人这样写道： “让我特别高兴的是， 当我想到我最初提出那个猜想的时侯， 你还是个孩子， 而我不得不等待你的长大”。
戴维斯也非常兴奋， 他在自己的经典著作《可计算性与不可解性》(Computability and Unsolvability) 的平装本序言中写道：
“我一生最大的快乐之一是 1970 年 2 月读到马蒂亚塞维奇的工作”。
而年轻的马蒂亚塞维奇同样对戴维斯、 罗宾逊夫人，
以及在解决希尔伯特第十问题的漫长征途中做出贡献的所有前辈数学家表达了深深的敬意。
在 20 世纪六七十年代那个寒冷的政治冬天里， 这些第一流的数学家们用他们的杰出工作划开了冷战的冰层，
让世人看到了科学的伟大人文力量。 按照罗宾逊夫人的说法， 这是一种存在于科学家心中的观念，
它跨越地理、 种族、 意识形态、 性别、 年龄、 甚至时代而存在， 过去、 现在及未来的所有数学家们彼此都是同事，
他们献身于一个共同的目标， 那便是最美丽的科学与艺术。
这是希尔伯特第十问题留给我们最丰厚的精神遗产。
返回目录
二零零五年八月二十四日写于纽约
二零零五年八月二十七日发表于本站
二零一三年十一月四日最新修订
https://www.changhai.org/
|