Low 集

预言机 $A$ 可能含有不可计算信息，却未必让“所有使用 $A$ 的程序是否停机”产生新的一级困难。Low 性正是这种信息贫乏性的精确定量：$A$ 本身可以逃出所有普通判定器，但当观察者升到停机问题层面，它造成的复杂性仍可被 $0^{\prime }$ 完整吸收。

这像一本答案不可由普通程序全部生成的手册，但所有依赖这本手册的有限计算轨迹，仍能由普通停机预言机分析。直觉中的“没帮助”必须限定到 jump；某个 low 集依然可能解决特定不可计算问题、编码一条无限路径或满足复杂组合要求。Low 不是“近似可计算”的口号，而是一条双向 Turing 归约。

定义的两半不对称。$0^{\prime }{\le }_T{A}^{\prime }$ 对每个 $A$ 都成立，真正需要证明的是 $A^{\prime }{\le }_T{0}^{\prime }$。构造 low c.e. 集时，通常安排 $0^{\prime }$ 能判断每个 $A$-预言机计算最终是否稳定；优先论证中的 restraint 负责保护已经宣告收敛的有限 oracle use。只说 $A{\le }_T{0}^{\prime }$ 远远不够，因为许多 ${\mathrm{\Delta }}_2^0$ 集的 jump 可高达 $0^{″}$。

每个可计算集合都是 low。若 $A$ 可判定，任意 $A$-预言机计算都可把每次查询替换为 $A$ 的判定器，因此 $A^{\prime }{\le }_T{0}^{\prime }$；反向 $0^{\prime }{\le }_T{A}^{\prime }$ 是跳跃的一般性质，于是 $A^{\prime }{\equiv }_T{0}^{\prime }$。例如偶数集 $E$ 的字面跳跃 $E^{\prime }$ 取决于程序编号，却和普通停机集有相同 degree。

关键非平凡事实是存在不可计算的 low c.e. 集。一个 low simple set 的有限伤害构造同时满足两族要求：一族把元素枚举进 $A$，使每个无限 c.e. 集都碰到 $A$；另一族为计算 ${\mathrm{\Phi }}_e^A(e)$ 设置有限 use 约束，只有更高优先级动作能伤害它。每个要求最终只受有限次伤害，$0^{\prime }$ 因而能判断最终收敛结果，得到 $A^{\prime }{\le }_T{0}^{\prime }$；simple 性又保证 $A$ 不可计算。这个机制说明 low 与可计算之间确有严格空隙。

Low 不能从 $A{\le }_T{0}^{\prime }$ 单独推出。取 $A=0^{\prime }$，显然 $A{\le }_T{0}^{\prime }$，但 $A^{\prime }=0^{″}{\not\equiv }_T{0}^{\prime }$，所以它不是 low。Low 也不等于“补集容易”：$A{\equiv }_T\bar{A}$，两者同时 low 或同时不 low。与high 集理路High 集High set · High degree · 高集在 c.e. degree 语境中跳跃达到 0′′ 的集合，刻画低于 0′ 的预言机所能具有的最大 jump 强度。的并列仅比较 jump 的两个极端；它们不是集合补运算，也不是把一个定义中的数字机械改成另一个数字。

Low basis theorem 说明 Cantor 空间 $2^{\mathbb{N}}$ 中每个非空 ${\mathrm{\Pi }}_1^0$ 类都含一个 low 成员。等价地，每棵无限可计算二叉树都有一条 low 路径；这里的二叉或适当可计算有界条件不能从树版本中删除。它常被用于选取路径，同时控制这条路径的 oracle 强度；路径可以不可计算，jump 却不超过 $0^{\prime }$。这个结论的对象不必 c.e.，因此应用时要区分“low 集的一般定义”与“low c.e. degree 的结构理论”。

在 c.e. 集构造中，low 性提供了一种保守约束：满足组合或代数要求的同时，不让新集合在 jump 层面携带额外停机信息。低性方法可用于 reverse mathematics、可计算结构与算法随机性，但具体定理常需要 low${}_n$、superlow 或 K-trivial 等更强条件；普通 low 不自动继承这些结论。

Degree 观点还解释了为什么 low 是代表元不变的。若 $A{\equiv }_{T}B$，跳跃保持等价，所以 $A^{\prime }{\equiv }_T{0}^{\prime }$ 当且仅当 $B^{\prime }{\equiv }_T{0}^{\prime }$。相反，枚举速度、索引集合长相与是否 c.e. 可能随代表元改变；因此“low degree 含有一个 c.e. 代表”与“任意代表都 c.e.”是两回事。

$K$-平凡性理路K-平凡性K-triviality · K-trivial set用前缀复杂度接近长度本身的描述成本定义 K-平凡集，区分统一常数、可计算性、零维数与低性。要求所有前缀的复杂度至多为长度本身复杂度加统一常数，并等价于对 Martin-Löf 随机性低。它确实蕴含本页的跳跃低性，但条件更强；把两种“低”视为同一个定义，会丢掉它对前缀信息和相对检验的特殊约束。