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，这时不能再把“至少”擅自收紧成等价。

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

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

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

也就是说， $A$ 能计算一个最终支配每个总可计算函数的函数，恰好等价于其 jump 至少达到 $0''$ 。若再有 $A\le_T0'$ ——特别地，若 $A$ c.e.——单调性给出 $A'\le_T0''$ ，左侧便收紧为本页采用的 $A'\equiv_T0''$ 。因此 c.e. 假设不是支配定理本身的前提，而是把“至少达到”改写成“恰好等于”时所需的上界。

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

例子与边界

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

更能揭示边界的是 high incomplete c.e. sets 的存在。构造时，一组要求确保 $A$ 不计算 $0'$ ，另一组把一个支配所有可计算函数的 $A$ -可计算函数编码进枚举。粗略地说，在阶段 $s$ 观察前 $e$ 个程序是否出现新的收敛，用 $A$ 的可变标记记录“最后一次变化以后”的大数；优先 restraint 防止对角化要求与支配标记无限互伤。有限伤害或 permitting 验证最终给出 $A<_T0'$ ，却仍有 $A'\equiv_T0''$ 。因此 high 绝不等同于 Turing complete。

仅有 $A\le_T0'$ 也不推出 high：任意可计算 $A$ 都满足这个上界，但 $A'\equiv_T0'$ ，低于 $0''$ 。取补集不会把 high 变 low，因为 $A\equiv_T\overline A$ 导致两者 jump 等价；补集通常还会离开 c.e. 范围。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 与各种低性、高性类值得单独研究的原因。

使用 high 一词时必须同时核对对象范围。若 oracle 不受 $A\le_T0'$ 约束，只知道 $0''\le_TA'$ ，它的 jump 可能远高于 $0''$ ；此时沿用 $A'\equiv_T0''$ 会丢掉真实强度。反过来，在 c.e. 范围内，上界由 $A\le_T0'$ 自动给出，证明 high 只需建立 $0''\le_TA'$ 。

参考资料

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 构造。

形式陈述 ​

反向链接

形式陈述