5_可归约性5.2.ZH解释

这段话是本节的开篇，起到了提纲挈领的作用。它告诉读者，我们将要学习一个新的主题，这个主题的核心是不可判定性。

首先，它回顾了之前的知识。在计算理论中，我们已经学习了很多关于自动机（如图灵机）的问题，其中一些是不可判定的，比如著名的停机问题（$A_{TM}$）。“不可判定性不仅限于与自动机相关的问题”这句话是在告诉我们，不要以为只有那些和图灵机、状态转移等复杂概念绑定的问题才是不可判定的。

接着，它引出了本节的主角：一个看似简单，但实际上是不可判定的问题。这个问题是关于“字符串简单操作”的。这形成了一个鲜明的对比：一个用简单规则描述的问题，其可解性却触及了计算的根本极限。

最后，它给出了这个问题的名字：邮政对应问题，英文是 Post Correspondence Problem，简称 PCP。这个名字听起来可能有点奇怪，但它源于其提出者 Emil Post。

这一段用一个非常生动的“多米诺骨牌”比喻来解释PCP到底是什么。

1. 基本元素：多米诺骨牌。这里的多米诺骨牌不是我们平时玩的那种带点数的，而是特制的。它被分成上下两部分，每一部分上都写着一个字符串。例如，一个骨牌上面是 "a"，下面是 "ab"。你可以把它想象成一个键值对，或者一个翻译规则，"a" 翻译成 "ab"。
2. 问题实例：一堆多米诺骨牌。一个PCP问题就是给你一套这样的骨牌。比如，给你四张牌：
   • 牌1: 上 "b", 下 "ca"
   • 牌2: 上 "a", 下 "ab"
   • 牌3: 上 "ca", 下 "a"
   • 牌4: 上 "abc", 下 "c"
3. 目标：寻找一个匹配。任务是，从这堆牌里选出一个序列（注意：牌可以重复使用，这是关键！），然后把它们挨个排列起来。当你这样做的时候，所有牌的上半部分会拼接成一个长字符串，下半部分也会拼接成另一个长字符串。如果这两个长字符串完全相同，那么你选出的这个骨牌序列就叫做一个“匹配”。
4. 一个匹配的例子。书中给出了一个例子，序列是：

[牌2], [牌1], [牌3], [牌2], [牌4]

我们来看看这个序列是如何形成匹配的：

• 上方字符串拼接：牌2上("a") + 牌1上("b") + 牌3上("ca") + 牌2上("a") + 牌4上("abc") = "abcaaabc"
• 下方字符串拼接：牌2下("ab") + 牌1下("ca") + 牌3下("a") + 牌2下("ab") + 牌4下("c") = "abcaaabc"

看，上下两个拼接出来的长字符串都是 "abcaaabc"，它们完全一样！所以，这个序列是一个匹配。

1. 可视化匹配。为了更直观地理解，书里画了一个图。这个图就像把上下两个长字符串对齐，然后用竖线把每个骨牌贡献的部分隔开。这清晰地显示了每一步拼接后，上下字符串是如何保持同步增长，并最终完全一致的。

这段话补充了PCP问题的另一面：并非所有PCP实例都有解。它给出了一个明确的、不存在匹配的例子，并解释了原因。

1. 可能性：无解。首先，它强调了一个重要的事实：不是你给我一堆牌，我就一定能找到一个匹配。有些牌堆的组合是“死局”。
2. 一个无解的例子。书中给出的牌堆是：
   • 牌1: 上 "abc", 下 "ab"
   • 牌2: 上 "ca", 下 "a"
   • 牌3: 上 "acc", 下 "ba"
3. 无解的原因。这里给出的理由非常直接且有力：对于这个牌堆里的每一张牌，上面的字符串都比下面的字符串要长。
   • 牌1: |"abc"| = 3, |"ab"| = 2。上方比下方长1。
   • 牌2: |"ca"| = 2, |"a"| = 1。上方比下方长1。
   • 牌3: |"acc"| = 3, |"ba"| = 2。上方比下方长1。

因为无论你选择哪张牌，或者选择多少张牌拼接在一起，上方字符串的总长度永远会比下方字符串的总长度要大。每当你添加一张牌，上方的长度增加量总是严格大于下方的长度增加量。因此，上方的总字符串和下方的总字符串长度永远不可能相等，更不用说内容相同了。所以，这个PCP实例不可能有匹配。

这一段的目的是从前面生动的谜题描述，过渡到计算理论中标准的、严谨的数学语言。这是证明一个问题不可判定的必要步骤。

1. 核心论断：开门见山地抛出本节最重要的结论：“邮政对应问题是确定一组多米诺骨牌是否具有匹配。这个问题是算法无法解决的。” 这里的“算法无法解决”就是不可判定的同义词。这意味着不存在一个图灵机（即算法），对于任何你给它的PCP实例，它都能停机并正确回答“有匹配”或“无匹配”。
2. 转向形式化：在证明这个惊人结论之前，必须先把问题本身用数学符号精确地定义清楚，不能再依赖“多米诺骨牌”这样的比喻。
3. 形式化定义 - 实例 (Instance)：一个PCP问题的“实例”被定义为一个集合 $P$。这个集合 $P$ 包含 $k$ 个元素。每个元素是一个“骨牌”，表示为 $[\frac{t_j}{b_j}]$，其中 $j$ 从1到 $k$。$t_j$ (top) 是第 $j$ 张牌上方的字符串，而 $b_j$ (bottom) 是下方的字符串。
4. 形式化定义 - 匹配 (Match)：一个“匹配”不再是一列骨牌图，而被定义为一个下标序列 $i_1, i_2, \ldots, i_l$。这个序列里的每个下标 $i_j$ 都必须是 $1$ 到 $k$ 之间的整数，代表你选择的是牌堆 $P$ 中的第 $i_j$ 张牌。这个序列之所以被称为“匹配”，需要满足一个核心条件：
   • $t_{i_{1}} t_{i_{2}} \cdots t_{i_{l}} = b_{i_{1}} b_{i_{2}} \cdots b_{i_{l}}$
   • 这个等式说的是：将序列中所有选定骨牌的上方字符串按顺序拼接起来，得到的结果必须和将它们的下方字符串按顺序拼接起来的结果完全相同。
