Chapter 5 | Undecidability¶

约 4869 个字预计阅读时间 24 分钟

引言：我们为什么要学这一章？¶

在之前的课程中，我们设计了各种自动机（DFA, PDA, TM）来解决问题。

本章的核心问题是：在这个世界上，是否存在图灵机（电脑）永远无法解决的问题？

答案是肯定的。这一章就是要画出“计算”的边界。

邱奇-图灵论题 (Church-Turing Thesis)¶

什么是“算法”？¶

在图灵机出现之前，人们对“算法”只有一个模糊的直觉。PPT 展示了函数定义的几种形式：

基本函数：零函数、后继函数等。

原始递归函数 (Primitive Recursive)：可以通过固定次数的循环计算出来的函数。

\(\mu\)-递归函数 (\(\mu\)-Recursive)：引入了 while 循环（最小化算子），允许无限循环。

关键结论：

\[\text{直觉上的算法} \approx \text{图灵机 (Turing Machine)}\]

邱奇-图灵论题 (The Thesis)¶

论题内容：任何在直觉上被认为是“可计算”的过程，都可以由一台图灵机来实现。

这不是一个可以被数学证明的定理，因为它连接了一个模糊的概念（直觉算法）和一个严格的数学模型（图灵机）。它是一个假设或公理。

至今为止，我们发明的所有计算模型（Lambda 演算、递归函数、现代计算机、量子计算机）在可计算能力上都等价于图灵机。

语言的层级¶

这是一个非常重要的地图，请务必记在脑子里：

Regular (正则语言)：由 DFA/NFA 识别。

Context-Free (上下文无关)：由 PDA 识别。

Context-Sensitive (上下文有关)：由线性有界自动机 (LBA) 识别。

Recursive (递归语言 / 可判定)：图灵机一定会停机并给出 Yes/No。这是我们最喜欢的状态。

Recursively Enumerable (R.E. / 递归可枚举)：图灵机对于 Yes 的输入会停机，但对于 No 的输入可能会死循环 (Loop)。这是“半可判定”。

Undecidable (不可判定)：圆环最外面的部分，图灵机根本搞不定的问题。

通用图灵机 (Universal Turing Machines, UTM)¶

思想起源¶

如果每解决一个问题都要造一台专门的机器（像早期的织布机），太麻烦了。我们能不能造一台机器 \(U\)，它可以模拟任何其他机器 \(M\)？

这就是软件的思想，\(U\) 就是硬件（CPU），输入给它的 \(M\) 就是软件代码。

编码 (Encoding)：如何把机器变成数据？¶

为了让 \(U\) 读懂 \(M\)，我们需要把 \(M\) 的状态、符号、转移函数都变成 \(\{0, 1\}\) 字符串。

数学编码规则：

符号编码：假设符号集合 \(\Sigma\)，用 \(a0^j\) 形式编码。

例如：空格 \(\sqcup \to a000\), \(\triangleright \to a001\)。

状态编码：假设状态集合 \(K\)，用 \(q\) 后接二进制编码。

例如：\(s \to q00\), \(q \to q01\), \(h \to q11\)。

转移函数 \(\delta\) 编码：

一条指令 \(\delta(q, a) = (p, b)\) 变成一个四元组字符串。

整个机器 \(M\) 就是一串长长的四元组列表。

我们用 \(\langle M \rangle\) 表示机器 \(M\) 编码后的字符串。

UTM 的工作原理¶

通用图灵机 \(U\) 接收输入 \(\langle M, w \rangle\)（即机器 \(M\) 的代码和它的输入 \(w\)）。

\[U(\langle M \rangle, w) = M(w)\]

模拟过程：

\(U\) 有三条纸带：

Tape 1: 存放 \(M\) 的纸带内容（工作区）。

Tape 2: 存放 \(M\) 的代码描述 \(\langle M \rangle\)（查询区）。

Tape 3: 存放 \(M\) 当前的状态（寄存器）。

