[拼音]：bukejiedu

[外文]：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)

一切递归集形成一个度，用Ο表示递归集的度。因为任何集 B与递归集A有关系，所以对任何度a都有Ο≤a，即Ο是小的度。用Ο┡表示完备集K的度，显然任何完备集都在度Ο┡中。因为K不是递归集，故有Ο<Ο┡。用[Ο，Ο┡]表示度类{a:Ο≤a≤Ο┡}。

一个度中若有一个递归可枚举集，则称这个度为递归可枚举度。因为Ο┡是完备集的度，所以对任何递归可枚举度a都有Ο≤a≤Ο┡。是否有递归可枚举度a使Ο

称 为 A的跃变，把A的跃变记为A┡。 度a=deg(A)的跃变度记为 a┡=deg(A┡)。度Ο的跃变度是Ο┡。对于任何递归可枚举度a，它的跃变度a┡满足Ο┡≤a┡≤Ο″，若有Ο┡=a┡则称递归可枚举度 a为低度，若有Ο″=a┡则称a为高度。

存在度α使Ο<α<Ο┡且对任何度b若b≠Ο则b≮α，这样的度a叫极小度。不存在非Ο的递归可枚举度是极小度。[Ο，Ο┡]的基数与实数区间[0，1]的基数相同，[Ο，Ο┡]也存在类似的稠密性质。[Ο，Ο┡]是上半格但不是格，每一个可数分配格都可嵌入 [Ο，Ο┡]中。存在一对非Ο的递归可枚举度，它们的较大下界是Ο；不存在一对非Ο的递归可枚举度，它们的较大下界是Ο而小上界则是Ο┡。

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

严正声明：本文由历史百科网注册或游客用户建柏自行上传发布关于» 不可解度的内容，本站只提供存储，展示，不对用户发布信息内容的原创度和真实性等负责。请读者自行斟酌。同时如内容侵犯您的版权或其他权益，请留言并加以说明。站长审查之后若情况属实会及时为您删除。同时遵循 CC 4.0 BY-SA 版权协议，尊重和保护作者的劳动成果，转载请标明出处链接和本声明内容：作者：建柏；本文链接：https://www.freedefine.cn/wenzhan/134841.html