跳转到内容

跳跃逆转定理

维基百科,自由的百科全书

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

定理

[编辑]

弗里德堡定理

[编辑]

,则存在 使

肖恩菲尔德定理

[编辑]

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

萨克斯定理

[编辑]

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

定理

[编辑]

参考资料

[编辑]