计算机科学

首页 > 计算机科学

跳跃逆转定理

2018-07-20 15:04:11    

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

目录

  • 1 定理
    • 1.1 弗里德堡定理
    • 1.2 肖恩菲尔德定理
    • 1.3 萨克斯定理
  • 2 参考资料

定理

弗里德堡定理

,则存在 使

肖恩菲尔德定理

且可用具备 的预言机递归枚举,则存在 使

萨克斯定理

且可用具备 的预言机递归枚举,则存在递归可枚举集合 使

参考资料

  • Rodney G. Downey, Steffen Lempp, and Richard A. Shore. Jumps of Minimal Degress Below (PDF). [2014-04-23] (英语).  参数|title=值左起第32位存在删除符 (帮助)
  • Robert I. Soare. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer. 2004. ISBN 9780387152998 (英语). 

相关推荐