MathLabs

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

第 7/9 步：完成整条链条:MRDP定理
上一步下一步
通俗地说

随着斐波那契这台增长引擎终于被证明是丢番图的,鲁滨逊此前从JR假设出发的全部自举机制一下子全都启动了:先是普通的幂运算 y=2xy = 2^x 变成丢番图的,然后是二项式系数,再然后是阶乘。

有了这些工具,就可以把任意计算机程序逐步运行的整个过程用丢番图方式编码出来——它内存与指令指针的每一个快照,都用这些快速增长的数来索引——从而完成了递归可枚举集合恰好就是丢番图集合这一证明,与戴维斯1953年的猜想精确吻合。这个综合结果现在被称为MRDP定理,以马丁·戴维斯、希拉里·普特南、朱莉娅·鲁滨逊与尤里·马季亚谢维奇的名字命名。

y=2x, (nk), n! all Diophantine  ⟹  every r.e. set is Diophantine (MRDP theorem)y = 2^x,\ \binom{n}{k},\ n! \text{ all Diophantine} \implies \text{every r.e. set is Diophantine (MRDP theorem)}
详细分析

一旦 v=F2uv = F_{2u} 被证明是丢番图的(第6步),第4步中鲁滨逊的JR机制就会依次启动:幂运算 y=2xy = 2^x 变成丢番图的(本质上是通过把 22 的幂与具有所需增长率的斐波那契型递推关联起来),然后是二项式系数函数 (nk)\binom{n}{k}(通过可归约为幂运算的生成函数恒等式),再然后是阶乘函数 n!n!。

有了阶乘与幂运算都是丢番图的,就可以用哥德尔式的编号方案,把一台图灵机整个构型历史——每个时间步的纸带内容、读写头位置与内部状态——编码为单个大数,并把“这个数编码了机器 ee 在输入 aa 上一次有效的停机计算”表达为关于 aa 与 ee 的一个丢番图条件。这就说明每个递归可枚举集合都是丢番图的,与戴维斯1953年的猜想精确吻合。

结合第2步中容易的方向(丢番图   ⟹  \implies r.e.),这就确立了MRDP定理:递归可枚举集合与丢番图集合恰好是同一个类。最后一步将利用这一等价性推导出希尔伯特第十问题的否定答案。

本步骤用到的知识
递归函数与图灵机一次不定方程