第 9 章不可判定性

编码、对角化、归约、Rice 定理与 PCP

Source scope
主要依据教材第 9 章：中文印刷页 255–286，对应 PDF p.268 左右至 p.299/301。教材主线包括非递归可枚举语言、递归语言与 RE 语言、通用语言、图灵机相关不可判定问题、归约、Rice 定理与 Post 对应问题。

1 0. 本章核心问题

第 8 章给出通用计算模型，第 9 章问：

是否每个数学定义清楚的问题都存在算法？

答案是否定的。

本章最重要的工具不是某一个“经典不可判定问题”，而是三种证明机制：

对角化；
归约；
语义性质定理（Rice 定理）。

2 1. 编码：把机器变成字符串

为了让图灵机“读取另一台图灵机”，必须把机器本身编码成有限字符串。

可以对状态、带符号、转移编号，再编码成二进制串。具体编码格式不重要，关键是：

每个合法 TM 有有限编码 \(\langle M\rangle\)；
编码可以被算法解析；
机器和输入可组合成 \(\langle M,w\rangle\)。

这使“程序作为数据”成为数学对象。

3 2. 可数性与对角化

所有有限二进制串是可数的，因此所有图灵机也是可数的。

但所有二进制语言是

\[ \mathcal P(\{0,1\}^*), \]

这是不可数集合。

因此：

存在不可由任何图灵机识别的语言。

这是一个基数论层面的存在证明。

3.1 2.1 对角语言

按某种方式枚举图灵机 \(M_1,M_2,\dots\) 与输入串 \(w_1,w_2,\dots\)，定义对角语言，让它在第 \(i\) 个位置故意与 \(M_i\) 对 \(w_i\) 的行为相反。

若某台机器声称识别该对角语言，把它放回自己的对角位置就产生矛盾。

4 3. 递归语言与递归可枚举语言

4.1 3.1 递归可枚举（RE / recognizable）

语言 \(L\) 是 RE，如果存在 TM \(M\)：

\(w\in L\) 时，\(M\) 最终接受；
\(w\notin L\) 时，\(M\) 可以拒绝，也可以永远运行。

4.2 3.2 递归（decidable）

语言 \(L\) 递归，如果存在判定器对每个输入都停机，并正确回答接受/拒绝。

显然：

\[ \text{Recursive}\subseteq \text{RE}. \]

4.3 3.3 一个重要补关系

若 \(L\) 和 \(\overline L\) 都是 RE，则 \(L\) 实际上可判定。

证明：并行交错模拟识别 \(L\) 与识别 \(\overline L\) 的两台机器。任一输入必属于二者之一，所以最终总有一台接受，从而可停机作答。

5 4. 通用语言与不可判定性

定义通用接受语言

\[ A_{TM}=\{\langle M,w\rangle\mid M\text{ 接受 }w\}. \]

它是 RE：通用 TM 只需模拟 \(M\) 在 \(w\) 上运行。

但它不可判定。

5.1 4.1 自引用证明结构

假设存在判定器 \(H\) 判断 \(\langle M,w\rangle\in A_{TM}\)。

构造机器 \(D\)，输入 \(\langle M\rangle\) 时故意反转 \(H\) 对 \(\langle M,\langle M\rangle\rangle\) 的答案。

再让 \(D\) 读取自己的编码 \(\langle D\rangle\)，得到

\[ D\text{ 接受 }\langle D\rangle \iff D\text{ 不接受 }\langle D\rangle, \]

矛盾。

6 5. 归约

若想证明问题 \(B\) 不可判定，常从已知不可判定问题 \(A\) 出发构造：

\[ A\le_m B. \]

这意味着存在可计算函数 \(f\)，使

\[ x\in A\iff f(x)\in B. \]

如果 \(B\) 有判定算法，那么先计算 \(f(x)\) 再调用 \(B\) 的算法，就能判定 \(A\)，矛盾。

6.1 5.1 方向一定要记住

证明 \(B\) 难：

\[ \boxed{\text{已知难问题 }A \longrightarrow \text{目标问题 }B} \]

不是反过来。

7 6. 与图灵机有关的不可判定问题

经典目标包括：

是否接受某个输入；
是否在某输入上停机；
机器语言是否为空；
机器语言是否有限/无限；
两台机器语言是否相等。

这些往往通过把 \(A_{TM}\) 的实例“嵌入”目标机器行为证明不可判定。

8 7. Rice 定理

Rice 定理给出一个极强原则：

图灵机所识别语言的任何非平凡语义性质都是不可判定的。

“语义性质”指只依赖 \(L(M)\)，不依赖机器代码写法。

“非平凡”指：

至少有一个 RE 语言具有该性质；
至少有一个 RE 语言不具有该性质。

例如：

“\(L(M)\) 是否为空”；
“\(L(M)\) 是否有限”；
“\(L(M)\) 是否正则”；

都属于非平凡语义性质，因此不可判定。

而“机器是否有 17 个状态”是语法性质，不由 Rice 定理直接覆盖。

9 8. Post 对应问题 PCP

给定若干“骨牌”

\[ \frac{x_i}{y_i}, \]

问是否存在非空索引序列 \(i_1,\dots,i_k\)，使

\[ x_{i_1}x_{i_2}\cdots x_{i_k} = y_{i_1}y_{i_2}\cdots y_{i_k}. \]

PCP 的惊人之处在于：规则极其简单，却不可判定。

教材先讨论“修改版 PCP”（MPCP），再通过归约完成 PCP 不可判定性证明。

10 9. 归约证明的写作模板

证明目标问题 \(B\) 不可判定：

选一个已知不可判定语言 \(A\)；
假设 \(B\) 有判定器 \(R\)；
给定任意 \(x\)，构造 \(f(x)\)；
证明 \[x\in A\iff f(x)\in B;\]
用 \(R(f(x))\) 判定 \(A\)；
与 \(A\) 不可判定矛盾。

必须同时说明：

构造 \(f\) 是可计算的；
两个方向的“当且仅当”都成立。

11 10. 常见错误

把“不可判定”写成“运行时间太长”；
归约方向反了；
只证明 \(x\in A\Rightarrow f(x)\in B\)，漏掉反向；
Rice 定理用在机器的语法属性上；
把 RE 与 recursive 混淆；
以为不可判定语言一定不可识别；实际上 \(A_{TM}\) 就是 RE 但不可判定。

12 11. 本章知识地图

Encoding machines as strings
        ↓
Diagonalization ──→ languages not even RE
        ↓
A_TM : RE but undecidable
        ↓
Reductions
  ├─ Halting-like problems
  ├─ language properties
  ├─ Rice theorem
  └─ PCP / grammar problems