5_可归约性5.1.ZH解释

这段话是本章的引言，起到了承上启下的作用。

• 承上：它首先回顾了第4章的核心内容。在计算理论中，我们需要一个精确的、数学化的模型来定义什么是“计算机”以及“计算”这个过程。第4章确立了图灵机 (Turing Machine) 就是这样一个标准模型。它虽然看起来简单（一条无限长的带子、一个读写头、一组状态），但其计算能力强大到可以模拟任何现代计算机能执行的算法。这被称为丘奇-图灵论题。同时，第4章不仅展示了图灵机能“做什么”（解决一些问题），更重要的是揭示了它的“不能做什么”。它通过“对角线法”证明了存在一个图灵机无法解决的问题，即 $A_{\mathrm{TM}}$ 问题。$A_{\mathrm{TM}}$ 问题问的是：“任意给定的图灵机 $M$ 是否接受任意给定的输入字符串 $w$？”。这个问题是不可判定的，意味着不存在一个图灵机（也就是不存在任何算法），能在有限时间内对所有可能的输入 $\langle M, w \rangle$ 都给出“是”或“否”的正确答案。

• 启下：本段接着预告了本章（第5章）的主要内容。既然我们已经有了一个已知的不可判定问题 $A_{\mathrm{TM}}$，我们能否利用它来发现更多不可判定问题呢？答案是肯定的。本章将介绍一种强大的技术——可归约性 (Reducibility)，它将成为我们证明其他问题也是不可判定的主要工具。

这一段用通俗的语言定义了“归约”（Reduction）的核心思想。

归约的本质是一个“问题转换”和“方案利用”的过程。它包含两个问题，我们称之为问题 A 和问题 B。归约做了这样一件事：它提供了一个通用的方法（一个算法），可以把任何一个“问题 A 的实例”转换成一个“问题 B 的实例”。这个转换必须满足一个关键特性：转换后得到的“问题 B 的实例”的答案，可以直接或经过简单变换后，作为原来“问题 A 的实例”的答案。

换句话说，如果我们有了一个能解决问题 B 的“黑盒子”（一个能解答所有B类问题的解决方案），那么通过归约，我们就能造出一个解决问题 A 的“黑盒子”。我们把问题 A 的输入扔进我们的转换器，转换器输出一个问题 B 的输入，然后把这个新的输入扔进解决 B 的“黑盒子”，拿到答案，这个答案就是我们想要的 A 的答案。

“使得第二个问题的解决方案可以用来解决第一个问题” 这句话是关键。它建立了一种“依赖关系”：A 的解决可以依赖于 B 的解决。

这个概念并不局限于计算机科学，日常生活中比比皆是。段落中提到的例子就是为了让我们更好地理解这一点。

这是对归约概念的第一个具体例子。

• 问题 A：在一个新城市里找到路。这是一个比较复杂和宽泛的任务。
• 问题 B：获得一张这个城市的地图。这是一个更具体、更明确的目标。

这里的归约逻辑是：

1. 识别依赖关系：你意识到，如果你拥有了“地图”（问题 B 的解决方案），那么“找路”（问题 A）就会变得非常简单，甚至是水到渠成。
2. 转换问题焦点：因此，你不再直接去思考“我该怎么走？”，而是将你的精力全部投入到解决“我该去哪里搞到一张地图？”这个问题上。你把解决 A 的任务，成功地转换（归约）为解决 B 的任务。
3. 利用解决方案：一旦你通过问路、去书店购买、或用手机App下载等方式解决了问题 B（获得了地图），你就可以利用这个地图，轻松地规划路线，从而解决问题 A。

这个例子清晰地展示了归约的核心：将一个问题的求解过程，转化为对另一个问题的求解过程的调用。

这段话是对前面例子的总结，并提炼出可归约性的几个关键属性，开始向形式化定义过渡。

1. “总是涉及两个问题，我们称之为$A$和$B$”: 明确了归约关系的基本结构，它是一个二元关系，作用于两个问题之间。
2. “如果$A$归约到$B$，我们可以使用$B$的解决方案来解决$A$”: 这是归约的功能性定义。写作 $A \le_m B$ （m代表多一归约，一种常见的归约类型）。这句话的核心意思是：解决B的难度 >= 解决A的难度。因为如果你能解决B，A也就迎刃而解了。反过来说，解决A不会比解决B更难。
3. “所以在我们的例子中，$A$是找路的问题，$B$是获得地图的问题”: 将抽象的A和B对应回具体的例子，加深理解。
4. “请注意，可归约性并没有说明单独解决$A$或$B$的问题，而只是说明在有$B$的解决方案的情况下，$A$的可解性”: 这是非常关键的一点，揭示了归约的相对性。
   • 归约不告诉你B是否可解。B可能是个很简单的问题（比如1+1=?），也可能是个极难的问题，甚至可能是不可解的问题。归约本身不关心这个。
   • 归约只建立了一个“如果...那么...”的逻辑链条：如果 B可解，那么 A也可解。
   • 这个逻辑链条的逆否命题同样至关重要：如果 A不可解，那么 B也必不可少。这正是我们将要用来证明问题不可解的核心武器。

这一段通过一个“归约链”的例子，来展示归约关系是可以传递的。

这个例子建立了一个任务依赖链条：

• 问题 A: 从波士顿到巴黎旅行。
• 问题 B: 购买一张波士顿到巴黎的机票。
• 问题 C: 赚到足够买机票的钱。
• 问题 D: 找到一份能赚钱的工作。

这个链条可以表示为： $A \le B \le C \le D$。

1. A 归约到 B ($A \le B$): 要完成旅行，一个关键步骤是获得交通工具的凭证。因此，旅行问题归约到买票问题。如果你解决了B（买到了票），A就有了前提保障。
2. B 归约到 C ($B \le C$): 要买到票，你需要支付费用。因此，买票问题归约到赚钱问题。如果你解决了C（有足够的钱），B就可以解决。
3. C 归约到 D ($C \le D$): 在多数情况下，赚钱需要有工作。因此，赚钱问题归约到找工作问题。如果你解决了D（找到了工作），C就有了来源。

这个链条展示了归约的传递性：如果 $A \le B$ 且 $B \le C$，那么 $A \le C$。在这个例子里，最终“从波士顿到巴黎旅行”这个问题，被归约到了“找到一份工作”这个问题。

这一段将可归约性的概念从生活实例过渡到更精确的数学问题领域，为进入计算理论的严格证明做准备。

1. “测量矩形面积的问题归约到测量其长度和宽度的问题”
   • 问题 A: 测量矩形面积。
   • 问题 B: 测量其长度和宽度。
   • 归约: 这是通过公式 面积 = 长 × 宽 实现的。这个公式告诉我们，只要我们能解决问题B（获得长度和宽度的值），我们就能通过一次乘法运算解决问题A。
   • 难度关系: 测量长度和宽度是更基本的操作。计算面积的难度不超过测量长度、宽度再加一次乘法。
2. “求解线性方程组的问题归约到求矩阵逆的问题”
   • 问题 A: 求解线性方程组。
   • 问题 B: 求一个矩阵的逆。
   • 背景: 一个线性方程组可以写成矩阵形式 $A\mathbf{x} = \mathbf{b}$。其中，$A$ 是系数矩阵，$\mathbf{x}$ 是未知数向量，$\mathbf{b}$ 是常数向量。我们的目标是解出 $\mathbf{x}$。
   • 归约: 如果矩阵 $A$ 的逆矩阵 $A^{-1}$ 存在（即B可解），我们可以通过在方程两边同时左乘 $A^{-1}$ 来求解 $\mathbf{x}$：
   • 方案利用: 如果你有一个能解决问题B的算法或工具（比如MATLAB里的 inv() 函数），你就可以用它来解决问题A。

这一段是本章乃至整个计算理论后半部分的核心思想的高度概括。它明确指出了可归约性最重要的两个应用。

1. 应用领域:
   • 可判定性分类 (Computability Theory): 即本章内容，用归约来划分问题是可判定的（有算法能解）还是不可判定的（没有算法能解）。
   • 复杂性理论 (Complexity Theory): 后续章节内容（如P vs NP），用归约来对可判定问题内部进行更精细的难度划分，比如哪些是“容易解”的（P类问题），哪些是“可能很难解”的（NP完全问题）。
2. 核心逻辑: “当$A$可归约到$B$时，解决$A$不会比解决$B$更难”。这是对 $A \le_m B$ 背后难度关系的再次强调。可以理解为：$Difficulty(A) \le Difficulty(B)$。
3. 两个主要推论 (Rules of Inference):
   • 推论1 (用于证明可判定性):
   • 前提1: $A$ 可归约到 $B$ ($A \le_m B$)。
   • 前提2: $B$ 是可判定的 (B is decidable)。
   • 结论: $A$ 也是可判定的 (A is decidable)。
   • 逻辑: 既然解决B的算法存在（前提2），并且我们有一个算法能把A转换成B（归约本身是可计算的），那么我们就可以组合出一个解决A的算法：先将A的实例转换成B的实例，再用B的算法去解，最后得到A的答案。整个过程是算法化的，所以A可判定。

• 推论2 (用于证明不可判定性):
• 这是推论1的逆否命题，也是本章的“核武器”。
• 前提1: $A$ 是不可判定的 (A is undecidable)。
• 前提2: $A$ 可归约到 $B$ ($A \le_m B$)。
• 结论: $B$ 也是不可判定的 (B is undecidable)。
• 逻辑（反证法）: 假设B是可判定的。根据推论1，既然 $A \le_m B$ 且 B 可判定，那么 A 也应该是可判定的。但这与前提1“A是不可判定的”相矛盾。因此，最初的假设“B是可判定的”必须是错误的。所以，B一定是不可判定的。

1. “这最后一个版本是证明各种问题不可判定性的关键”: 明确点出，本书接下来将反复使用推论2。我们会拿一个已知的、坚不可摧的不可判定问题（比如 $A_{\mathrm{TM}}$）作为我们的A，然后想办法把它归约到一个我们想证明其不可判定性的新问题B上。一旦归约成功，B的“死刑”就判了。

这句话是对上一段核心思想的最终总结，也是对接下来所有证明的“一句话攻略”。

• “我们证明一个问题不可判定的方法”: 指明了我们的目标——证明某个新问题是不可判定的。
• “是”: 引出具体的方法。
• “证明”: 强调这个过程需要严格的数学论证。
• “某个已知不可判定的问题”: 这是我们的出发点和武器。在本书的这个阶段，这个“已知不可判定问题”主要就是 $A_{\mathrm{TM}}$。我们把它当作“困难的黄金标准”。
• “可以归约到它”: “它”指的是我们想要证明其不可判定性的那个新问题。

所以，整个流程是：

已知不可判定问题 ($A_{known}$) $\le_m$ 新问题 ($B_{new}$) $\implies$ $B_{new}$ 是不可判定的

这一段正式开始了第一个使用归约方法的证明。它介绍了即将被证明为不可判定的新问题——停机问题 ($HALT_{\mathrm{TM}}$)。

1. 回顾已知: 首先，再次强调我们的出发点和“武器”——$A_{\mathrm{TM}}$ 的不可判定性。
   • $A_{\mathrm{TM}} = \{\langle M, w\rangle \mid M \text{ 是一个图灵机且 } M \text{ 接受 } w\}$。
   • 这个问题问的是“是否接受？”。
2. 引入新问题: 介绍停机问题 $HALT_{\mathrm{TM}}$。
   • 这个问题问的是“是否停机？”。
   • 停机包含两种情况：接受 (accept) 并停机，或者拒绝 (reject) 并停机。不停机的情况被称为循环 (loop)。
   • 所以，$HALT_{\mathrm{TM}}$ 关心的是机器最终会不会给出一个明确的答复（无论是接受还是拒绝），而不是陷入无限循环。
3. 两者的关系:
   • 如果一个图灵机 $M$ 在输入 $w$ 上接受了，那么它一定停机了。
   • 如果一个图灵机 $M$ 在输入 $w$ 上停机了，它可能是接受了，也可能是拒绝了。
   • 从集合关系上看，$A_{\mathrm{TM}}$ 中的每个元素 $\langle M, w\rangle$ 也都属于 $HALT_{\mathrm{TM}}$ (只要 $M$ 接受 $w$)。但反之不成立。
4. 声明证明策略: 明确指出我们将要使用的证明方法，完全符合上一节总结的“一句话攻略”。
   • 目标: 证明 $HALT_{\mathrm{TM}}$ 是不可判定的。
   • 方法: 将 $A_{\mathrm{TM}}$ 归约到 $HALT_{\mathrm{TM}}$ (证明 $A_{\mathrm{TM}} \le_m HALT_{\mathrm{TM}}$)。
   • 逻辑: 一旦归约成功，由于 $A_{\mathrm{TM}}$ 是不可判定的，根据推论2，$HALT_{\mathrm{TM}}$ 也必须是不可判定的。
5. 形式化定义: 给出了 $HALT_{\mathrm{TM}}$ 的严格集合定义。

这部分是定理5.1的“证明思路”，它用非形式化的语言，引导读者理解整个证明的核心逻辑。这是一种非常好的教学方法，先讲故事，再给代码。

1. 设定证明框架——反证法 (Proof by Contradiction):
   • 第一步：假设。我们假设结论的反面是正确的，即假设“$HALT_{\mathrm{TM}}$ 是可判定的”。
   • 第二步：推导。从这个假设出发，进行一系列逻辑上无懈可击的推导。
   • 第三步：导出矛盾。我们的推导最终会得出一个与已知事实（公理或已证定理）相违背的结论。
   • 第四步：下结论。由于推导过程无误，那一定是最初的假设出了问题。因此，假设是错误的，其反面（我们想证明的结论）才是正确的。