5. 形式化定义 - 语言 (Language)：在计算理论中，我们习惯于将“问题”等同于“语言”。一个判定问题对应一个语言，这个语言包含了所有答案为“是”的实例的编码。
   • $PCP$ 被定义为一个语言。这个语言是一个集合。
   • 集合中的元素是 $\langle P \rangle$。这里的尖括号 $\langle \cdot \rangle$ 表示对实例 $P$ 的一种标准编码（比如，一个描述所有骨牌上下字符串的字符串）。
   • 一个编码 $\langle P \rangle$ 属于语言 $PCP$ 的充要条件是：实例 $P$ 具有一个匹配。
   • 因此，“确定实例 $P$ 是否有匹配”这个问题，就等价于“判断字符串 $\langle P \rangle$ 是否属于语言 $PCP$”这个问题。

这是一个核心定理的陈述，非常简洁但极其重要。

• 定理 5.15: 只是一个编号，用于在书中引用。
• PCP: 指的是我们刚刚形式化定义的邮政对应问题，或者等价地，语言 $PCP$。
• 是: 这是一个确定性的论断。
• 不可判定的 (Undecidable): 这是本定理的核心结论。它的含义是：不存在任何一个算法（即不存在任何一个总会停机的图灵机），能够对任意给定的 PCP 实例 P，都能在有限时间内正确地判定 P 是否有匹配。

换句话说，你可以写程序去尝试寻找一个PCP的匹配，如果运气好，实例有解且解比较短，你的程序可能会找到它。但是，如果实例无解，你的程序可能会永远运行下去，不断地尝试更长更复杂的组合，永不停止。不可判定性保证了我们不可能设计出一个完美的程序，它在无解的情况下也能自信地停机并报告“无解”。

这段话概述了证明定理5.15的总体策略。这是一个非常经典且强大的证明技巧，叫做归约（Reduction）。

1. 概念上的简单性与细节的复杂性：作者首先打了个预防针。这个证明的核心思想（idea）很漂亮，也直接，但是实现这个思想需要处理大量繁琐的细节。这提示读者要抓住主线，不要过早迷失在细节中。
2. 主要技术：从 $A_{TM}$ 归约：这是整个证明的核心方法。
   • $A_{TM}$: 这是我们已知的、经典的不可判定问题——接受问题（或停机问题的变种），即判断一个给定的图灵机 $M$ 是否接受输入字符串 $w$。
   • 归约: 归约是一种“问题转化”的技巧。如果我们想证明问题B是难的，我们可以这样做：找一个我们已经知道是难的问题A，然后展示一个方法，能把任何一个A问题的实例，转化成一个B问题的实例，并且转化后的B问题实例的解，和原来A问题实例的解有直接的对应关系。
   • 从 $A_{TM}$ 归约到 PCP: 这里的思路是：
   • 假设PCP是可判定的（即存在一个解决PCP的算法，我们叫它 PCP_Solver）。
   • 我们将展示一个“转换器”算法，这个算法可以接收任何一个 $A_{TM}$ 的实例（也就是一对 $\langle M, w \rangle$）。
   • 这个“转换器”会输出一个PCP的实例 $P$。
   • 这个转换的巧妙之处在于：
   • 当且仅当 $M$ 接受 $w$ 时，构造出来的 $P$ 才会有匹配。
   • 那么，如果我们真的有 PCP_Solver，我们就可以这样来解决 $A_{TM}$：
3. 拿到一个 $A_{TM}$ 实例 $\langle M, w \rangle$。
4. 用我们的“转换器”把它变成一个PCP实例 $P$。
5. 把 $P$ 喂给假想的 PCP_Solver。
6. 如果 PCP_Solver 说 "有匹配"，我们就断定 $M$ 接受 $w$。
7. 如果 PCP_Solver 说 "无匹配"，我们就断定 $M$ 不接受 $w$。
   • 这样一来，我们就利用一个假想的PCP解法器，造出了一个 $A_{TM}$ 的解法器。但我们早就知道 $A_{TM}$ 是不可判定的，不可能有解法器。这个矛盾说明，我们最初的假设“PCP是可判定的”一定是错误的。
   • 因此，PCP必须是不可判定的。
8. 核心构造：匹配 = 接受计算历史：如何实现上面说的那个“转换器”？这里的绝妙点子是，让构造出来的PCP实例 $P$ 的任何一个匹配，其本质都必须是图灵机 $M$ 在输入 $w$ 上的一个接受计算历史的字符串表示。
   • 计算历史 (Computation History): 这是一个图灵机计算过程的快照序列。它从初始格局（configuration）开始，比如 $C_1 = q_0w_1w_2...$，然后是根据转移函数得到的第二个格局 $C_2$，接着是 $C_3$，直到最终达到接受状态或拒绝状态。一个接受计算历史就是以接受状态结尾的这样一个格局序列。
   • 构造的目标: 我们将设计一套多米诺骨牌，当你试图去寻找一个匹配时，这些骨牌的规则会“逼迫”你必须在下方逐步构建出 $M$ 在 $w$ 上的计算历史。上方字符串则总是比下方“慢半拍”，最终在计算结束时“追上”，形成匹配。

在进入核心构造前，作者先提出并解决了三个“小”的技术性问题。这些问题就像是在盖大楼前平整土地，虽然不是主体结构，但能让后续施工更简单、更规范。

