|
除了自己的无知， －苏格拉底 |
||
| 信 息 | ||
|
All English Contents 作品列表 | 电子图书 站长简介 | 常见问题 版权说明 | 电子邮箱 |
||
| 统 计 | ||
|
自 2008-02-01 以来 本文点击数 32,995 自 2008-02-01 以来 本站点击数 33,450,396 昨日点击数 7,463 今日点击数 231 |
||
| 备 注 | ||
|
本文发表于二零零五年十月二十六日《中国青年报》的冰点探索栏目。 发表时编辑拟定的标题为： “会下金蛋的鹅――希尔伯特第十问题 (上)”， 两个小节的标题分别为 “什么是希尔伯特第十问题” 与 “不可判定命题的启示”。 |
||
|
喜欢本人文字的读者 Hilbert 第十问题漫谈 (上)
数学问题是数学中最具魅力的部分之一， 并且也是数学史上许多思想和进展的重要源泉。 据说有人曾建议德国著名的数学家希尔伯特 (David Hilbert, 1862-1943) 去解决费马猜想 (Fermat's conjecture)， 以夺取为这一猜想而设的沃尔夫斯凯尔奖金 (Wolfskehl Prize)， 希尔伯特却笑了笑回答说： “我为什么要杀掉一只会下金蛋的鹅呢？” 在希尔伯特看来， 一个象费马猜想那样的数学问题对数学的价值是无可估量的。 希尔伯特不仅舍不得 “杀鹅”， 还怀着极大的热诚为 20 世纪的数学界做了一回 “寻鹅之人”。 1900 年， 在于巴黎举办的第二届国际数学家大会上， 希尔伯特做了一次堪称数学史上影响最为深远的演讲， 演讲的题目叫做 “数学问题” (The Problems of Mathematics)。 在那次演讲中， 希尔伯特列举了 23 个他认为最具重要意义的数学问题[注一]。 那些问题被后人称为 “希尔伯特问题” (problems of Hilbert)。 自那次演讲之后， 解决希尔伯特问题成了许多数学家终生为止奋斗的目标， 而在解决这些问题的过程中源源不断产生出来的 “金蛋”， 则为 20 世纪的数学发展注入了极大的生机和活力。 在本文中， 我们就来讲述有关这些数学问题中第十个——即所谓 “希尔伯特第十问题” (Hilbert's tenth problem)——的一些故事。 希尔伯特第十问题是一个与解方程有关的问题。 解方程大家都不陌生， 在中学时我们就已解过许多简单的方程， 比如 2x—2y=1， x2+y2=z2， 等。 我们所举的这两个简单方程有一个共同特点， 那就是都只包含未知数的整数次幂， 而且系数也都是整数， 这类方程被称为整系数代数多项式方程。 数学家们对这类方程的研究有着漫长的历史。 在公元 3 世纪的时侯， 古希腊数学家丢番图 (Diophantus, 200?-284?) 发表了一部长篇巨著， 叫做 《算术》(Arithmetica)。 这部著作共有 13 卷， 经过 1700 余年的漫长岁月， 目前被公认流传于世的有 6 卷[注二]。 丢番图在这部著作中对整系数代数多项式方程进行了大量研究， 那些研究对代数与数论的发展有着先驱性的贡献。 后人为了纪念他， 把整系数代数多项式方程统称为丢番图方程 (Diophantine Equation)， 而丢番图本人， 则被一些人尊称为 “代数学之父” (the father of algebra)。 对于丢番图方程， 数学家们最感兴趣的一个传统问题乃是它是否有整数解 (或自然数解)。 对于简单的丢番图方程来说， 这是很容易找到答案的， 比如上面提到的 x2+y2=z2 有整数解 (早在 3000 多年前， 中国古代的数学家就知道这个方程的一组特解： 即 “勾三股四弦五”)； 另一方面， 2x—2y=1 则没有整数解 (因为方程的左边为偶数， 右边却为奇数)。 但对于一般的丢番图方程来说， 判断它是否有整数解却往往是一件极其困难的事情， 其中最著名的例子就是上面提到过的费马猜想， 即 xn + yn = zn 在 n>2 时没有非零整数解， 它是在隔了 300 多年后才得到的证明[注三]。 长期以来， 人们对丢番图方程是否有整数解的研究都是针对特定形式的丢番图方程进行的。 但是， 人们显然也可以提出这样一个问题， 即有没有办法对任意形式的丢番图方程是否有整数解进行研究？ 或者更具体地说， 是否能找到一种普遍的算法 (algorithm)， 可用来判定一个任意形式的丢番图方程是否有整数解， 从而一劳永逸地解决这类问题？ 这就是著名的希尔伯特第十问题。 这样的问题在数学上被称为判定问题 (decision problem)， 因为它寻求的是对数学命题进行判定的算法。 希尔伯特是一位对数学充满乐观信念的数学家。 在他提出希尔伯特第十问题的时侯， 虽然没有明确表示那样的算法一定存在， 但他没有用 “是否存在那样的算法” 作为问题的表述方式， 而是直接要求数学家们寻找那样的算法， 可见他对存在一个肯定的答案怀有期待。 这种期待与他在其他方面对数学所表示出的乐观看法是一脉相承的。 但是， 数学的发展却往往是像希尔伯特那样的数学大师都无法预料的。 希尔伯特第十问题要求寻找判定丢番图方程是否有解的算法。 但究竟什么是算法呢？ 在希尔伯特提出问题之时却其实并不存在一个明确定义。 这是研究希尔伯特第十问题所遇到的第一个困难。 这一困难使得希尔伯特第十问题在提出后整整 30 年没有取得任何实质进展。 对算法的研究直到 20 世纪 30 年代开始才逐渐深入起来。 什么是算法呢？ 粗略且顾名思义地讲， 算法就是 (通过有限多的步骤) 对数学函数进行有效计算的方法。 反过来说， 如果一个数学问题能够通过可以有效计算的数学函数得到答案， 那么我们就称这一数学问题存在算法。 因此算法研究的一个重要的切入点便是寻找可以有效计算的函数。 但是， 到底什么样的函数是可以有效计算的呢？ 一开始数学家们并没有普遍结论， 只知道一些最简单的函数 (比如常数函数)， 以及用那些函数通过若干简单规则 (比如相加) 组合出来的函数， 是可以有效计算的。 数学家们将这类函数称为递归函数 (recursive function)。 1931 年， 年轻的法国数学家赫尔布兰德 (Jacques Herbrand, 1908-1931) 对递归函数进行了研究， 并给著名逻辑学家哥德尔 (Kurt Gödel, 1906-1978) 写信叙述了自己的研究结果。 不幸的是， 哥德尔当时正处于自己一生最重大的成果——哥德尔不完全性定理 (Gödel's incompleteness theorems)——的研究期间， 没有立即对赫尔布兰德的工作做出回应[注四]。 更不幸的是， 那年的夏天， 年仅 23 岁的赫尔布兰德在攀登阿尔卑斯山时不幸遇难， 他的工作因此被暂时埋没了起来。 与赫尔布兰德的研究差不多同时， 在 20 世纪 30 年代初的时侯， 美国普林斯顿大学 (Princeton University) 的逻辑学家丘奇 (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 的一篇文章中明确提出希尔伯特第十问题 “期待一个不可解性证明”。 当时波斯特在纽约市立大学 (The City College of New York) 任教， 他的这一观点深深地打动了一位学生， 使后者走上了毕生钻研希尔伯特第十问题的征途。 那位学生名叫戴维斯 (Martin Davis, 1928-)， 是解决希尔伯特第十问题的关键人物。
二零零五年八月二十四日写于纽约 站长近期发表的作品
|
