什么是不可解度

从比较计算难易程度出发来研究自然数子集分类的递归论分支。在某种标准下计算难度相同的集合形成这种标准下的一个度。递归论中研究得比较多的两种度是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)B)。若

且

则称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]的基数相同，[Ο，Ο┡]也存在类似的稠密性质。[Ο，Ο┡]是上半格但不是格，每一个可数分配格都可嵌入 [Ο，Ο┡]中。存在一对非Ο的递归可枚举度，它们的最大下界是Ο；不存在一对非Ο的递归可枚举度，它们的最大下界是Ο而最小上界则是Ο┡。

研究在[Ο，Ο┡]上的偏序性质特别是代数结构性质是不可解度理论的重要内容。