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

集合 $S \subseteq \mathbb{Z}_{\ge 0}$ 是递归可枚举的(r.e.),或者说可枚举的,是指存在一个算法,只要给足时间,就能按某种顺序恰好输出 $S$ 的元素(不保证会停机,也不要求对非成员说明任何情况)。集合 $S$ 是丢番图的,是指存在一个整数系数多项式 $P$,使得 $a \in S \iff \exists x_1, \ldots, x_n \in \mathbb{Z}_{\ge0}$ 且 $P(a, x_1, \ldots, x_n) = 0$。

“丢番图 $\implies$ r.e.”这一蕴含是显然的:按对角线方式遍历所有元组 $(x_1, \ldots, x_n)$ 与所有候选值 $a$,一旦找到解就输出 $a$。反方向的蕴含——每个r.e.集合都是丢番图的——则远非显然,因为多项式方程看起来比任意算法那种灵活的逐步逻辑要僵硬得多,是纯粹代数性质的工具。

马丁·戴维斯在1953年猜想这两个概念事实上完全重合;下一步将精确陈述这个猜想及其意义。