相对PA度与图灵可归约性的关系

嘿，这个问题问到点子上了——相对PA度和图灵可归约性都是计算理论与反向数学里的核心概念，理清它们的关联确实很重要。

先再明确一下你提到的定义：

根据Dzhafarov–Mummert所著Reverse Mathematics中定义2.8.24，我们称函数$f \in 2^\omega$相对于$g \in 2^\omega$具有PA度（记作$f \gg g$），当且仅当所有$f$-可计算函数构成$\Pi_1^{0, g}$类的一个基。

针对你的问题：是的，我们可以证明如果$f \gg g$，那么$f \geq_\mathrm{T} g$。

具体的推导思路其实很直观，我们可以通过构造一个特殊的$\Pi_1^{0, g}$类来完成证明：

• 首先，考虑由$g$自身构成的单点集合：${g}$。这个集合是一个$\Pi_1^{0, g}$类——因为它的补集是所有与$g$在至少一个位置上取值不同的无限二进制串，而这个补集可以用$g$作为参数写成$\Sigma_1^{0, g}$形式（简单来说，就是“存在某个$n$，使得串的第$n$位不等于$g(n)$”），所以原集合就是$\Pi_1^{0, g}$类。
• 由于$f \gg g$，根据定义，这个$\Pi_1^{0, g}$类中必须存在一个$f$-可计算的元素。但这个类里只有$g$这一个元素，所以$g$必然是$f$-可计算的，也就是$f \geq_\mathrm{T} g$。

换个更通俗的说法：既然$f$能“覆盖”所有$\Pi_1^{0, g}$类的可计算基，那连只包含$g$自己的类都能被$f$计算到，自然$f$就能算出$g$，满足图灵可归约的要求。

备注：内容来源于stack exchange，提问作者T. Asai