Turing 归约

形式陈述 ​

对语言 $A,B\subseteq {\mathrm{\Sigma }}^{\ast }$，若存在一台以 $B$ 为预言机并对所有输入停机的预言机图灵机公理库预言机图灵机Oracle Turing machine可在一步内查询某固定语言成员资格的相对可计算性模型。 $M^B$，满足

$$x\in A⟺M^B(x)\text{ 接受},$$

则称 $A$ Turing 归约到 $B$，记作 $A{\le }_{T}B$。机器可提出有限多次查询，后一次查询可依赖前面收到的答案；正、负预言机答案都能参与后续计算。若 $A{\le }_{T}B$ 且 $B$ 可判定，则用 $B$ 的判定器替代预言机即可判定 $A$。该关系可传递。

在经典可计算性中，${\le }_T$ 不附带时间或查询次数上界。复杂度理论中的 polynomial-time Turing reduction（Cook reduction）还要求外层机器在多项式时间内运行，因而查询数和查询长度也受多项式约束。

直觉 ​

映射归约公理库映射归约Mapping reduction · Many-one reduction用可计算函数把一个语言成员关系变换为另一个语言成员关系。像一次性编译：把源实例翻译成一个目标实例。Turing 归约则把目标问题当作可反复调用的子程序。算法可以根据第一次回答决定第二次问什么，因此它表达的不只是实例翻译，还包括与黑盒进行有限轮、自适应的计算。

归约方向仍表示“有了 $B$ 就能解决 $A$”。所以要用已知困难的 $A$ 证明 $B$ 困难，需要构造 $A{\le }_{T}B$，而不是反向。预言机的内部成本被忽略，只衡量外层如何使用答案。

例子与边界 ​

任意映射归约 $A{\le }_{m}B$ 都给出 Turing 归约：计算唯一的查询 $f(x)$，询问它是否属于 $B$，并原样返回答案。反过来通常不成立，因为 Turing 机器可以多次、自适应查询。

每个语言与其补集彼此 Turing 归约：

$$A{\le }_T\bar{A},\bar{A}{\le }_{T}A,$$

只需查询同一个输入并翻转答案。这个现象清楚显示 Turing 归约比 many-one 归约更灵活；many-one 归约若要求成员与非成员同向保存，不能简单靠翻转一个 oracle bit 表达所有同样关系。

查询必须由一台实际的外层图灵机有限地产生，不能把“知道 $B$ 的全部答案”当作无限建议写进程序。若机器只在 $x\in A$ 时停机，它至多给出相对可识别性，不足以定义这里的判定型归约。经典 ${\le }_T$ 也不能直接用来证明多项式时间 hardness，因为它可能进行极慢计算或超长查询。

推论与应用 ​

定义 $A{\equiv }_{T}B$ 当且仅当 $A{\le }_{T}B$ 且 $B{\le }_{T}A$，可计算性理论据此把语言分成 Turing degrees，比较不可计算信息的相对强弱。停机问题给出比可判定集合更高的计算能力，而对“带停机预言机的机器是否停机”再次对角化会产生更高层级。

Turing 归约也澄清可判定性公理库可判定性Decidability · Recursive language存在对每个输入都停机并正确回答是或否的算法这一性质。的传递：目标预言机若可由普通算法实现，整个外层计算就能去预言机化。复杂度语境则应使用受资源限制的归约公理库多项式时间归约Polynomial-time reduction · Karp reduction用一个多项式时间可计算的变换把问题 A 的实例转换为问题 B 的实例。并明确是 many-one 还是 Turing 版本，不能仅写“归约”后混用两者的闭包性质。

参考资料

• Hartley Rogers Jr., Theory of Recursive Functions and Effective Computability, MIT Press, 1987, Chs. 9–13, relative computability and degrees.
• Robert I. Soare, Recursively Enumerable Sets and Degrees, Springer, 1987, Chs. I–III, Turing reducibility and degree structure.
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013, Ch. 5, reducibility and oracles.