跳跃逆转定理

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

定理

编辑

弗里德堡定理

编辑

 ,则存在   使  

肖恩菲尔德定理

编辑

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

萨克斯定理

编辑

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

定理

编辑

参考资料

编辑