逻辑：\(U\) 每次看一眼 Tape 1 的符号和 Tape 3 的状态，去 Tape 2 查表找到对应的指令，然后更新 Tape 1 和 Tape 3。

停机问题 (The Halting Problem)¶

为什么会有不可判定问题？(计数论证)¶

图灵机的数量是可数的 (Countable)，因为每个 TM 都可以编码成一个整数。

语言（问题的集合）的数量是不可数的 (Uncountable)。

结论：甚至都不用构造，从数学上讲，绝大多数语言都是图灵机无法识别的。

停机问题的定义¶

\[H = \{ \langle M \rangle w \mid \text{TM } M \text{ 在输入 } w \text{ 上会停机} \}\]

我们想知道：是否存在一个算法（图灵机），输入任意一段代码 \(M\) 和输入 \(w\)，能百分之百告诉我们 \(M\) 是死循环还是会停机？

对角线法证明 (Diagonalization Proof)¶

这是反证法 (Proof by Contradiction)。

假设：\(H\) 是递归的（可判定的）。即存在一个万能检测机 \(M_0\)，它总是能停机并回答 Yes/No。

\[M_0(\langle M, w \rangle) = \begin{cases} \text{Yes (Accept)}, & \text{如果 } M \text{ 在 } w \text{ 上停机} \\ \text{No (Reject)}, & \text{如果 } M \text{ 在 } w \text{ 上死循环} \end{cases}\]

构造：我们利用 \(M_0\) 构造一个捣乱的机器 \(D\) (Diagonal)，它的输入只有 \(\langle M \rangle\)：

\(D\) 调用 \(M_0(\langle M, \langle M \rangle \rangle)\)（即问 \(M_0\)：如果把 \(M\) 的代码喂给 \(M\) 自己，它会停机吗？）

如果 \(M_0\) 说“会停机”：\(D\) 就故意进入死循环。

如果 \(M_0\) 说“死循环”：\(D\) 就立即停机。

矛盾时刻：

现在，把 \(D\) 自己的代码 \(\langle D \rangle\) 喂给 \(D\) 运行，即计算 \(D(\langle D \rangle)\)：

如果 \(D\) 在 \(\langle D \rangle\) 上停机 \(\to\) 说明 \(M_0\) 判定它死循环 \(\to\) 矛盾！

如果 \(D\) 在 \(\langle D \rangle\) 上死循环 \(\to\) 说明 \(M_0\) 判定它停机 \(\to\) 矛盾！

结论：假设不成立，\(H\) 是不可判定的（Not Recursive）。

\(H\) 与 \(\overline{H}\) 的性质¶

\(H\) 是 R.E. (递归可枚举) 的：因为我们可以运行 UTM 模拟 \(M\)。如果 \(M\) 停机，UTM 就会停机说 Yes。但如果 \(M\) 死循环，UTM 也会死循环（无法输出 No）。

\(\overline{H}\) (停机问题的补集，即“死循环问题”) 不是 R.E. 的。

定理：如果一个语言 \(L\) 和它的补集 \(\overline{L}\) 都是 R.E. 的，那么 \(L\) 必定是 Recursive 的。

因为 \(H\) 不是 Recursive，所以 \(\overline{H}\) 连 R.E. 都不是。这意味着：我们甚至无法写程序来“确认”一个程序死循环了（它可能下一秒就停机，也可能永远不停，我们永远不知道）。

归约 (Reduction) —— 问题的传染性¶

什么是归约？¶

归约是一种将新问题转化为旧问题的技巧。

记号：\(L_1 \leq L_2\) （\(L_1\) 归约到 \(L_2\)）。

意思是：如果我有解决 \(L_2\) 的万能神器（Subroutine），我就能造出解决 \(L_1\) 的机器。

数学定义：

存在一个可计算函数 \(\tau: \Sigma^* \to \Sigma^*\)，使得：

\[x \in L_1 \iff \tau(x) \in L_2\]

