跳跃逆转定理

Template:Expert Template:No footnotes 跳跃逆转定理是递归论中关于不可解度的三个定理，定理给出满足特定条件的不可解度的“图灵逆跳跃”的存在性。

定理

弗里德堡定理

设 $B{\ge }_T{\mathrm{𝟎}}^{\prime }$，则存在 $A$ 使 $A^{\prime }{\equiv }_{T}B$。

肖恩菲尔德定理

设 $B{\ge }_T{\mathrm{𝟎}}^{\prime }$ 且可用具备 ${\mathrm{𝟎}}^{\prime }$ 的预言机递归枚举，则存在 $A{\le }_T{\mathrm{𝟎}}^{\prime }$ 使 $A^{\prime }{\equiv }_{T}B$。

萨克斯定理

设 $B{\ge }_T{\mathrm{𝟎}}^{\prime }$ 且可用具备 ${\mathrm{𝟎}}^{\prime }$ 的预言机递归枚举，则存在递归可枚举集合 $A$ 使 $A^{\prime }{\equiv }_{T}B$。

定理

• 波斯特定理
• 克莱尼–波斯特定理
• 弗里德堡–穆奇尼克定理
• 波斯纳–罗宾逊定理

参考资料

• Template:Cite web
• Template:Cite book