查看“︁跳跃逆转定理”︁的源代码

{{expert|time=2014-04-23T07:11:14+00:00}}
{{no footnotes|time=2014-04-23T07:11:14+00:00}}
'''跳跃逆转定理'''是[[递归论]]中关于[[不可解度]]的三个定理，定理给出满足特定条件的不可解度的“图灵逆跳跃”的存在性。

== 定理 ==
=== 弗里德堡定理 ===
设 <math>B\ge_T\mathbf{0}^\prime</math>，则存在 <math>A</math> 使 <math>A^\prime\equiv_T B</math>。

=== 肖恩菲尔德定理 ===
设 <math>B\ge_T\mathbf{0}^\prime</math> 且可用具备 <math>\mathbf{0}^\prime</math> 的[[预言机]][[递归可枚举集合|递归枚举]]，则存在 <math>A\le_T\mathbf{0}^\prime</math> 使 <math>A^\prime\equiv_T B</math>。

=== 萨克斯定理 ===
设 <math>B\ge_T\mathbf{0}^\prime</math> 且可用具备 <math>\mathbf{0}^\prime</math> 的预言机递归枚举，则存在递归可枚举集合 <math>A</math> 使 <math>A^\prime\equiv_T B</math>。

== 定理 ==
* [[波斯特定理]]
* [[克莱尼–波斯特定理]]
* [[弗里德堡–穆奇尼克定理]]
* [[波斯纳–罗宾逊定理]]

== 参考资料 ==
* {{cite web|author=Rodney G. Downey, Steffen Lempp, and Richard A. Shore|title=Jumps of Minimal Degress Below <math>\mathbf{0}^\prime</math>|url=http://www.math.cornell.edu/~shore/papers/pdf/minfin822.pdf|accessdate=2014-04-23|language=en|format=PDF}}
* {{cite book|language=en|author=Robert I. Soare|title=Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets|year=2004|publisher=Springer|isbn=9780387152998}}

[[Category:递归论]]
[[Category:计算机科学]]

{{数学小作品}}