24小时热门版块排行榜

返回列表

当前主题已经存档。

当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

formleaf

木虫 (正式写手)

应助: 0 (幼儿园)
贵宾: 1.097
金币: 3383.1
散金: 2780
红花: 3
帖子: 991
在线: 69.6小时
虫号: 698652
注册: 2009-02-09
性别: GG
专业: 组合数学

[交流] 【转帖】Hilbert 第十问题漫谈

1. 问题

数学问题是数学中最具魅力的部分之一，并且也是数学史上许多重要思想的源泉。据说有人曾建议德国著名的数学家希尔伯特 (David Hilbert, 1862-1943) 去解决费尔马猜想，以夺取为这一猜想而设的沃尔夫斯凯尔奖金 (Wolfskehl Prize)，希尔伯特却笑笑回答说： “我为什么要杀掉一只会下金蛋的鹅呢？” 在希尔伯特看来，一个象费尔马猜想这样的数学问题对数学的价值是无可估量的。希尔伯特不仅舍不得 “杀鹅”，还怀着极大的热诚为二十世纪的数学界做了一回 “寻鹅之人”。 1900 年，在巴黎举行的第二届国际数学家大会上，希尔伯特做了一次堪称数学史上影响最为深远的演讲，演讲的题目叫做 “数学问题”。在这一演讲中，希尔伯特列举了二十三个他认为最具重要意义的数学问题[注一]。这些问题被后人称为 “希尔伯特问题”。解决希尔伯特问题成了许多数学家终生奋斗的目标，而在解决这些问题的过程中源源不断地产生出的 “金蛋” 则为二十世纪的数学发展注入了极大的生机。

在本文中我们就来讲述有关这些数学问题中的第十个 - 即希尔伯特第十问题 - 的一些故事。

希尔伯特第十问题是一个与解方程有关的问题。解方程大家都不陌生，在中学时我们就解过许多简单的方程，比如 2x-2y=1， x2+y2=z2，等。我们所举的这两个简单方程有一个共同的特点，那就是它们只包含未知数的整数次幂，而且系数也都是整数，这类方程被称为整系数代数多项式方程。数学家们对这类方程的研究有着漫长的历史。

公元三世纪的时侯，古希腊数学家丢番图 (Diophantus, 200?-284?) 发表了一部长篇巨著，叫做《算术》。这部著作共有十三卷，经过一千七百余年的漫长岁月，现在流传于世的有六卷。丢番图在这部著作中对整系数代数多项式方程进行了大量的研究，这些研究对代数与数论的发展有着先驱性的贡献。后人为了纪念他，就把整系数代数多项式方程称为丢番图方程 (Diophantine Equation)。

对于丢番图方程，数学家们最感兴趣的一个问题就是研究它是否有整数解 (或自然数解)。对于简单的方程来说这是很容易找到答案的，比如上面提到的 x2+y2=z2 有整数解 (早在三千多年前，我国古代的数学家就知道这个方程的一组解：即勾三股四弦五)；另一方面， 2x-2y=1 则没有整数解 (因为方程的左边为偶数，右边却为奇数)。但对于一般的丢番图方程来说，判断它是否有整数解却往往是一件极其困难的事情，其中最著名的例子就是费尔马猜想，即 xn + yn = zn 在 n>2 时没有非零整数解，隔了三百多年才得到证明[注二]。

长期以来，人们对丢番图方程是否有整数解的研究都是针对特定形式的丢番图方程进行的。那么有没有办法对一般的丢番图方程是否有整数解进行研究呢？或者具体地说，是否可以找到一种普遍的算法，可以用来判定一个任意的丢番图方程是否有整数解，从而一劳永逸地解决这类问题呢？这便是著名的希尔伯特第十问题。这样的问题在数学上被称为判定问题 (Decision Problem)，因为它寻求的是对数学命题进行判定的算法。

希尔伯特是一位对数学充满乐观信念的数学家。在他提出这一问题的时侯，虽然没有明确表示这样的算法一定存在，但他没有用 “是否存在这样的算法” 作为问题的表述，而是直接要求数学家们寻找这样的算法，可见他对存在一个肯定的答案怀有期待。这种期待也与他在其它方面对数学的乐观看法一脉相承。但后来的数学发展却出现了连希尔伯特这样的数学大师都始料未及的变化。

2. 算法

希尔伯特第十问题要求寻找判定丢番图方程是否有解的算法。但究竟什么是算法呢？在当时却没有一个明确的定义。这是研究希尔伯特第十问题所遇到的第一个困难。这一困难使得希尔伯特第十问题在提出后整整三十年没有取得任何实质进展。

对算法的研究直到二十世纪三十年代起才逐渐深入起来。

什么是算法呢？粗略地讲，算法是 (通过有限多的步骤) 对数学函数进行有效计算的方法。或者反过来说，如果一个数学问题能够通过可以有效计算的数学函数得到答案，那么我们就说这个数学问题存在算法。因此算法研究的一个重要的切入点便是寻找可以有效计算的函数。到底什么样的函数是可以有效计算的呢？一开始数学家们并没有普遍的结论，只知道一些最简单的函数，以及用这些函数通过若干简单规则组合出的函数是可以有效计算的。数学家们把这类函数叫做递归函数 (Recursive Function)。

