跳跃逆转定理
2020-06-14 21:11:33
跳跃逆转定理是递归论中关于不可解度的三个定理,定理给出满足特定条件的不可解度的“图灵逆跳跃”的存在性。
设
,则存在 使 。设
且可用具备 的预言机递归枚举,则存在 使 。设
且可用具备 的预言机递归枚举,则存在递归可枚举集合 使 。跳跃逆转定理是递归论中关于不可解度的三个定理,定理给出满足特定条件的不可解度的“图灵逆跳跃”的存在性。
设
,则存在 使 。设
且可用具备 的预言机递归枚举,则存在 使 。设
且可用具备 的预言机递归枚举,则存在递归可枚举集合 使 。