Turing degree

一个集合可被看作无限问答表。若有了 $B$ 的完整成员资格问答器便能计算 $A$，就说 $B$ 至少携带解决 $A$ 所需的信息。Degree 忽略问答表的表面编码，只保留彼此可有效翻译的信息量：把停机实例编码成单带机器、寄存器机或程序—输入对，得到的字面集合不同，只要翻译可双向计算，它们便属于同一 degree。

“信息量”在这里是偏序而非一个实数分数。两个集合可能各自解决对方不能解决的问题，因而无法比较；写成 degree 不是把它们强行排进一条难度排行榜。Join 则像把两本互不覆盖的问答手册装订在一起：偶奇标记让两部分都可取回，任何同时能计算 $A$ 和 $B$ 的预言机也能计算这份装订本，因此它确是最小共同上界。

Degree 还刻意忘掉效率。一个归约可以运行极久、提出很多自适应查询，只要每个输入最终停机即可。两个问题在 Turing degree 上相同，不意味着它们在多项式时间、查询次数或实际数据表示上同样困难；这里只衡量绝对可计算能力。

任意有限集合 $F$ 都可由把其元素写进程序的判定器处理，所以 ${\mathrm{deg}}_T(F)=\mathbf{0}$；偶数集、素数集等可判定无限集合也在同一 degree。取对角停机集 $K=\{e:{\mathrm{\Phi }}_e(e)\downarrow \}$ 与成对停机集 $H=\{⟨e,x⟩:{\mathrm{\Phi }}_e(x)\downarrow \}$。从 $K$ 到 $H$，把 $e$ 映成 $⟨e,e⟩$；从 $H$ 到 $K$，有效产生一个索引 $q(e,x)$，其程序忽略自身输入并模拟 ${\mathrm{\Phi }}_e(x)$。于是 $K{\equiv }_{T}H$，二者代表 ${\mathbf{0}}^{\prime }$，但绝非同一个自然数集合。

对 join，若查询 $2n$ 就读出 $n\in A$，查询 $2n+1$ 就读出 $n\in B$，所以 $A,B{\le }_{T}A\oplus B$。反之，给定任意 $C$ 且 $A,B{\le }_{T}C$，先看输入奇偶，再调用相应的 $C$-预言机程序，即得 $A\oplus B{\le }_{T}C$。这段可复算的编码证明了“最小上界”，而不只是画出一个向上的箭头。

边界首先是归约口径。互相 many-one 可归约必然推出 Turing 等价，但反向不成立；Turing degree 会合并更多集合。其次，$A\subseteq B$ 与 $A{\le }_{T}B$ 没有一般蕴含关系：集合包含谈哪些数出现，归约谈能否用询问 $B$ 的算法决定 $A$。最后，degree 的符号 ${\mathbf{0}}^{\prime }$ 表示等价类；把它和某个具体编码的 $0^{\prime }$ 混用，在只谈 degree 时无妨，在讨论 many-one 完全性或索引变换时却可能丢失必要的统一性。

Post 的问题问是否存在 c.e. degree 严格夹在 $\mathbf{0}$ 与 ${\mathbf{0}}^{\prime }$ 之间。Friedberg–Muchnik 定理给出肯定答案，并且构造了互不可比的 c.e. degrees；这说明“可计算—停机完备”之间不是空档，也说明 c.e. 集合没有按难度排成链。优先法由此成为构造 degree、同时满足一列相互干扰要求的核心技术。

跳跃在 degree 上严格递增：$\mathbf{a}<{\mathbf{a}}^{\prime }$。它为 low/high 定义提供共同坐标，也通过 jump inversion、density 与 minimal degree 等定理揭示偏序的局部结构。需要强调，某个 c.e. 集合 Turing 不完备只说明其 degree 小于 ${\mathbf{0}}^{\prime }$；是否 simple、low 或 high 是额外性质，不能从“不完备”一个词推出。

Turing degree 还帮助区分结果的编码依赖性。若结论只依赖 degree，研究者可以选择最方便的代表元和配对函数；若结论涉及一一归约、程序索引或可计算置换，就必须回到具体集合。Myhill 同构定理比 Turing 等价强得多，正因为它保留了足够的有效结构来构造整个自然数集上的置换。