第4章：可判定性（Decidability）

一、导读

1.1 本章学习目标

第4章探讨什么是"可判定的"——哪些问题可以被算法解决，哪些不能。图灵证明了停机问题是不可判定的。

1.2 为什么第四章如此重要

可判定性理论揭示了计算的根本限制。理解哪些问题不可计算，是理解计算本质的关键。

1.3 核心问题引导

什么是可判定语言？

停机问题是什么？为什么不可判定？

对角化方法是什么？

还有哪些问题是不可判定的？

二、核心概念详解

4.1 可判定语言

一个语言是可判定的，如果存在一个图灵机在每一步都停机，并且接受该语言中的所有字符串、拒绝不在该语言中的字符串。

可判定语言类：
正则语言 ⊂ 上下文无关语言 ⊂ 可判定语言 ⊂ 图灵可识别语言

4.2 停机问题

定理：$A_{TM} = \{\langle M, w \rangle \mid M \text{ 是图灵机，} M \text{ 接受 } w\}$ 是图灵可识别的，但不是可判定的。

证明（反证法）：

假设存在图灵机 $H$ 判定 $A_{TM}$：

• $H(\langle M, w \rangle)$ 接受，如果 $M$ 接受 $w$
• $H(\langle M, w \rangle)$ 拒绝，如果 $M$ 不接受 $w$

构造图灵机 $D$：

• $D(\langle M \rangle)$：运行 $H(\langle M, \langle M \rangle \rangle)$

- 如果 $H$ 接受，则 $D$ 拒绝

- 如果 $H$ 拒绝，则 $D$ 接受

现在考虑 $D(\langle D \rangle)$：

• 如果 $D$ 接受 $\langle D \rangle$，则 $D$ 拒绝 $\langle D \rangle$（矛盾）
• 如果 $D$ 拒绝 $\langle D \rangle$，则 $D$ 接受 $\langle D \rangle$（矛盾）

因此 $H$ 不存在，$A_{TM}$ 不可判定。

4.3 对角化方法

对角化是证明不可判定性的核心技巧：

假设有一个列表：
M₁(w₁) = 接受
M₂(w₂) = 拒绝
M₃(w₃) = 接受
...

构造 D，使得 D(Mᵢ) ≠ Mᵢ(Mᵢ)
D 不在列表中！矛盾。

4.4 不可判定问题

许多重要问题是不可判定的：

• 停机问题
• Post 对应问题
• 波斯特问题
• 希尔伯特第十问题（丢番图方程的可解性）

三、实战案例

4.1 停机问题的实际意义

假设可以判定程序是否停机：

// 这个程序会停机吗？
function f(n) {
    // 检查 n 是否是某个丢番图方程的解
    // 如果是，返回 true
    // 如果遍历所有解都找不到，继续搜索
}

// 如果能判定停机，就能解决数论中的许多未解决问题
// 但图灵证明了这是不可能的

四、本章小结

可判定性理论揭示了计算的根本限制。停机问题是不可判定的，这意味着不存在通用算法能判断任意程序是否停机。对角化方法是证明不可判定性的核心技巧。

五、思考与练习

停机问题的证明思路是什么？

对角化方法的直觉是什么？

还有哪些问题是不可判定的？

不可判定性对实际编程有什么影响？

图灵可识别和可判定有什么区别？