补充资料：不可解度

    　　从比较计算难易程度出发来研究自然数子集分类的递归论分支。在某种标准下计算难度相同的集合形成这种标准下的一个度。递归论中研究得比较多的两种度是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≤ⁱB,则称B是（图灵）完备集。K与噖 是完备集。
　　
　　一切递归集形成一个度,用Ο表示递归集的度。因为任何集 B与递归集A有关系，所以对任何度a都有Ο≤a，即Ο是最小的度。用Ο┡表示完备集K的度，显然任何完备集都在度Ο┡中。因为K不是递归集,故有Ο<Ο┡。用[Ο,Ο┡]表示度类{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]的基数相同,[Ο,Ο┡]也存在类似的稠密性质。[Ο,Ο┡]是上半格但不是格，每一个可数分配格都可嵌入 [Ο,Ο┡]中。存在一对非Ο的递归可枚举度，它们的最大下界是Ο；不存在一对非Ο的递归可枚举度，它们的最大下界是Ο而最小上界则是Ο┡。
　　
　　研究在[Ο,Ο┡]上的偏序性质特别是代数结构性质是不可解度理论的重要内容。
　　

说明：补充资料仅用于学习参考，请勿用于其它任何用途。