1. 第一个技术点：磁头不能左移越界
   • 问题: 标准的图灵机模型允许磁头在纸带上向左或向右移动。如果磁头在最左边的格子，然后收到一个向左移动的指令，它会停留在原地。但这种“撞墙”行为在我们的构造中会引入不必要的复杂性。
   • 解决方案: 我们先对要模拟的图灵机 $M$ 做一个简单的预处理，得到一个等价的图灵机 $M'$。$M'$ 的行为和 $M$ 完全一样，只是它永远不会尝试移出纸带的左边界。这很容易做到：修改 $M$ 的转移函数，让它在开始时在纸带最左边写一个特殊的标记，比如 $`。然后规定，只要磁头读到 `$，它就必须向右移动。这样一来，$M'$ 就和 $M$ 计算能力等价，但行为更规范。所以，后面我们可以安全地假设我们模拟的 $M$ 就有这个好性质。
2. 第二个技术点：空输入字符串 $w=\varepsilon$
   • 问题: 我们的构造需要将输入 $w$ 放在初始的多米诺骨牌上。如果 $w$ 是空字符串 $\varepsilon$，那么初始格局中就没有输入部分，这会使构造稍微有点不同。
   • 解决方案: 为了统一处理，我们规定，如果 $w$ 是空的，我们就用一个空格符号 $\sqcup$ 来代替它。因为图灵机在空输入上运行时，纸带上本来就全是空格，所以这只是让初始格局的表示更加明确。
3. 第三个技术点：强制从第一张骨牌开始
   • 问题: PCP的规则是，你可以从牌堆里任意选一张牌作为起点。但在我们的构造中，我们希望匹配必须从一个非常特殊的骨牌开始——这张骨牌负责设定图灵机的初始格局。如果玩家可以随便从中间的“计算步骤”骨牌开始，整个模拟就乱套了。
   • 解决方案: 作者这里用了一个两步走的策略：
   • 步骤一：引入一个更强的变种问题。我们先定义一个PCP的修改版，叫做修改的邮政对应问题 (MPCP)。MPCP的规则和PCP一样，但增加了一条额外的限制：任何合法的匹配都必须以牌堆中的第一张牌 $[\frac{t_1}{b_1}]$ 开始。
   • 步骤二：先解决简单版本。我们接下来的证明，将首先证明 $A_{TM}$ 可以归约到 MPCP。也就是说，我们将构造一个MPCP实例，它的解对应于图灵机的计算历史。
   • 步骤三：再把MPCP归约回PCP。在证明的最后，我们会展示一个通用的方法，能把任何一个MPCP实例转换成一个PCP实例，并且保证新PCP实例的解法和原MPCP实例的解法等价。这样，整个证明链条就完整了：$A_{TM} \le_m MPCP \le_m PCP$。根据归约的传递性，就证明了 $A_{TM} \le_m PCP$。

这是证明核心部分的正式开始。

1. 深入细节: 作者明确表示，前面的铺垫结束，现在要进入构造的“深水区”。目标是设计一个PCP实例 $P$（实际上是MPCP实例 $P'$），其行为能模拟图灵机 $M$ 在输入 $w$ 上的计算。
2. 归约法的标准开场白: “我们让图灵机 $R$ 判定 PCP，并构造图灵机 $S$ 来判定 $A_{TM}$。”
   • 这是一个典型的反证法和归约法结合的表述。
   • 假设存在一个图灵机 $R$ 能够判定 PCP。也就是说，我们假设 PCP 是可判定的。$R$ 就是我们假想的那个 PCP_Solver。
   • 目标是基于这个假设，构造出另一个图灵机 $S$，而这个 $S$ 竟然能够判定 $A_{TM}$。
   • 由于我们已知 $A_{TM}$ 是不可判定的，所以能判定 $A_{TM}$ 的图灵机 $S$ 是不可能存在的。
   • 这个矛盾的出现，说明我们最初的假设——“存在一个图灵机 $R$ 能判定 PCP”——是错误的。因此，PCP 必定是不可判定的。
   • 接下来的所有内容，都是在描述如何构造这个图灵机 $S$。
3. 定义被模拟的图灵机 M:
   • 为了清晰，作者重申了图灵机 $M$ 的七元组形式化定义：$M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$。
   • $Q$: 状态的有限集合。
   • $\Sigma$: 输入字母表，即输入字符串 $w$ 中可能出现的字符集合。
   • $\Gamma$: 纸带字母表，包含 $\Sigma$ 以及空格符号 $\sqcup$ 和其他可能的辅助符号。
   • $\delta$: 转移函数，是图灵机的核心规则，形如 $\delta(q, a) = (r, b, D)$，表示在状态 $q$ 读到符号 $a$ 时，会转移到状态 $r$，将 $a$ 改写为 $b$，并向方向 $D$ (左或右) 移动。
   • $q_0$: 初始状态。
   • $q_{accept}$: 接受状态。
   • $q_{reject}$: 拒绝状态。
4. 构造器 S 的功能:
   • $S$ 是一个算法（一个图灵机），它接收 $\langle M, w \rangle$ 作为输入。
   • $S$ 的工作是输出一个 MPCP 的实例 $P'$。
   • 这个 $P'$ 的设计必须满足那个黄金法则：“$M$ 接受 $w$ 当且仅当 $P'$ 有一个（MPCP）匹配”。
5. 分步构造: 作者将整个复杂的构造过程拆分成了七个部分。这是一种非常好的教学和论证方法，将一个大问题分解成若干个小侧面，逐一击破。每个部分都旨在模拟图灵机计算的一个特定方面（例如，磁头右移、左移、纸带复制、计算开始、计算结束等）。
6. 穿插解释与实例: 为了避免这七个步骤过于抽象，作者承诺会在描述构造规则的同时，给出一个具体的例子，展示这些规则是如何工作的。

