热门问题
时间线
聊天
视角
跳跃逆转定理
来自维基百科,自由的百科全书
Remove ads
跳跃逆转定理是递归论中关于不可解度的三个定理,定理给出满足特定条件的不可解度的“图灵逆跳跃”的存在性。
![]() | 此条目需要精通或熟悉相关主题的编者参与及协助编辑。 (2014年4月23日) |
定理
设 ,则存在 使 。
Remove ads
设 且可用具备 的预言机递归枚举,则存在递归可枚举集合 使 。
Remove ads
定理
- 波斯特定理
- 克莱尼–波斯特定理
- 弗里德堡–穆奇尼克定理
- 波斯纳–罗宾逊定理
参考资料
- Rodney G. Downey, Steffen Lempp, and Richard A. Shore. Jumps of Minimal Degress Below (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 (英语).
![]() | 这是一篇关于数学的小作品。您可以通过编辑或修订扩充其内容。 |
Remove ads
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads