不可解度

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

定义

假设一个图灵机程序可以随意获取自然数函数${\displaystyle g}$的值（即使${\displaystyle g}$不可计算），且该图灵机计算自然数函数${\displaystyle f}$，则定义函数${\displaystyle f}$由函数${\displaystyle g}$ 图灵可计算，记作${\displaystyle f\leq _{T}g}$。符合以上特点的图灵机称为具备函数${\displaystyle g}$的预言机。若集合${\displaystyle B}$的特征函数可计算集合${\displaystyle A}$，则${\displaystyle A\leq _{T}B}$。

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

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

所有不可解度的搜集记作${\displaystyle {\mathcal {D}}}$。

图灵跳跃

图灵跳跃算符是不可解度上的算符。设${\displaystyle A}$为一集合，则其图灵跳跃${\displaystyle A^{\prime }}$的不可解度，为所有具备集合${\displaystyle A}$的停机问题的预言机的集合的不可解度。

零度的图灵跳跃是停机问题的不可解度，也即${\displaystyle \mathbf {0} ^{\prime }}$。

图灵锥

设${\displaystyle C}$为不可解度，则所有可计算${\displaystyle C}$的不可解度的搜集${\displaystyle \operatorname {Cone} (C):=\{D\in {\mathcal {D}}\;\vert \;D\geq _{T}C\}}$叫做${\displaystyle C}$上的图灵锥。

定理

• 波斯特定理
• 克莱尼–波斯特定理
• 弗里德堡–穆奇尼克定理
• 波斯纳–罗宾逊定理
• 跳跃逆转定理

参考资料

• Robert I. Soare. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer. 2004. ISBN 9780387152998 （英语）.