归约的逻辑方向（千万别搞反！）¶

定理：如果 \(L_1\) 是不可判定的，且 \(L_1 \leq L_2\)，那么 \(L_2\) 也是不可判定的。

直觉：\(L_1\) 已经是一个已知的“绝症”（如停机问题）。如果我们能证明解决 \(L_2\) 就能顺便解决 \(L_1\)，那说明 \(L_2\) 至少和 \(L_1\) 一样难。因为 \(L_1\) 无解，所以 \(L_2\) 肯定也无解。

经典归约案例¶

PPT 中展示了几个经典的不可判定问题，都是通过从 \(H\)（通用停机问题）归约而来的：

空带停机问题 (Halting on Empty Tape)¶

问题：给定 \(M\)，它在空输入 \(\epsilon\) 上会停机吗？

归约方法 (\(H \to\) 空带问题)：

输入是 \(\langle M, w \rangle\)。

构造新机器 \(M_w\)：不管输入什么，先把自己纸带清空，写上 \(w\)，然后模拟 \(M\)。

这样：\(M_w\) 在空带上停机 \(\iff M\) 在 \(w\) 上停机。

如果空带问题可解，通用停机问题就可解。矛盾。

在任意输入上停机 (Halting on Some Input)¶

问题：\(M\) 是否至少在一个输入上停机？

构造：修改 \(M\) 变成 \(M'\)，\(M'\) 忽略真实输入，强行把纸带换成 \(\epsilon\) 并运行原机器逻辑。

在所有输入上停机 (Halting on Every Input / Total)¶

问题：\(M\) 是不是一个完备的算法（永不死循环）？

这也是不可判定的。

机器等价性 (Equivalence)¶

问题：\(L(M_1) = L(M_2)\) 吗？

这比停机问题更难，同样不可判定。

有限自动机的空语言检测¶

问题: 给定 DFA \(M\)，判定 \(L(M) = \emptyset\)。
答案: 这是可判定的 (Decidable)！别看到“空语言”就觉得不可判定。
理由: DFA 的状态是有限的。我们只需要从起始状态开始，做一次 BFS/DFS (广度/深度优先搜索)。如果在图中能走到任何一个接受状态，就不空；如果走不到，就是空。这不需要运行机器，只需要分析图结构。

语言的可数性¶

问题: \(L = \{ \langle M \rangle \mid L(M) \text{ 是可数的} \}\)。
答案: 递归的 (Recursive)（即这个问题是废话）。
理由: 任何图灵机识别的语言 \(L(M)\) 都是 \(\Sigma^*\) 的子集。\(\Sigma^*\) 本身是可数无限集，所以它的任何子集都是可数的。所有图灵机都满足这个条件。所以这个判定器只需要一直输出 Yes 即可。

包含偶数个 b¶

