希尔伯特第十问题

希尔伯特的第十个问题，就是不定方程（又称为丢番图方程）的可解答性。这是希尔伯特于1900年在巴黎的国际数学家大会演说中，所提出的23个重要数学问题的第十题。

这个问题是问，对于任意多个未知数的整系数不定方程，要求给出一个可行的方法（verfahren），使得借助于它，通过有限次运算，可以判定该方程有无整数解。

这里德文的方法（verfahren），就是英文所谓的算法（algorithm）。对于算法的概念我们是不陌生的，例如远在古希腊时代，人们就知道可以使用辗转相除法，求两个自然数的最大公约数。还有，任给一个自然数，也存在着一个方法，在有限步骤内，可以判定这个数是不是质数。

虽然人们很早就有了算法的朴素概念，但对于到底什么是可行的计算，仍没有精确的概念。一个问题的可解与不可解究竟是什么含意，当时的人们还不得而知。然而为了研究第十问题，必须给予算法精确化的观念。这点还有赖于数理逻辑学对可计算性理论的发展，才得以实现。

基本观念

不定方程

不定方程是指含任意数量变元的整系数多项式方程

P(x_{1},x_{2},...,x_{k})=\sum _{0\leq i_{j}\leq n_{j}}a_{i_{1}i_{2}...i_{k}}x_{1}^{i_{1}}x_{2}^{i_{2}}...x_{k}^{i_{k}}=0

1\leq j\leq k

这里 $a_{i_{1}i_{2}...i_{k}}$ 都是正整数、负整数或零，而变元 $x_{1},x_{2},...,x_{k}$ 的定义域是自然数或整数。若能找到整数 $m_{1},m_{2},...,m_{k}$ ，使得

P(m_{1},m_{2},...,m_{k})=0

则称此不定方程具有整数解。例如：

P(x,y,z)=x^{2}+y^{2}-z^{2}

则(3,4,5)、(5,12,13)等都是它的整数解。事实上可找出它所有的整数解： $a=k(m^{2}-n^{2}),b=2kmn,c=k(m^{2}+n^{2})$ ，其中 $k,m,n\in \mathbb {N*} ,m>n$ 。这是著名的勾股定理或称毕式定理。

著名的费马最后定理，是说当 $n>2$ 时，方程式

P(x,y,z)=x^{n}+y^{n}-z^{n}=0

没有非零整数解。

丢番图集

自然数，自然数对（或具有自然数的n-元组）的有丢番图定义的集合被称为丢番图集。丢番图定义可以由方程组或单个方程给出，因为方程组

p_{1}=0,\ldots ,p_{k}=0\,

等价于单个方程：

p_{1}^{2}+\cdots +p_{k}^{2}=0.\,

递归可枚举集可以被描述为一个集合，对其存在一种算法，对这个算法，当集合的一个成员被输入时最终会停机，但一个非成员被输入时会不确定的继续。是可计算性理论（亦即递归论）给出了算法可计算性的直觉符号的精确解释，因而使得递归可枚举性的符号具有完美的严格性。显然，丢番图集是递归可枚举的。因为可以排列所有可能的未知数的值的多元组为一个序列，然后对于一个给定的参数值，一个接一个的测试这些多元组，看他们是否是相应方程的解。希尔伯特第十问题的不可解性源于令人惊讶的事实──其逆命题成立：

每个递归可枚举集都是丢番图集。

这一结果即马季亚谢维奇定理（由他提供的完成证明的关键步骤）和MRDP定理（即尤里·马季亚谢维奇（Yuri Matiyasevich），朱莉娅·罗宾逊（Julia Robinson），马丁·戴维斯（Martin Davis）和希拉里·普特南（Hilary Putnam）各人姓氏的首字母缩写）。因为“存在一个递归可枚举集是不可计算的”，希尔伯特第十问题的不可解性是其直接后果。实际上，还有更多的结论：有一个多项式

p(a,x_{1},\ldots ,x_{n})

有整数系数使对于方程

p(a,x_{1},\ldots ,x_{n})=0

有自然数解的 $a$ 的值的集合不可计算。因此，不仅没有一般的算法测试丢番图方程可解性，甚至也没有算法来测试单一参数家族的方程。

丢番图函数

递归函数

递归可枚举集

通用丢番图集

历史发展

第十问题的解决是众人集体的智慧结晶。其中美国数学家马丁·戴维斯（Martin Davis）、希拉里·普特南（Hilary Putnam）和朱莉娅·罗宾逊（英语：Julia Robinson）（Julia Robinson）做出了突出的贡献。而最终的结果，是由俄国数学家尤里·马季亚谢维奇（Yuri Matiyasevich）于1970年所完成的。

年代	事件
1944	埃米尔·莱昂·珀斯特（英语：Emil Leon Post）首先猜测，对于第十问题，应寻求不可解的证明。
1949	马丁·戴维斯利用库尔特·哥德尔的方法，并应用中国余数定理的编码技巧，得到递归可枚举集的戴维斯范式 $\{a\|\exists y\,\forall k\!_{\leq y}\,\exists x_{1},\ldots ,x_{n}[p(a,k,y,x_{1},\ldots ,x_{n})=0]\}$ 其中 $p$ 是不定方程。他注意到丢番图集的补集并非丢番图的。而递归可枚举集对于补集运算也非封闭的，他因此猜测这两个集合类是相同的。
1950	朱莉娅·罗宾逊在未知戴维斯工作的情况下，试图证明幂函数是丢番图的 $z=y^{x}$ 虽然并未成功，她发现如果存在这样的丢番图集 $D=\{(a,b)\}$ ，使得 $(a,b)\in D\Rightarrow b<a^{a}$ 而且 $\forall k>0\,\exists (a,b)\in D$ 　使得　 $b>a^{k}$ 在假设这样丢番图集存在（称为J.R.）的情况下，她证明了幂函数是丢番图的。并且如果幂函数是丢番图的，那么二项式系数、阶乘以及质数集合都是丢番图的。
1959	戴维斯与普特南共同研究了指数丢番图集，也就是以丢番图方程所定义的集合，但其中指数可以是未知数。使用戴维斯范式与罗宾逊的方法，并且利用数论中一个当时尚未证明的假设（注：已于2004年由班·格林（英语：Ben Green）和陶哲轩所证明）：存在任意有限长度全由质数所组成的算数级数，他们证明了每一个递归可枚举集都是指数丢番图的。因此若是J.R.成立，就可以将“指数”两字拿掉，而得到每一个递归可枚举集都是丢番图的。因而第十问题是不可解的。
1960	罗宾逊证明了上述的数论假设是不必要的，并且大大简化了证明。从而可知，只要能证明幂函数是丢番图的，第十问题就可以解决。而关键又是寻找满足J.R.假设的丢番图集。
1961-1969	戴维斯与普特南提出数种可证明J.R.的假定。罗宾逊指出，若存在一个全由质数组成的无限丢番图集，便可证明J.R.
1970	尤里·马季亚谢维奇指出可由十个一次和二次的联立不定方程组，定义偶角标的斐波那契函数： $b=F_{2a}$ 其中 $F_{n}$ 是第 $n$ 个斐波那契数。也就是它是丢番图的，并满足J.R.假设。从而可构造出一个不定方程，它不是递归可解的。也就是不存在算法，可以计算该方程式的整数解。因此使得希尔伯特第十问题，得到最终否定的解答。