跳跃逆转定理

此條目需要精通或熟悉相关主题的编者参与及协助编辑。 (2014年4月23日) 請邀請適合的人士改善本条目。更多的細節與詳情請參见討論頁。

此條目已列出參考文獻，但因為沒有文內引註而使來源仍然不明。 (2014年4月23日) 请加上合适的文內引註来改善这篇条目。

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

设 ${\displaystyle B\geq _{T}\mathbf {0} ^{\prime }}$，则存在 ${\displaystyle A}$ 使 ${\displaystyle A^{\prime }\equiv _{T}B}$。

设 ${\displaystyle B\geq _{T}\mathbf {0} ^{\prime }}$ 且可用具备 ${\displaystyle \mathbf {0} ^{\prime }}$ 的预言机递归枚举，则存在 ${\displaystyle A\leq _{T}\mathbf {0} ^{\prime }}$ 使 ${\displaystyle A^{\prime }\equiv _{T}B}$。

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

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

• Rodney G. Downey, Steffen Lempp, and Richard A. Shore. Jumps of Minimal Degress Below ${\displaystyle \mathbf {0} ^{\prime }}$ (PDF). [2014-04-23] （英语）. 
• Robert I. Soare. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer. 2004. ISBN 9780387152998 （英语）. 

这是一篇关于数学的小作品。您可以通过编辑或修订扩充其内容。 查 论 编