解法：MRDP定理:丢番图集合恰为递归可枚举集合(1970年)

希尔伯特第十问题是他1900年在国际数学家大会演讲中提出的23个问题中的第十个,要求给出一个经有限步操作的程序,对任意多项式 $P(x_1, \ldots, x_n) \in \mathbb{Z}[x_1, \ldots, x_n]$ 判定方程 $P(x_1, \ldots, x_n) = 0$ 是否有整数解。有两个特点使这一要求很强:算法必须是一致的——用一个程序覆盖所有次数和所有系数元组——而且必须对每个输入都停机并给出正确的是/否答案,而不是只在某个可判定子类上成功。

若干子类当时已经可判定。线性方程 $a_1 x_1 + \cdots + a_n x_n = b$ 归结为计算 $\gcd(a_1, \ldots, a_n)$;一元方程 $P(x) = 0$ 在通分后归结为常数项的整除性;二元二次方程则属于二元二次型与佩尔方程理论,已由连分数方法基本解决。所有经典技巧都无法触及的是一般情形:丢番图方程可以编码任意复杂的算术结构,且未知数个数 $n$ 没有上界。

最终的解答由马季亚谢维奇于1970年完成,答案是否定的,而它要求把"程序"这个非正式的词变成数学对象。下面的证明沿用的是马季亚谢维奇2008年 Scholarpedia 综述中的路线:把丢番图可定义性等同于递归可枚举性,再引入图灵停机问题的不可判定性。