2. 具体化假设:
   • 假设“$HALT_{\mathrm{TM}}$ 是可判定的”，这意味着存在一个图灵机，我们称之为 $R$，它能判定 $HALT_{\mathrm{TM}}$。
   • $R$ 的功能：输入 $\langle M, w \rangle$，如果 $M$ 在 $w$ 上停机，$R$ 就接受并停机；如果 $M$ 在 $w$ 上循环，$R$ 就拒绝并停机。重要的是，$R$ 自己永远不会循环。$R$ 就是我们幻想中存在的那个完美的“死机检测器”。
3. 构建归约: 我们的目标是利用这个虚构的机器 $R$，来构造另一个机器 $S$，让 $S$ 能够判定 $A_{\mathrm{TM}}$。这就完成了 $A_{\mathrm{TM}} \le_m HALT_{\mathrm{TM}}$ 的归约。
4. 第一人称体验（角色扮演 S）: 为了让思路更清晰，作者让我们想象自己就是机器 $S$。
   • 你的任务: 判定 $A_{\mathrm{TM}}$。输入是 $\langle M, w \rangle$。你需要判断 $M$ 是否接受 $w$。
   • 一个失败的尝试: 最直接的想法是“直接模拟 $M$ 在 $w$ 上的运行”。
   • 如果 $M$ 接受了 $w$，你（$S$）也接受。这没问题。
   • 如果 $M$ 拒绝了 $w$，你（$S$）也拒绝。这也行。
   • 问题在于：如果 $M$ 在 $w$ 上循环了，你的模拟也会跟着一起循环下去，永不停止。但你的身份是“判定器”(Decider)，判定器绝不允许循环。所以，直接模拟的方案失败了。
5. 正确的方案（使用“外挂”R）: 现在，你（$S$）被赋予了一个超能力——可以调用机器 $R$（那个完美的“死机检测器”）。
   • 第一步: 拿到输入 $\langle M, w \rangle$ 后，你不要直接去模拟 $M$。而是先把 $\langle M, w \rangle$ 作为输入，去问你的“外挂” $R$。
   • 第二步: 分析 $R$ 的回答。
   • 情况1: $R$ 回答“拒绝”。这意味着 $R$ 判断出 $M$ 在 $w$ 上会循环。如果 $M$ 循环，它肯定不会接受 $w$。所以，$\langle M, w \rangle$ 不属于 $A_{\mathrm{TM}}$。在这种情况下，你（$S$）就可以放心地直接拒绝。
   • 情况2: $R$ 回答“接受”。这意味着 $R$ 判断出 $M$ 在 $w$ 上最终会停机。这太棒了！因为现在你知道了模拟 $M$ 在 $w$ 上的运行绝对不会导致无限循环。
   • 第三步: 在 $R$ 告诉你 $M$ 会停机之后，你（$S$）现在可以安全地去模拟 $M$ 在 $w$ 上的运行了。
   • 模拟的结果只会有两种：$M$ 接受 $w$，或者 $M$ 拒绝 $w$。
   • 如果模拟结果是 $M$ 接受，你（$S$）就接受。
   • 如果模拟结果是 $M$ 拒绝，你（$S$）就拒绝。
6. 导出矛盾:
   • 通过上述步骤，我们设计出了一个完整的、在任何输入 $\langle M, w \rangle$ 上都能正确判断 $M$ 是否接受 $w$ 并且自身永不循环的图灵机 $S$。
   • 换句话说，我们证明了：如果 $HALT_{\mathrm{TM}}$ 是可判定的（即 $R$ 存在），那么 $A_{\mathrm{TM}}$ 也是可判定的（即 $S$ 存在）。
   • 但是，我们在定理4.11中已经铁证如山地证明了 $A_{\mathrm{TM}}$ 是不可判定的！
   • 这就产生了矛盾。
7. 最终结论:
   • 矛盾的根源在于我们最初的假设——“$HALT_{\mathrm{TM}}$ 是可判定的”。
   • 因此，这个假设必须是错误的。
   • 结论：$HALT_{\mathrm{TM}}$ 是不可判定的。

这部分是定理5.1的严格形式化证明。它将刚才“证明思路”中的描述，翻译成了图灵机伪代码的形式。

“为了获得矛盾，我们假设图灵机$R$判定$H A L T_{\mathrm{TM}}$。”

这再次重申了反证法的起点。我们假设存在这样一个判定器 $R$。

• $R(\langle M, w \rangle)$ 接受 $\iff M$ 在 $w$ 上停机。
• $R(\langle M, w \rangle)$ 拒绝 $\iff M$ 在 $w$ 上循环。
• $R$ 自身总是停机的。

“我们构造图灵机$S$来判定$A_{\mathrm{TM}}$，其操作如下。”

这是归约的核心步骤：构建一个新机器 $S$，并利用 $R$ 作为其子程序。我们的目标是让 $S$ 成为 $A_{\mathrm{TM}}$ 的判定器。

$S$ 的算法描述：

$S$ 被设计为一个接受输入 $\langle M, w \rangle$ 的图灵机。

• “1. 在输入$\langle M, w\rangle$上运行图灵机$R$。”
• 这是 $S$ 的第一步。$S$ 将自己的输入原封不动地传给子程序 $R$。
• $S$ 会等待 $R$ 完成计算并给出结果（“接受”或“拒绝”）。因为 $R$ 是个判定器，所以 $S$ 在这一步的等待过程保证是有限的。

• “2. 如果$R$拒绝，则拒绝。”
• $R$ 拒绝意味着什么？根据 $R$ 的定义，这意味着 $M$ 在输入 $w$ 上会无限循环。
• 如果 $M$ 会循环，它肯定永远不会进入接受状态。
• 因此，$M$ 不接受 $w$，$\langle M, w \rangle$ 不属于 $A_{\mathrm{TM}}$。
• 在这种情况下，$S$ 做出拒绝的决定是完全正确的。并且 $S$ 在这一步就停机了。

• “3. 如果$R$接受，则模拟$M$在$w$上的运行直到停机。”
• $R$ 接受意味着什么？根据 $R$ 的定义，这意味着 $M$ 在输入 $w$ 上保证会停机。
• 这个保证是至关重要的，它使得 $S$ 接下来可以安全地进行模拟，而不用担心自己会陷入无限循环。
• $S$ 启动一个标准的通用图灵机模拟程序，来执行 $M$ 在 $w$ 上的指令。
• 因为已经知道 $M$ 会停机，所以这个模拟过程也保证是有限的。

• “4. 如果$M$接受了，则接受；如果$M$拒绝了，则拒绝。”
• 这是模拟结束后的处理。模拟的结果只有两种：$M$ 停机并接受，或者 $M$ 停机并拒绝。
• 如果 $M$ 接受 $w$，那么 $\langle M, w \rangle$ 属于 $A_{\mathrm{TM}}$。$S$ 此时做出接受的决定是正确的。
• 如果 $M$ 拒绝 $w$，那么 $\langle M, w \rangle$ 不属于 $A_{\mathrm{TM}}$。$S$ 此时做出拒绝的决定是正确的。
• 在这两种情况下，$S$ 都停机了。

“显然，如果$R$判定$H A L T_{\text {TM }}$，那么$S$判定$A_{\text {TM }}$。”

这是一个总结性陈述。我们来验证 $S$ 是否真的是 $A_{\mathrm{TM}}$ 的判定器。

• 正确性: 对于任何输入 $\langle M, w \rangle$：
• 如果 $\langle M, w \rangle \in A_{\mathrm{TM}}$ (即 $M$ 接受 $w$)，那么 $M$ 必定会停机。$R$ 会接受，然后 $S$ 模拟 $M$ 也会得到接受的结果，所以 $S$ 接受。正确。
• 如果 $\langle M, w \rangle \notin A_{\mathrm{TM}}$ (即 $M$ 拒绝或循环)，分两种情况：
• $M$ 拒绝 $w$：那么 $M$ 会停机。$R$ 会接受，然后 $S$ 模拟 $M$ 会得到拒绝的结果，所以 $S$ 拒绝。正确。
• $M$ 循环于 $w$：那么 $M$ 不会停机。$R$ 会拒绝，根据第2步，$S$ 直接拒绝。正确。
• 结论：$S$ 总能给出正确的答案。
• 停机性: $S$ 的每一步都是保证停机的。第1步因为 $R$ 是判定器。第2步直接停机。第3步因为 $R$ 保证了 $M$ 会停机。第4步是模拟结束后的操作，自然也停机。所以 $S$ 自身永远不会循环。
• 综上，$S$ 确实是一个 $A_{\mathrm{TM}}$ 的判定器。

“因为$A_{\text {TM }}$是不可判定的，$H A L T_{\text {TM }}$也必须是不可判定的。”

这是反证法的最后一步。

• 我们成功地从“$H A L T_{\mathrm{TM}}$ 是可判定的”这个假设，推导出了“$A_{\mathrm{TM}}$ 是可判定的”这个结论。
• 这个结论与定理4.11（$A_{\mathrm{TM}}$ 不可判定）直接矛盾。
• 因此，我们的初始假设是错误的。
• 所以，$H A L T_{\mathrm{TM}}$ 必须是不可判定的。证明完毕。

这段话是对刚刚完成的证明进行方法论上的总结，并指出其普遍性。

1. “定理5.1阐明了我们证明一个问题不可判定的策略”: 刚才证明 $HALT_{\mathrm{TM}}$ 的过程，不仅仅是解决了一个问题，更重要的是，它为我们提供了一个可重复使用的“模板”或“蓝图”。
2. “这种策略是大多数不可判定性证明所共有的”: 这个模板（即归约法）是证明不可判定性的标准工具。接下来的许多证明都会遵循几乎完全相同的模式：
   • 第一步: 宣称要用反证法，通过归约来证明新问题 B 是不可判定的。
   • 第二步: 假设 B 是可判定的，即存在一个判定器 $R_B$。
   • 第三步: 利用 $R_B$ 构造一个判定器 $S_A$ 来解决某个已知不可判定的问题 A (通常是 $A_{\mathrm{TM}}$)。
   • 第四步: 指出 $S_A$ 的存在与“A是不可判定的”这个事实相矛盾。
   • 第五步: 宣布假设错误，因此 B 必须是不可判定的。
3. “除了$A_{\text {TM }}$本身的不可判定性，它是通过对角线法直接证明的”: 这是一个非常重要的区分。归约法本身需要一个“困难的源头”作为起点。这个最初的、最根本的不可判定问题，不能通过归约来证明（因为当时还没有更早的已知不可判定问题可以归约过来）。
   • $A_{\mathrm{TM}}$ 的不可判定性，是通过一种完全不同的、更根本的证明技巧——对角线法 (Diagonalization) ——来直接确立的。
   • 对角线法由康托尔在研究无穷集合时首创，图灵巧妙地将其应用于计算理论，构造出一个任何图灵机都无法正确判断的“悖论式”输入。

这一段引入了本节要讨论的第二个不可判定问题：图灵机语言为空问题 ($E_{\mathrm{TM}}$)。

1. “我们现在提出其他几个定理及其证明，作为使用归约方法证明不可判定性的进一步例子”: 开宗明义，接下来的内容是实践和巩固上一节学到的归约策略。
2. “设...”: 开始形式化定义新问题。
3. $E_{\mathrm{TM}}$ 的定义: 这个问题问的是：给定的图灵机 $M$ 所接受的语言是否为空集 $\emptyset$。
   • 语言 (Language): 一个图灵机 $M$ 的语言，记作 $L(M)$，是指它所接受的所有字符串的集合。$L(M) = \{w \mid M \text{ 接受 } w\}$。
   • 空集 (Empty Set, $\emptyset$): 不包含任何元素的集合。
   • $L(M)=\emptyset$ 意味着，对于任何可能的输入字符串 $w$，图灵机 $M$ 都不会接受。它可能会在所有输入上都拒绝，或者在所有输入上都循环，或者在某些输入上拒绝、另一些上循环，但绝不会进入接受状态。
   • $E$ 代表 "Empty"。

这是定理5.2的“证明思路”。它再次使用了“角色扮演”和“排除错误选项”的方式，引导我们找到正确的归约构造。

1. 重申证明模式: 和定理5.1一样，采用反证法，通过将 $A_{\mathrm{TM}}$ 归约到 $E_{\mathrm{TM}}$ 来制造矛盾。
   • 假设: $E_{\mathrm{TM}}$ 可判定，即存在一个判定器 $R$。$R$ 的功能是：输入 $\langle M \rangle$，如果 $L(M)=\emptyset$ 则接受，否则拒绝。$R$ 自身永不循环。
   • 目标: 利用 $R$ 构造一个 $A_{\mathrm{TM}}$ 的判定器 $S$。$S$ 的输入是 $\langle M, w \rangle$。
2. 一个失败的尝试:
   • 想法: $S$ 拿到输入 $\langle M, w \rangle$后，直接把 $\langle M \rangle$ 扔给 $R$。
   • 分析:
   • 如果 $R$ 接受 $\langle M \rangle$，说明 $L(M)$ 是空的。既然 $M$ 不接受任何字符串，那它自然也不接受 $w$。此时 $S$ 可以安全地拒绝。这部分逻辑是对的。
   • 问题在于: 如果 $R$ 拒绝 $\langle M \rangle$，说明 $L(M)$ 不是空的。这意味着 $M$ 至少接受一个字符串。但这个字符串是哪个？是 "abc"？是 "10101"？还是恰好就是我们关心的那个 $w$？我们完全不知道。仅仅知道 $M$ 会接受“某个”字符串，对于判断它是否接受“特定”的 $w$ 毫无帮助。
   • 结论: 这个简单的想法失败了。
