数学问题是数学中最具魅力的部分之一，也是数学史上许多重要思想的源泉。据说，有人曾建议德国著名的数学家希尔伯特（DavidHilbert，1862～1943）去解决费马猜想，以夺取为这一猜想而设的沃尔夫斯凯尔奖金（WolfskehlPrize），希尔伯特笑笑说：“我为什么要杀掉一只会下金蛋的鹅呢？”

　 在希尔伯特看来，一个像费马猜想这样的数学问题对数学的价值是无可估量的。希尔伯特不仅舍不得“杀鹅”，还怀着极大的热诚为20世纪的数学界做了一回“寻鹅之人”。1900年，在巴黎举行的第二届国际数学家大会上，希尔伯特做了一次堪称数学史上影响最为深远的演讲，题目是“数学问题”。在演讲中，希尔伯特列举了23个他认为最具重要意义的数学问题，这些问题被后人称为“希尔伯特问题”。解决希尔伯特问题成了许多数学家终生奋斗的目标，在解决这些问题的过程中，源源不断地产生出的“金蛋”为20世纪的数学发展注入了极大的生机。

　 什么是希尔伯特第十问题

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

　 公元3世纪，希腊数学家丢番图（Diophantus，200？～284？）发表了一部长篇巨著《算术》。这部13卷的著作，经过1700多年的漫长岁月，流传至今的只有六卷。丢番图在这部著作中对整系数代数多项式方程进行的大量研究，对代数与数论的发展有着先驱性的贡献。后人为纪念他，把整系数代数多项式方程称为丢番图方程（DiophantusEquation）。

　 对于丢番图方程，数学家们最感兴趣的是它是否有整数解（或自然数解）。对于简单的方程这是很容易找到答案的，比如x2＋y2＝z2有整数解（早在3000多年前，我国古代的数学家就知道这个方程的一组解：即勾三股四弦五）；2x－2y＝1则没有整数解（因为方程的左边为偶数，右边却为奇数）。但对于一般的丢番图方程来说，判断它是否有整数解却是件极困难的事，其中最著名的例子就是费马猜想，即xn＋yn＝zn在n＞2时没有非零整数解，直到300多年后才得到证明。

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

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

　 不可判定命题的启示

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

　 直到20世纪30年代，对算法的研究才逐渐深入。

　 数学上，算法是（通过有限多的步骤）对数学函数进行有效计算的方法。因此算法研究的一个重要的切入点，是寻找可以有效计算的函数。到底什么样的函数是可以有效计算的呢？数学家们开始并没有普遍的结论，只知道一些最简单的函数，以及用这些函数通过若干简单规则组合出的函数是可以有效计算的。数学家们把这类函数叫做递归函数（RecursiveFunction）。

　 1931年，年轻的法国数学家赫尔布兰德（JacquesHerbrand，1908～1931）对递归函数进行了研究，并给著名逻辑学家哥德尔（KurtGdel，1906～1978）写信叙述了自己的研究结果。哥德尔当时正处于自己一生中最重大的成果―――哥德尔不完全性定理―――的研究时期，没有立即对赫尔布兰德的工作做出回应。那一年的夏天，年仅23岁的赫尔布兰德在攀登阿尔卑斯山时不幸遇难，他的工作因此被暂时埋没了。

　 与赫尔布兰德的研究差不多同时，20世纪30年代初，普林斯顿大学的美国逻辑学家丘奇（AlonzoChurch，1903～1995）也在积极从事逻辑及算法的研究，并且发展出了一种新的逻辑体系。他让自己的两个学生克林（StephenKleene，1909～1994）与罗瑟（JohnRosser，1907～1989）对这一体系做细致的研究。两个学生都是一流好手，克林后来还成为一流的逻辑学家。他们的研究很快就有了结果，但这结果大大出乎丘奇的意料。他们发现丘奇的那套体系竟然是自相矛盾的！命运似乎只有一个：放弃。幸运的是，丘奇的那套体系中有一个组成部分是自洽的，因此可以保留下来，这部分叫做兰姆达运算（λ－calculus）。

　 这种兰姆达运算可以用来定义函数，而所有用兰姆达运算定义的函数都是可以有效计算的。在对兰姆达运算做了研究之后，丘奇提出了一个大胆的猜测，他猜测所有可以有效计算的函数都可以用兰姆达运算来定义。

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

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

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

　 在这些有关算法的研究中，数学家们还提出了一个重要的概念：递归可枚举集（RecursivelyEnumerableSet）。即由可以有效计算的函数所生成的自然数的集合。对于一个集合来说，一个很基本的问题就是判断一个元素是否属于该集合。递归可枚举集也不例外。当数学家们研究递归可枚举集的时候，发现了一个十分微妙的结果：对于某些递归可枚举集来说，我们无法判定一个自然数是否属于该集合！换句话说，有一些递归可枚举集是不可判定的。这一结果把对算法的研究与判定问题联系了起来，为后来解决希尔伯特第十问题埋下了重要的伏笔。

　 这一系列结果出现在1936～1937年间。那时候，在数学中存在无法判定的命题已经不是一件新鲜事了。早在5年前哥德尔就已经证明了他的不完全性定理，即任何足够复杂并且自洽的数学体系都必定包含不可判定的命题。当时已知的不可判定命题大都集中在逻辑领域内。在数学的其他领域中，究竟哪些命题是不可判定的呢？这个问题在整整10年之后才开始有答案。

　 1947年美国数学家波斯特（EmilPost，1897～1954）找到了第一个逻辑领域以外的不可判定命题。波斯特是一位有着深刻洞察力的逻辑学家，7岁时随父母从波兰移民到美国，是美国逻辑学的先驱之一。他早将近10年就得到了与哥德尔不完全性定理相似的结果，由于想对结果作更全面的分析而没有及时发表。1936年，几乎与哥德尔、丘奇及图灵同时，波斯特独立提出了类似于图灵的结果，他也是最早意识到希尔伯特第十问题可能会有否定答案的数学家之一。1944年，他在一篇文章中明确提出希尔伯特第十问题“期待一个不可解性证明”。当时波斯特在纽约市立大学任教，他的这一观点深深打动了一位学生，使后者走上了毕生钻研希尔伯特第十问题的征途。这位学生名叫戴维斯（MartinDavis，1928～），是解决希尔伯特第十问题的关键人物。