跳跃逆转定理

维基百科,自由的百科全书
跳到导航 跳到搜索

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

定理[编辑]

弗里德堡定理[编辑]

,则存在 使

肖恩菲尔德定理[编辑]

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

萨克斯定理[编辑]

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

定理[编辑]

参考资料[编辑]