问题: \(L_{even} = \{ \langle M \rangle \mid L(M) \text{ 至少包含一个有偶数个 b 的串} \}\)。
归约: \(H \leq L_{even}\)。
构造: 给定 \(\langle M, w \rangle\)。构造 \(M'\)：

\(M'\) 接收输入 \(x\)。
如果 \(x \neq \epsilon\) (空串包含0个b，是偶数)，直接拒绝（或者做其他处理，只要保证不干扰）。
如果 \(x = \epsilon\)，则运行 \(M\) 在 \(w\) 上。
如果 \(M\) 停机，则 \(M'\) 接受 \(x\)。

分析:

\(M\) 停机 \(\to M'\) 接受 \(\epsilon\) \(\to L(M')\) 包含 \(\epsilon\) (0个b) \(\to\) Yes。
\(M\) 死循环 \(\to M'\) 谁也不接受 \(\to L(M')\) 为空 \(\to\) No。

语言大小为 2024¶

问题: \(L_{2024} = \{ \langle M \rangle \mid |L(M)| = 2024 \}\)。
归约: \(H \leq L_{2024}\)。
构造: 给定 \(\langle M, w \rangle\)。构造 \(M'\)：

\(M'\) 接收输入 \(x\)。
\(M'\) 首先运行 \(M\) 在 \(w\) 上（把这作为守门员）。
如果 \(M\) 停机，那么 \(M'\) 检查 \(x\) 是否属于某个特定的集合 \(A\)（\(A\) 是我们预设好的、刚好有2024个字符串的集合）。
如果 \(x \in A\)，接受；否则拒绝。

分析:

\(M\) 停机 \(\to M'\) 变成了识别 \(A\) 的机器 \(\to |L(M')| = 2024 \to\) Yes。
\(M\) 死循环 \(\to M'\) 卡在第一步，谁也不接受 \(\to |L(M')| = 0 \neq 2024 \to\) No。

R.E. 语言的性质与枚举¶

枚举 (Enumeration)¶

定义：一个 TM \(M\) 枚举语言 \(L\)，是指 \(M\) 可以不断地打印出属于 \(L\) 的字符串 \(w_1, w_2, \dots\)。这个机器打印出的所有串的集合就是它枚举的语言。

定理：一个语言是 R.E. 的 \(\iff\) 它有一个枚举器。

R.E. 的全称就是 Recursively Enumerable。如果 \(L\) 是 R.E. 的，我们可以用“Dovetailing (交替模拟/鸽巢)”技术：模拟所有可能的 \(w\)，第一步模拟 \(w_1\)，第二步模拟 \(w_1, w_2\)，第三步模拟 \(w_1, w_2, w_3\)... 谁停机了就打印谁。

词典序枚举 (Lexicographical Enumeration)¶

定义: 如果机器打印的字符串是按字典序排列的（长度短的在前，同长度的按字母表排），且不重复，这就是词典序枚举。

输出流: \(a, b, aa, ab, ba, bb \dots\)

关键区别: 普通枚举可能先打印长的，再打印短的，甚至永远不知道后面还有没有短的。但词典序枚举是有序的。

定理: 语言 \(L\) 是 递归的 (Recursive/Decidable) \(\iff\) \(L\) 可以被词典序枚举。

证明思路:

\(\Rightarrow\): 如果 \(L\) 可判定，我就按顺序生成 \(\Sigma^*\) 的所有串 \(s_1, s_2 \dots\)，每个都扔给判定器。如果是 Yes 就打印，No 就丢掉。因为判定器不卡死，所以我能按顺序一直打印。
\(\Leftarrow\): 如果 \(L\) 能被词典序枚举。给定一个输入 \(w\)，我就启动枚举器看着它打印。

如果打印出了 \(w\)，我就输出 Yes。
如果打印出了一个比 \(w\) 更长（或字典序更后）的字符串，我就知道 \(w\) 永远不会出现了（因为是按顺序排队的），所以我可以直接输出 No。
这就避免了死等，所以是可判定的！

莱斯定理 (Rice's Theorem)¶

莱斯定理 (Rice's Theorem) —— 必考点¶

这个定理是判断不可判定性的“大杀器”。

定理内容：

对于关于 R.E. 语言的任何非平凡 (non-trivial) 属性，判定一个图灵机 \(M\) 识别的语言 \(L(M)\) 是否满足该属性，是不可判定的。

公式化：

令 \(P\) 是 R.E. 语言的一个子集（即一种性质）。

如果：

\(P \neq \emptyset\) （至少有一个语言满足它）

\(P \neq \text{所有 R.E. 语言}\) （至少有一个语言不满足它）

那么，判定 \(\langle M \rangle \in P\) 是不可判定的。

例子：

“\(L(M)\) 是空的吗？” \(\to\) 不可判定。

“\(L(M)\) 是有限集吗？” \(\to\) 不可判定。

“\(L(M)\) 是正则语言吗？” \(\to\) 不可判定。

“\(L(M)\) 包含字符串 'hello' 吗？” \(\to\) 不可判定。

注意：莱斯定理是关于语言（输入输出行为）的性质，而不是关于机器本身（代码结构）的性质。

“\(M\) 有 5 个状态” \(\to\) 这是可判定的（数一下代码就行），不适用莱斯定理。

“\(M\) 接受空串” \(\to\) 这是关于语言的，不可判定。

证明思路总结 (Proving Strategies)¶

证明某个语言是非 \(\text{REC}\) 的 (Proving a Language is Non-Recursive / Undecidable)¶

证明一个语言 \(A\) 是不可判定的（即 \(A \notin \text{REC}\)），有两种主要方法：

归约 (Reduction) 法：

找到一个从 \(H\) 或其他已知非 \(\text{REC}\) 的语言到 \(A\) 的归约。
思路：如果存在 \(L_{non-REC} \le A\)，且 \(L_{non-REC}\) 已知是不可判定的（例如，停机问题 \(H\)），那么根据归约定理， \(A\) 也一定是不可判定的。

反证法 (Contradiction) / 对角线法 (Diagonalization)：

或者使用反证法。
思路：假设 \(A\) 是可判定的，即存在一个总是停机的 TM \(M_A\)。利用 \(M_A\) 来构造一个会产生矛盾的 TM \(M_{diag}\)（类似于证明停机问题不可判定性的方法）。

为什么说是对角线法

在计算理论中，证明像停机问题这类问题不可判定时，同样使用了类似的“对角线”构造：

假设某个语言 \(\text{A}\) 是可判定的（即存在一个总是停机的图灵机 \(\text{M}_A\) 可以判定它）。
我们将所有图灵机 \(\text{M}_1, \text{M}_2, \text{M}_3, \dots\) 看作是“行”，将所有可能的输入 \(w_1, w_2, w_3, \dots\) 看作是“列”。
创建一个无限表格，表格中的每个单元格 \((i, j)\) 表示图灵机 \(\text{M}_i\) 在输入 \(w_j\) 上的行为（例如：接受、拒绝或死循环）。
利用假设中存在的判定机 \(\text{M}_A\)，构造一个新的图灵机 \(\text{M}_{\text{diag}}\)。这个 \(\text{M}_{\text{diag}}\) 的核心逻辑是针对对角线元素进行“反转”：

\(\text{M}_{\text{diag}}\) 在输入 \(\text{M}_i\) 的编码时，会模拟 \(\text{M}_i\) 在它自己（\(\text{M}_i\) 的编码）上的行为（这是对角线元素）。
然后 \(\text{M}_{\text{diag}}\) 会做出与 \(\text{M}_i(\text{M}_i)\) 相反的判定：如果 \(\text{M}_i\) 接受 \(\text{M}_i\)，那么 \(\text{M}_{\text{diag}}\) 就拒绝；如果 \(\text{M}_i\) 拒绝 \(\text{M}_i\)，那么 \(\text{M}_{\text{diag}}\) 就接受。

最终，这个新构造的图灵机 \(\text{M}_{\text{diag}}\) 的行为会与所有图灵机列表中的任何一个图灵机都不同，因为它在输入 \(\text{M}_i\) 的编码时，会与 \(\text{M}_i\) 产生相反的结果。而任何图灵机都必须在那个无限的列表中，这就导致了矛盾，证明了最初的假设是错误的，即 \(\text{A}\) 是不可判定的。

因此，这种通过关注并构造一个在对角线位置上与列表中所有元素都“不同”的新对象（新数 \(\text{x}\) 或新机器 \(\text{M}_{\text{diag}}\)）来导出矛盾的证明方法，都被统称为对角线法。

莱斯定理 (Rice's Theorem)：

或者使用 Rice's Theorem。
思路：莱斯定理指出，任何关于 TM 语言的非平凡性质都是不可判定的。如果 \(A\) 描述的是 TM 语言 \(L(M)\) 的一个性质（如“\(L(M)\) 是正则的”、“\(L(M)\) 是空集”等），只要这个性质不是对所有 TM 都成立或对所有 TM 都不成立（即非平凡），那么 \(A\) 就是不可判定的。

证明某个语言是 \(\text{REC}\) 的 (Proving a Language is Recursive / Decidable)¶

证明一个语言 \(A\) 是可判定的（即 \(A \in \text{REC}\)），有三种主要方法：

构造 \(\text{TM}\) decide \(A\)：

构造一个 TM 总是停机并判定 \(A\)。
思路：直接设计一个 TM \(M_A\)，证明它对于任何输入 \(w\) 都能在有限时间内停在接受状态 \(y\) 或拒绝状态 \(n\)。

归约法 (Reduction) - 逆用：

或者找到一个从 \(A\) 到已知 \(\text{REC}\) 语言的归约。
思路：如果存在 \(A \le L_{REC}\)，且 \(L_{REC}\) 已知是可判定的，那么根据归约定理， \(A\) 也是可判定的。

互补法 (Complement) - 利用 \(\text{RE}\) 封闭性：

或者使用 Lemma. \(A\) 是 \(\text{REC}\) \(\iff\) \(A\) 和 \(\overline{A}\) 都是 \(\text{RE}\) 的。
思路：如果可以证明语言 \(A\) 是递归可枚举的（构造半判定 TM \(M_A\)），并且它的补集 \(\overline{A}\) 也是递归可枚举的（构造半判定 TM \(M_{\overline{A}}\)），则 \(A\) 必定是递归的。

证明某个语言是非 \(\text{RE}\) 的 (Proving a Language is Non-Recursively Enumerable)¶

证明一个语言 \(A\) 是非递归可枚举的（即 \(A \notin \text{RE}\)），有两种主要方法：

互补法 (Complement) - 利用 \(H\)：

使用 Lemma. \(A\) 是 \(\text{REC}\) \(\iff\) \(A\) 和 \(\overline{A}\) 都是 \(\text{RE}\) 的。

思路：

找到一个已知非 \(\text{REC}\) 的语言 \(L\)（例如 \(H\)）。
证明 \(L\) 是 \(\text{RE}\) 的。
根据引理，\(L\) 不是 \(\text{REC}\) 的 意味着 \(\overline{L}\) 一定不是 \(\text{RE}\) 的（否则 \(L\) 就是 \(\text{REC}\) 的了）。
找到一个从 \(\overline{L}\) 到 \(A\) 的归约 \(f\)，即 \(\overline{L} \le A\)。
因为 \(\overline{L}\) 是非 \(\text{RE}\) 的，所以 \(A\) 也必然是非 \(\text{RE}\) 的。

归约法 (Reduction) - 逆用：

或者找到已知非 \(\text{RE}\) 的语言到 \(A\) 的归约。
思路：如果存在 \(L_{non-RE} \le A\)，且 \(L_{non-RE}\) 已知是非 \(\text{RE}\) 的（例如 \(H_d\) 或 \(\overline{H}\)），那么 \(A\) 也一定是非 \(\text{RE}\) 的。

证明某个语言是 \(\text{RE}\) 的 (Proving a Language is Recursively Enumerable)¶

证明一个语言 \(A\) 是递归可枚举的（即 \(A \in \text{RE}\)），有两种主要方法：

构造 \(\text{TM}\) semidecide \(A\)：

构造一个 TM \(M_A\)，使得当且仅当 \(w \in A\) 时，\(M_A\) 停机并接受。
思路：直接设计一个 TM \(M_A\)，证明它只在输入属于 \(A\) 时停机（对于 \(w \notin A\) 的输入，它可能永远运行）。

归约法 (Reduction)：

或者找到一个从 \(A\) 到已知 \(\text{RE}\) 语言的归约。
思路：如果存在 \(A \le L_{RE}\)，且 \(L_{RE}\) 已知是 \(\text{RE}\) 的，那么 \(A\) 也是 \(\text{RE}\) 的。