3. 正确的方案（精巧的构造）:
   • 核心思想: 我们不能直接问关于 $M$ 的问题，因为 $R$ 给的信息太宽泛了。我们必须构造一个新的、特制的图灵机，我们叫它 $M_1$，然后把 $M_1$ 的描述 $\langle M_1 \rangle$ 喂给 $R$。这个 $M_1$ 的设计必须非常巧妙，使得 $R$ 对 $M_1$ 的回答能够间接地告诉我们关于“$M$ 是否接受 $w$”的信息。
   • $M_1$ 的设计蓝图:
   • $S$ 在拿到输入 $\langle M, w \rangle$ 后，它的工作不是去运行什么，而是“在内部”动态地生成一台新的图灵机 $M_1$ 的设计图（编码）。
   • $M_1$ 的行为逻辑被设定为：
   • 对于任何不等于 $w$ 的输入 $x$ (即 $x \neq w$)，$M_1$ 直接拒绝。
   • 对于等于 $w$ 的输入 $x$ (即 $x = w$)，$M_1$ 不自己做决定，而是完全模仿 $M$ 在 $w$ 上的行为。也就是说，$M_1$ 在内部运行一个对 $M$ 在 $w$ 上的模拟。如果 $M$ 接受 $w$，$M_1$ 就接受；如果 $M$ 拒绝或循环于 $w$，$M_1$ 也跟着拒绝或循环。
   • 分析这个构造:
   • $M_1$ 能接受的唯一可能的字符串就是 $w$。所有其他字符串都被它直接过滤掉了。
   • 因此，$M_1$ 的语言 $L(M_1)$ 只有两种可能性：
   • 情况A: 如果 $M$ 接受 $w$，那么 $M_1$ 也会接受 $w$。此时 $L(M_1) = \{w\}$，这是一个非空语言。
   • 情况B: 如果 $M$ 不接受 $w$ (拒绝或循环)，那么 $M_1$ 也不会接受 $w$。由于 $M_1$ 已经拒绝了所有其他字符串，所以 $M_1$ 不接受任何字符串。此时 $L(M_1) = \emptyset$，这是一个空语言。
   • 如何利用 $R$: 现在，$S$ 把构造好的 $\langle M_1 \rangle$ 交给 $R$。
   • 如果 $R$ 接受 $\langle M_1 \rangle$，根据 $R$ 的定义，这意味着 $L(M_1) = \emptyset$。这对应我们分析的情况B，说明 $M$ 不接受 $w$。于是 $S$ 就可以拒绝。
   • 如果 $R$ 拒绝 $\langle M_1 \rangle$，这意味着 $L(M_1) \neq \emptyset$。这对应我们分析的情况A，说明 $M$ 接受 $w$。于是 $S$ 就可以接受。
   • 归约成功: 通过这个构造，$S$ 完美地将判断“$M$ 是否接受 $w$”的问题，转换成了判断“$M_1$ 的语言是否为空”的问题。$S$ 只需要执行这个构造，调用 $R$，然后根据 $R$ 的结果给出相反的答案，就能成为 $A_{\mathrm{TM}}$ 的判定器。这就产生了我们想要的矛盾。

这部分是定理5.2的严格形式化证明，它把“证明思路”中的构造方案用伪代码清晰地表达出来。

第一部分：$M_1$ 的形式化描述

• “让我们用我们的标准符号来表示证明思路中描述的修改后的机器。我们称之为$M_{1}$。”
• 这里开始给出 $M_1$ 的精确算法。这个 $M_1$ 是由 $S$ 根据自己的输入 $\langle M, w \rangle$ 动态构造出来的。

• $M_1$ 的算法:
• “在输入 $x$ 上：”: 这是 $M_1$ 自己运行时所遵循的规则。$x$ 是未来可能给 $M_1$ 的任何输入。
• “1. 如果$x \neq w$，则拒绝。”: $M_1$ 的第一道关卡。它把自己接收到的输入 $x$ 和它“内心”里存着的那个从 $S$ 那里继承来的字符串 $w$ 进行比较。如果不一样，就立刻拒绝并停机。
• “它通过扫描输入并逐个字符地与$w$进行比较...从而以显而易见的方式进行$x=w$的测试。”: 这句话解释了“如何实现 $x \neq w$ 的判断”，这是一个非常基本和标准的图灵机操作，是可计算的。
• “2. 如果$x=w$，则在输入$w$上运行$M$，如果$M$接受，则接受。”: 只有当输入 $x$ 精确地等于 $w$ 时，才进入第二步。在这一步，$M_1$ 启动一个内部模拟器，去运行它同样继承自 $S$ 的图灵机 $M$ 在输入 $w$ 上的过程。然后，$M_1$ 的行为完全复制 $M$ 的行为：如果 $M$ 接受，$M_1$ 就接受；如果 $M$ 拒绝或循环，$M_1$ 也会跟着拒绝或循环。

• $M_1$ 的语言分析: 正如“证明思路”中分析的，这个构造确保了 $L(M_1)$ 要么是 $\{w\}$ (当 $M$ 接受 $w$ 时)，要么是 $\emptyset$ (当 $M$ 不接受 $w$ 时)。

第二部分：$S$ 的形式化描述

• “综上所述，我们假设图灵机$R$判定$E_{\mathrm{TM}}$，并构造图灵机$S$来判定$A_{\text {TM }}$，如下所示。”: 重申反证法的框架，并开始描述 $S$ 的算法。

• $S$ 的算法:
• “在输入$\langle M, w\rangle$上...”: $S$ 接收一个图灵机 $M$ 和一个字符串 $w$ 的编码。
• “1. 使用$M$和$w$的描述构造刚刚描述的图灵机$M_{1}$。”: 这是 $S$ 的核心创造性工作。$S$ 作为一个“机器制造机”，它读取 $M$ 的指令集和字符串 $w$，然后输出一台新的图灵机 $M_1$ 的描述（编码）。这个构造过程本身是一个算法，是可计算的。
• “2. 在输入$\left\langle M_{1}\right\rangle$上运行$R$。”: $S$ 将其“作品” $\langle M_1 \rangle$ 作为输入，去调用它假设存在的“空语言判定器” $R$。$S$ 等待 $R$ 的判决结果。
• “3. 如果$R$接受，则拒绝；如果$R$拒绝，则接受。”: 这是 $S$ 做出最终裁决的步骤，它采取了与 $R$ 相反的逻辑。
• $R$ 接受 $\langle M_1 \rangle$: 意味着 $L(M_1) = \emptyset$。根据我们对 $M_1$ 的分析，这等价于 $M$ 不接受 $w$。所以 $S$ 应该拒绝。
• $R$ 拒绝 $\langle M_1 \rangle$: 意味着 $L(M_1) \neq \emptyset$。根据我们对 $M_1$ 的分析，这等价于 $M$ 接受 $w$。所以 $S$ 应该接受。
• 注意这里有一个小小的逻辑跳跃：当 $R$ 拒绝时，$S$ 就接受。这实际上是颠倒了 $R$ 的输出。

第三部分：得出结论

• “如果$R$是$E_{\mathrm{TM}}$的判决器，$S$将是$A_{\mathrm{TM}}$的判决器。”: 这个构造是成功的。我们已经证明了，借助判定器 $R$，$S$ 可以正确且总能停机地判定 $A_{\mathrm{TM}}$。
• “$A_{\mathrm{TM}}$的判决器不能存在，所以我们知道$E_{\mathrm{TM}}$必须是不可判定的。”: 这再次应用了反证法的最终逻辑。既然我们从“$E_{\mathrm{TM}}$ 可判定”的假设推出了“$A_{\mathrm{TM}}$ 可判定”这个谬论，那么最初的假设必然是错误的。因此，$E_{\mathrm{TM}}$ 是不可判定的。

这一段引入了本节要讨论的第三个不可判定问题：图灵机语言为正则语言问题 ($REGULAR_{\mathrm{TM}}$)。

1. 问题背景: 这一段从一个更广阔的视角来提出问题。我们知道图灵机是计算能力最强的模型之一。比它计算能力弱的模型有很多，比如有限自动机 (Finite Automata, FA) 和 下推自动机 (Pushdown Automata, PDA)。它们分别对应识别正则语言 (Regular Languages) 和上下文无关语言 (Context-Free Languages, CFL)。
   • 一个自然而然的问题是：我们拿出一个图灵机 $M$，它可能非常复杂，但它所接受的语言 $L(M)$，有没有可能恰好是一个比较简单的语言，比如一个正则语言？如果是这样，就意味着我们可以用一个能力更弱、结构更简单的有限自动机来完成和这个复杂图灵机同样的工作（接受同样的语言）。
   • 这个问题在编译器优化、程序验证等领域有实际意义。如果我们能判定一个复杂的程序实际上只在实现一个正则逻辑，我们就可以用更高效、更易于分析的方法来替代它。
2. 定义新问题 $REGULAR_{\mathrm{TM}}$:
   • “判断给定图灵机是否具有等价的有限自动机的问题”: 这是问题的非形式化描述。
   • “这个问题等同于判断图灵机是否识别正则语言”: 这是根据计算理论的基本知识（乔姆斯基谱系）得到的等价描述。有限自动机能且仅能识别正则语言。
   • 形式化定义: 给出了问题的集合表示。

这是定理5.3的“证明思路”，揭示了一个非常精妙的归约构造。

1. 确定基本框架:
   • 方法: 从 $A_{\mathrm{TM}}$ 进行归约的反证法。
   • 假设: $REGULAR_{\mathrm{TM}}$ 是可判定的，即存在一个判定器 $R$。$R$ 的功能是：输入 $\langle M \rangle$，如果 $L(M)$ 是正则语言则接受，否则拒绝。
   • 目标: 利用 $R$ 构造一个 $A_{\mathrm{TM}}$ 的判定器 $S$。
2. 点出难点:
   • “现在不那么明显的是如何利用$R$的能力来帮助$S$完成任务”: 与 $E_{\mathrm{TM}}$ 不同，这里的 $R$ 提供的不是“是/否”这种简单的二元信息，而是“正则/非正则”这种更抽象的属性。如何把“$M$ 是否接受 $w$”这个具体事件，和一个语言的“正则性”这种全局属性联系起来，是本证明的难点和亮点。
3. 核心构造思想:
   • 和证明 $E_{\mathrm{TM}}$ 时一样，$S$ 在收到输入 $\langle M, w \rangle$ 后，需要动态地构造一台新的图灵机 $M_2$。
   • $M_2$ 的设计目标是：它的语言 $L(M_2)$ 的正则性，要完全依赖于“$M$ 是否接受 $w$”这一事件。
   • 具体设计蓝图: 我们需要找到两种语言，一种是确定正则的，另一种是确定非正则的。然后让 $M_2$ 的行为在这两种语言之间切换。
   • 选定的非正则语言: $\{0^n1^n \mid n \ge 0\}$。这是我们最熟悉的非正则语言，它需要无限的记忆来匹配0和1的数量。我们用它来充当“毒药”。
   • 选定的正则语言: $\Sigma^*$，即包含所有可能字符串的语言。这是一个非常简单的正则语言。我们用它来充当“解药”。
4. $M_2$ 的行为逻辑:
   • $S$ 收到 $\langle M, w \rangle$ 后，构造出的 $M_2$ 运行在自己的输入 $x$上，逻辑如下：
   • 第一步: $M_2$ 首先检查自己的输入 $x$ 是否符合 $\{0^n1^n\}$ 的形式。
   • 如果 $x$ 的形式是 $0^n1^n$: $M_2$ 立刻接受 $x$。
   • 这意味着 $\{0^n1^n\}$ 这个非正则语言，永远是 $L(M_2)$ 的一个子集。
   • 第二步: 如果 $x$ 的形式不是 $0^n1^n$：
   • 在这种情况下，$M_2$ 不立即做决定。它会“暂停”对 $x$ 的处理，转而在内部模拟 $M$ 在 $w$ 上的运行。
   • 如果 $M$ 接受了 $w$: 那么 $M_2$ 就接受当前的输入 $x$。
   • 如果 $M$ 不接受 $w$ (拒绝或循环): 那么 $M_2$ 就拒绝当前的输入 $x$。
5. 分析 $M_2$ 的语言 $L(M_2)$:
   • 情况A: 如果 $M$ 接受 $w$。
   • 对于形如 $0^n1^n$ 的字符串 $x$，$M_2$ 接受它们（根据第一步）。
   • 对于不形如 $0^n1^n$ 的字符串 $x$，$M_2$ 也接受它们（因为 $M$ 接受 $w$，第二步的条件满足了）。
   • 因此，在这种情况下，$M_2$ 接受了所有的字符串。$L(M_2) = \Sigma^*$。而 $\Sigma^*$ 是一个正则语言。
   • 情况B: 如果 $M$ 不接受 $w$。
   • 对于形如 $0^n1^n$ 的字符串 $x$，$M_2$ 接受它们（根据第一步）。
   • 对于不形如 $0^n1^n$ 的字符串 $x$，$M_2$ 会拒绝它们（因为 $M$ 不接受 $w$，第二步的条件不满足）。
   • 因此，在这种情况下，$M_2$ 只接受形如 $0^n1^n$ 的字符串。$L(M_2) = \{0^n1^n \mid n \ge 0\}$。这是一个经典的非正则语言。
