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

1970年,尤里·马季亚谢维奇利用由 $F_0=0, F_1=1, F_{n+1}=F_n+F_{n-1}$ 定义的斐波那契数 $F_n$,提供了所缺的JR关系。由于对黄金比例 $\varphi = (1+\sqrt{5})/2$ 有 $F_n \sim \varphi^n/\sqrt{5}$,关系 $v = F_{2u}$ 相对 $u$ 呈指数增长,恰好是鲁滨逊JR假设所要求的那种增长。

马季亚谢维奇通过利用斐波那契数之间深刻的整除恒等式——最重要的是 $F_m \mid F_n \iff m \mid n$ 与 $\gcd(F_m, F_n) = F_{\gcd(m,n)}$——并结合矩阵恒等式 $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}$,证明了 $v = F_{2u}$ 本身是丢番图的;这个矩阵恒等式把斐波那契数与一个类佩尔方程的解联系起来,使其递归定义能够重新表述为一个有限的纯多项式约束系统。

这正是鲁滨逊近二十年前分离出的JR假设本身,因此完成了鲁滨逊、戴维斯与普特南的归约链条:鲁滨逊此前已经证明由任意JR关系可以推出的幂运算、二项式系数与阶乘,现在全都真正成为丢番图的了。