跳躍逆轉定理

跳躍逆轉定理是遞歸論中關於不可解度的三個定理，定理給出滿足特定條件的不可解度的「圖靈逆跳躍」的存在性。

定理

弗里德堡定理

設 ${\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 （英語）.