希尔伯特第十问题

设计一个通用算法，对任意给定的丢番图方程（未知数为一个或多个、系数为整数的多项式方程），能在有限步骤内判定它是否存在整数解。

这一否定性解答如今称为MRDP定理（马季亚谢维奇–罗宾逊–戴维斯–普特南定理），是分阶段建立起来的。1953年，马丁·戴维斯猜想：每一个整数的递归可枚举集恰好是某个丢番图方程族的解集——这正是把（源自图灵停机问题的）不可判定性转移到数论中所需的关键想法。朱莉娅·罗宾逊指出了一个必不可少的技术要素：一个呈指数增长的丢番图关系（「JR假设」）。1961年，戴维斯、希拉里·普特南与罗宾逊证明了戴维斯猜想针对指数丢番图方程的一个版本，把整个问题归约为寻找一个确实是丢番图（多项式）性质的指数增长关系。尤里·马季亚谢维奇于1970年补上了这最后一块拼图，证明斐波那契数列满足一个丢番图条件，从而完成了证明，表明这样的算法不可能存在。