1900年，在巴黎举行的第二届国际数学家大会上，希尔伯特做了一次堪称数学史上影响最为深远的演讲，题目是“数学问题”。在演讲中，希尔伯特列举了23个他认为最具重要意义的数学问题，这些问题被后人称为“希尔伯特问题”。希尔伯特第十问题是所有23个问题中最短的一个，但从某种意义说，其深远却最大，尤其是对计算机科学而言。

一、什么是希尔伯特第十问题

希尔伯特第十问题又称“判定丢番图方程的可解性”对其具体的描述为“给定一个系数均为有理整数，包含任意个未知数的丢番图方程：设计一个过程，通过有限次的计算，能够判定该方程在有理数整数上是否可解。”希尔伯特所谓的“方法”就是“算法”。人们很早就有了算法的朴素概念，但对于到底什么是可行的计算，仍没有精确的概念。一个问题的可解与不可解究竟是什么含意，当时的人们还不得而知。然而为了研究第十问题，必须给予算法精确化的概念。这点还有赖于数理逻辑学对可计算性理论的发展，才得以实现。

从另一个角度看，希尔伯特第十问题就是一个与解方程有关的问题，具体来说就是寻找判定丢番图方程是否有解的算法的问题。公元3世纪，希腊数学家丢番图发表了一部长篇巨著《算术》。丢番图在这部著作中对整系数代数多项式方程进行的大量研究，对代数与数论的发展有着先驱性的贡献。后人为纪念他，把整系数代数多项式方程称为丢番图方程。数学家们对丢番图方程最感兴趣的是它是否有自然数解（或整数解）。对于简单的方程这是很容易找到答案的，如我国3000多年前的勾三股四玄五的勾股定理。

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

不过，希尔伯特提出问题是直接要求数学家们寻找这样的算法，可见他对存在一个肯定的答案怀有期待。但不幸的是，从正面来寻找这样一种普遍的算法一直困扰着数学家，直到上个世纪30年代人们对算法的研究才从否定希尔伯特第十问题的角度重新审视这个难题，也就是说这个难题的突破口来自于不可判定命题的启示。

可当时人们对什么是算法并没有明确的定义。随着研究的深入，大家逐渐认识到所谓算法就是通过有限多的步骤，对数学函数进行有效计算的方法。于是便开始寻找可以有效计算的函数。到底什么样的函数是可以有效计算的呢？数学家们开始并没有普遍的结论，只知道一些最简单的函数，以及用这些函数通过若干简单规则组合出的函数是可以有效计算的。数学家们把这类函数叫做递归函数（Recursive Function）。在数理逻辑中，研究递归函数的理论被称为递归论或能行性论，主要探讨“能行计算”、“能行判定”的问题。递归论也称为可计算性理论，它产生于对算法的研究。主要研究可计算对象的计算复杂性和不可计算对象的结构，也是计算机科学的理论基础。它的目的是研究计算和相对计算的本质。

“能行性”所探讨的对象都是离散的，其中自然数是离散对象中最简单和普遍的。所以能行性论便以讨论自然数为主。自然数虽然简单普遍，但也有其自身的缺陷，例如它不能进行无限制的减与除，人们便引入负数和有理数，进而是实数与复数，使人们对外部世界的认识更加深入。可同时对自然数本身的离散性和能行性的研究却忽略了，这不能不说是一种遗憾。

后来到了16世纪，法国的Pascal开始明确使用数学归纳法，这是近代对自然数特性的最初的注意。以后人们，如Dedekind和Peano，在发展自然数论时，不但有系统地使用数学归纳法，而且也使用原始递归函数来定义新函数。到1923年，Skolem明确宣称，原始递归函数可定义所有初等数论中的数论函数，他的这一宣称凸显出原始递归函数的重要意义。另外，1931年哥德尔证明其著名的不完全定理时，原始递归函数也起到了不可或缺的作用。从此后，原始递归函数正式问世。

