查看“︁不可解度”︁的源代码

'''不可解度'''，或'''图灵度'''（Turing degree），是[[数学逻辑]]的名词，尤其应用在[[可计算性理论]]中。

== 定义 ==

假设一个[[图灵机]]程序可以随意获取[[自然数函数]]<math>g</math>的值（即使<math>g</math>不可计算），且该图灵机计算自然数函数<math>f</math>，则定义函数<math>f</math>由函数<math>g</math> '''[[图灵]]可计算'''，记作<math>f\le_T g</math>。符合以上特点的图灵机称为具备函数<math>g</math>的[[预言机]]。若集合<math>B</math>的[[特征函数]]可计算集合<math>A</math>，则<math>A\le_T B</math>。

在计算机科学和数理逻辑中，自然数集合的图灵度或者不可解度是对此集合的算法不可解性的度量。图灵度在可计算理论中是根本性的概念，在可计算理论里，自然数集合通常被看作一个判定问题，而图灵度则给出了解决与此集合相连的判定问题的困难程度。

如果两集合<math>A,B</math>有同一不可解度（也即两者互相图灵可计算），则称两集合为'''图灵等价'''，记作<math>A\equiv_T B</math>。图灵等价是一个[[等价关系]]，其等价类称作不可解度。图灵可计算关系是所有不可解度的[[搜集]]上的[[偏序]]。所有可计算集合（也即图灵等价于[[空集]]的集合）的不可解度为<math>\mathbf{0}</math>（零度）。

所有不可解度的搜集记作<math>\mathcal{D} </math>。

== 图灵跳跃 ==

图灵跳跃算符是不可解度上的[[算符]]。设<math>A</math>为一集合，则其图灵跳跃<math>A^\prime</math>的不可解度，为所有具备集合<math>A</math>的[[停机问题]]的预言机的集合的不可解度。

零度的图灵跳跃是[[停机问题]]的不可解度，也即<math>\mathbf{0}^\prime </math>。

== 图灵锥 ==
设<math>C</math>为不可解度，则所有可计算<math>C</math>的不可解度的搜集<math>\operatorname{Cone}(C) := \{ D \in \mathcal{D} \;\vert\; D\ge_T C \}</math>叫做<math>C</math>上的图灵锥。

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

== 参考资料 ==
* {{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:遞歸論|B]]