不可解度(卷名：数学)
degrees of unsolvability
从比较计算难易程度出发来研究自然数子集分类的递归论分支。在某种标准下计算难度相同的集合形成这种标准下的一个度。递归论中研究得比较多的两种度是m度与图灵度。
设A与B是两个非负整数的子集，假若存在递归函数ƒ使得
则称A可m归约于B(见图1
)并记为
。如果A可m归约于B，就把判定x是否属于A的问题化归为判定ƒ(x)是否属于B的问题，因为ƒ是可计算函数，所以关于A的判定计算问题不难于B，而且若B是可计算的则A也是可计算的。如果
且
，则称A与B是m等价的并记为
，类
被称为A的m度。假若B是递归可枚举集且任何递归可枚举集A都可m归约于B，则称B是m完备的。关于图灵机停机问题的集合
就是一个m完备集。设B的补集为峫，要判定元素x在不在峫中，只要判定x在不在B中就可以了，因此直观上峫应该可归约于B。但是上面给出的m归约办不到这一点。例如，噖 不可m 归约于K。因此需要有新的更一般的归约标准，图灵归约(见图2
)是其中最重要的一个。称“A图灵归约于B”（或“A递归于B”，或“A相对于B可计算”）是指：有一个算法 T，当输入非负整数x时，依据该算法进行的计算过程中，可以随时向外息源询问“y是否属于B”这样的问题，并根据外息源的回答来决定下一步计算怎样进行，直到给出x是否属于A时为止。
用“
”表示"A图灵归约于B"，用“
”表示 “
且
”。记
并称其为 A的图灵度。若
则记作deg(A)≤deg(B)。若deg（A）≤deg（B）但
则记作deg(A)
且
则称deg（A）与deg(B)为不可比度。若B是递归可枚举集且对任何递归可枚举集A都有A≤iB，则称B是（图灵）完备集。K与噖 是完备集。一切递归集形成一个度，用Ο表示递归集的度。因为任何集 B与递归集A有关系
，所以对任何度a都有Ο≤a，即Ο是最小的度。用Ο′表示完备集K的度，显然任何完备集都在度Ο′中。因为K不是递归集，故有Ο<Ο′。用[Ο，Ο′]表示度类{a:Ο≤a≤Ο′}。一个度中若有一个递归可枚举集，则称这个度为递归可枚举度。因为Ο′是完备集的度，所以对任何递归可枚举度a都有Ο≤a≤Ο′。是否有递归可枚举度a使Ο<a<Ο′呢？这个问题是递归论中有名的波斯特问题。1956～1957年，A.A.穆切尼克与R.M.弗里德贝格创造了有穷损害方法证明了在[Ο，Ο′]中有两个互不可比的递归可枚举度，从而肯定地解决了波斯特问题。
称集合
为集合A的跃变，把A的跃变记为A′。 度a=deg(A)的跃变度记为 a′=deg(A′)。度Ο的跃变度是Ο′。对于任何递归可枚举度a，它的跃变度a′满足Ο′≤a′≤Ο″，若有Ο′=a′则称递归可枚举度 a为低度，若有Ο″=a′则称a为高度。存在度α使Ο<α<Ο′且对任何度b若b≠Ο则b≮α，这样的度a叫极小度。不存在非Ο的递归可枚举度是极小度。[Ο，Ο′]的基数与实数区间[0，1]的基数相同，[Ο，Ο′]也存在类似的稠密性质。[Ο，Ο′]是上半格但不是格，每一个可数分配格都可嵌入 [Ο，Ο′]中。存在一对非Ο的递归可枚举度，它们的最大下界是Ο；不存在一对非Ο的递归可枚举度，它们的最大下界是Ο而最小上界则是Ο′。
研究在[Ο，Ο′]上的偏序性质特别是代数结构性质是不可解度理论的重要内容。