沿着Skolem的思路，人们继续追问，原始递归函数是否就是一切可计算的数论函数。没过多久Ackermann给出了否定的证明。他具体刻画出一个增长速度远超一切的原始递归函数，但它却是可计算的。于是寻找更广泛的可计算函数便成为研究的重点。哥德尔根据Herbrand的暗示，建议引进一般递归函数，Kleene对这个建议进行了改进和进一步的阐明，它成为教科书上普遍采用的一般递归函数的定义。毫无疑问，它比原始递归函数更广，然而，人们还是继续追问，教科书的定义是否已经包括所有的“可计算函数”呢？如果还有，又该如何定义？

1936年，Church和Turing先后出现了二个著名的论题，Church提出，可计算函数便是一般递归函数。而Turing提出，可计算函数就是由图灵机所计算的函数。Kleene证明，这二个论题等价，现在通称Church-Turing论题。当年提出这个论题时，人们觉得过于武断，大家总是希望找出反例，可随着时间的推移，不仅没有找到反例，反而使有利于这个论题的例子越来越多。因此，在数理逻辑界几乎没人反对Church-Turing论题了。不过，承认这个论题并非意味着大功告成，不能再行发展了，还有许多以前无法做到的事情，都可以根据这个论点给出结论。

有了这个论题，首先就解决了“判定问题”，此前可以断定某些问题是不能能行地解决（或判定），现在可以说某某问题可以能行解决（或判定）。万一这种办法找不到却不敢断定，某某问题不能能行解决（或判定），因为“找不出”不等于“不存在”。面对这样的局面，只有接受Church-Turing论题，将“能行地解决（或判定）解释为“有一般递归函数”，把“能行地判定”解释为“有一个一般递归谓词”因此，当我们证明“没有相应的一般递归函数”或“没有相应的一般递归谓词”时，答案就是否定的了。正因为如此，久而未决的判定不定方程是否有解的希尔伯特第十问题，便解决了。但这个解决与希尔伯特当初的乐观态度相反，是从否定的方面解决的，也就是说，希尔伯特所期望的一般算法是不存在的。

否定地解决希尔伯特第十问题有什么意义？我们说图灵机为可计算性划了界，这就是所谓的“停机问题”（Halting Problem）。通俗地说，停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。如果这个问题可以在有限的时间之内解决，可以有一个程序判断其本身是否会停机并做出相反的行为。这时候显然不管停机问题的结果是什么，都不会符合要求。所以这是一个不可解的问题。也就是说，一个图灵机无法判断另一个图灵机的“命运”。但是图灵机毕竟只是图灵用来解决“判定问题”的一个思维构建。然而，一切计算方法的可计算性都等价于图灵机吗？这里所说的“一切”主要是在说人脑。其背后还有一个更深远也更具哲学意味的问题：图灵机的极限究竟只是一类机器的建构，还是恰好反映了物理世界对认知的某种约束？图灵机恰好发现了人类不可获知之物吗？从这个主题引出了很多重要的研究，例如维纳的《控制论》(通俗本叫《人有人的用处》)、香农的《自动机研究》还有冯诺依曼的《计算机与人脑》。

再扩展一步，整个宇宙是一台图灵机吗？如果宇宙的起源是确定的、宇宙中所有的规则是确定的，那么不就意味着宇宙中已经发生正在发生和将会发生的一切都是确定的吗？那么自由意志在哪里？“拉普拉斯妖”（Démon de Laplace）就是这样一个全知的存在。拯救了自由意志的居然是“判定问题”即使宇宙真的是一台图灵机，仍然没有办法预知未来，因为这是一个不可判定的问题。直到程序真的被执行，未来根本不存在。未来仍然是等着人去创造的。这就是自由意志。因此，解决了希尔伯特第十问题就意味着把人的“自由意志”从拉普拉斯妖的魔咒中解放出来。

转载本文请联系原作者获取授权，同时请注明本文来自刘钢科学网博客。
链接地址：https://blog.sciencenet.cn/blog-105489-606422.html

上一篇：印欧语系的“祖先”
下一篇：科学网的一个新动向