戴维斯-普特南-罗宾逊-马蒂亚谢维奇定理

M．戴维斯、H．普特南、J．罗宾逊和ю．马蒂亚谢维奇四人共同证明：希尔伯特第十问题是不可解的。

希尔伯特在1900年的世界数学家大会上曾提出23个尚未解决的问题作为对20世纪数学家的挑战。其中的第十问题是个判定问题：

“10．任意刁番图方程的判定

设有具有任意多未知数的刁番图方程，要求给出一个过程，使用该过程可以在有穷步运算之内确定该方程是否有整数解。”(所谓刁番图方程就是只考虑其整数解的整系数多项式方程。)

希尔伯特的问题是针对整数解提出的。应用一点简单的数论知识(例如拉格朗日的四平方数定理)便可证明希尔伯特的问题等价于关于刁番图方程是否有自然数解的判定问题；而这又等价于判定任何一个刁番图集是否为空的问题。

刁番图集都是递归可枚举集。如果全体刁番图集只是递归可枚举集类的一个真子类，希尔伯特问题或许有希望获解；如果刁番图集的类等同于递归可枚举集的类，那就意味着希尔伯特第十问题是不可解的。

这个结果是在20年中逐步得到的。1952年，J．罗宾逊证明：如果存在一个二元刁番图谓词R(x，y)，其中一个变元依另一个变元的递增速度是指数率的(即使R(x，y)为真的那些x，y满足y≥a(a＞1))，则指数谓词z=u是刁番图谓词。但她并未能证明这样的R(x，y)存在。此后，1958年，M．戴维斯证明：对每个递归可枚举集SN，存在刁番词谓词D(k，x，y)使S=｛x｜ykD(k，x，y)｝(*)(kP(k)为k(k≤y→P(k))的缩写。)(*)式在五、六十年代曾被称为“戴维斯范式”，它表明半可判定谓词与刁番图谓词之间至多相差一个有界全称量词，如能进一步消去这个有界全称量词就可以证明半可判定谓词都是刁番图谓词，从而希尔伯特第十问题不可解。但是戴维斯当时并未找到消去这个全称量词的办法。

1961年，戴维斯和普特南又进一步得到了一条关于指数刁番图集的重要定理，所谓指数刁番图方程指的是由自然数和未知数经加、减、乘和幂运算而得到的方程。也可以看作将若干形如u(v是未知数，u是自然数或未知数)代入某个刁番图方程中的若干变元而得到的方程．例如

2xy+3xy-6z－2=0

就是一个指数刁番图方程。设P(x，…，x，y，…，y)=0是一指数刁番图方程，则形如

yy…y［P(x，…，x，y，…，y)=0］

的谓词称为指数刁番图谓词，其外延集｛(x，…，x)｜y，…y［p(x，…x，y，…y)=0］｝

称为指数刁番图集。

戴维斯和普特南在一项(至今未得到证明的)假设：“存在任意有穷长的全由素数组成的等差数列”之下，证明了：每个递归可枚举集都是指数刁番图集。

随后，J．罗宾逊检查了他们的证明，发现那项假设是不必要的，于是综合上述三人的结果就是：每个递归可枚举集都是指数刁番图集。将这个结果和上述J．罗宾逊1952年的结果联系起来，就意味着只要找到一个(一个变元依另一个变元)以指数率增长的刁番词谓词，就可以证明“每个递归可枚举集都是刁番图集”，从而希尔伯特第十问题不可解。

1970年，ю．马蒂亚谢维奇终于证明：“x是第2n个斐波那契数”是刁番图谓词。所谓斐波那契数是指自然数列

1，1，2，3，5，8，13，21，…

(从第三项起，每项都是前两项之和。)第2n个斐波那契数就是上述序列的偶数项子列

1，3，8，21，… (* *)

利用归纳法容易证明x＜2(k是(* *)中的序号)。

综合上述所有结果就得到戴维斯-普特南-罗宾逊-马蒂亚谢维奇定理。每个递归可枚举集都是刁番图集。从而希尔伯特第十问题不可解。