欢 迎 访 问 卢 昌 海 个 人 主 页

除了自己的无知,
我什么都不懂。

-苏格拉底

 
信 息
 
 
 
已发表作品列表
站长简介 | 常见问题
版权说明 | 电子信箱
 
统 计
 
 
 
自 2008-02-01 以来
本文点击数
17,740
自 2008-02-01 以来
本站点击数
16,890,019
昨日点击数 3,936
今日点击数 141
 
备 注
 
 
 

本文发表于二零零五年十月二十六日《中国青年报》的冰点探索栏目。 发表时编辑拟定的标题为: “会下金蛋的鹅――希尔伯特第十问题 (上)”, 两个小节的标题分别为 “什么是希尔伯特第十问题” 与 “不可判定命题的启示”。

Hilbert 第十问题漫谈 (上)

- 卢昌海 -

返回目录

David Hilbert
David Hilbert

1. 问题

数学问题是数学中最具魅力的部分之一, 并且也是数学史上许多思想和进展的重要源泉。 据说有人曾建议德国著名的数学家希尔伯特 (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), 因为它寻求的是对数学命题进行判定的算法。

希尔伯特是一位对数学充满乐观信念的数学家。 在他提出希尔伯特第十问题的时侯, 虽然没有明确表示那样的算法一定存在, 但他没有用 “是否存在那样的算法” 作为问题的表述方式, 而是直接要求数学家们寻找那样的算法, 可见他对存在一个肯定的答案怀有期待。 这种期待与他在其他方面对数学所表示出的乐观看法是一脉相承的。

但是, 数学的发展却往往是像希尔伯特那样的数学大师都无法预料的。

2. 算法

希尔伯特第十问题要求寻找判定丢番图方程是否有解的算法。 但究竟什么是算法呢? 在希尔伯特提出问题之时却其实并不存在一个明确定义。 这是研究希尔伯特第十问题所遇到的第一个困难。 这一困难使得希尔伯特第十问题在提出后整整 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-), 是解决希尔伯特第十问题的关键人物。

返回目录 | 下一篇

注释

  1. 这 23 个问题中有一些——比如第八问题——不是单一问题。 另外, 这些问题是以演讲的文稿而非演讲本身为依据排列的, 希尔伯特在演讲中直接提及的只有其中的 10 个问题 (本文所述的第十问题不在其中)。
  2. 除公认的 6 卷外, 另有 4 卷发现于 20 世纪的阿拉伯文抄本也被认为有可能是丢番图《算术》或其注释本的译本。
  3. 细心的读者可能会注意到, 在本文中我们没有对整数、 正整数, 及自然数 (零及正整数) 等做出区分。 这是因为 可以证明, 对于希尔伯特第十问题来说, 把解限定在这些数集的任意一者中都是等价的。
  4. 哥德尔给赫尔布兰德的回应只是不够 “立即”, 而非没有。 他的回信写于 1931 年 7 月 25 日, 赫尔布兰德遇难的时间则是 7 月 27 日, 只相隔了两天, 赫尔布兰德没来得及收到回信就去世了。
  5. 具体地讲, 图灵当时的目的是要研究希尔伯特于 1928 年提出的有关一阶逻辑的判定问题。
  6. 不过, 需要提醒读者的是, 把可以有效计算的函数等同于丘奇、 哥德尔、 图灵等人提出的、 彼此等价的函数并不是建立在数学证明的基础之上的, 而只是一个猜测性的论题, 即所谓 “丘奇论题” (Church's Thesis)。 一般认为, 丘奇论题是无法被证明的, 因为 “有效计算” 本身是一个不存在精确定义的概念, 它本质上取决于人们对 “有效” 及 “计算” 这样的非精确概念的理解。 如果有一天人们发现有必要改变或拓展原先对这些概念的理解, 则数学上的一些相关结果——包括希尔伯特第十问题的解决方式——会有可能需要作出相应的改变。
  7. 读者们想必猜到了, 这些集合之所以被称为 “递归可枚举集”, 乃是因为可以有效计算的函数的定义之一叫做 “赫尔布兰德-哥德尔递归函数”。
  8. 确切地讲, 这是哥德尔第一不完全性定理 (Gödel's first incompleteness theorems)。

站长近期发表的作品

网友讨论选录

  • 网友: 韩雪涛   (发表于 2009-12-02)

    “《算术》…… 现在流传于世的有六卷”——1973 年, 人们奇迹般地发现了四卷先前不为人知的阿拉伯文译本。 因此现在传世的《算术》一书有十卷。

    另外问卢兄: 介绍马蒂亚塞维奇研究希尔伯特第十问题的那几段文字, 兄的资料来自何处? 打算在自己的书中用一下, 是否可以?

  • 网友: 卢昌海   (发表于 2009-12-02)

    欢迎韩兄。

    那段文字的资料来源很可能是 Yandell 的《The Honors Class》, 不过我现在不在家, 无法核实。

    关于韩兄提到的丢番图的另四卷, Wikipedia 上的说法是: “Of the original thirteen books of which Arithmetica consisted only six have survived, though there are some who believe that four Arab books discovered in 1968 are also by Diophantus”。 按照该说法, 那四卷阿拉伯文发现于 1968 年, 是否是丢番图的著作尚无定论。 不知韩兄的资料出自何处? 如果可靠的话, 我将在文末添一个补注加以说明。

  • 网友: 韩雪涛   (发表于 2009-12-02)

    呵呵, 其实经常光顾兄的个人主页。 关于丢番图的《算术》, 看到兄的回贴倒是愣了一下。 因为我看到的中文资料都是如我上一贴中所说。 现录李文林主编的《数学珍宝——历史文献精选》181 页的一段文字: 1973 年, 在伊朗境内的马什哈德又发现 4 卷阿拉伯文抄本, 据专家鉴定应属原著第 4、 5、 6、 7 卷 (含 101 个问题), 而先前的希腊文本则为第 1、 2、 3、 8、 9、 10 卷 (含 189 个问题)。 另外, 国内研究世界数学史的梁宗巨在《世界数学通史》中, 杜瑞芝主编的《数学史辞典》中都是这样介绍的。 看了兄的回贴, 有些不放心, 又查了一本较近出版的《数学史通论》中译本。 书中是这样介绍的: ……只有六卷在希腊保存下来了, 另外有四卷最近发现了其阿拉伯文的版本, 从其内容来看, 它似乎是整部著作中的第 4 到第 7 卷, 随后才是希腊文的后三卷。 ……阿拉伯文的那几卷在风格上与希腊文的那几卷略有不同, 其中对一个问题的解的每一步说明得更充分。 因此, 很有可能, 这本阿拉伯的著作不是丢番图原著的译本, 而是从希帕蒂娅在公元400年左右所写的《算术》的注释本翻译过来的。

  • 网友: 卢昌海   (发表于 2009-12-02)

    我核对了一下, 所引资料的确是 Yandell 的《The Honors Class》。

    谢谢韩兄提供的有关《算术》另四卷的信息, 我在文末加了一个补注。

  • 网友: 韩雪涛   (发表于 2009-12-02)

    多谢卢兄。

本文的讨论期限已过, 如果您仍想讨论本文,
请在每个月前七天的 “读者周” 期间前来讨论。

>> 查阅目前尚在讨论期限内的文章 <<