6. 如何利用 $R$:
   • $S$ 将构造好的 $\langle M_2 \rangle$ 交给判定器 $R$。
   • 如果 $R$ 接受 $\langle M_2 \rangle$，说明 $L(M_2)$ 是正则语言。这对应我们的情况A，即 $M$ 接受 $w$。于是 $S$ 就可以接受。
   • 如果 $R$ 拒绝 $\langle M_2 \rangle$，说明 $L(M_2)$ 是非正则语言。这对应我们的情况B，即 $M$ 不接受 $w$。于是 $S$ 就可以拒绝。
7. 点明易错点:
   • “请注意，图灵机$M_{2}$的构造并非是为了实际在某些输入上运行它”: 再次强调！$S$ 只是一个“设计师”和“建筑师”，它建造了 $M_2$ 的蓝图 $\langle M_2 \rangle$。$S$ 自己从不运行 $M_2$。$S$ 建造 $M_2$ 的唯一目的，就是把这份蓝图交给 $R$ 去“审查”。审查过程是 $R$ 的事，我们假设的 $R$ 有能力审查蓝图并判断其最终产品的性质（语言是否正则）。

这部分是定理5.3的严格形式化证明。

第一部分：$S$ 和 $M_2$ 的形式化描述

• “我们设$R$是判定$R E G U L A R_{\mathrm{TM}}$的图灵机，并构造图灵机$S$来判定$A_{\text {TM }}$。”: 再次设立反证法框架。假设存在判定器 $R$，我们要用它构造 $A_{\mathrm{TM}}$ 的判定器 $S$。

• $S$ 的算法:
• “在输入$\langle M, w\rangle$上...”: $S$ 接收 $M$ 和 $w$。
• “1. 构造以下图灵机$M_{2}$。”: $S$ 的核心工作是构建 $M_2$ 的描述。
• $M_{2}=$"在输入$x$上：”: 这是被构造出来的 $M_2$ 的行为规范。
• “2. 如果$x$具有$0^{n} 1^{n}$的形式，则接受。”: $M_2$ 做的第一件事是检查自己的输入 $x$。如果 $x$ 是一串0后面跟着相同数量的1（比如 "0011", "000111"），$M_2$ 就接受它。这是一个可以由图灵机完成的检查（例如，来回划掉0和1）。
• “3. 如果$x$不具有此形式，则在输入$w$上运行$M$，如果$M$接受$w$，则接受。”: 如果 $x$ 的形式不是 $0^n1^n$，$M_2$ 就转而执行一个内部任务：模拟 $M$ 在 $w$ 上的运行。注意，$M_2$ 此时完全忽略了它自己的输入 $x$。它唯一的行为动机来自于 $M$ 对 $w$ 的反应。如果内部模拟显示 $M$ 接受了 $w$，$M_2$ 就接受它当前的输入 $x$。否则（如果 $M$ 拒绝或循环），$M_2$ 就在这里拒绝或循环，从而不接受 $x$。
• “4. 在输入$\left\langle M_{2}\right\rangle$上运行$R$。”: $S$ 将构造好的 $M_2$ 的描述 $\langle M_2 \rangle$ 喂给判定器 $R$。
• “5. 如果$R$接受，则接受；如果$R$拒绝，则拒绝。”: $S$ 的最终决定直接复制 $R$ 的决定。我们来分析这一步的逻辑。

第二部分：逻辑分析

• $S$ 的决策逻辑:
• 如果 $R$ 接受 $\langle M_2 \rangle$，意味着 $R$ 判断 $L(M_2)$ 是一个正则语言。根据我们对 $M_2$ 的分析，这只发生在 $M$ 接受 $w$ 的情况（此时 $L(M_2) = \Sigma^*$）。$A_{\mathrm{TM}}$ 问题的答案是“是”，所以 $S$ 接受是正确的。
• 如果 $R$ 拒绝 $\langle M_2 \rangle$，意味着 $R$ 判断 $L(M_2)$ 是一个非正则语言。根据我们对 $M_2$ 的分析，这只发生在 $M$ 不接受 $w$ 的情况（此时 $L(M_2) = \{0^n1^n\}$）。$A_{\mathrm{TM}}$ 问题的答案是“否”，所以 $S$ 拒绝是正确的。

• 构造的有效性:
• 这个构造成功地将“$M$ 是否接受 $w$”这个问题映射到了“$L(M_2)$ 是否为正则语言”这个问题上。
• $M$ 接受 $w \iff L(M_2)$ 是正则语言 ($\Sigma^*$)
• $M$ 不接受 $w \iff L(M_2)$ 是非正则语言 ($\{0^n1^n\}$)
• 因此，$S$ 通过调用 $R$ 并采纳其结果，成为了 $A_{\mathrm{TM}}$ 的一个完美判定器。

第三部分：得出矛盾

• 我们从“$REGULAR_{\mathrm{TM}}$ 可判定”的假设，导出了“$A_{\mathrm{TM}}$ 可判定”的结论。
• 这与 $A_{\mathrm{TM}}$ 的不可判定性相矛盾。
• 因此，假设错误，$REGULAR_{\mathrm{TM}}$ 是不可判定的。

