跳跃逆转定理
![]() | 此條目需要精通或熟悉相关主题的编者参与及协助编辑。 (2014年4月23日) |
跳跃逆转定理是递归论中关于不可解度的三个定理,定理给出满足特定条件的不可解度的“图灵逆跳跃”的存在性。
定理
弗里德堡定理
设 ,则存在 使 。
肖恩菲尔德定理
萨克斯定理
设 且可用具备 的预言机递归枚举,则存在递归可枚举集合 使 。
定理
参考资料
- 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 (英语).
![]() | 这是一篇关于数学的小作品。您可以通过编辑或修订扩充其内容。 |