跳躍逆轉定理

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

定理

弗里德堡定理

設 $B\geq _{T}\mathbf {0} ^{\prime }$，則存在 $A$ 使 $A^{\prime }\equiv _{T}B$。

肖恩菲爾德定理

設 $B\geq _{T}\mathbf {0} ^{\prime }$ 且可用具備 $\mathbf {0} ^{\prime }$ 的預言機遞歸枚舉，則存在 $A\leq _{T}\mathbf {0} ^{\prime }$ 使 $A^{\prime }\equiv _{T}B$。

薩克斯定理

設 $B\geq _{T}\mathbf {0} ^{\prime }$ 且可用具備 $\mathbf {0} ^{\prime }$ 的預言機遞歸枚舉，則存在遞歸可枚舉集合 $A$ 使 $A^{\prime }\equiv _{T}B$。

定理

• 波斯特定理
• 克萊尼–波斯特定理
• 弗里德堡–穆奇尼克定理
• 波斯納–羅賓遜定理

參考資料

• Rodney G. Downey, Steffen Lempp, and Richard A. Shore. Jumps of Minimal Degress Below $\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 （英語）.