[科普中国]-跳跃逆转定理

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

定理弗里德堡定理设 ，则存在 使 。1

肖恩菲尔德定理设 且可用具备 的预言机递归枚举，则存在 使 。2

萨克斯定理设 且可用具备 的预言机递归枚举，则存在递归可枚举集合 使 。

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所