不可解度

在计算机科学和数理逻辑中，不可解度（以艾伦图灵的名字命名）或一组自然数的不可解度衡量了该集合的算法不可解性水平。

不可解度的概念是可计算性理论的基础，自然数集通常被视为决策问题。 一个集合的不可理解度是衡量解决与该集合相关的决策问题的难易程度，即判断一个任意数是否在给定集合中的难易程度。

如果两个集合具有相同的不可解性级别，则它们是图灵等价的； 每个不可解度都是图灵等价集的集合，因此当两个集不是图灵等价时，它们处于不同的不可解度。 此外，不可解度是部分有序的，因此如果集合 X 的不可解度小于集合 Y 的不可解度，则任何（不可计算的）正确判断数字是否在 Y 中的过程都可以有效地转换为 一个正确决定数字是否在 X 中的过程。从这个意义上说，一个集合的不可解度对应于它的算法不可解性级别。

不可理解度由 Emil Leon Post (1944) 引入，许多基本结果由 Stephen Cole Kleene 和 Post (1954) 建立。 从那时起，不可理解度一直是一个深入研究的领域。 该领域的许多证明都使用称为优先级方法的证明技术。

对于本文的其余部分，词集将指代一组自然数。 如果有一个 oracle 图灵机在给定 Y 中的成员资格的 oracle 时决定 X 中的成员资格，则称集合 X 可图灵化简为集合 Y。符号 X ≤T Y 表示 X 可图灵化简为 Y。

如果 X 是图灵可归约到 Y 并且 Y 是图灵可归约到 X，则两个集合 X 和 Y 被定义为图灵等价。符号 X ≡T Y 表示 X 和 Y 是图灵等价的。 关系 ≡T 可以看作是等价关系，这意味着对于所有集合 X、Y 和 Z：

• X ≡T X
• X ≡T Y 表示 Y ≡T X
• 如果 X ≡T Y 且 Y ≡T Z，则 X ≡T Z。

A不可解度是关系≡T的等价类。 符号 [X] 表示包含集合 X 的等价类。不可解度的整个集合表示为 D {\displaystyle {\mathcal {D}}} 。

不可解度有一个偏序 ≤ 定义，因此 [X] ≤ [Y] 当且仅当 X ≤T Y。存在一个包含所有可计算集的xxx不可解度，并且这个度数小于其他所有度数。 它表示为 0（零），因为它是偏序集 D {\displaystyle {\mathcal {D}}} 的最小元素。 （通常对不可理解度使用粗体符号，以便将它们与集合区分开来。当不会发生混淆时，例如 [X]，则不需要粗体。）

对于任何集合 X 和 Y，X join Y，写作 X ⊕ Y，被定义为集合 {2n : n ∈ X} 和 {2m+1 : m ∈ Y} 的并集。 X ⊕ Y 的不可解度是 X 和 Y 的度数的最小上限。因此 D {\displaystyle {\mathcal {D}}} 是一个连接半格。 度数 a 和 b 的最小上限表示为 a ∪ b。 众所周知，D {\displaystyle {\mathcal {D}}} 不是格，因为存在没有xxx下界的度数对。

对于任何集合 X，符号 X' 表示将 X 用作预言机时暂停（当给定索引作为输入时）的预言机索引集。 集合X'称为X的图灵跳跃。度[X]的图灵跳跃定义为度[X']； 这是一个有效的定义，因为只要 X ≡ T Y，X' ≡T Y'。一个关键的例子是 0'，即停机问题的程度。

• 每个不可解度都是可数无限的，也就是说，它恰好包含 ℵ 0 {\displaystyle \aleph _{0}} 集合。
• 有 2 ℵ 0 {\displaystyle 2{\aleph _{0}}} 不同的不可解度。
• 对于每个度 a 严格不等式 a <; a′成立。
• 对于每个度数 a，低于 a 的度数集合是可数的。 大于 a 的度数集大小为 2 ℵ 0 {\displaystyle 2{\aleph _{0}}} 。

对不可理解度的结构进行了大量研究。 以下调查仅列出了众多已知结果中的一部分。 从研究中可以得出的一个普遍结论是，不可解度的结构极其复杂。

• 学位很少。 如果 a 不为零并且在 0 和 a 之间没有度数，则 a 度数是最小的。 因此度数的顺序关系不是稠密顺序。
• 不可解度不是按≤T线性排序的。
• 事实上，对于每个非零度数 a，都有一个度数 b 与 a 无法比较。
• 有一组 2 ℵ 0 {\displaystyle 2{\aleph _{0}}} 成对不可比的不可解度。
• 存在没有xxx下界的度数对。 因此 D {\displaystyle {\mathcal {D}}} 不是格子。
• 每个可数偏序集都可以是