Turing 归约 | Codeboy's Blog

形式陈述

对语言 $A,B\subseteq\Sigma^*$ ，若存在一台以 $B$ 为预言机并对所有输入停机的预言机图灵机 $M^B$ ，满足

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

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

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

直觉

映射归约像一次性编译：把源实例翻译成一个目标实例。Turing 归约则把目标问题当作可反复调用的子程序。算法可以根据第一次回答决定第二次问什么，因此它表达的不只是实例翻译，还包括与黑盒进行有限轮、自适应的计算。

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

例子与边界

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

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

A\le_T\overline A,\qquad \overline A\le_TA,

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

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

推论与应用

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

Turing 归约也澄清可判定性的传递：目标预言机若可由普通算法实现，整个外层计算就能去预言机化。复杂度语境则应使用受资源限制的归约并明确是 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.