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）还要求外层机器在多项式时间内运行，因而查询数和查询长度也受多项式约束。

把语言有效编码为自然数集合后，同一定义用于 $A,B\subseteq\mathbb N$ 。函数版本写 $f\le_TB$ ，意为某台 $B$ -预言机对每个合法输入停机并输出总函数 $f$ 的值；集合版本正是其特征函数的情形。对自然数值总函数，这也等价于函数图 $\{(x,y):f(x)=y\}$ 可由 $B$ 判定：一方向先求值再比较，反方向依次搜索 $y$ ，总性保证恰有一个成功值。多元输入使用固定可计算元组编码。

直觉

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

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

例子与边界

任意映射归约 $A\le_mB$ 都给出 Turing 归约：计算唯一的查询 $f(x)$ ，询问它是否属于 $B$ ，并原样返回答案。反向不成立，甚至一次查询后允许翻转答案就已更强：下述停机集的补集给出反例。

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

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

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

取停机集 $K$ 。它可识别而 $\overline K$ 不可识别，所以不可能有 $\overline K\le_mK$ ：先计算映射再运行 $K$ 的识别器，否则就会识别 $\overline K$ 。但 $\overline K\le_TK$ 的翻转算法始终有效，给出两种归约的严格分离。

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

推论与应用

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

Turing 归约也澄清可判定性的传递：目标预言机若可由普通算法实现，整个外层计算就能去预言机化。复杂度语境则应使用受资源限制的归约并明确是 many-one 还是 Turing 版本，不能仅写“归约”后混用两者的闭包性质。

将同一个 oracle 交给随机性检验者，会得到相对 Martin-Löf 随机性。若 $X\le_TA$ ，oracle $A$ 能逐位生成 $X$ 的前缀检验，所以 $X$ 不可能相对于 $A$ 随机；不过被相对检验捕获，不反过来保证整条序列可由 oracle 计算。

参考资料

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.

形式陈述 ​

反向链接

形式陈述