计算机科学和数学的那点儿破事儿

1928年的国际数学家大会在波诺尼亚举行，会上希尔伯特又提粗了他的一个另一个著名问题——所谓的判定问题：找出一个算法来判定一个给定的命题是否为其他命题的逻辑推论。

该问题的趣味性在于以下施诗：数学的哥哥分支可以一律用公里体系呈现出来，其中的鼎力为前面公理的逻辑结果。像希尔伯特所寻求的这样的算法，能使数学家集中注意力于他们工作的令人高兴得部分，即明确表达公里并称述有趣的结果，而将从公理中退出的这些结果的费力的工作留给算法。

然而该问题远非是上面的如意算盘。1992年，波斯特取得了关于该问题的实质性的进步，他证明了命题逻辑——处理呗成为关联词的语言元素的逻辑部分有效地接纳了这种算法，即所谓的真值表方法。然后希尔伯特提出了将该结果扩展也处理量词的逻辑部分——即谓词逻辑。

该问题由美国的丘奇于英国的图灵于1936年分别独立地加以解决。结果是否定的（从中可以看出，对证明的寻求仍旧构成了做数学的中心部分）：希尔伯特所寻求的这种算法是不存在的。但这一事实的证明以一种实质性的进展为先决条件：尽管算法存在性的证明能够仅仅通过展示为先决条件：尽管算法存在性的证明能够仅仅通过展示具有所期望的性质的算法而完成，但是不存在性的证明需要除去每一个可能的算法，因此需要给出算法这一概念的完整刻画。

这样一个模糊、直觉的概念竟然能容纳精确地、形式的刻画，这一事实是令人惊讶地发现。这一点是通过一系列的对算法加以定义的尝试实现的，最终所有的定义被证明是等价的。而确实是图灵的方法最终使数学家意识到，该定义已经被发现。当今他的定义可以被翻译成似乎是平凡的术语——算法是可以用任何一种所谓的通用语言翻译成计算机程序的方法。

的确，1936年计算机还不存在。然而，计算机的进展正是基于图灵引入了通用计算机——通过执行一个程序能够完成每一个可计算函数——这一概念，确切地说，是基于从仅能够完成固定计算的专门计算机，例如计算器，能够完成任何可执行计算——例如计算机——的转变。

图灵得到了判定问题的否定结果，通过将停机问题——即判定一个给定的程序是否将最终终止它的计算并停止于事先输入的数据——翻译成逻辑语言。这一问题可以很容易地被证明是不可判定的，从下面的意义上来说：没有程序能判定它，通过使用经典的对角线法——由康托在集合论中首次引入，后来罗素用于他的悖论，哥德尔用于他得不完全性定理的证明中，因此这一方法为图灵所熟知（也为丘奇所熟知，他用先死的方式解决了这一问题，只是使用他关于算法的等价定义——lambda演算）。

判定问题的解决方法给出了各个领域中关于不可判定性证明的一种方法，通过恰当地翻译成停机问题或其他相似性的问题。从数学的角度来看，该方法的最有趣的应用是希尔伯特第十问题的否定：能否找出一个有整数（正的和负的）系数的多项式（含有一个或多个变量）是否有整数的零点——即通过多项式等于零而得到的丢叛徒方程是否有整数根的算法。

在1900年国际数学家大会时，希尔伯特第十问题的特殊情形的肯定解答就为人所知了。例如，找出最大公因数的欧几里得算法能被用于处理一次丢番图方程，因为a1x1+…+anxn=b有整数解，当且仅当a1,…,an的最大公因子能整除b。此外搞死的二次互反律能使人们处理二次丢番图方程。

1968年，阿兰·贝克尔给出了一个结果——三次或更高次多项式方程解的有效上街，该结果能被用于处理椭圆方程的情形，为此他赢得了1970年度菲尔兹奖。这一事实显示出了希尔伯特第十问题，莫德尔猜想于费马达定理之间存在内在联系。贝克尔的结果后来被扩展到处理任意含有两个变量的丢番图方程。

解决这些特殊情形的困难按时了希尔伯特问题的答案是否定的，因此一般判定算法是不存在的。马丁·戴维斯、希拉里·普特兰、茱莉亚·鲁滨逊和尤里·马蒂亚瑟维奇给出了这一事实的证明。1960年，他们当中的前三位说明了如何将停机问题翻译成丢番图方程——由于加入了指数函数而变得丰富——语言（任一给定程序的行为由一个方程描绘，因而该程序停止当且仅当该方程有一个解），后来1970年马蒂亚瑟维奇从中去掉了指数函数。

一个改进的马蒂亚塞维奇的结果说明了：有九个变量的丢番图方程的情形已经是不可判定的，但是还不知道这是否是最佳可能结果。事实上，贝克尔猜想：有三个变量的丢番图方程就已经是不可判定的了。