第5章：可归约性（Reducibility）

一、导读

1.1 本章学习目标

第5章讲解归约技术——通过将一个问题转化为另一个问题来证明不可判定性。

1.2 为什么第五章如此重要

归约是计算理论中最强大的证明工具。通过归约，可以将一个已知不可判定的问题转化为新问题，从而证明新问题也不可判定。

1.3 核心问题引导

什么是图灵可归约性？

映射可归约性是什么？

如何用归约证明不可判定性？

归约的传递性有什么意义？

二、核心概念详解

5.1 图灵可归约性

语言 $A$ 图灵可归约于语言 $B$（$A \leq_T B$），如果存在一个图灵机，使用 $B$ 作为预言机（oracle），可以判定 $A$。

直觉：如果 A ≤_T B，则 B "至少和 A 一样难"
如果 B 可判定，则 A 也可判定
等价地：如果 A 不可判定，则 B 也不可判定

5.2 映射可归约性

语言 $A$ 映射可归约于语言 $B$（$A \leq_m B$），如果存在一个可计算函数 $f$，使得对所有 $w$：

$$w \in A \iff f(w) \in B$$

映射可归约比图灵可归约更强
映射可归约意味着：
- 可以将 A 的实例转换为 B 的实例
- 通过解决 B 来解决 A

5.3 用归约证明不可判定性

证明：$HALT_{TM} = \{\langle M, w \rangle \mid M \text{ 在 } w \text{ 上停机}\}$ 不可判定。

证明：已知 $A_{TM}$ 不可判定。证明 $A_{TM} \leq_m HALT_{TM}$。

构造函数 $f$：

• 输入 $\langle M, w \rangle$
• 构造图灵机 $M'$：在输入 $x$ 上，$M'$ 模拟 $M$ 在 $x$ 上的运行

- 如果 $M$ 接受 $x$，$M'$ 接受

- 如果 $M$ 拒绝 $x$，$M'$ 进入无限循环

• 输出 $\langle M', w \rangle$

则：$M$ 接受 $w$ $\iff$ $M'$ 在 $w$ 上停机 $\iff$ $\langle M', w \rangle \in HALT_{TM}$

因此 $A_{TM} \leq_m HALT_{TM}$，所以 $HALT_{TM}$ 不可判定。

三、实战案例

5.1 归约链

已知不可判定：A_TM
    ↓ 归约
停机问题 HALT_TM
    ↓ 归约
空性问题 E_TM
    ↓ 归约
等价性问题 EQ_TM

每个问题都通过归约从前一个问题推导其不可判定性

四、本章小结

归约是证明不可判定性的核心工具。图灵可归约和映射可归约是两种主要的归约方式。通过归约链，可以证明越来越多的问题不可判定。

五、思考与练习

图灵可归约和映射可归约有什么区别？

如何用归约证明新问题不可判定？

归约的传递性意味着什么？

有哪些问题是可判定的？

归约在实际编程中有什么应用？