High 集 | Codeboy's Blog

形式陈述

本页固定经典 c.e. degree 理论的口径：自然数集合先经标准有效编码看作可识别语言；这样的 c.e. 集 $A$ 称为 high，若

A'\equiv_T0''.

由于 c.e. 集满足 $A\le_T0'$ ，跳跃单调性给 $A'\le_T0''$ ；high 条件断言这个上界被达到。这里 $A'$ 与 $0''$ 是Turing 跳跃， $\equiv_T$ 比较degree而非字面相等。对任意已知 $A\le_T0'$ 的集合，同一等式也可作为 high 定义；若完全取消这个上界，一些文献用 $0''\le_TA'$ 定义广义 high，允许跳跃高于 $0''$ 。

一般化的 high $_n$ 常在 $A\le_T0'$ 或 c.e. 范围内写作 $A^{(n)}\equiv_T0^{(n+1)}$ 。不同作者对广义 high、generalized high $_n$ 的基准略有区别，引用结果时必须抄全量词和 join 条件。本页只固定最常用的一阶 c.e. 口径。

High 衡量的是 jump 的强度。它既不等于 $A=0'$ ，也不要求 $A$ 能直接判定普通停机问题；事实上存在 Turing 不完备却 high 的 c.e. 集。

含有这种 c.e. 代表的 Turing 等价类称为 high c.e. degree。跳跃条件在等价类内不变，但其他代表未必仍是 c.e.；因此 high 集与 high degree 分别指代表和承载该不变性质的商类。

直觉

所有 c.e. 集都能由 $0'$ 判定，所以它们的 jump 最多到 $0''$ 。High 集虽然可能没有完整的 $0'$ 信息，却把有限阶段的枚举安排得足够复杂，使“使用 $A$ 的程序会不会停机”已经能编码第二跳的全部难度。Low 集使 jump 停在最低可能的 $0'$ ；high 集则使 jump 抵达 c.e. 范围允许的天花板。

Martin 的支配刻画在任意 oracle $A$ 上都可写成

0''\le_TA' \quad\Longleftrightarrow\quad \exists f:\mathbb N\to\mathbb N\;\bigl[f\le_TA\;\land\;\forall g\,(g\text{ 总可计算}\Rightarrow \exists N\,\forall n\ge N\;f(n)>g(n))\bigr].

也就是说， $A$ 能计算一个最终支配每个总可计算函数的函数，恰好等价于其 jump 至少达到 $0''$ 。若再有 $A\le_T0'$ ——特别地，若 $A$ c.e.——单调性给出 $A'\le_T0''$ ，左侧便收紧为本页采用的 $A'\equiv_T0''$ 。在 c.e. 范围内，证明 high 因而只需建立下界 $0''\le_TA'$ 。

High 因而描述一种间接强度：预言机未必回答所有 $0'$ 查询，却能通过自己的枚举时机和可计算函数捕捉下一层全性信息。把它翻译成“集合元素很多”或“枚举得很快”都不正确；有限改动不会改变 degree，更不会改变 high 性。

例子与边界

标准例子是 $A=0'$ 。它是 c.e.，且按定义 $(0')'=0''$ ，所以 high。这个例子同时校准方向：high 要比较 $A'$ 与 $0''$ ，不能写成 $A'\equiv_T0'$ ；后者正是 low 条件。

Sacks 证明存在 high 但 Turing 不完备的 c.e. 集。一个构造方法同时建立 c.e. 集 $A,C$ ：对每个预言机程序 $\Phi$ ，安排 $C\ne\Phi^A$ ，于是 $C\not\le_TA$ ；由于 $C\le_T0'$ ，这也保证 $A<_T0'$ 。

高性要求则把 $\Pi^0_2$ 完备集 $\mathrm{INF}=\{e:W_e\text{ 无限}\}$ 编入一个 $A$ -可计算的稳定近似。相对化 Shoenfield 极限定理于是给出 $\mathrm{INF}\le_TA'$ ，再由完备性得到 $0''\le_TA'$ 。两组要求通过无限伤害优先构造协调，分别控制 $A$ 本身的计算能力与它跳跃后的计算能力；这解释了不完备性为何能与高性共存。

仅有 $A\le_T0'$ 也不推出 high：任意可计算 $A$ 都满足这个上界，但 $A'\equiv_T0'$ ，低于 $0''$ 。取补集不会把 high 变 low，因为 $A\equiv_T\overline A$ 导致两者 jump 等价；补集也不再是 c.e.：否则两边都可枚举会使 $A$ 可计算，与 high 性矛盾。Low 集与 high 集在 c.e. degrees 中互斥，却不是逻辑否定关系：大量 c.e. degrees 既不 low 也不 high。

推论与应用

Highness 把 degree 理论中的二阶停机信息转成可操作的函数增长条件。研究 c.e. 集合的枚举、可计算结构的谱或算法随机性时，支配函数往往比直接模拟 $A'$ 更方便；证明仍需指出刻画所依赖的归约和对象范围，不能把“能压过若干已见函数”误作最终支配全部可计算函数。

High/low 二分也显示 jump 会压缩不同信息。可能有 $A<_T0'$ 却 $A'\equiv_T0''$ ，也可能有不可计算 $B$ 却 $B'\equiv_T0'$ ；所以从 $A'$ 的位置无法恢复 $A$ 的唯一 degree。Jump 不是单射，这正是 jump inversion 与各种低性、高性类值得单独研究的原因。

参考资料

Robert I. Soare, Recursively Enumerable Sets and Degrees, Springer, 1987，p. 71 及 Chapter IV，high degrees 与支配函数刻画。
S. Barry Cooper, Computability Theory, Chapman & Hall/CRC, 2004，章节 “The Jump Operator and High/Low Degrees”。
Gerald E. Sacks, Degrees of Unsolvability, Princeton University Press, 1966，Chapters III–IV，jump、inversion 与 c.e. degree 构造。
Steffen Lempp, Priority Arguments in Computability Theory，3.2 节 Theorem 7：high incomplete c.e. degree 的无限伤害构造。

形式陈述 ​

反向链接

形式陈述