这是七个构造部分中的第一个，也是最关键的一步：设置计算的起点。

1. 构造规则: 规则非常明确，就是创建一张特定的多米诺骨牌，并把它放在牌堆 $P'$ 的第一个位置。
   • 这张牌的上方是 #。# 是一个特殊的分隔符，用来标记计算历史中格局的开始和结束。
   • 这张牌的下方是 # + 初始格局 + #。
   • 初始格局的表示法是 $q_0 w_1 w_2 \cdots w_n$。这是一种标准的图灵机格局表示：$q_0$ 是初始状态，它紧跟在磁头当前指向的符号 $w_1$ 的左边。$w_1 w_2 \cdots w_n$ 是纸带上的输入字符串 $w$。
   • 所以下方的整个字符串是 #q_0w_1...w_n#。
2. 强制性起点: 因为我们构造的是一个 MPCP 实例，而 MPCP 要求匹配必须从第一张牌开始。所以，任何一个合法的匹配，都必然是以这张牌开头的。
3. 产生的效果: 当我们把这张起始牌放下时，匹配的初始状态就形成了：
   • 上方字符串 (Top): #
   • 下方字符串 (Bottom): #q_0w_1...w_n#
   • 此时，上方和下方字符串的第一个字符 # 是匹配的，但下方多出了一大串 q_0w_1...w_n#。这就产生了一个“债务”：上方的字符串必须想办法“追赶”上并匹配掉下方的这串字符。
4. 后续策略: 这段解释了整个证明的核心机制。我们如何让上方的字符串“追赶”上来？答案不是随便添加字符，而是通过一系列精心设计的多米诺骨牌。这些骨牌的作用是：
   • 当你为了匹配掉下方的第一个格局 $C_1$ 而在上方添加字符时，你被迫在下方添加了第二个格局 $C_2$。
   • 这个过程会一直持续下去。你为了匹配 $C_k$，被迫在下方生成 $C_{k+1}$。
   • 这就形成了一个“上方追赶，下方延伸”的链条反应，而这个链条反应恰好就是图灵机的计算过程。

这三部分是构造的核心，它们负责将图灵机的每一步转移函数规则，都翻译成对应的多米诺骨牌。这些骨牌是模拟得以进行下去的“齿轮”。

第4部分：复制（不变的部分）

我们先看最简单的第4部分。

• 规则: 对于纸带字母表 $\Gamma$ 中的每一个符号 $a$，我们都添加一张形如 $[\frac{a}{a}]$ 的骨牌。
• 作用: 图灵机在一步计算中，只会改变磁头及其所在位置的符号，纸带上其他地方的符号是不变的。这些 $[\frac{a}{a}]$ 骨牌就是“复印机”，它们的作用就是将上一个格局中那些没有被磁头扫过的部分，原封不动地“复制”到下一个格局中。在我们的匹配构造中，这意味着当你需要在上方匹配一个符号 a 时，你可以用这张牌，它同时会在下方也添加一个 a，保持了纸带这部分的稳定。

第2部分：磁头右移

• 规则: 这条规则对应图灵机的右移动作。如果转移函数说 $\delta(q, a) = (r, b, R)$（在状态q读到a，变成状态r，把a写成b，然后磁头向右R移），我们就添加一张骨牌 $[\frac{qa}{br}]$。
• 作用: 让我们看看这张骨牌如何模拟计算。
• 在旧格局中，磁头在a上，表示为 ...qa...。
• 在我们的PCP匹配中，底部有 ...qa... 这部分。上方的字符串需要追赶并匹配掉 qa。
• 这时，我们正好可以使用我们构造的这张 $[\frac{qa}{br}]$ 骨牌。
• 使用后：上方添加了 qa，成功匹配。下方则添加了 br。
• 我们看看格局发生了什么变化：
• 旧格局片段: ... q a ...
• 新格局片段: ... b r ...
• 这恰好是磁头右移的正确表示！原来磁头在a左边，现在状态q消失，a变成b，新的状态r出现在了b的右边（也就是原a的下一个位置）。这张骨牌完美地实现了状态转移、字符改写和磁头右移的模拟。

第3部分：磁头左移

• 规则: 这条规则对应左移动作，稍微复杂一点。如果 $\delta(q, a) = (r, b, L)$（在状态q读到a，变成状态r，把a写成b，然后磁头向左L移），那么对于纸带字母表中的任意一个符号c，我们都添加一张骨牌 $[\frac{cqa}{rcb}]$。
• 作用:
• 在旧格局中，磁头在a上，它左边有一个符号c，表示为 ...cqa...。
• 我们的PCP匹配的底部有 ...cqa... 这部分，上方需要追赶匹配。
• 我们使用对应的骨牌 $[\frac{cqa}{rcb}]$。
• 使用后：上方添加 cqa，成功匹配。下方添加了 rcb。
• 格局变化：
• 旧格局片段: ... c q a ...
• 新格局片段: ... r c b ...
• 这正是磁头左移的正确表示！a被改写为b，而新的状态r出现在了c的前面。
• 为什么需要c？ 因为左移时，新的状态r会跑到前一个符号c的左边。为了正确放置r，我们的骨牌必须“看到”磁头左边是什么符号。因为c可以是纸带上的任何符号，所以对于每一个可能的c，我们都要准备一张对应的骨á牌。

这一段通过一个具体的例子，串联起了前面 Part 1, 2, 4 的构造规则，展示了模拟是如何真实发生的。

1. 设定示例场景:
   • 纸带字母表 $\Gamma = \{0, 1, 2, \sqcup\}$
   • 输入字符串 $w = 0100$
   • 起始状态 $q_0$
   • 一个转移规则: $\delta(q_0, 0) = (q_7, 2, R)$。这条规则的意思是：在状态 $q_0$ 读到 0，则状态变为 $q_7$，将 0 改写为 2，然后磁头右移。
   • 初始格局: $C_1 = q_00100$