这一段是对刚刚完成的证明进行扩展和泛化，并引出一个极为重要的通用定理——赖斯定理 (Rice's Theorem)。

1. 证明方法的可扩展性:
   • “同样，可以通过类似的证明来表明...”: 这句话指出，我们刚才用来证明 $REGULAR_{\mathrm{TM}}$ 的那套方法论，并非只能用一次，它是一个强大的“模板”，可以被广泛应用。
   • 可证明的其他问题:
   • 上下文无关语言问题: 判断 $L(M)$ 是否是一个上下文无关语言 (CFL)。我们可以把 $M_2$ 的非正则部分换成一个“非上下文无关”的语言（比如 $\{a^nb^nc^n \mid n \ge 0\}$），而正则部分换成一个上下文无关语言（比如 $\Sigma^*$ 或 $\{0^n1^n\}$）来进行类似的构造。
   • 可判定语言问题: 判断 $L(M)$ 是否是一个可判定语言。
   • 有限语言问题: 判断 $L(M)$ 是否是一个有限集。我们可以构造 $M_2$，使其在 $M$ 接受 $w$ 时语言为 $\Sigma^*$ (无限)，在 $M$ 不接受 $w$ 时语言为 $\{0^n1^n \text{ for } n < 100\}$ (有限)。
2. 引入通用结果——赖斯定理:
   • “实际上，一个称为赖斯定理的通用结果指出...”: 与其一个一个地证明，数学家们发现这些证明都有共同的模式，于是他们将这个模式抽象出来，形成了一个一劳永逸的、非常强大的定理。
   • 赖斯定理的核心内容: “判断图灵机识别的语言的任何非平凡属性都是不可判定的。”
   • 属性 (Property): 指的是语言的某种性质。比如，“是正则的”、“是有限的”、“包含字符串'aba'”、“是空集”等等，这些都是语言的属性。
   • 非平凡属性 (Nontrivial Property): “非平凡”意味着这个属性不是对所有语言都成立，也不是对所有语言都不成立。换句话说，至少存在一个语言具有该属性，也至少存在一个语言不具有该属性。
   • 平凡属性的例子: “是一个语言”（所有图灵机语言都是语言，这是平凡的）、“可以被图灵机识别”（根据定义，所有 $L(M)$ 都可以被图灵机 $M$ 识别，这也是平凡的）。
   • 非平凡属性的例子: 我们上面提到的所有问题（空、正则、CFL、有限、包含'aba'等）都是非平凡的。例如，对于“是空语言”这个属性，$\emptyset$ 满足它，而 $\{a\}$ 不满足它。
   • 赖斯定理的威力: 有了赖斯定理，我们再遇到类似问题时，就不需要重新做复杂的归约构造了。我们只需要检查两点：
3. 这个问题是不是关于图灵机语言的属性的？（而不是关于图灵机本身，比如“这个图灵机有超过50个状态吗？”这种问题赖斯定理不管）。
4. 这个属性是不是非平凡的？
   • 如果两点都满足，我们就可以直接“引用赖斯定理”，宣布该问题是不可判定的。
5. 预告: “我们在问题5.16中给出赖斯定理。” 这表明本书将在习题部分对赖斯定理进行更详细的阐述和证明。

这一段引入了本节的第四个不可判定问题：图灵机等价性问题 ($EQ_{\mathrm{TM}}$)，并特别指出，这次的证明将采用一个新的策略。

1. 回顾与展望:
   • “到目前为止，我们证明语言不可判定的策略涉及从$A_{\text {TM }}$进行归约。”: 总结了前面的所有证明 ($HALT_{\mathrm{TM}}$, $E_{\mathrm{TM}}$, $REGULAR_{\mathrm{TM}}$) 都是直接或间接地把“万恶之源” $A_{\mathrm{TM}}$ 归约过来。
   • “有时...从其他不可判定语言...进行归约会更方便。”: 提出了一个新的思路。既然我们已经证明了 $HALT_{\mathrm{TM}}$ 和 $E_{\mathrm{TM}}$ 也是不可判定的，它们也加入了“不可判定问题俱乐部”，成为了新的“困难源头”。现在，我们可以不必每次都回到最初的 $A_{\mathrm{TM}}$，而是可以从任何一个已知的不可判定问题出发。这体现了归约的传递性。如果 $A \le_m B$ 且 $B \le_m C$，则 $A \le_m C$。
   • “借此机会提供一个通过从$E_{\mathrm{TM}}$进行归约来证明不可判定性的示例。”: 明确了本节证明的教学目的——演示如何利用一个“中途”的不可判定问题 ($E_{\mathrm{TM}}$) 来进行归约。
2. 引入新问题 $EQ_{\mathrm{TM}}$:
   • 问题描述: “测试两台图灵机的等价性”。
   • “等价”的定义: 在这里，“等价”指的是它们识别（接受）完全相同的语言。即 $L(M_1) = L(M_2)$。两个图灵机内部的实现逻辑、状态数、运行时间可以完全不同，但只要它们最终接受的字符串集合一模一样，我们就说它们是等价的。
   • 问题的重要性: 这个问题在程序验证、编译器优化等领域至关重要。例如，我想用一个更优化的程序 $M_2$ 去替换一个旧的程序 $M_1$，我必须保证 $M_2$ 和 $M_1$ 在功能上是完全等价的，即 $L(M_1) = L(M_2)$。这个定理告诉我们，不存在一个通用的算法来自动完成这种等价性检查。
3. 形式化定义:
   • 给出了 $EQ_{\mathrm{TM}}$ 的集合表示。

这是定理5.4的“证明思路”。它揭示了这次归约构造为何如此简单和直观。

1. 确定归约方向和框架:
   • 框架: 依然是反证法。假设 $EQ_{\mathrm{TM}}$ 可判定。
   • 目标: 利用这个假设，证明 $E_{\mathrm{TM}}$ 可判定，从而导出矛盾。
   • 归约方向: $E_{\mathrm{TM}} \le_m EQ_{\mathrm{TM}}$。
2. 核心思想——特例化 (Specialization):
   • 分析两个问题:
   • $E_{\mathrm{TM}}$ 问题：输入 $\langle M \rangle$，问 $L(M) = \emptyset$ ?
   • $EQ_{\mathrm{TM}}$ 问题：输入 $\langle M_1, M_2 \rangle$，问 $L(M_1) = L(M_2)$ ?
   • 发现关系: 仔细观察，你会发现 $E_{\mathrm{TM}}$ 问题看起来就像是 $EQ_{\mathrm{TM}}$ 问题的一个“特殊情况”。
   • 如何特殊化: 如果在 $EQ_{\mathrm{TM}}$ 问题中，我们把其中一台机器，比如说 $M_2$，固定成一台我们已知的、其语言就是空集 $\emptyset$ 的机器，那么 $EQ_{\mathrm{TM}}$ 问题就变成了：
3. 归约的构造蓝图:
   • 假设我们有一个能判定 $EQ_{\mathrm{TM}}$ 的“黑盒子” $R$。
   • 我们要构造一个能判定 $E_{\mathrm{TM}}$ 的机器 $S$。
   • $S$ 的工作流程如下：
   • $S$ 接收输入 $\langle M \rangle$。它的任务是判断 $L(M)$ 是否为空。
   • $S$ 不直接处理 $M$，而是先构造一个非常简单的、固定的图灵机 $M_\emptyset$，这个 $M_\emptyset$ 的功能就是拒绝所有输入，所以我们确切地知道 $L(M_\emptyset) = \emptyset$。
   • 然后，$S$ 把 $\langle M, M_\emptyset \rangle$ 这一对图灵机的编码，作为输入喂给“黑盒子” $R$。
   • $S$ 等待 $R$ 的回答。$R$ 会告诉我们 $L(M)$ 是否等于 $L(M_\emptyset)$。
   • 如果 $R$ 回答“是”（接受），那就意味着 $L(M) = L(M_\emptyset) = \emptyset$。这正是 $S$ 想要知道的！于是 $S$ 就可以接受。
   • 如果 $R$ 回答“否”（拒绝），那就意味着 $L(M) \neq L(M_\emptyset) = \emptyset$。于是 $S$ 就可以拒绝。
   • 这个构造非常直接，几乎没有复杂的逻辑。

这部分是定理5.4的严格形式化证明，其简洁性体现了证明思路的巧妙。

第一部分：$S$ 的形式化描述

• “我们设图灵机$R$判定$E Q_{\text {TM }}$，并构造图灵机$S$来判定$E_{\text {TM }}$，如下所示。”: 设立反证法框架。假设存在 $EQ_{\mathrm{TM}}$ 判定器 $R$，用它构造 $E_{\mathrm{TM}}$ 判定器 $S$。

• $S$ 的算法:
• “在输入$\langle M\rangle$上，其中$M$是图灵机：”: $S$ 接收一个图灵机 $M$ 的编码。它的目标是判断 $L(M)$ 是否为空。
• “1. 在输入$\left\langle M, M_{1}\right\rangle$上运行$R$，其中$M_{1}$是拒绝所有输入的图灵机。”: 这是整个归约的核心。
• $S$ 首先需要一个“参照物”——一个我们确定其语言为空的图灵机。这里选择了 $M_1$，一个非常简单的、对任何输入都直接拒绝的图灵机。我们可以轻易地写出 $M_1$ 的描述，它只有一个状态，无论读到什么符号都进入拒绝状态。因此，我们确切地知道 $L(M_1) = \emptyset$。
• $S$ 将它自己的输入 $\langle M \rangle$ 和这个固定的参照物 $\langle M_1 \rangle$ 配对，形成一个新的输入 $\langle M, M_1 \rangle$。
• $S$ 将这个配对的输入交给假想的 $EQ_{\mathrm{TM}}$ 判定器 $R$ 去处理。
• “2. 如果$R$接受，则接受；如果$R$拒绝，则拒绝。”: $S$ 的最终决定完全复制 $R$ 的决定。

第二部分：逻辑分析

• $S$ 的决策逻辑:
• 如果 $R$ 接受 $\langle M, M_1 \rangle$，根据 $R$ 的定义，这意味着 $L(M) = L(M_1)$。既然我们知道 $L(M_1) = \emptyset$，这就等价于 $L(M) = \emptyset$。这正是 $E_{\mathrm{TM}}$ 问题所要判断的“是”的情况。所以 $S$ 接受是正确的。
• 如果 $R$ 拒绝 $\langle M, M_1 \rangle$，根据 $R$ 的定义，这意味着 $L(M) \neq L(M_1)$。既然 $L(M_1) = \emptyset$，这就等价于 $L(M) \neq \emptyset$。这正是 $E_{\mathrm{TM}}$ 问题所要判断的“否”的情况。所以 $S$ 拒绝是正确的。

• 构造的有效性:
• 这个构造成功地将 $E_{\mathrm{TM}}$ 判定问题 $\langle M \rangle$ 转换成了 $EQ_{\mathrm{TM}}$ 判定问题 $\langle M, M_1 \rangle$。
• $L(M) = \emptyset \iff L(M) = L(M_1) \iff R \text{ 接受 } \langle M, M_1 \rangle$
• 因此，$S$ 成为了 $E_{\mathrm{TM}}$ 的一个完美判定器。

第三部分：得出矛盾

• “如果$R$判定$E Q_{\mathrm{TM}}$，则$S$判定$E_{\mathrm{TM}}$。”: 总结我们构造的成功。
• “但根据定理5.2，$E_{\mathrm{TM}}$是不可判定的，”: 引用我们之前已经证明的事实。我们已经有了一个“不可判定俱乐部”的成员 $E_{\mathrm{TM}}$。
• “因此$E Q_{\mathrm{TM}}$也必须是不可判定的。”: 反证法得出结论。既然从“$EQ_{\mathrm{TM}}$ 可判定”的假设推出了“$E_{\mathrm{TM}}$ 可判定”的谬论，那么假设错误，$EQ_{\mathrm{TM}}$ 必须是不可判定的。

这一部分引入了一个全新的、非常强大的归约技术——计算历史法 (Computation History Method)，并给出了核心概念计算历史的定义。

1. 引入新技术:
   • “计算历史方法是证明$A_{\text {TM }}$可归约到某些语言的重要技术”: 开宗明义，我们正在学习一种新的、用于构造归约的“套路”。
   • 适用场景: “当要证明不可判定的问题涉及测试某事物是否存在时，此方法通常很有用”。这里的“某事物”通常指的就是一个“合法的计算过程”。
   • 举例: 提到了一个非常著名的例子——希尔伯特第十问题。这个问题问的是：给定一个多项式方程，判断它是否存在整数解。马季亚谢维奇在1970年证明了这个问题是不可判定的，其证明的核心思想就是将图灵机的计算历史编码成一个多项式方程，使得“图灵机停机”等价于“多项式有整数解”。这展示了计算历史法的强大威力。
2. 计算历史的非形式化定义:
   • “图灵机在输入上的计算历史仅仅是机器处理输入时所经历的配置序列”: 这句话给出了一个直观的定义。
   • 配置 (Configuration/Instantaneous Description, ID): 指的是图灵机在某个瞬间的“快照”。一个快照需要包含三个信息：
3. 当前机器处于哪个状态 ($q_i$)。
4. 当前磁带上的全部内容。
5. 当前读写磁头的位置。
   • 通常，我们将这三者合在一起表示，例如 u q v，表示当前状态是 q，磁带上是字符串 uv，且磁头指向 v 的第一个符号。
   • 配置序列: 计算历史就是一连串这样的“快照”，从开始到结束，记录了计算的每一步。
   • “它是这台机器计算的完整记录”: 就像飞机的“黑匣子”，或者一段程序的“log文件”，它包含了重现整个计算过程所需的所有信息。
6. 计算历史的形式化定义 (定义 5.5):
   • 接受计算历史 (Accepting Computation History):
   • 它是一个有限的配置序列 $C_1, C_2, \ldots, C_l$。
   • 它必须满足三个条件：
7. 起始正确: $C_1$ 必须是 $M$ 在输入 $w$ 上的起始配置。通常是 $q_0w_1w_2...w_n$，其中 $q_0$ 是起始状态，磁头在 $w$ 的第一个字符上。
8. 过程合法: 序列中的每一步转换都必须是合法的。即对于任意 $i > 1$，$C_i$ 必须是根据 $M$ 的转移函数 $\delta$ 从 $C_{i-1}$ 推导出的下一个配置。
9. 结局正确: $C_l$ (最后一个配置) 必须是一个接受配置，即 $C_l$ 中包含接受状态 $q_{\text{accept}}$。
   • 拒绝计算历史 (Rejecting Computation History): 定义类似，唯一的区别是最后一个配置 $C_l$ 是一个拒绝配置（包含拒绝状态 $q_{\text{reject}}$）。
   • 如果 $M$ 在 $w$ 上循环: 那么它永远不会进入接受或拒绝状态，因此它在 $w$ 上既没有接受计算历史，也没有拒绝计算历史。

这一部分首先对计算历史做了补充说明，然后引入了我们将要研究的第一个与计算历史法相关的计算模型——线性有界自动机 (Linear Bounded Automaton, LBA)。

第一部分：计算历史的补充

• “计算历史是有限序列”: 再次强调，只有停机的计算才有计算历史。
• “确定性机器...最多有一个计算历史”: 对于DTM，路径是唯一的。
• “非确定性机器...可能有多个计算历史”: 对于NTM，一个输入可能对应多条并行的计算路径，其中一些可能接受，一些可能拒绝，一些可能循环。只要有一条路径接受，NTM就接受该输入。
• “目前，我们继续关注确定性机器”: 明确了当前讨论的范围，以简化问题。

第二部分：引入 LBA

• “我们第一个使用计算历史方法...涉及一种称为线性有界自动机的机器”: 预告了 LBA 即将扮演的角色。LBA 将作为我们构造的“计算历史检查器”。

第三部分：LBA 的定义 (定义 5.6)

• “线性有界自动机是一种受限制的图灵机”: LBA 不是一个全新的模型，它是图灵机的一个变种，其能力受到了限制。
• 核心限制: “磁头不允许移出包含输入的磁带部分”。
• 假设输入字符串是 $w$，其长度为 $n$。那么 LBA 的读写头只能在为 $w$ 分配的这 $n$ 个格子内移动。
• 这与标准图灵机形成鲜明对比，后者的磁头可以无限制地向右移动，使用无限的存储空间。
• 边界行为: “如果机器试图将磁头移出输入的两端，则磁头会停留在原地”。
• 这定义了当磁头试图“越界”时会发生什么。它不会像某些模型那样导致崩溃，而是像撞到一堵无形的墙，保持在边界单元格不动。
• 这类似于标准图灵机在最左端不能再向左移动。LBA 相当于在输入的右端也设置了这样一个“墙”。

这部分是对 LBA 定义的进一步解释，并配上了一张示意图来加深理解。

1. “内存受限的图灵机”: 再次强调 LBA 的核心特征是其有限的工作空间。
2. 示意图解读:
   • 图中的磁带: 图中画出了一条磁带，但两端被明确地标记为“左端”和“右端”，并用竖线表示边界。这与标准图灵机两端用省略号表示无限延伸的画法截然不同。
   • 输入: 输入字符串被放置在这段有界的磁带上。
   • 读写头: 读写头被画在了磁带的中间，箭头指向下方，表示它只能在这个有界区域内活动。
   • 有限自动机控制器: 和标准图灵机一样，它有一个有限状态的控制器来决定下一步的行为。
   • 整体感觉: 整个图示传达出一种“被框住”、“受限制”的感觉。
3. “它只能解决需要适应输入所用磁带的内存问题”: 这句话说明了 LBA 的能力边界。它能解决的问题，其算法所需的内存空间不能超过输入本身长度的常数倍。例如，判断一个字符串是否是回文串 ($w = w^R$)，LBA可以做到（来回比较两端的字符并做标记）。但是，如果一个问题需要 $n^2$ 或 $2^n$ 的空间（$n$是输入长度），LBA就无能为力了。
4. “使用比输入字母表更大的磁带字母表可以使可用内存增加一个常数因子”: 这是一个技术细节，解释了为什么内存是“线性”的，而不完全等于输入长度 $n$。
   • 输入字母表 $\Sigma$: 原始输入字符串中允许出现的字符集合。
   • 磁带字母表 $\Gamma$: LBA 在计算过程中允许在磁带上读写的字符集合。$\Sigma \subseteq \Gamma$。
   • 增加内存的技巧: 我们可以让 $\Gamma$ 更丰富。例如，除了原始字符 'a', 'b'，我们还可以在 $\Gamma$ 中加入带标记的字符，如 'a_dot' (表示这个a下面做了个点标记), 'b_checked' (表示这个b已经被检查过)。甚至可以用一个磁带符号表示一对或多元组，如 $\langle a, 1, \text{checked} \rangle$。如果 $\Gamma$ 的大小是 $|\Sigma|$ 的 $k$ 倍，我们相当于把每个格子的信息容量扩大了 $k$ 倍，总内存就是 $k \times n$，仍然是线性的。
5. “因此，我们说对于长度为$n$的输入，可用内存量与$n$成线性关系——因此得名。”: 总结了“线性有界”这个名字的由来。

这一部分分为两个层次：首先介绍 LBA 的强大能力和它自己的接受问题 $A_{\mathrm{LBA}}$，然后给出一个关键的引理，计算 LBA 可能配置的总数。

第一部分：LBA 的能力和 $A_{\mathrm{LBA}}$ 问题

1. “尽管有内存限制，线性有界自动机（LBA）的功能相当强大”: 作者先给我们一个“惊喜”。虽然 LBA 看起来受限，但它的计算能力远超我们的想象。
2. LBA能解决的问题:
   • $A_{\mathrm{DFA}}$: 判断一个 DFA 是否接受某个字符串。
   • $A_{\mathrm{CFG}}$: 判断一个 CFG 是否能生成某个字符串 (CYK算法)。
   • $E_{\mathrm{DFA}}$: 判断一个 DFA 的语言是否为空。
   • $E_{\mathrm{CFG}}$: 判断一个 CFG 的语言是否为空。
   • “每个CFL都可以由LBA判决”: 接受一个上下文无关语言的问题，LBA 都能解决。
3. LBA 不能解决的可判定语言: “要找到一个不能由LBA判决的可判定语言需要一些功夫”。这暗示了 LBA 的能力上限，但指出找到这样的例子并不容易。这部分内容将在第9章（空间复杂性）中讨论。
4. 引入 $A_{\mathrm{LBA}}$ 问题: 这是 LBA 版本的“接受问题”。
   • 与 $A_{\mathrm{TM}}$ 的对比: 它的定义形式和 $A_{\mathrm{TM}}$ 一模一样，只是把“TM”换成了“LBA”。
   • 核心区别: $A_{\mathrm{TM}}$ 是不可判定的，而我们马上要证明 $A_{\mathrm{LBA}}$ 是可判定的。这是图灵机和线性有界自动机一个根本性的区别。

第二部分：引理 5.8

1. 引理的作用: “在证明$A_{\mathrm{LBA}}$的可判定性之前，我们发现以下引理很有用”。这个引理是证明 $A_{\mathrm{LBA}}$ 可判定性的基石。
2. 引理内容: “LBA只能有有限数量的配置”。这是由其有限的内存决定的。引理给出了这个有限数量的精确计算公式。
3. 形式化陈述:
   • 给定参数:
   • $q$: LBA 的状态总数。
   • $g$: LBA 的磁带字母表 $\Gamma$ 中的符号总数。
   • $n$: 输入字符串的长度，也就是磁带的长度。
   • 结论: LBA 在此设置下，总共有 $q \times n \times g^n$ 个不同的配置。

这部分是引理5.8的详细证明，它解释了公式 $qng^n$ 是如何通过基本计数原理推导出来的。

1. “回想一下，$M$的配置就像其计算过程中的快照。”: 再次使用“快照”这个直观的比喻来定义配置。
2. “配置由控制状态、磁头位置和磁带内容组成。”: 明确指出构成一个配置的三个独立要素。这是应用乘法原理的前提。
3. 逐项分析可能性的数量:
   • 控制状态: “$M$有$q$个状态。” 所以，状态部分有 $q$ 种可能性。
   • 磁头位置: “其磁带长度为$n$，因此磁头可以位于$n$个位置之一。” 所以，磁头位置部分有 $n$ 种可能性。
   • 磁带内容: “并且磁带上可以出现$g^{n}$种可能的磁带符号串。”
   • 磁带有 $n$ 个格子。
   • 每个格子可以填入 $g$ 个不同符号中的任意一个。
   • 第1个格子有 $g$ 种选择。
   • 第2个格子有 $g$ 种选择。
   • ...
   • 第 $n$ 个格子有 $g$ 种选择。
   • 根据乘法原理，总的磁带内容组合数是 $g \times g \times \ldots \times g$ ($n$次)，即 $g^n$。
4. “这三个量的乘积是$M$在长度为$n$的磁带上不同配置的总数。”:
   • 将三个独立要素的可能性数量相乘，得到最终结果。
   • 总数 = (状态的可能性) $\times$ (磁头位置的可能性) $\times$ (磁带内容的可能性)
   • 总数 = $q \times n \times g^n$

这是定理5.9的“证明思路”，解释了为什么 $A_{\mathrm{LBA}}$ 是可判定的，这与 $A_{\mathrm{TM}}$ 形成了鲜明对比。

1. 目标: 构造一个判定器来解决 $A_{\mathrm{LBA}}$。这个判定器在任何输入 $\langle M, w \rangle$ (其中 M 是 LBA) 上，都能在有限时间内给出“接受”或“拒绝”的答案。
2. 基本策略: 模拟。最直接的方法就是模拟 LBA $M$ 在输入 $w$ 上的运行。
3. 遇到的困难: 和之前分析 $A_{\mathrm{TM}}$ 时一样，直接模拟的最大障碍是无限循环。如果 $M$ 在 $w$ 上循环，我们的模拟器也会跟着循环，这就无法成为一个判定器。
4. 解决困难的关键——检测循环:
   • 循环的本质: 一个确定性计算模型（如 LBA 或 DTM）如果进入了它曾经到达过的同一个配置，那么由于其后续行为是完全由当前配置决定的，它必然会重复从那个配置开始的整个计算序列，从而陷入无限循环。
   • LBA 的特殊性: 与标准图灵机不同，LBA 的配置总数是有限的！引理5.8给了我们这个定心丸，并算出了确切的上限：$qng^n$。
   • 鸽巢原理 (Pigeonhole Principle): 想象有 $k = qng^n$ 个“鸽巢”（代表所有可能的配置），而 LBA 的计算过程是不断放出“鸽子”（代表当前的配置）。如果 LBA 运行了 $k+1$ 步，它就放出了 $k+1$ 只鸽子。由于只有 $k$ 个鸽巢，必然至少有一只鸽子飞进了它之前飞过的巢，即配置发生了重复。
   • 检测方法: 因此，我们不需要在模拟时存储所有见过的配置并进行比较（虽然这也是一种方法）。一个更简单的方法是设置一个“计时器”。我们让模拟最多运行 $qng^n$ 步。
   • 如果在这 $qng^n$ 步之内，$M$ 停机了（接受或拒绝），那很好，我们得到了答案。
   • 如果运行了 $qng^n$ 步之后，$M$ 仍然没有停机，我们就可以百分之百地确定它已经进入了一个无限循环。因为它已经经历了 $qng^n+1$ 个配置，必然有重复。
5. 完整的判定策略:
   • 给定输入 $\langle M, w \rangle$。
   • 首先从 $M$ 的描述中提取状态数 $q$，从磁带字母表中得到符号数 $g$，并测量输入 $w$ 的长度 $n$。
   • 计算出配置数上限 $k = qng^n$。
   • 开始模拟 $M$ 在 $w$ 上的运行，并同时启动一个步数计数器，从0开始。
   • 在每一步模拟后，计数器加1。
   • 如果在模拟过程中，$M$ 进入接受状态，则我们的判定器接受并停机。
   • 如果在模拟过程中，$M$ 进入拒绝状态，则我们的判定器拒绝并停机。
   • 如果计数器的值达到了 $qng^n$，而模拟仍未结束，我们的判定器就强行停止模拟，并直接拒绝（因为我们断定它已经循环了）。

这个策略覆盖了所有可能性，并且保证在有限步内（最多 $qng^n$ 步）结束。因此，它是一个有效的判定器。

这部分是定理5.9的严格形式化证明，它将“证明思路”中的策略描述成一个具体的算法。

第一部分：算法 L 的描述

• “判定$A_{\mathrm{LBA}}$的算法如下。$L=$”: 我们将要构造的这个判定器命名为 $L$。
• “在输入$\langle M, w\rangle$上，其中$M$是LBA，$w$是字符串：”: 算法 $L$ 的输入。

• “1. 模拟$M$在$w$上的运行，持续$q n g^{n}$步或直到停机。”: 这是算法的核心步骤。
• 准备工作 (隐含): 在开始模拟前，判定器 $L$ 首先需要从输入 $\langle M, w \rangle$ 中解析出三个关键参数：
• $q$: $M$ 的状态数。
• $g$: $M$ 的磁带字母表大小。
• $n$: $w$ 的长度。
• 然后计算出步数上限 $k = qng^n$。
• 模拟过程: $L$ 启动一个通用 LBA 模拟器，并设置一个计数器。
• 停止条件: 这个模拟过程有两个停止条件，哪个先满足就按哪个来：

1. $M$ 自己停机了（进入接受或拒绝状态）。
2. 模拟的步数达到了上限 $k = qng^n$。
   • 由于 $k$ 是一个有限的可计算的数，这个模拟步骤保证会在有限时间内结束。

• “2. 如果$M$已停机，如果它接受了，则接受；如果它拒绝了，则拒绝。如果它没有停机，则拒绝。”: 这是模拟结束后，$L$ 如何做出最终判决的规则。
• 情况1: $M$ 自己停机了: 这意味着模拟是因为第一个停止条件而结束的。
• 如果 $M$ 的停机状态是接受，那么 $\langle M, w \rangle \in A_{\mathrm{LBA}}$，所以 $L$ 也接受。正确。
• 如果 $M$ 的停机状态是拒绝，那么 $\langle M, w \rangle \notin A_{\mathrm{LBA}}$，所以 $L$ 也拒绝。正确。
• 情况2: $M$ 没有停机: 这意味着模拟是因为第二个停止条件（超时）而结束的。
• “如果它没有停机，则拒绝。”: 此时 $L$ 直接拒绝。
• 理由: 正如“证明思路”中分析的，运行了 $qng^n$ 步还没停，意味着 LBA $M$ 必定已经重复了至少一个配置，陷入了无限循环。既然 $M$ 循环了，它就不会接受 $w$，所以 $\langle M, w \rangle \notin A_{\mathrm{LBA}}$。因此 $L$ 拒绝是正确的。

第二部分：证明总结

• “如果$M$在$w$上在$q n g^{n}$步内没有停机，它必然根据引理5.8重复了一个配置，因此正在循环。”: 对算法第2步中“超时则拒绝”的合理性进行了再次说明，强调了其理论基础是引理5.8和鸽巢原理。
• “这就是为什么我们的算法在这种情况下拒绝的原因。”: 总结陈词。

这一段是一个重要的转折。它在刚刚证明了 LBA 的一个“好消息” ($A_{\mathrm{LBA}}$ 可判定) 之后，立刻要给我们一个“坏消息”，即 LBA 的空语言问题 $E_{\mathrm{LBA}}$ 依然是不可判定的。

1. 承上启下:
   • 回顾不同点: “定理5.9表明LBA和TM在一个基本方面有所不同：对于LBA，接受问题是可判定的，但对于TM则不然。” 这是对 $A_{\mathrm{LBA}}$ 和 $A_{\mathrm{TM}}$ 性质差异的总结。这个差异的根源在于内存是否有限。
   • 引入相似点: “然而，某些涉及LBA的其他问题仍然是不可判定的。” 这句话告诉我们，不要因为 $A_{\mathrm{LBA}}$ 可判定就认为 LBA 是一个“简单”的模型。在其他方面，它和标准图灵机一样，能够引发不可判定性。
2. 引入新问题 $E_{\mathrm{LBA}}$:
   • 问题名称: 空性问题 $E_{\mathrm{LBA}}$。
   • 形式化定义: $E_{\mathrm{LBA}}=\{\langle M\rangle \mid M \text{ 是一个LBA且 } L(M)=\emptyset\}$。
   • 问题描述: 给定一个 LBA 的编码 $\langle M \rangle$，判断它所接受的语言是否为空集。即，是否存在任何一个字符串 $w$，使得 $M$ 接受 $w$？如果不存在这样的 $w$，则 $L(M)=\emptyset$。
   • 与 $E_{\mathrm{TM}}$ 的关系: 这个问题的定义与 $E_{\mathrm{TM}}$ 完全一样，只是把“TM”换成了“LBA”。
3. 声明证明策略:
   • “为了证明$E_{\mathrm{LBA}}$是不可判定的，我们给出一个使用计算历史方法的归约。”:
   • 目标: 证明 $E_{\mathrm{LBA}}$ 不可判定。
   • 工具: 计算历史方法。
   • 手段: 归约。具体来说，我们将从一个已知的不可判定问题（$A_{\mathrm{TM}}$）归约到 $E_{\mathrm{LBA}}$。即证明 $A_{\mathrm{TM}} \le_m E_{\mathrm{LBA}}$。

这是定理5.10“计算历史归约法”的证明思路。它描绘了如何将一个“动态的计算过程”问题 ($A_{\mathrm{TM}}$) 转化为一个“静态的语言属性”问题 ($E_{\mathrm{LBA}}$)。

1. 确定框架:
   • 方法: 从 $A_{\mathrm{TM}}$ 归约的反证法。
   • 假设: $E_{\mathrm{LBA}}$ 可判定，即存在一个判定器 $R_{ELBA}$。
   • 目标: 利用 $R_{ELBA}$ 构造 $A_{\mathrm{TM}}$ 的判定器 $S_{ATM}$。
2. 核心构造思想:
   • $S_{ATM}$ 接收输入 $\langle M, w \rangle$。它的目标是判断 $M$ 是否接受 $w$。
   • $S_{ATM}$ 会根据 $M$ 和 $w$ 构造一个特定的 LBA，我们称之为 $B$。
   • 这个 LBA $B$ 被设计成一个“计算历史验证器”。
   • $B$ 的语言 $L(B)$ 被设计为：包含且仅包含 $M$ 在 $w$ 上的接受计算历史的字符串表示。
3. 分析 $L(B)$ 的性质:
   • 情况1: 如果 $M$ 接受 $w$。
   • 那么根据定义，必然存在一个接受计算历史 (一个配置序列 $C_1, \ldots, C_l$)。
   • 我们将这个序列编码成一个单一的字符串（例如，用 # 分隔每个配置：#C1#C2#...#Cl#）。这个字符串就是 $M$ 在 $w$ 上的接受计算历史的表示。
   • LBA $B$ 被设计成会接受这个特定的字符串。
   • 因此，在这种情况下，$L(B)$ 至少包含一个元素，所以 $L(B)$ 非空。
   • 情况2: 如果 $M$ 不接受 $w$ (拒绝或循环)。
   • 那么根据定义，不存在接受计算历史。
   • 因此，没有任何一个字符串是“$M$在$w$上的接受计算历史”。
   • LBA $B$ 被设计成只接受这种字符串，所以它将不接受任何输入。
   • 因此，在这种情况下，$L(B)$ 为空 ($L(B) = \emptyset$)。
4. 如何利用假想的判定器 $R_{ELBA}$:
   • $S_{ATM}$ 将构造好的 $\langle B \rangle$ 输入给 $R_{ELBA}$。
   • 如果 $R_{ELBA}$ 接受 $\langle B \rangle$，说明它判断 $L(B)$ 是空的。这对应情况2，意味着 $M$ 不接受 $w$。所以 $S_{ATM}$ 应该拒绝。
   • 如果 $R_{ELBA}$ 拒绝 $\langle B \rangle$，说明它判断 $L(B)$ 是非空的。这对应情况1，意味着 $M$ 接受 $w$。所以 $S_{ATM}$ 应该接受。
   • 通过这种方式，$S_{ATM}$ 利用 $R_{ELBA}$ 完美地判定了 $A_{\mathrm{TM}}$。
5. 对构造过程的要求:
   • “我们不仅需要展示$B$的存在，还需要展示图灵机如何在给定$M$和$w$的描述的情况下获得$B$的描述”: 这是一个关键的技术要点。归约本身必须是一个可计算的过程。我们的 $S_{ATM}$ 必须是一个图灵机，它执行的“构造 LBA $B$”这个动作，必须是一个算法。我们必须能说清楚 $S_{ATM}$ 是如何一步步生成 $B$ 的编码的。
6. 再次强调“构造不运行”:
   • “我们构造$B$只是为了将其描述输入到假定的$E_{\mathrm{LBA}}$判决器中，而不是为了在某些输入上运行$B$”: 和之前的证明一样，$S_{ATM}$ 只是 $B$ 的“设计师”，它从不运行 $B$。$S_{ATM}$ 的工作是创造出一个“艺术品”（$B$ 的描述），然后把它交给“鉴定师”（$R_{ELBA}$）去评判。

这一部分开始深入到 LBA $B$ 的具体构造细节。$B$ 是一个“计算历史验证器”。这里描述了 $B$ 的输入格式和它要执行的验证任务。

1. 输入格式:
   • LBA $B$ 的输入，我们称之为 $x$，是一个字符串。
   • 这个字符串 $x$ 声称自己是一个“$M$在$w$上的接受计算历史”。
   • 为了让机器能够处理，我们将这个计算历史的配置序列 $C_1, C_2, \ldots, C_l$ 编码成一个单一字符串。
   • 编码方式: 使用一个特殊的分隔符 # (假设它不在 $M$ 的字母表中) 来隔开每个配置。
   • 图5.11的解释:
   • 图中展示了一个长条，代表字符串 $x$。
   • # C1 # C2 # ... # Cl #: 这就是 $x$ 的格式。它以 # 开头，以 # 结尾，中间是用 # 分隔的各个配置 $C_i$。
   • 这个字符串 $x$ 就是 LBA $B$ 要分析的对象。
2. LBA $B$ 的工作流程 (高层描述):
   • $B$ 接收一个输入字符串 $x$。
   • 它的目标是：如果 $x$ 确实是 $M$ 在 $w$ 上的一个合法的接受计算历史，那么 $B$ 就接受 $x$；否则，$B$ 拒绝 $x$。
   • 为了做到这一点，$B$ 需要像一个裁判一样，检查 $x$ 是否满足成为“接受计算历史”的所有条件。
3. 验证的三个核心条件:
   • $B$ 首先会解析字符串 $x$，利用 # 分隔符把它切分成一个个的配置字符串 $C_1, C_2, \ldots, C_l$。然后，它依次检查以下三件事：
   • 条件1: 起点是否正确?
   • $B$ 需要验证 $C_1$ 是否等于 $M$ 在 $w$ 上的起始配置。
   • 起始配置是由 $M$ 的起始状态 $q_0$ 和输入 $w$ 唯一决定的，通常是 $q_0w$。
   • 由于 $S_{ATM}$ 在构造 $B$ 的时候，是知道 $M$ 和 $w$ 的，所以它可以把“正确的起始配置 $q_0w$”这个字符串硬编码到 $B$ 的逻辑里。$B$ 只需要比较它的第一个配置 $C_1$ 和它内心存着的那个标准答案是否一致即可。
   • 条件2: 每一步转换是否合法?
   • 这是最核心、最复杂的检查。$B$ 需要遍历所有相邻的配置对 $(C_i, C_{i+1})$，检查从 $C_i$ 到 $C_{i+1}$ 的转换是否符合 $M$ 的转移函数 $\delta$。
   • 一次合法的转换，只会改变磁头周围很小一片区域。$C_i$ 和 $C_{i+1}$ 在大部分位置上应该是完全相同的。$B$ 需要验证：
   • 远离磁头的地方，内容不变。
   • 磁头下的符号、状态、磁头的新位置，这三者的变化是否与 $\delta$ 的某条规则匹配。
   • 条件3: 终点是否正确?
   • $B$ 需要验证最后一个配置 $C_l$ 是否是一个接受配置。
   • 这很简单， $B$ 只需要扫描 $C_l$ 这个字符串，看看里面是否包含 $M$ 的接受状态 $q_{\text{accept}}$ 即可。
4. LBA 的角色: 整个过程，LBA $B$ 都在自己的输入磁带（即字符串 $x$）上来回移动、比较、做标记，来完成这三项检查。由于 $x$ 的长度是有限的，LBA 的有限内存是足够的。

这一段详细描述了 LBA $B$ 是如何执行之前提到的三项检查的，特别是最难的第二项。

1. 检查条件1 (起始配置):
   • “$M$在$w$上的起始配置$C_{1}$是字符串$q_{0} w_{1} w_{2} \cdots w_{n}$...$B$直接内置了这个字符串，因此它能够检查第一个条件。”
   • 这是说，在构造 LBA $B$ 的时候，我们的构造算法 $S$ 会把正确的起始配置（例如 q0abc）作为一个常量字符串“写死”在 $B$ 的程序逻辑里。
   • 当 $B$ 运行时，它只需要读取输入 $x$ 的第一部分（直到第一个 #），然后和它内置的这个“标准答案”进行逐字符比较。如果完全一样，检查通过。
2. 检查条件3 (接受配置):
   • “接受配置是包含$q_{\text {accept }}$状态的配置，因此$B$可以通过扫描$C_{l}$寻找$q_{\text {accept }}$来检查第三个条件。”
   • 这个检查也很简单。$B$ 移动到输入 $x$ 的末尾，找到最后一个配置 $C_l$。然后，它在 $C_l$ 这个子字符串上从头到尾扫描一遍，寻找是否存在 $q_{\text{accept}}$ 这个子串。如果找到了，检查通过。
3. 检查条件2 (合法转移):
   • “第二个条件最难检查。”: 这是整个验证过程的技术核心。
   • “对于每对相邻配置，$B$检查$C_{i+1}$是否合法地跟随$C_{i}$。”: $B$ 需要做一个循环，依次处理 $(C_1, C_2), (C_2, C_3), \ldots, (C_{l-1}, C_l)$。
   • “此步骤涉及验证$C_{i}$和$C_{i+1}$除了磁头下方和相邻位置外是否相同。”: 一步图灵机转移只会影响局部。比如，如果转移函数是 $\delta(q, a) = (p, b, R)$，那么在配置串中，只有状态 q 会变成 p，q 右边的符号 a 会变成 b，并且状态 p 会出现在 b 的右边。其他远离这三个位置（状态、磁头原位置、磁头新位置）的符号都应该保持不变。
   • “然后$B$通过在$C_{i}$和$C_{i+1}$的相应位置之间进行之字形移动来验证更新是否正确完成。”: 这是 LBA 在有限内存上进行比较的经典技巧。
   • 想象 LBA 的磁带上写着 ...#Ci#Ci+1#...。
   • $B$ 的磁头先定位到 $C_i$ 的第一个字符。
   • 它需要比较 $C_i$ 的第 $k$ 个字符和 $C_{i+1}$ 的第 $k$ 个字符是否相同（对于远离磁头的位置）。
   • 为了实现这一点，$B$ 会：
4. 读取 $C_i$ 的第 $k$ 个字符，并用一个特殊的“已读”标记（比如在字符下面加个点）来改写它，以记住自己读了什么以及读到了哪里。
5. 然后磁头向右长途跋涉，越过 #，到达 $C_{i+1}$ 的第 $k$ 个字符。
6. 比较这里的字符是否和它刚才记住的一样。如果不一样（并且这里不是合法的磁头活动区域），则验证失败，B拒绝。
7. 如果一样，它也在这里做一个标记，然后回头，长途跋涉回到 $C_i$ 中刚刚标记过的位置的右边一个，即第 $k+1$ 个字符。
8. 重复这个“之”字形或“Z”字形的来回比较过程，直到 $C_i$ 和 $C_{i+1}$ 都被比较完毕。
   • “为了在之字形移动时跟踪当前位置，$B$用点标记磁带上的当前位置。”: 这就是刚才描述的技巧。LBA 利用它可写的磁带，在输入上做标记，充当“指针”或“书签”，来辅助自己完成复杂的比较任务。这正是 LBA 虽然内存有限但功能强大的原因。
   • “最后，如果满足条件1、2和3，$B$接受其输入。”: 只有当所有检查都成功通过后，$B$ 才会进入接受状态。任何一步检查失败，都会导致 $B$ 立刻进入拒绝状态。

这部分是定理5.10的最终形式化证明，并附上了 LBA $B$ 的工作流程图。

第一部分：$S$ 的形式化描述

• “通过反转判决器的答案...”: 这是对“证明思路”的总结，预示了 $S$ 的决策逻辑。
• $S$ 的算法:
• “在输入$\langle M, w\rangle$上...”: $S$ 接收 $A_{\mathrm{TM}}$ 的一个实例。
• “1. 根据证明思路中的描述，从$M$和$w$构造LBA $B$。”:
• 这是 $S$ 的核心构造步骤。$S$ 作为一个“编译器”，读取 $M$ 的转移函数和字符串 $w$，然后生成 LBA $B$ 的完整描述。$B$ 的逻辑就是我们刚刚详细讨论过的“计算历史验证器”。这个构造过程是纯算法的，是可计算的。
• “2. 在输入$\langle B\rangle$上运行$R$。”: $S$ 调用假设存在的 $E_{\mathrm{LBA}}$ 判定器 $R$，并将它刚刚的“作品” $\langle B \rangle$ 作为输入。
• “3. 如果$R$拒绝，则接受；如果$R$接受，则拒绝。”: $S$ 的最终判决与 $R$ 的判决相反。
• 为什么相反？
• $R$ 接受 $\iff L(B) = \emptyset \iff M$ 不接受 $w$。所以 $S$ 应该拒绝。
• $R$ 拒绝 $\iff L(B) \neq \emptyset \iff M$ 接受 $w$。所以 $S$ 应该接受。
• 这个逻辑是正确的。

第二部分：逻辑分析与矛盾

• “如果$R$接受$\langle B\rangle$...”: 这段话详细地重申了上一条的逻辑，确保读者完全理解为什么 $S$ 的判决是正确的，以及为什么它要和 $R$ 反着来。
• 这个构造成功地用 $R$ (判定 $E_{\mathrm{LBA}}$) 造出了 $S$ (判定 $A_{\mathrm{TM}}$)。
• 这与 $A_{\mathrm{TM}}$ 不可判定相矛盾。
• 因此，最初的假设（$R$ 存在）是错误的。$E_{\mathrm{LBA}}$ 是不可判定的。

第三部分：图 5.12 解读

• 图的标题: “LBA $B$检查图灵机计算历史”。
• 图的整体结构: 这是一个流程图，描述了 LBA $B$ 在接收其输入 $x$（即计算历史字符串）后所做的事情。
• 起点: “输入x (计算历史)”
• 第一步: “把x分解成C1, ..., Cl”: 对应解析输入字符串。
• 第二步: “C1是M在w上的起始配置吗?”: 对应检查条件1。
• 如果是“否”，则“拒绝”。
• 如果是“是”，则进入下一步。
• 第三步: “Cl是接受配置吗?”: 对应检查条件3。
• 如果是“否”，则“拒绝”。
• 如果是“是”，则进入下一步。
• 第四步 (循环): “对于每个i从1到l-1”: 这是一个循环结构，对应检查条件2。
• 循环体: “Ci+1合法地跟随Ci吗?”
• 如果对于任何一个 $i$，“否”，则“拒绝”。
• 只有当所有的 $i$ 都检查通过（“是”）后，才能退出循环。
• 终点: 如果所有检查都通过了，流程最终指向“接受”。
• 图的意义: 这张图以一种非常直观的方式，总结了 LBA $B$ 的内部工作逻辑。它清晰地表明，$B$ 本身就是一个复杂的算法，而这个算法的目标就是验证一个字符串的语法和语义。

这一段将我们的战场从图灵机和LBA，转移到了更简单的计算模型——上下文无关文法 (Context-Free Grammar, CFG) 和 下推自动机 (Pushdown Automaton, PDA)，并引入了本节的新主角：$ALL_{\mathrm{CFG}}$ 问题。

1. 应用领域的扩展:
   • “我们也可以使用通过计算历史进行归约的技术来建立...不可判定性”: 指出“计算历史法”这个工具非常强大，不仅能用于证明关于 TM 和 LBA 的问题，还能“降维打击”，用来证明关于 CFG 和 PDA 的问题。
2. 回顾与对比:
   • 回顾: “回想一下...定理4.8中...判断上下文无关文法是否生成任何字符串——也就是说，是否$L(G)=\emptyset$。”
   • 在第4章，我们证明了 CFG的空语言问题 $E_{\mathrm{CFG}}$ 是可判定的。我们可以通过一个算法，检查一个文法 G 是否能生成任何字符串。
   • 对比: “现在我们证明一个相关的问题是不可判定的。”
   • 这里形成了一个鲜明的对比，类似于 $A_{\mathrm{LBA}}$ (可判定) vs $E_{\mathrm{LBA}}$ (不可判定)。对于 CFG，空语言问题 $E_{\mathrm{CFG}}$ 是可判定的，但我们将要证明的全语言问题 $ALL_{\mathrm{CFG}}$ 是不可判定的。
   • 这种“对称”问题的性质差异，是计算理论中一个非常迷人的主题。
3. 引入新问题 $ALL_{\mathrm{CFG}}$:
   • 问题描述: “判断上下文无关文法是否生成所有可能字符串的问题。”
   • 动机: “证明这个问题是不可判定的，是证明上下文无关文法等价性问题不可判定的主要步骤。” 这句话指出了研究 $ALL_{\mathrm{CFG}}$ 的一个重要目的，它是证明 $EQ_{\mathrm{CFG}}$ (判断两个CFG是否等价) 不可判定的垫脚石。
4. 形式化定义:
   • 给出了 $ALL_{\mathrm{CFG}}$ 的集合表示。

这是定理5.13的“证明思路”的第一部分，它设定了归约的总体策略，这个策略非常巧妙，与之前的证明有所不同。

1. 确定框架:
   • 方法: 从 $A_{\mathrm{TM}}$ 归约的反证法。
   • 假设: $ALL_{\mathrm{CFG}}$ 可判定，即存在一个判定器 $R_{ALL}$。
   • 目标: 利用 $R_{ALL}$ 构造 $A_{\mathrm{TM}}$ 的判定器 $S_{ATM}$。
2. 预告“转折”:
   • “这个证明类似于定理5.10的证明”: 说明我们仍然会使用计算历史这个核心工具。
   • “但有一个小的额外转折...稍微修改了计算历史的表示方式”: 这是一个重要的提醒。直接使用 #C1#C2#... 这种格式的计算历史，对于 CFG (或 PDA) 来说，验证起来有困难。我们需要对这个“证据”的格式做一些手脚，让 PDA 能更方便地处理。
3. 核心构造思想 (反向逻辑):
   • 之前的证明 $E_{\mathrm{LBA}}$ 时，我们构造的 LBA $B$ 的语言是接受计算历史的集合。所以 $L(B)$ 非空 $\iff M$ 接受 $w$。
   • 这次，我们的目标是使用 $ALL_{\mathrm{CFG}}$ 判定器。这个判定器关心的是语言是否为 $\Sigma^*$。
   • 因此，我们的构造策略是反过来的：
   • 我们要构造一个 CFG $G$。
   • 这个 $G$ 的语言 $L(G)$ 被设计为：所有不是 $M$ 在 $w$ 上的接受计算历史的字符串的集合。
   • 即，$L(G) = \Sigma^* - \{ \text{x} \mid \text{x 是 M 在 w 上的接受计算历史} \}$ (这里用集合减法表示)。
4. 分析 $L(G)$ 的性质:
   • 情况1: 如果 $M$ 不接受 $w$。
   • 那么，不存在接受计算历史。
   • 这意味着“$M$在$w$上的接受计算历史”的集合是空集。
   • 所以 $L(G) = \Sigma^* - \emptyset = \Sigma^*$。在这种情况下，文法 $G$ 生成全语言。
   • 情况2: 如果 $M$ 接受 $w$。
   • 那么，存在一个（对于确定性TM）或多个（对于NTM）接受计算历史。
   • 假设 $x_{accept}$ 是那个唯一的接受计算历史字符串。
   • 那么 $L(G) = \Sigma^* - \{x_{accept}\}$。
   • 在这种情况下，文法 $G$ 生成了除了 $x_{accept}$ 之外的所有字符串。它的语言不是全语言。
5. 如何利用假想的判定器 $R_{ALL}$:
   • $S_{ATM}$ 在收到 $\langle M, w \rangle$ 后，构造出这个特殊的文法 $G$。
   • $S_{ATM}$ 将 $\langle G \rangle$ 输入给 $R_{ALL}$。
   • 如果 $R_{ALL}$ 接受 $\langle G \rangle$，说明它判断 $L(G) = \Sigma^*$。这对应情况1，意味着 $M$ 不接受 $w$。所以 $S_{ATM}$ 应该拒绝。
   • 如果 $R_{ALL}$ 拒绝 $\langle G \rangle$，说明它判断 $L(G) \neq \Sigma^*$。这对应情况2，意味着 $M$ 接受 $w$。所以 $S_{ATM}$ 应该接受。
   • 再次地，通过这种巧妙的构造和反向逻辑，$S_{ATM}$ 完美地判定了 $A_{\mathrm{TM}}$。

这一段深入到 CFG $G$ 的构造细节。$G$ 的目标是生成所有“无效”的计算历史。这里将“无效”这个概念分解成了三个具体的、可操作的子条件。

1. “一个字符串可能由于几个原因而不能成为接受计算历史”: 这是一个关键的分解思想。一个字符串要想成为一个“合法的接受计算历史”，必须同时满足我们之前讨论的三个条件（起点正确、过程合法、终点正确）。反过来说，一个字符串只要违反了这三个条件中的任何一个，它就不是一个合法的接受计算历史。
2. 利用“或”关系: 我们的文法 $G$ 就要利用这个“或”关系。$G$ 将由三个子文法 $G_1, G_2, G_3$ 组合而成（通过一个初始规则 $S \to S_1 | S_2 | S_3$）。
   • $G_1$ 负责生成所有违反条件1的字符串。
   • $G_2$ 负责生成所有违反条件3的字符串。
   • $G_3$ 负责生成所有违反条件2的字符串。
   • 因此，总的语言 $L(G) = L(G_1) \cup L(G_2) \cup L(G_3)$。这个并集就包含了所有“无效”的计算历史字符串。
3. 三个“失败”条件:
   • “1. 不以$C_{1}$开头”: $C_1$ 是 $M$ 在 $w$ 上的唯一正确的起始配置。任何一个字符串，如果它的格式不是 #C1#...，那它肯定不是一个合法的接受历史。例如，它的第一个配置不是 $C_1$，或者格式就不对（比如开头不是#）。生成所有这样的字符串对于 CFG 是可能的。
   • “2. 不以接受配置结尾”: 合法的接受历史必须以一个包含 $q_{\text{accept}}$ 的配置 $C_l$ 结尾。任何一个字符串，如果它的最后一个配置 $C_l$ 中不包含 $q_{\text{accept}}$，那它就不是。生成所有这样的字符串对于 CFG 也是可能的。
   • “3. 某些$C_{i}$根据$M$的规则不能正确地生成$C_{i+1}$”: 这是最核心的部分。一个字符串可能起点和终点都“看起来”对，但中间的某一步转换是“作弊”的。例如，从 $C_i$ 到 $C_{i+1}$ 的转换不符合 $M$ 的转移函数。$G$ 的任务就是捕捉到这种“作弊”行为。
4. 对整体逻辑的再次确认:
   • “如果$M$不接受$w$，则不存在接受计算历史”: 在这种情况下，任何一个字符串 $x$ 都会至少违反上述三个条件中的一个。（如果一个字符串 $x$ 碰巧同时满足了这三个条件，那它本身就构成了一个接受计算历史，与“不存在接受计算历史”的前提矛盾）。
   • “因此所有字符串都以某种方式失败。因此，$G$将生成所有字符串，正如所期望的。”: 既然所有字符串都是“无效”的，而 $G$ 的设计目标就是生成所有“无效”的字符串，那么在这种情况下，$L(G)$ 自然就是 $\Sigma^*$。这与我们上一节的分析完全吻合。

这是整个证明中最具技术含量和最巧妙的部分。它描述了如何构造一个下推自动机 (PDA) $D$ 来识别所有“无效”的计算历史，并引入了一个关键的“转折”来解决技术难题。

第一部分：从 CFG 到 PDA

• “我们不直接构造$G$，而是构造一个PDA $D$”: 作者选择了先设计 PDA，再利用已有的理论（定理2.20）将其自动转换为等价的 CFG。
• 原因: “设计一个PDA比设计一个CFG更容易”。对于很多语言，特别是需要“匹配”或“比较”的，用 PDA 的栈操作来思考，比用文法的递归推导来思考要直观得多。PDA 是一个“机器模型”，更接近算法思维。

第二部分：PDA D 的设计

• 非确定性分支: PDA $D$ 利用了其非确定性的特点。在开始时，它会“猜”当前的输入字符串 $x$ 到底违反了三个失败条件中的哪一个，然后进入对应的子程序去验证这个猜测。
• 分支1 (检查起点): 验证 $x$ 的开头不是 #C1#。这对于 PDA 来说很简单，只需要顺序读取并比较即可。
• 分支2 (检查终点): 验证 $x$ 的结尾不包含 $q_{\text{accept}}$。这也简单，PDA 可以一直读到输入末尾再做判断。
• 分支3 (检查过程): 这是最难的，目标是识别出存在某一步 $C_i \to C_{i+1}$ 是非法的。

第三部分：分支3的实现与遇到的问题

• 分支3的初步想法:

1. 非确定性地选择一个 $C_i$: PDA 在输入串上一直前进，在任何一个 # 之后，它都可以“猜测”：“好，我现在开始检查这一步 $C_i$ 和下一步 $C_{i+1}$ 的关系。”
2. 压栈: 它将整个 $C_i$ 读完，并将其内容逐字符压入堆栈。
3. 比较: 读到下一个 # 后，它开始读取 $C_{i+1}$，同时从堆栈中弹出字符，进行比较。
4. 发现错误则接受: 如果在比较过程中发现不匹配（并且这个不匹配不符合转移函数的规定），PDA 就进入接受状态。
   • 遇到的问题: “当$D$从堆栈弹出$C_{i}$时，它是倒序的”。
   • 堆栈是后进先出 (LIFO) 的。如果 $C_i = c_1c_2...c_k$，压栈顺序是 $c_1, c_2, \ldots, c_k$。那么弹出的顺序就是 $c_k, \ldots, c_2, c_1$，即 $C_i$ 的逆序，记作 $C_i^R$。
   • 而 PDA 需要将弹出的内容与正序的 $C_{i+1}$ 进行比较。比较 $C_i^R$ 和 $C_{i+1}$ 是非常困难的，PDA 的有限状态控制器无法记住整个字符串来完成这个错位的比较。

第四部分：解决方案——“转折”

• “我们以不同的方式写入接受计算历史”: 既然无法改变 PDA 的堆栈行为，我们就改变我们所要“检查”的数据的格式！
• 新的计算历史格式: “每隔一个配置以倒序出现”。
• 图5.14解读: 图中清晰地展示了新的格式：

# C1 # C2^R # C3 # C4^R # ... #

• $C_1$ 是正序。
• $C_2^R$ 是 $C_2$ 的逆序 (Reversed)。
• $C_3$ 是正序。
• $C_4^R$ 是 $C_4$ 的逆序。
• ... 以此类推。
• 这个“转折”如何解决问题:
• 现在，当 PDA 要检查从 $C_1 \to C_2$ 的转换时：

1. 它读取 $C_1$ 并将其压栈。
2. 然后它开始读取 $C_2^R$。
3. 此时，它从栈顶弹出的字符是 $C_1$ 的最后一个字符，而它从输入带上读到的是 $C_2^R$ 的第一个字符（也就是 $C_2$ 的最后一个字符）。太棒了！顺序现在是匹配的（都是从尾部开始比较）。
   • 当 PDA 要检查从 $C_2^R \to C_3$ 的转换时：
4. 它读取 $C_2^R$ 并将其压栈。压栈的内容是 $C_2$ 的逆序。
5. 然后它开始读取 $C_3$。
6. 此时，它从栈顶弹出的字符是 $C_2^R$ 的最后一个字符（也就是 $C_2$ 的第一个字符），它从输入带上读到的是 $C_3$ 的第一个字符。顺序又是匹配的（从头部开始比较）。
   • “在这种修改形式下，PDA能够压入一个配置，以便在弹出时，顺序适合与下一个配置进行比较。”: 总结了这个技巧的精髓。通过预先对一半的数据进行“翻转”，我们完美地配合了堆栈“后进先出”的特性。

第五部分：最终设计目标

• “我们设计$D$来接受任何不是修改形式的接受计算历史的字符串。”: 再次明确 PDA $D$ 的最终任务，只不过现在它要检查的是这种“正反交替”格式的计算历史。如果一个字符串不满足这种格式的合法性（起点、终点、过程任一出错），$D$ 就要接受它。

这是全文的最后一句，它起到了两个作用：总结和延伸。

1. 总结 (隐含): 到这里，定理5.13 ($ALL_{\mathrm{CFG}}$ 不可判定) 的证明思路已经阐述完毕。完整的形式化证明比较冗长，通常在教科书中会省略或留作习题，因为其核心的、最具启发性的思想（计算历史+正反交替的PDA构造）已经讲清楚了。
2. 延伸与应用:
   • “在练习5.1中，您可以使用定理5.13来证明$E Q_{\mathrm{CFG}}$是不可判定的。”: 这句话将我们刚刚得到的新知识 ($ALL_{\mathrm{CFG}}$ 不可判定) 立刻投入使用。
   • 新问题: $EQ_{\mathrm{CFG}}$，即上下文无关文法的等价性问题。
   • $EQ_{\mathrm{CFG}} = \{\langle G_1, G_2 \rangle \mid G_1, G_2 \text{ 是CFG且 } L(G_1) = L(G_2) \}$。
   • 这个问题问的是：给定的两个CFG，它们生成的语言是否完全相同？
   • 证明策略提示: 这句话暗示了一个从 $ALL_{\mathrm{CFG}}$ 到 $EQ_{\mathrm{CFG}}$ 的归约。
   • 这个归约的思路和我们证明 $E_{\mathrm{TM}} \le_m EQ_{\mathrm{TM}}$ 时惊人地相似，都是特例化。
   • 归约思路:
   • 假设 $EQ_{\mathrm{CFG}}$ 可判定，即存在判定器 $R_{EQCFG}$。
   • 我们要构造 $ALL_{\mathrm{CFG}}$ 的判定器 $S_{ALLCFG}$。
   • $S_{ALLCFG}$ 接收输入 $\langle G \rangle$，想判断 $L(G)$ 是否等于 $\Sigma^*$。
   • $S_{ALLCFG}$ 先构造一个固定的、我们确切知道其语言就是 $\Sigma^*$ 的文法 $G_{all}$ (例如 $S \to aS|bS|\epsilon$)。
   • 然后 $S_{ALLCFG}$ 调用 $R_{EQCFG}$ 来比较 $\langle G, G_{all} \rangle$。
   • 如果 $R_{EQCFG}$ 接受，说明 $L(G) = L(G_{all}) = \Sigma^*$，于是 $S_{ALLCFG}$ 接受。
   • 如果 $R_{EQCFG}$ 拒绝，说明 $L(G) \neq \Sigma^*$，于是 $S_{ALLCFG}$ 拒绝。
   • 这样就从 $ALL_{\mathrm{CFG}}$ 归约到了 $EQ_{\mathrm{CFG}}$。因为 $ALL_{\mathrm{CFG}}$ 刚被证明是不可判定的，所以 $EQ_{\mathrm{CFG}}$ 也必然是不可判定的。