希尔伯特第十问题

不定方程

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

${\displaystyle 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}$ 　　　　　${\displaystyle 1\leq j\leq k}$ 

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

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

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

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

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

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

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

没有非零整数解。

丢番图集

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

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

等价于单个方程：

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

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

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

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

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

有整数系数使对于方程

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

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

丢番图函数

递归函数

递归可枚举集

通用丢番图集

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

• Hilbert第十问题漫谈 （页面存档备份，存于互联网档案馆）
• 希尔伯特第十问题：一段数学发现史
• Hilbert's Tenth Problem page（页面存档备份，存于互联网档案馆）
• Hilbert's 10th Problem （页面存档备份，存于互联网档案馆）