2. 应用 Part 1 规则:
   • 构造起始骨牌：$[\frac{\#}{\#q_00100\#}]$。
   • 匹配从这张牌开始，形成初始状态：
   • 上方: #
   • 下方: #q_00100#
   • 如图所示，下方比上方多出一截 q_00100#，需要被匹配掉。
3. 应用 Part 2 和 Part 4 规则:
   • 根据 $\delta(q_0, 0) = (q_7, 2, R)$，Part 2 规则生成了核心的“计算骨牌”：$[\frac{q_0 0}{2 q_7}]$。
   • 根据 $\Gamma$ 的内容，Part 4 规则生成了“复制骨牌”：$[\frac{0}{0}], [\frac{1}{1}], [\frac{2}{2}], [\frac{\sqcup}{\sqcup}]$。
4. 演示匹配过程 (如何匹配掉 q_00100#):
   • 目标: 上方需要生成 q_00100# 来匹配下方。
   • 第一步: 匹配 q_00。我们看到有张计算骨牌 $[\frac{q_0 0}{2 q_7}]$。它的上方是 q_00，正好是我们需要的！
   • 我们使用这张牌。上方成功添加 q_00。下方则被迫添加 2q_7。
   • 第二步: 匹配 1。我们用复制骨牌 $[\frac{1}{1}]$。上方添加 1，下方也添加 1。
   • 第三步: 匹配 0。我们用复制骨牌 $[\frac{0}{0}]$。上方添加 0，下方也添加 0。
   • 第四步: 匹配 0。再次使用复制骨牌 $[\frac{0}{0}]$。上方添加 0，下方也添加 0。
   • （这里原文跳过了一步，就是匹配最后的 #，我们将在Part 5看到这张牌）
5. 展示匹配结果:
   • 我们使用的骨牌序列是：$[\frac{q_0 0}{2 q_7}], [\frac{1}{1}], [\frac{0}{0}], [\frac{0}{0}]$ (暂时忽略最后的 #)。
   • 上方字符串 拼接起来是 q_00 + 1 + 0 + 0 = q_00100。
   • 下方字符串 拼接起来是 2q_7 + 1 + 0 + 0 = 2q_7100。
   • 现在我们把起始牌和这串序列连起来看：
   • 总上方: # (来自起始牌) + q_00100 = #q_00100
   • 总下方: #q_00100# (来自起始牌) + 2q_7100 = #q_00100#2q_7100
   • 观察：我们为了匹配掉下方的第一个格局 $C_1 = q_00100$，在上方成功地构造了它。但作为代价，我们在下方被迫构造出了第二个格局 $C_2 = 2q_7100$！
   • $C_1$ 到 $C_2$ 的演化 q_00100 -> 2q_7100 正是应用了 $\delta(q_0, 0)=(q_7, 2, R)$ 规则的结果。模拟成功！
6. 引出下一步: 作者指出，这个过程需要能持续下去。目前，格局之间没有分隔。为了从 $C_2$ 模拟到 $C_3$，我们需要一个方法来处理格局之间的分隔符 #。这就引出了 Part 5。

这一部分解决了两个在模拟过程中出现的“边界”问题：如何分隔格局，以及如何处理图灵机无限长的纸带。

1. 第一张骨牌: $[\frac{\#}{\#}]$
   • 规则: 添加一张上方是 #，下方也是 # 的骨牌。
   • 作用: 这是一张简单的“复制”骨牌，专门用来处理格局分隔符 #。
   • 必要性: 回到上一个例子，当上方字符串成功匹配掉 $C_1 = q_00100$ 后，下方字符串变成了 #q_00100#C_2...。此时，上方需要匹配的下一个符号就是 #。这张 $[\frac{\#}{\#}]$ 骨牌正好能完成这个任务：上方添加一个 # 完成了匹配，同时下方也添加一个 #，这个下方新加的 # 正好成为新格局 $C_2$ 和未来可能出现的 $C_3$ 之间的分隔符。它确保了计算历史 ...#C_1#C_2#C_3... 的结构能够被正确地维护。
2. 第二张骨牌: $[\frac{\#}{\sqcup \#}]$
   • 规则: 添加一张上方是 #，下方是 sqcup# 的骨牌。
   • 作用: 这张骨牌用来模拟图灵机纸带的无限性。
   • 必要性: 在图灵机的计算中，磁头可能会移动到之前从未访问过的、布满空格符号 $\sqcup$ 的区域。例如，一个格局可能是 uqv，但下一步磁头右移，格局可能变成 ubrv'，其中 $v'$ 是 $v$ 的一部分。如果 $v$ 是空的，磁头移到 $v$ 的右边，它实际上是移到了一个原来是隐式的 $\sqcup$ 上。我们的格局表示是有限字符串，无法表示无限的空格。这张骨牌提供了一个机制来“按需生成”这些空格。
   • 如何工作: 这张骨牌和上一张 $[\frac{\#}{\#}]$ 骨牌在使用时机上是相同的，都是在匹配完一个格局后，去匹配下一个分隔符 # 时使用。但它提供了一个选择：
   • 选择1 (用 $[\frac{\#}{\#}]$): 上下都加 #。新旧格局长度可能不变（或因计算而改变）。
   • 选择2 (用 $[\frac{\#}{\sqcup \#}]$): 上方加 #，下方加 sqcup#。这相当于在下一个格局的末尾（#的前面）人为地增加了一个空格符 $\sqcup$。这模拟了纸带向右“延伸”了一格。当图灵机需要用到更多纸带空间时，匹配过程就可以通过选择这张骨牌来提供。

这一段继续使用之前的例子，连续演示了图灵机的第二步和第三步计算是如何在PCP匹配中被模拟的，分别展示了一个右移和一个左移操作。

模拟第二步计算（右移）

1. 新的转移规则: 假设 $\delta(q_7, 1) = (q_5, 0, R)$。这是第二步计算的规则。
2. 生成对应骨牌 (Part 2): 根据此规则，构造器会生成一张右移骨牌 $[\frac{q_7 1}{0 q_5}]$。
3. 延续匹配:
   • 当前状态: 上方是 #q_00100，下方是 #q_00100#2q_7100。
   • 下一个任务: 上方需要匹配掉下方的 #2q_7100。
   • 步骤 3.1: 匹配 #。使用 Part 5 的 $[\frac{\#}{\#}]$ 骨牌。上方添加 #，下方也添加 #。
   • 上方: #q_00100#
   • 下方: #q_00100#2q_7100#
   • 步骤 3.2: 匹配 2。使用 Part 4 的复制骨牌 $[\frac{2}{2}]$。
   • 上方: #q_00100#2
   • 下方: #q_00100#2q_7100#2
   • 步骤 3.3: 匹配 q_71。使用我们刚生成的右移骨牌 $[\frac{q_7 1}{0 q_5}]$。
   • 上方: #q_00100#2q_71
   • 下方: #q_00100#2q_7100#20q_5
   • 步骤 3.4: 匹配剩下的 00。使用两次 $[\frac{0}{0}]$。
   • 第二步模拟完成:
   • 最终上方: #q_00100#2q_7100
   • 最终下方: #q_00100#2q_7100#20q_500
   • 观察: 我们成功在上方匹配了第二个格局 $C_2 = 2q_7100$ (注意这里的 $C_2$ 表示法有些出入，应该是 $2q_7100$)。作为代价，在下方生成了第三个格局 $C_3 = 20q_500$。
   • 我们检查一下这个格局演化 2q_7100 -> 20q_500 是否正确。确实是应用 $\delta(q_7, 1)=(q_5, 0, R)$ 的结果。

模拟第三步计算（左移）

1. 新的转移规则: 假设 $\delta(q_5, 0) = (q_9, 2, L)$。这是第三步计算规则。
2. 生成对应骨牌 (Part 3):
   • 这是一个左移动作。我们需要考虑磁头左边的符号。在格局 $C_3 = 20q_500$ 中，磁头在第二个0上，它左边的符号是第一个0。所以，我们需要一个 c=0 的左移骨牌。
   • Part 3 的规则会生成一系列骨牌，包括我们需要的那个：
   • 当 c=0: $[\frac{0q_50}{q_902}]$
   • 当 c=1: $[\frac{1q_50}{q_912}]$ (虽然当前用不上，但构造时会生成)
   • ...等等。
3. 延续匹配:
   • 当前状态: 上方是 #...#C_2，下方是 #...#C_2#C_3。
   • 任务: 上方需要匹配 #C_3，即 #20q_500。
   • 过程: 类似于上一步，用 $[\frac{\#}{\#}], [\frac{2}{2}], [\frac{0}{0}]$ 匹配掉 #20。
   • 关键步骤: 匹配 q_50。不对，左移骨牌是三个字符的，它需要匹配 0q_50。
   • 让我们回看格局 $C_3 = 20q_500$。磁头 q_5 左边是 0，当前读的是 0。所以要匹配的部分是 0q_50。
   • 我们使用左移骨牌 $[\frac{0q_50}{q_902}]$。
   • 上方添加 0q_50，成功匹配。下方被迫添加 q_902。
   • 第三步模拟完成:
   • 我们看看下方发生了什么：在格局 C_3=...20q_500... 之后，我们通过一系列骨牌，在底部生成了第四个格局 $C_4$。
   • $C_3$ 中片段 ...20q_50... 对应生成了 $C_4$ 的片段 ...2q_902...。
   • 格局演化 ...20q_500... -> ...2q_9020... (忽略其他部分)。这正是应用 $\delta(q_5, 0) = (q_9, 2, L)$ 的结果。模拟再次成功！

这部分处理的是模拟的“终局”：当图灵机进入接受状态 $q_{accept}$ 时，如何让PCP匹配得以成功完成。

1. 终局问题: 目前为止，我们的构造中，上方字符串总是比下方字符串短一个格局。如果图灵机进入 $q_{accept}$ 并停机，这个“债务”就永远还不清了，PCP匹配也就无法完成。这是不行的，因为我们要求“$M$接受$w$” 当且仅当 “$P'$有匹配”。所以，当$M$接受时，我们必须提供一种方法让匹配完成。
2. 解决方案：“吃豆人”模式: 当图灵机进入 $q_{accept}$ 状态后，我们引入一套新的“伪计算”规则。这些规则不再模拟图灵机的真实计算，而是进入一个“清场”或“收尾”阶段。这个阶段的目标就是让上方字符串能快速“吃掉”下方剩余的字符，最终追平下方。
3. 构造规则 (Part 6):
   • 对于纸带字母表 $\Gamma$ 中的每一个符号 a，我们添加两类骨牌：
   • $[\frac{a q_{accept}}{q_{accept}}]$: 对应 $q_{accept}$ 状态“吃掉”其右侧的符号 a。
   • $[\frac{q_{accept} a}{q_{accept}}]$: 对应 $q_{accept}$ 状态“吃掉”其左侧的符号 a。
4. 工作机制:
   • 假设在某个格局中，出现了 $q_{accept}$，比如 ...b q_{accept} a...。
   • 上方需要匹配这段 ...b q_{accept} a...。
   • 吃掉右边的 a: 上方需要匹配 q_{accept}a。我们可以用骨牌 $[\frac{q_{accept} a}{q_{accept}}]$。
   • 使用后: 上方添加 q_{accept}a，下方只添加 q_{accept}。
   • 效果: 上方字符串比下方多“追赶”了一个字符 a 的长度。格局从 ...b q_{accept} a... 变成了 ...b q_{accept}...。
   • 吃掉左边的 b: 接下来上方可能需要匹配 b q_{accept}。我们可以用骨牌 $[\frac{b q_{accept}}{q_{accept}}]$。
   • 使用后: 上方添加 b q_{accept}，下方只添加 q_{accept}。
   • 效果: 上方又多追赶了一个字符 b 的长度。格局从 ...b q_{accept}... 变成了 ...q_{accept}...。
   • 这个过程可以不断重复， $q_{accept}$ 就像一个“吃豆人”，不断地将左右两边的纸带符号“吃掉”（在上方匹配掉，但在下方不再产生它们），从而迅速缩短下方字符串，让上方字符串有机会追上。
5. 图示解释:
   • 图中展示了，当最后一个真实格局包含 $q_{accept}$ 后，比如下方是 ...#...q_{accept}01#。
   • 上方匹配掉 #... 后，开始匹配 q_{accept}01。
   • 它会先用 $[\frac{q_{accept}0}{q_{accept}}]$，再用 $[\frac{q_{accept}1}{q_{accept}}]$ (假设 $q_{accept}$ 在0左边)。
   • 这个过程最终会让下方只剩下 ...#q_{accept}#，而上方则匹配了完整的最后一个格局。

这是七个部分的最后一部分，也是画龙点睛之笔。它负责处理“吃豆人”阶段结束后留下的最后一点“尾巴”，让整个匹配完美闭合。

1. 收尾后的状态: 经过第6部分的“吃豆人”阶段，下方字符串中原本复杂的最后一个格局，如 10q_{accept}1，已经被“吃”得只剩下 $q_{accept}$ 了。并且，最后的格局分隔符 # 也已经被处理。所以，当收尾阶段结束时，PCP匹配的状态大致如下：
   • 上方: ...#C_{final-1}\#10q_{accept}1 (这里匹配了整个最终格局)
   • 下方: ...#C_{final-1}\#10q_{accept}1##q_{accept}\# (经过吃豆人阶段，最终简化为类似这样)
   • 简化一下，在“吃豆”过程的最后，上下字符串会是这样的形态：
   • 上方: ...C_{final}
   • 下方: ...C_{final}\#q_{accept}\#
   • 此时，上方需要匹配的是 #q_{accept}\#。
2. 最后的障碍: 上方字符串需要匹配掉 #q_{accept}\#。我们不能用之前的骨牌，因为它们会让下方继续延伸。我们需要一张能“终结”匹配的骨牌。
3. 构造规则 (Part 7): 添加一张非常特殊的骨牌 $[\frac{q_{accept}\#\#}{\#}]$。
   • 注意这张牌上方的 # 有两个。这是书中的一个印刷错误或简化写法。它应该是 q_{accept}## 或者 q_{accept}#，这取决于Part 6如何精确处理末尾的#。我们根据其功能来理解：它的作用是匹配掉 q_{accept} 和它后面的 #。
   • 让我们假设一个更清晰的版本是 $[\frac{q_{accept}\#}{\#}]$。上方匹配q_{accept}#，下方只生成一个#。
   • 或者，如果图示是正确的，那么上方需要匹配 q_{accept}##。
4. 工作机制 (Final Closure):
   • 让我们回到刚才的状态：
   • 上方: ...C_{final}
   • 下方: ...C_{final}\#q_{accept}\#
   • 上方需要匹配 #q_{accept}\#。
   • 步骤1: 用 $[\frac{\#}{\#}]$ 匹配第一个#。
   • 上: ...C_{final}\#
   • 下: ...C_{final}\#q_{accept}\#\#
   • 步骤2: 现在上方需要匹配 q_{accept}\#。我们使用这张最后的终结骨牌 $[\frac{q_{accept}\#\#}{\#}]$ （假设它的上方是 q_{accept}#，下方是空的，或者像书中那样，上方q_{accept}##，下方#）。它的核心功能是让上方增长，而下方缩短或少量增长。
   • 图示所展示的：图中的最后一步显示，上方添加了 q_accept##，下方只添加了一个 #。
   • 之前: 上方 ...#0，下方 ...#0q_accept##
   • 使用骨牌: $[\frac{q_{accept}\#\#}{\#}]$
   • 之后: 上方 ...#0q_accept##，下方 ...#0q_accept###
   • 这样上下就完全相等了！匹配完成！
5. 总结: 这张最终骨牌是完成匹配的临门一脚。它允许上方字符串匹配掉由 $q_{accept}$ 和分隔符组成的最后残余部分，同时确保下方字符串不再增长或以一种可控的方式增长，从而使得上下两方的字符串最终可以完全相等。

这部分是证明的最后一步，它负责将我们刚刚完成的对 MPCP 的归约，推广到原始的 PCP 问题。

1. 完成对 $P'$ 的构造: 作者总结，至此，我们已经完整地描述了如何从一个图灵机实例 $\langle M, w \rangle$ 构造出一个 MPCP 实例 $P'$。这个 $P'$ 的性质是：$M$ 接受 $w$ 当且仅当 $P'$ 有一个（MPCP）匹配。
2. MPCP 和 PCP 的区别: 再次强调两者的唯一区别：MPCP 要求匹配必须从第一张牌开始，而 PCP 没有这个要求。
3. 一个陷阱 (Trivial Match): 作者提出了一个有趣的问题。如果我们直接把构造好的 $P'$ 当成一个 PCP 问题实例（忽略“必须从第一张开始”的规则），它是否总是有解？答案是“是”。
   • 思考提示: “它非常短”。
   • 答案: 在 Part 4 中，我们为每个纸带符号 a 都添加了“复制”骨牌 $[\frac{a}{a}]$。只要字母表 $\Gamma$ 不是空的，我们总能找到至少一张这样的骨牌。比如 $[\frac{0}{0}]$。那么，序列 ([0/0]) 本身就是一个PCP匹配！上方是 0，下方也是 0。
   • 结论: 这意味着，如果我们不做任何修改，直接把 $P'$ 用于对PCP的归约，归约就失败了。因为无论 $M$ 是否接受 $w$，构造出的 $P'$ 总会有一个这种简单的“平凡匹配”，所以我们无法根据 $P'$ 是否有解来判断 $M$ 是否接受 $w$。
4. 最终的技巧: 为了解决上述问题，我们需要一个方法，把 MPCP 的“必须从第一张牌开始”这个外部规则，变成 PCP 实例内部的约束。
5. 核心思想: 我们要对 $P'$ 中的所有骨牌进行“编码”或“改造”，创造出一个新的PCP实例 $P$。这个改造要达到一个效果：在新的牌堆 $P$ 中，唯一可能作为匹配起点的牌，就是那张源自 $P'$ 的起始牌。所有其他的牌，它们的上下字符串开头都不一样，所以它们不可能是起点。
6. 引入新符号: 为了实现这个技巧，我们将引入一些新的符号，即 * 和 diamond。

这是实现从 MPCP 到 PCP 转换的具体技术，即 * 编码技巧。

1. 定义 * 编码:
   • 首先定义了三种在字符串中插入 * 的操作：
   • star u: 在 u 的每个字符前加 。例: u="abc" -> star u="abc"。
   • u star: 在 u 的每个字符后加 。例: u="abc" -> u star="abc"。
   • star u star: 在 u 的每个字符前后都加 。例: u="abc" -> star u star="abc*"。
   • 注意，书中的 star u star 的例子 u1u2...un 和 u star 的例子 u1u2...un* 都和 u star 的定义更吻合。我们以文字描述为准：star u star 是前后都加。这里的核心思想是：star u 和 u star 的交错模式不同。
2. 构造新的PCP实例 P:
   • 假设我们已经有了 MPCP 实例 $P' = \{[\frac{t_1}{b_1}], [\frac{t_2}{b_2}], ..., [\frac{t_k}{b_k}]\}$。
   • 我们基于 $P'$ 构造新的 PCP 实例 $P$。$P$ 中的骨牌是对 $P'$ 中骨牌的改造：
   • 改造起始牌 (第1张): $P'$ 的第一张牌 $[\frac{t_1}{b_1}]$ 被改造成 $P$ 中的第一张牌 $[\frac{\star t_1}{\star b_1 \star}]$。
   • 改造其他牌 (第2到k张): $P'$ 的其他牌 $[\frac{t_i}{b_i}]$ ($i>1$) 被改造成 $P$ 中的 $[\frac{\star t_i}{b_i \star}]$。
   • 添加一张特殊牌: $P$ 中还额外增加了一张全新的牌 $[\frac{*\diamond}{\diamond}]$。这里 diamond 是另一个新符号。
3. 分析新实例 P 的性质:
   • 强制起点: 让我们看看 $P$ 中的牌，哪一张可以作为 PCP 匹配的起点。
   • 第一张牌: $[\frac{\star t_1}{\star b_1 \star}]$。上方以 开始，下方也以 开始。它可以作为起点。
   • 其他改造牌: $[\frac{\star t_i}{b_i \star}]$ ($i>1$)。上方以 开始，但下方以 $b_i$ 的第一个字符开始（它不是 ）。所以它们不能作为起点。
   • 特殊牌: $[\frac{*\diamond}{\diamond}]$。上方以 * 开始，下方以 diamond 开始。也不能作为起点。
   • 结论: 唯一能启动匹配的只有第一张改造牌。这样，我们就用骨牌自身的设计，强制了匹配必须从对应于原 MPCP 起始牌的那张牌开始。
4. * 的交错作用:
   • 一旦匹配从 $[\frac{\star t_1}{\star b_1 \star}]$ 开始，我们看看字符串的样子：
   • 上: t_1_1t_1_2...
   • 下: b_1_1b_1_2...*
   • 下方比上方多一个结尾的 *。现在，如果我们选择一张改造牌 $[\frac{\star t_i}{b_i \star}]$ 接在后面：
   • 上: ...t_1_n + t_i_1t_i_2... -> ...t_1_nt_i_1t_i_2...
   • 下: ...b_1_m + b_i_1b_i_2... -> ...b_1_mb_i_1b_i_2...
   • 你会发现， 和原始符号始终保持着 a b c ... 和 a b c ... 这种交错模式。上方总是在奇数位是 ，偶数位是原符号。下方总是在偶数位是 *，奇数位是原符号。
   • 这个精巧的设计保证了，只要下方比上方多一个 ，这个状态就会一直维持下去。 只是一个“骨架”，它不影响原始符号的匹配逻辑，原始符号的匹配完全由 $t_i$ 和 $b_i$ 决定。
   • 所以，如果 $P'$ 有一个 MPCP 匹配，那么 $P$ 也会有一个对应的 PCP 匹配。
5. 特殊牌 $[\frac{*\diamond}{\diamond}]$ 的作用:
   • 这个在原文中的牌应该是 $[\frac{*}{\diamond}]$ 或类似的，原文 $[\frac{*\diamond}{\diamond}]$ 有点令人困惑。我们假设它的作用是处理最后的尾巴。在匹配的最后，上方可能需要一个 来匹配下方多出的最后一个 。但如果用 $[\frac{*}{*}]$，下方又会多一个 。这张特殊牌（可能应该是 $[\frac{*}{\empty}]$，上方 ，下方空）允许上方添加一个 * 而下方不添加任何东西，从而完成最终的闭合。书中的 $[\frac{*\diamond}{\diamond}]$ 可能是一个更复杂的机制，但其核心思想是完成最后的对齐。