1931 年，年轻的法国数学家赫尔布兰德 (Jacques Herbrand, 1908-1931) 对递归函数进行了研究，并给著名逻辑学家哥德尔 (Kurt Gödel, 1906-1978) 写信叙述了自己的研究结果。但哥德尔当时正处于自己一生最重大的成果 - 哥德尔不完全性定理 - 的研究时期，没有立即对赫尔布兰德的工作做出回应[注三]。那一年的夏天，年仅二十三岁的赫尔布兰德在攀登阿尔卑斯山时不幸遇难，他的工作因此被暂时埋没了起来。

与赫尔布兰德的研究差不多同时，在二十世纪三十年代初的时侯，普林斯顿大学的美国逻辑学家丘奇 (Alonzo Church, 1903-1995) 也在积极从事逻辑及算法的研究，并且发展出了一种新的逻辑体系。他让自己的两位学生 - 克林 (Stephen Kleene, 1909-1994) 与罗瑟 (John Rosser, 1907-1989) 对这一体系做细致的研究。他的这两位学生都是第一流的好手，克林更是后来自己也成为了第一流的逻辑学家，他们的研究很快就有了结果，但这结果却大大出乎丘奇的意料。他们发现丘奇的那套体系竟然是自相矛盾的！自相矛盾的逻辑体系只能有一个命运，那就是被放弃。但幸运的是，丘奇的那套体系中有一个组成部分仍然是自洽的，因此可以保留下来，这一部分叫做兰姆达运算 (λ-calculus)。这种兰姆达运算是做什么用的呢？它可以用来定义函数，而所有用兰姆达运算定义的函数都是可以有效计算的。在对兰姆达运算做了研究之后，丘奇提出了一个大胆的猜测，他猜测所有可以有效计算的函数都可以用兰姆达运算来定义。

1934 年，丘奇向到普林斯顿大学访问的哥德尔介绍了这一猜测，但哥德尔却不以为然。丘奇不服气，于是请哥德尔给出一个他认为合适的描述。哥德尔没有让他久等，一两个月后就给出了一种完全不同的描述。哥德尔所给出的这种描述的基础正是三年前赫尔布兰德在给他的信中叙述的结果。哥德尔对这一结果进行了完善。这一结果因此被人们称为赫尔布兰德-哥德尔递归函数。

就这样，丘奇与哥德尔各自给出了一种体系，来描述可以有效计算的函数。那么两者孰优孰劣呢？丘奇与克林经过研究，很快证明了这两种看上去完全不同的描述方式实际上是彼此等价的。这两位著名逻辑学家的工作殊途同归大大增强了丘奇的信心，他相信人们已经找到了可以有效计算的函数的普遍定义。但哥德尔及其他一些人对此却仍然怀有疑虑。最终打消这种疑虑的是英国数学家图灵 (Alan Turing, 1912-1954)。

图灵当时对丘奇及哥德尔在这方面的研究并不知情。他所研究的课题是什么样的运算可以用机器来实现[注四]。他的这一研究对后来计算机科学的发展起到了深远的影响。在图灵的研究接近完成的时侯，他的导师注意到了丘奇与哥德尔的工作。于是图灵对彼此的工作进行了比较，结果发现丘奇与哥德尔所定义的那些函数与他的抽象计算机可以计算的函数恰好吻合！图灵把这一结果作为附录加进了自己的论文。这一下就连哥德尔也心悦诚服了，毕竟，有什么能比在抽象计算机上可以直接计算更接近 “可以有效计算” 以及算法的基本含义呢[注五]？

在这些有关算法的研究中，数学家们还提出了一个重要的概念，叫做 “递归可枚举集” (Recursively Enumerable Set)。什么叫做递归可枚举集呢？那是指由可以有效计算的函数所生成的自然数的集合[注六]。我们知道，对于一个集合来说，有一个很基本的问题就是判断一个元素是否属于该集合。递归可枚举集也不例外。但是当数学家们研究递归可枚举集的时侯，却发现了一个十分微妙的结果，那就是对于某些递归可枚举集来说，我们无法判定一个自然数是否属于该集合！换句话说，有一些递归可枚举集是不可判定的。这一结果把对算法的研究与判定问题联系了起来，为后来解决希尔伯特第十问题埋下了重要的伏笔。

这一系列结果的出现主要集中在 1936-1937 年间。那时侯，在数学中存在无法判定的命题本身已经不是一件新鲜事了。因为早在五年前哥德尔就已经证明了他的不完全性定理，那就是任何足够复杂并且自洽的数学体系都必定包含不可判定的命题[注七]。但当时已知的不可判定命题大都集中在逻辑领域内。那么在数学的其他领域中究竟哪些命题是不可判定的呢？这个问题在整整十年之后才开始有答案。 1947 年美国数学家波斯特 (Emil Post, 1897-1954) 找到了第一个逻辑领域以外的不可判定命题。波斯特是一位有着深刻洞察力的逻辑学家，七岁时随父母从波兰移民到美国，是美国逻辑学的先驱之一。他比哥德尔早了将近十年就得到了与哥德尔不完全性定理相似的结果，但由于想对结果作更全面的分析而没有及时发表。 1936 年，几乎与上面提到的哥德尔、丘奇及图灵同时，波斯特独立提出了非常类似于图灵的结果。波斯特同时还是最早意识到希尔伯特第十问题可能会有否定答案的数学家之一。他在 1944 的一篇文章中明确提出希尔伯特第十问题 “期待一个不可解性证明”。当时波斯特在纽约市立大学任教，他的这一观点深深地打动了一位学生，使后者走上了毕生钻研希尔伯特第十问题的征途。那位学生名叫戴维斯 (Martin Davis, 1928-)，是解决希尔伯特第十问题的关键人物。

返回目录 | 下一篇

注释

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

回复此楼