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

阿兰·图灵在其1936年关于可计算数的奠基性论文中,定义了一个精确的计算数学模型(图灵机),并用一个对角线式的自指论证证明了停机问题是不可判定的:集合 $K = \{ e : \Phi_e(e){\downarrow} \}$(即以自身代码作为输入时会停机的程序代码 $e$)不存在能对每个 $e$ 都正确判定成员关系的算法。

然而 $K$ 仍然是递归可枚举的:一个算法可以在输入 $e$ 上逐步模拟程序 $e$,一旦模拟停机就输出 $e$;对于 $e \notin K$,它只是永远不会终止,因此它能确认成员关系,却永远无法确定地否定它。$K$ 是r.e.但不可判定集合的典型例子,基本上每一个经典的不可判定性结果都以某种方式归约到它。

根据上一步证明的MRDP定理,递归可枚举的 $K$ 本身必定是丢番图的:存在一个多项式 $P$,使得 $e \in K \iff \exists x_1, \ldots, x_n\, P(e, x_1, \ldots, x_n) = 0$。这恰好为最后一步所需要的归约铺平了道路,以便把图灵的不可判定性结果转移到希尔伯特第十问题上。