3_丘奇-图灵论题3.1.ZH解释

这部分内容是第三章的引言，起到了承上启下的作用。它首先回顾了之前章节中已经学习过的两种计算模型：有限自动机（Finite Automata, FA）和下推自动机（Pushdown Automata, PDA）。

1. 回顾已有模型：
   • 有限自动机 (FA)：它被描述为一个内存非常有限的设备模型。这里的“少量内存”指的是，有限自动机的状态是有限的，它只能通过从一个状态转移到另一个状态来“记住”信息。它没有外部存储器，所以它能记住的信息量严格受限于其状态的数量。这使得它适合模拟一些简单的、对历史信息依赖很小的过程，比如自动售货机、电梯控制器或者识别简单文本模式。
   • 下推自动机 (PDA)：它被描述为比有限自动机更强大的模型。它的强大之处在于它拥有一个无限的内存，但这个内存的使用方式是受限的。这个内存是一个栈（stack），遵循“后进先出”（Last-In, First-Out, LIFO）的原则。你可以把栈想象成一个只能从顶部放入或取出盘子的弹簧碟子架。这种内存结构使得下推自动机能够处理需要“配对”或“计数”的更复杂的语言，比如编程语言中括号的匹配 ( ... ) 或者形如 $a^n b^n$ 的语言（n个a后面跟着n个b）。
2. 指出已有模型的局限性：
   • 文章明确指出，即使是拥有无限内存的下推自动机，也无法完成一些“非常简单的任务”。这里的“简单”是从人类直觉来看的，但在计算理论中有严格的定义。例如，下推自动机无法识别像 $a^n b^n c^n$（n个a，n个b，n个c）这样的语言。这是因为栈的“后进先-出”特性使得它在匹配完b和a之后，就忘记了n的具体值，无法再用它来检查c的数量是否也等于n。
   • 这个局限性引出了一个关键结论：有限自动机和下推自动机都“过于受限”，不能作为通用计算机（general-purpose computer）的模型。通用计算机指的是我们日常使用的计算机，它们可以执行任何我们能用算法描述的计算任务（在内存和时间允许的范围内）。
3. 引出新模型的需求：
   • 既然现有的模型不够强大，那么就需要一个更强大的、能够模拟真实计算机计算能力的模型。这为下一节引入图灵机（Turing Machine）埋下了伏笔。丘奇-图灵论题的核心思想就是，任何可以用算法解决的问题，都可以由图灵机来解决。因此，图灵机成为了衡量“可计算性”的黄金标准。

这部分正式引入了图灵机（Turing Machine, TM）的概念，并描述了其基本构成和工作原理。

1. 图灵机的提出与定位：
   • 提出者和时间：由艾伦·图灵在1936年提出，这是一个历史性的里程碑。
   • 核心特性：它被描述为“与有限自动机类似”，这意味着它也有状态和状态转移的概念。但关键区别在于其内存——“无限且不受限制的内存”。这里的“不受限制”是与下推自动机的栈内存相对的，意味着图灵机的内存可以被随机访问。
   • 模型地位：图灵机被认为是“通用计算机的更精确模型”，并断言“图灵机可以做所有真实计算机能做的事情”。这正是丘奇-图灵论题的非形式化表述。它暗示了图灵机的计算能力与我们直觉中的“算法”或“机械过程”是等价的。
2. 图灵机的强大与局限：
   • 强大性：它能模拟任何真实计算机。
   • 局限性：即使如此强大的图灵机，也“无法解决某些问题”。这预示了计算理论中一个深刻的结论：存在“不可计算”或“不可判定”的问题。这些问题构成了“计算的理论极限”，是任何计算设备（无论多强大）都无法逾越的鸿沟。
3. 图灵机的物理模型：
   • 无限磁带 (Infinite Tape)：这是图灵机的内存。它被想象成一条在两个方向上无限延伸的带子，上面划分成一个个的方格（cell），每个方格可以存储一个符号。这个“无限”是理论上的抽象，保证了计算不会因为内存耗尽而终止。
   • 磁头 (Head)：这是一个读写设备。在任意时刻，磁头都指向磁带上的一个方格。它可以做三件事：
4. 读取 (Read)：读取当前方格中的符号。
5. 写入 (Write)：擦除当前方格的符号，并写入一个新符号。
6. 移动 (Move)：向左或向右移动一个方格。
7. 图灵机的计算过程概述：
   • 初始状态：计算开始时，输入字符串被预先放置在磁带上（通常是从最左端开始），磁带的其他部分则充满了特殊的空白符号（blank symbol）。磁头初始时指向输入字符串的第一个符号。
   • 计算步骤：机器根据其当前状态和磁头读取到的符号，依据其内部的规则（转移函数），执行写入和移动操作，并进入下一个状态。
   • 存储与读取：机器可以在磁带的任何位置写入信息（作为“草稿”或“标记”），并通过移动磁头回到那个位置来再次读取它。这种“随机访问”能力是其比下推自动机强大的根本原因。
   • 终止与输出：计算会一直持续，直到机器进入两种特殊的“停机状态”之一：
   • 接受状态 (accept state)：如果进入此状态，机器停机并“接受”输入字符串。
   • 拒绝状态 (reject state)：如果进入此状态，机器停机并“拒绝”输入字符串。
   • 无限循环 (Looping)：如果机器永远不进入接受或拒绝状态，它将“永远运行，永不停止”。这种情况被称为“循环”或“不停机”。

这部分通过一张示意图和四点总结，直观地强化了图灵机与有限自动机的核心区别。

1. 图 3.1 示意图分析：
   • FINITE CONTROL (有限控制器)：这部分对应图灵机的“大脑”，也就是它的状态集合 $Q$ 和转移函数 $\delta$。它在任何时候都处于某个特定的状态中。图中画了一个 q_i，表示当前状态。
   • TAPE (磁带)：这是一条被划分为方格的带子。图中显示了 ... a b a b b a a ... 这样的符号序列，代表磁带上存储的内容。两端的省略号 ... 形象地表示了磁带向两个方向无限延伸。
   • HEAD (磁头)：图中用一个箭头指向磁带上的某个方格，表示磁头当前的位置。这个磁头兼具“读”和“写”的功能（Read/Write head）。
2. 四点区别的详细解释：
   • 区别 1: 可读可写 vs. 只读
   • 图灵机：磁头可以在当前方格上写入新的符号，从而改变磁带内容。这使得磁带不仅仅是输入介质，更是可读可写的工作空间（working space）或内存。
   • 有限自动机：其输入磁带是只读的。磁头只能从左到右读取输入，不能修改。
   • 意义：可写能力是图灵机强大的关键。它可以用磁带来存储中间计算结果、做标记、计数等等，极大地扩展了其计算能力。

• 区别 2: 双向移动 vs. 单向移动
• 图灵机：磁头可以向左（L）或向右（R）移动。
• 有限自动机：磁头通常只能从左到右移动一次，读完就结束了。
• 意义：双向移动意味着图灵机可以反复地扫描和处理输入。它可以先读一遍数据，做些标记，然后回到开头再根据标记进行下一步处理。这种“随机访问”的能力是解决复杂问题的基础。

• 区别 3: 无限内存 vs. 无内存/有限内存
• 图灵机：磁带在理论上是无限长的。这意味着计算的唯一限制是算法本身，而不是内存大小。
• 有限自动机：它没有外部内存。其唯一的“记忆”就是它的当前状态，而状态是有限的。
• 意义：无限内存消除了因存储空间不足而导致计算失败的可能性，使得图灵机能够处理任意大小的输入和任意复杂的计算（只要该计算是可能的）。

• 区别 4: 立即停机的特殊状态 vs. 读完输入后判断
• 图灵机：一旦进入 q_accept（接受状态）或 q_reject（拒绝状态），计算立即停止。无论磁头上还有没有未读的输入。
• 有限自动机：通常需要读取完整个输入字符串，然后根据其所在的最终状态是否为接受状态来判断。
• 意义：这种“立即生效”的机制使得图灵机的设计更加灵活。例如，一旦发现输入不符合某种格式，可以立即进入拒绝状态，而无需继续处理剩余的无效部分。这也引入了“停机”和“不停机（循环）”这对核心概念。

这部分通过一个具体的例子——识别语言 $B=\{w\#w\}$，来展示图灵机是如何工作的。它首先用一个生动的比喻来启发思考，然后给出了一个非形式化但清晰的算法描述。

1. 问题定义：
   • 目标语言：$B = \{w\#w \mid w \in \{0,1\}^*\}$。这个语言包含所有由一个 # 分隔的、两边完全相同的二进制字符串组成的字符串。例如，011#011 属于 $B$，但 011#010 和 01#01#01 都不属于 $B$。
   • 任务：设计一个图灵机 $M_1$，当输入字符串属于 $B$ 时接受，否则拒绝。
2. 思想启发（比喻）：
   • 想象自己是一个站在一条很长很长的写满 0 和 1 的纸带（磁带）前的检查员。纸带太长，你记不住全部内容。
   • 你的任务是确认 # 两边的字符串是否一样。
   • 你可以做的是：在纸带上来回走动（移动磁头），并在你看过的字符上打叉（写入/标记）。
   • 最自然的策略（“显而易见的策略”）就是：
3. $M_1$ 的算法描述：

这是对比喻中策略的更正式的算法化描述。

• 核心思想：通过“之字形”（zig-zag）的移动来回比较 # 两侧的字符，并用“划掉”（crossing off）的方式来标记已比较过的字符。
• 步骤 1：之字形比较与标记
• 这是一个循环过程。在每一次循环中，机器：

1. 找到 # 左边第一个还没被划掉的字符。
2. 记住这个字符（通过进入不同的状态，比如“刚刚看到了0”状态）。
3. 用一个特殊符号（比如 x）将其“划掉”（写入）。
4. 向右移动，越过 #。
5. 找到 # 右边第一个还没被划掉的字符。
6. 比较这个字符和刚才记住的字符。
   • 如果不匹配，立即进入拒绝状态。
   • 如果匹配，也用 x 将其“划掉”。
7. 然后磁头移回磁带左端，开始下一次循环。
   • 边界情况处理：在这个过程中，如果根本找不到 #，或者一侧的字符已经用完而另一侧还有（例如 01#010），都会导致不匹配，从而拒绝。

• 步骤 2：最终检查
• 当步骤 1 的循环结束时，意味着 # 左边的所有字符都已经被划掉了。
• 这时需要做最后一次检查：# 右边是否还有没被划掉的字符？
• 如果有（例如输入是 01#010），说明右边的字符串比左边的长，它们不相等，所以拒绝。
• 如果没有（右边也全部被划掉了），说明左右两边长度相同，且对应位置的字符都匹配。所以接受。

这部分通过一系列图形化的“快照”（snapshots）来可视化之前描述的 $M_1$ 算法在处理一个具体输入 011000#011000 时的过程。每个快照展示了在某个时间点磁带的内容以及磁头的位置。

1. 第一个快照 (Top):
   • 磁带内容: 011000#011000
   • 磁头位置: 指向最左边的第一个 0。
   • 解释: 这是计算的初始状态。输入字符串被完整地放在磁带上，磁头位于起始位置。
2. 第二个快照:
   • 磁带内容: x11000#011000
   • 磁头位置: 指向 # 后面的第一个 0。
   • 解释: 这显示了第一次比较的过程。机器读取了最左边的 0，将其用 x “划掉”，然后磁头向右移动，越过 #，到达了 # 右边字符串的第一个字符 0，准备进行比较。
3. 第三个快照:
   • 磁带内容: x11000#x11000
   • 磁头位置: 指向 # 后面的 x。
   • 解释: 比较完成。因为 # 左右两边的第一个字符都是 0，匹配成功。所以 # 右边的 0 也被划掉了。现在磁头可能正在向左移动，准备回到磁带的左半部分开始下一轮比较。
4. 第四个快照:
   • 磁带内容: xx1000#x11000
   • 磁头位置: 指向 # 后面的第一个 1。
   • 解释: 这显示了第二次比较的过程。机器在左半部分找到了第一个未被划掉的字符 1（位于第二个位置），将其划掉，然后磁头移动到右半部分，找到了第一个未被划掉的字符 1（也位于第二个位置），准备比较。
5. 后续快照（未完全展示）:
   • 这个过程会继续下去。第三轮会比较并划掉两边的 1。第四轮比较并划掉两边的 0，依此类推。
6. 最后一个快照 (Bottom):
   • 磁带内容: xxxxxx#xxxxxx
   • 磁头位置: 指向 # 后面的最后一个 x。
   • 解释: 这显示了所有比较都成功完成后的状态。# 两边的所有 0 和 1 都被 x 替换了。此时，机器会执行算法的第二步：检查 # 两侧是否还有未划掉的字符。它会发现两边都没有了，因此最终会进入接受状态。

这些快照是“不连续的”，意味着它们省略了磁头来回移动的许多中间步骤，只展示了每个“之字形”比较的关键时刻，从而清晰地说明了算法的宏观进展。

这短短的一段话起到了一个重要的过渡作用，它连接了前面非形式化、高层次的描述和后面严格、数学化的形式化定义。

1. 承认之前描述的不足：
   • 作者明确指出，像刚才对 $M_1$ 的描述（“之字形遍历”、“划掉符号”）是“草图式”（sketchy）的。
   • “草图式”意味着它只勾勒了轮廓，传达了核心思想，但“并未提供所有细节”。例如，它没有明确说明：
   • 机器有多少个状态？每个状态代表什么意义？（比如“正在向右找#”、“记住了一个0”、“正在向左返回”等）
   • 当处于状态 q 并读到符号 a 时，具体应该写入什么符号 b，向哪个方向移动，并进入哪个新状态 r？这些精确的指令都没有给出。
2. 引入形式化描述的必要性：
   • 为了精确无误地定义一台图灵机，我们需要一个形式化描述（formal description）。
   • 这个描述将遵循一个标准的形式化定义（formal definition），就像我们为有限自动机（五元组）和下推自动机（七元组）所做的那样。
   • 形式化描述会把所有细节都交代清楚，不留任何模糊空间，使得机器的行为是完全确定和可分析的。
3. 预告形式化定义的复杂性：
   • 作者在这里打了一个“预防针”：“实际上，我们几乎从不提供图灵机的形式化描述，因为它们往往非常庞大。”
   • 这暗示了图灵机的形式化定义（特别是转移函数 $\delta$）会非常复杂和冗长，即使是对于像 $M_1$ 这样看起来相对简单的任务。
   • 这也解释了为什么在计算理论中，我们更倾向于使用更高层次的、类似算法的描述来沟通思想。只要我们确信这种高层次描述可以被转化成一个严格的形式化定义，它就是有效且被接受的。

这部分给出了图灵机的严格数学定义。它首先聚焦于最核心的转移函数 $\delta$，然后给出了完整的七元组定义。

1. 转移函数 $\delta$ 的讲解：
   • 核心地位：$\delta$ 被称为定义的核心，因为它包含了图灵机的“程序”或“逻辑”。它规定了机器在任何情况下应该如何行动。
   • 函数签名：$\delta: Q \times \Gamma \longrightarrow Q \times \Gamma \times\{\mathrm{L}, \mathrm{R}\}$。这是一个数学函数的标准表示法，我们来逐步拆解它：
   • 输入 (Domain): $Q \times \Gamma$。这是一个笛卡尔积，表示 $\delta$ 函数的输入是一个序对 (状态, 符号)。具体来说，就是 (当前状态, 当前磁头下的符号)。
   • 输出 (Codomain): $Q \times \Gamma \times \{\mathrm{L}, \mathrm{R}\}$。这也是一个笛卡尔积，表示 $\delta$ 函数的输出是一个三元组 (新状态, 要写入的符号, 移动方向)。
   • 工作实例：文中举例说明：如果 $\delta(q, a) = (r, b, \mathrm{L})$，这意味着：
   • IF: 机器当前状态是 $q$，且磁头读到的符号是 $a$。
   • THEN: 机器将执行以下三个动作：
2. 进入新的状态 $r$。
3. 在当前磁带方格上，擦除 $a$ 并写入 $b$。
4. 将磁头向左（L for Left）移动一个方格。
5. 定义 3.3：图灵机七元组

这是一个类似于有限自动机（五元组）和下推自动机（七元组）的形式化定义，它精确地描述了一台图灵机需要的所有组件。

• $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$

下面是每个组件的详细解释：

1. $Q$ (状态集)：一个有限的集合，包含了所有可能的状态。例如，在 $M_1$ 的例子里，可能的状态有“寻找#”、“记住了一个0”、“向左返回”等。$Q$ 是有限的，这体现了控制器本身的内存是有限的。
2. $\Sigma$ (输入字母表)：一个有限的集合，包含了可以出现在初始输入字符串中的所有符号。关键点是，它不能包含空白符号 $\sqcup$。这是为了让机器能识别出输入的结束位置。
3. $\Gamma$ (磁带字母表)：一个有限的集合，包含了所有可以出现在磁带上的符号。它必须满足两个条件：
   • $\sqcup \in \Gamma$：空白符号必须是磁带字母表的一部分。
   • $\Sigma \subseteq \Gamma$：输入字母表必须是磁带字母表的子集。这意味着输入字符串中的所有符号都可以在磁带上出现。此外，$\Gamma$ 还可以包含一些额外的、不在 $\Sigma$ 中的符号，比如前面例子中的划掉标记 x。
4. $\delta$ (转移函数)：就是前面详细解释过的机器的“程序”，规定了机器的所有行为。
5. $q_0$ (起始状态)：$Q$ 中的一个特殊状态，是机器开始计算时所处的初始状态。
6. $q_{accept}$ (接受状态)：$Q$ 中的一个特殊状态。一旦进入这个状态，机器立即停机并接受输入。
7. $q_{reject}$ (拒绝状态)：$Q$ 中的另一个特殊状态。一旦进入这个状态，机器立即停机并拒绝输入。同时规定 $q_{reject} \neq q_{accept}$，这两个状态必须是不同的。

这部分内容详细描述了图灵机从启动到运行的整个过程，并引入了一个极其重要的概念——格局 (configuration)，用于精确地捕捉图灵机在任意时刻的“快照”。

1. 计算的启动与运行：
   • 初始设置：
   • 输入 $w = w_1w_2...w_n$ 被放置在磁带的最左边。
   • 磁带的其他所有位置都填充着空白符号 $\sqcup$。
   • 磁头初始时位于最左边的方格，即 $w_1$ 上。
   • 机器处于起始状态 $q_0$。
   • 输入的边界：因为输入字母表 $\Sigma$ 不包含 $\sqcup$，所以从左到右遇到的第一个 $\sqcup$ 就自然地成为了输入字符串的右边界。
   • 计算过程：机器根据转移函数 $\delta$ 的规则一步步进行计算。
   • 左边界处理：这是一个重要的技术细节。如果磁头已经在最左端的方格，而转移函数指令是向左移动 L，那么磁头将停留在原地不动。这提供了一种检测磁带左端的方法。
   • 计算的终结：
   • 进入 $q_{accept}$ 或 $q_{reject}$，计算停止。
   • 如果永远不进入这两个状态，机器就“永远运行”（循环）。
2. 格局 (Configuration) 的引入：
   • 目的：为了能够形式化地描述图灵机的计算过程，我们需要一种方法来表示机器在任何一个瞬间的完整状态。这个“完整状态”就是格局。
   • 格局三要素：一个格局必须包含三个信息：
3. 当前状态 (current state)
4. 当前磁带内容 (current tape contents)
5. 当前磁头位置 (current head location)
   • 格局的表示法:
   • 采用一种紧凑的字符串表示法：u q v。
   • q：是当前的状态，属于 $Q$。
   • uv：是磁带上从最左端到最后一个非空白字符之间的内容。u 是磁头左边的部分，v 是磁头指向的以及右边的部分。
   • 磁头位置：被约定为 v 的第一个字符。
   • 格局示例详解：
   • 格局: 1011 q_7 01111
   • 当前状态: $q_7$
   • 磁带内容: 字符串 1011 和 01111 拼接起来，即 101101111。磁带上这部分之外都是空白 sqcup。
   • 磁头位置: 指向 01111 的第一个字符，也就是整个磁带上的第五个字符 0。
   • 图 3.4 的解读：这幅图直观地展示了格局 1011 q_7 01111 对应的物理状态。有限控制器处于状态 $q_7$，磁带上写着 101101111，并且读写头恰好指在那个 0 上面。

这部分内容使用之前引入的“格局”表示法，来严格定义图灵机的“一步计算”。这个“一步计算”被称为“产生”（yields）。

1. “产生” (Yields) 的概念：
   • “格局 $C_1$ 产生格局 $C_2$” 是 “图灵机在处于 $C_1$ 所描述的瞬时状态时，根据其转移函数 $\delta$，执行一次操作后，进入了 $C_2$ 所描述的瞬时状态” 的形式化说法。
   • 这是对图灵机动态行为的数学建模。
2. 向左移动 (L) 的形式化定义：
   • 前提: 假设转移函数规定 $\delta(q_i, b) = (q_j, c, L)$。这意味着当状态为 $q_i$、读到符号 $b$ 时，应变为状态 $q_j$、写入符号 $c$、并向左移动。
   • 初始格局: $u a q_i b v$。
   • 当前状态是 $q_i$。
   • 磁头在 $b$ 上。
   • 磁头左边的字符是 $a$。
   • 磁带相关部分是 $uabv$。
   • 产生的新格局: $u q_j a c v$。
   • $b$ 被 $c$ 替换，所以磁带现在是 $uacv$。
   • 状态从 $q_i$ 变为 $q_j$。
   • 磁头向左移动一格，原来在 $b$ 上，现在移动到了 $a$ 上。
   • 在新的格局表示法中，状态 $q_j$ 正好写在了它所指向的字符 $a$ 的左边。这完美地符合了格局的表示规则。
   • 所以，我们说 $u a q_i b v$ 产生 $u q_j a c v$。
3. 向右移动 (R) 的形式化定义：
   • 前提: 假设转移函数规定 $\delta(q_i, b) = (q_j, c, R)$。这意味着当状态为 $q_i$、读到符号 $b$ 时，应变为状态 $q_j$、写入符号 $c$、并向右移动。
   • 初始格局: $u a q_i b v$。
   • 同上，磁头在 $b$ 上。
   • 产生的新格局: $u a c q_j v$。
   • $b$ 被 $c$ 替换，磁带变为 $uacv$。
   • 状态从 $q_i$ 变为 $q_j$。
   • 磁头向右移动一格，原来在 $b$ 上，现在移动到了 $v$ 的第一个字符上（如果 $v$ 不为空）。
   • 在新的格局表示法中，状态 $q_j$ 正好写在了它所指向的 $v$ 的左边，而 $b$ 被替换后的 $c$ 归入了左边部分，成为 $uac$。这也完美符合格局表示规则。
   • 所以，我们说 $u a q_i b v$ 产生 $u a c q_j v$。
4. 边界情况 (Special Cases)：
   • 左端 (Left End)：
   • 初始格局: $q_i b v$ (磁头在最左边的字符 $b$ 上)。
   • 向左移动: 如果 $\delta(q_i, b) = (q_j, c, L)$，因为磁头不能移出左边界，它会停在原地。新格局是 $q_j c v$。状态变为 $q_j$，b被c覆盖，磁头仍然在最左边（新c）上。
   • 向右移动: 如果 $\delta(q_i, b) = (q_j, c, R)$，新格局是 $c q_j v$。b被c覆盖，磁头移到右边v的第一个字符上。
   • 右端 (Right End)：
   • 初始格局: $u a q_i$。这被视为等同于 $u a q_i \sqcup$。
   • 假设 $\delta(q_i, \sqcup) = (q_j, c, R)$。
   • 初始格局等效于 $u a q_i \sqcup$。根据右移规则，产生的新格局是 $u a c q_j \sqcup$ (因为 $v$ 是空串)。这可以简写为 $u a c q_j$。
   • 这说明图灵机可以在磁带的空白区域上写入，从而扩展其工作空间。

这部分内容基于“格局”和“产生”的概念，正式定义了什么叫“图灵机接受一个字符串”，并引出了两个核心的语言类别：图灵可识别语言和图灵可判定语言。

1. 特殊格局的定义：
   • 起始格局 (Start Configuration): 对于输入字符串 w，起始格局固定为 q_0 w。这精确地描述了计算开始的瞬间。
   • 接受格局 (Accepting Configuration): 任何状态为 q_accept 的格局。
   • 拒绝格局 (Rejecting Configuration): 任何状态为 q_reject 的格局。
   • 停机格局 (Halting Configuration): 接受格局和拒绝格局统称为停机格局。它们是计算的终点，不会再“产生”任何新的格局。
   • 关于 $\delta$ 的补充说明: 因为停机格局是终点，所以转移函数 $\delta$ 对于 q_accept 和 q_reject 状态的输入是无关紧要的。因此，可以认为 $\delta$ 的定义域实际上是 $(Q - \{q_{accept}, q_{reject}\}) \times \Gamma$。
2. “接受”一个输入的定义：
   • 图灵机 $M$ 接受输入 $w$ 的条件是：存在一个有限的格局序列 $C_1, C_2, ..., C_k$。
   • 这个序列必须满足三个条件：
3. $C_1$ 必须是起始格局 $q_0 w$。
4. 序列中任意相邻的两个格局 $C_i$ 和 $C_{i+1}$，必须满足 $C_i$ 产生 $C_{i+1}$。这表示这是一个合法的计算步骤序列。
5. 最后一个格局 $C_k$ 必须是一个接受格局。
   • 语言 L(M): 由图灵机 $M$ 接受的所有字符串 w 构成的集合，被称为 $M$ 的语言，记作 $L(M)$。
6. 图灵可识别语言 (Turing-recognizable Language)：
   • 定义 3.5: 如果一个语言 $L$ 是某个图灵机 $M$ 的语言（即 $L = L(M)$），那么 $L$ 就被称为图灵可识别的。
   • 这类语言有时也被称为“递归可枚举语言”（recursively enumerable language）。
7. 计算的三种可能结果：
   • 当一台图灵机 $M$ 在输入 w 上运行时，有且只有三种可能性：
8. 接受 (Accept): $M$ 进入 $q_{accept}$ 并停机。
9. 拒绝 (Reject): $M$ 进入 $q_{reject}$ 并停机。
10. 循环 (Loop): $M$ 永不进入 $q_{accept}$ 或 $q_{reject}$，计算永不停止。
    • 重要的区分: 对于一个输入 w，如果它不被接受，有两种可能：要么被明确拒绝，要么机器陷入循环。
11. 图灵可判定语言 (Turing-decidable Language)：
    • 动机: “循环”是一个不确定的状态。我们无法知道机器是正在进行一个超长时间的计算，还是已经陷入了死循环。这种不确定性在很多实际应用中是不可接受的。因此，我们更偏爱那些“从不循环”的图灵机。
    • 判决机 (Decider): 一个在任何输入上都能保证停机（无论是接受还是拒绝）的图灵机被称为判决机。
    • 判决 (Decides): 如果一个判决机识别一个语言，我们就说它“判决”这个语言。
    • 定义 3.6: 如果一个语言 $L$ 可以被某个判决机 $M$ 所判决，那么 $L$ 就被称为图灵可判定的，或简称可判定的 (decidable)。
    • 这类语言有时也被称为“递归语言”（recursive language）。
12. 两个类别的关系：
    • 从定义可以看出，任何一个可判定的语言，必然是图灵可识别的。（因为判决机也是一台图灵机）。
    • 反过来不一定成立。文章预告了，后面会证明存在图灵可识别但不可判定的语言。这是计算理论中一个非常深刻和重要的结果。

这部分是接下来几个具体示例的引言，旨在说明描述图灵机的不同层次，并解释为什么本书主要采用高层次描述。

1. 回顾描述方法:
   • 作者提到，我们可以像之前学习有限自动机和下推自动机一样，通过完整列出七元组的每一个组件来给出一个图灵机的形式化描述。这是最底层、最精确的描述方法。
2. 形式化描述的缺点:
   • 麻烦 (tedious) 和 庞大 (very large): 作者再次强调，对于几乎所有非平凡的图灵机，写出完整的七元组（特别是转移函数 $\delta$ 的所有规则）是一项极其繁琐和冗长的工作。
3. 本书采用的策略:
   • 主要使用高层次描述 (higher-level descriptions): 这指的是类似之前对 $M_1$ 的算法描述（“之字形遍历”、“划掉”等）。这种描述更接近伪代码，关注算法逻辑而非状态转移的细节。
   • 原因: 高层次描述“足够精确”并且“更容易理解”。它能清晰地传达解决问题的思路，而不会让读者淹没在海量的状态和转移规则中。
4. 重要提醒:
   • 高层次描述是简写: 必须牢记，任何一个高层次描述都只是其背后那个庞大的形式化描述的一个“简写”或“别名”。
   • 可转化性: 理论上，只要有足够的时间和耐心，任何一个清晰的高层次描述都可以被“编译”或“翻译”成一个完整的、严格的形式化七元组描述。这个可转化性保证了高层次描述的严谨性。
5. 接下来示例的目的:
   • 为了帮助读者建立高层次描述、状态图和形式化描述这三者之间的联系，接下来的两个例子（示例 3.7 和 3.9）会提供状态图 (state diagram)。
   • 状态图是一种中间层次的描述，它比算法描述更具体（显示了状态和转移），但比完整的 $\delta$ 函数列表更直观。
   • 作者也贴心地提示，如果读者已经理解了这三者之间的关系，可以跳过这两个详细的例子。

这部分给出了第一个详细的图灵机示例 $M_2$，用于判定一个非上下文无关语言 $A = \{0^{2^n}\}$。它首先给出了高层次的算法描述，然后解释了算法背后的逻辑。

1. 目标语言:
   • $A = \{0^{2^n} \mid n \ge 0\}$。这个语言由长度为2的幂的 0 串组成。
   • 示例:
   • $n=0, 2^0=1$: "0" 属于 $A$。
   • $n=1, 2^1=2$: "00" 属于 $A$。
   • $n=2, 2^2=4$: "0000" 属于 $A$。
   • $n=3, 2^3=8$: "00000000" 属于 $A$。
   • "000", "00000" 等不属于 $A$。
2. $M_2$ 的高层次算法描述:

这是一个循环算法，每次循环都包含以下几个阶段：

• 阶段 1: 划掉一半的0: 机器从左到右扫描磁带上的 0。它划掉第一个 0，跳过第二个，划掉第三个，跳过第四个，如此类推。本质上，它是在执行“除以2”的操作。
• 阶段 2 & 3: 检查与停机: 这是在阶段 1 的扫描过程中同时进行的检查。
• 在扫描结束时，如果发现这一轮总共只有一个 0，那么原始的 0 的数量一定是2的某次幂（最终被除到只剩1）。所以接受。
• 如果在扫描结束时，发现 0 的数量是奇数，并且这个奇数大于1（比如3, 5, 7...），那么原始数量肯定不是2的幂（因为一个2的幂，除了1之外，不可能是奇数）。所以拒绝。
• 阶段 4: 复位: 将磁头移回到磁带的最左端，为下一轮循环做准备。
• 阶段 5: 循环: 回到阶段 1，在剩下的未被划掉的 0 上重复这个过程。

1. 算法逻辑解释:
   • 核心思想: 反复将 0 的数量除以2。
   • 一个数是2的幂，当且仅当它可以通过反复除以2（且每次都整除）最终得到1。
   • 举例: 输入 "000000" (6个0)
2. 第一次循环: 划掉第1, 3, 5个 0。剩下3个 0。在扫描结束时，机器发现总数是6（偶数），所以继续。
3. 第二次循环: 在剩下的3个 0 中，划掉第1个，跳过第2个，划掉第3个。剩下1个 0。在扫描结束时，机器发现总数是3（奇数且大于1）。根据规则3，拒绝。
   • 举例: 输入 "0000" (4个0)
4. 第一次循环: 划掉第1, 3个 0。剩下2个 0。总数4是偶数，继续。磁带看起来像 x0x0。
5. 第二次循环: 在剩下的2个 0 中，划掉第1个，跳过第2个。等等，这里算法描述有点歧义，我们看状态图会更清晰。但思想是，在剩下的 0 中再划掉一半。比如划掉第一个剩下的 0。剩下1个 0。总数2是偶数，继续。
6. 第三次循环: 此时磁带上只剩下1个 0。根据规则2，接受。

这部分给出了 $M_2$ 的形式化描述的关键部分——状态图，并解释了图中的符号和一些设计选择。

1. 七元组的组成部分:
   • $Q$: 状态集被明确列出，包含7个主要状态及接受/拒绝状态。
   • $\Sigma$: 输入字母表只包含符号 0。
   • $\Gamma$: 磁带字母表包含 0、划掉符号 x 和空白符号 sqcup。
2. 状态图 (图 3.8) 的解读:

这张图是转移函数 $\delta$ 的图形化表示。每个节点是一个状态，每个带标签的箭头是一个转移规则。

• 标签格式: read -> write, move。例如 0 -> x, R 表示：如果读到 0，就把它改成 x，然后磁头向右移动。
• 简写: symbol -> move，如 0 -> R，表示读到 symbol，不改变磁带内容，只移动磁头。

1. 算法在状态图中的实现:

让我们跟踪算法的流程：

• $q_1$ (起始状态):
• sqcup -> R (到 $q_{reject}$): 如果输入是空字符串，拒绝。
• 0 ->sqcup, R (到 $q_2$): 这是个特殊处理。机器先把第一个 0 变成 sqcup。这有两个目的：一是标记磁带的左端，方便以后返回；二是作为第一次“划掉”。注意，这里用的划掉符号是 sqcup 而不是 x，是为了简化。
• $q_2$ 和 $q_3$ (交替划掉和跳过): 这是“划掉每隔一个0”的核心。
• $q_2$ (期待跳过): x -> R (在 $q_2$ 循环), 0 -> R (到 $q_3$)。在 $q_2$ 状态，遇到 x 就跳过，遇到第一个 0 也跳过，并进入 $q_3$ 状态。
• $q_3$ (期待划掉): x -> R (在 $q_3$ 循环), 0 -> x, R (到 $q_2$)。在 $q_3$ 状态，遇到 x 就跳过，遇到第一个 0 就划掉 (x)，然后回到 $q_2$ 状态，准备下一次跳过。
• 这个 $q_2 \leftrightarrow q_3$ 的循环实现了“跳过一个，划掉一个”的逻辑。
• 扫描结束的判断 (在 $q_2$ 和 $q_3$):
• 在 $q_2$ 状态，如果扫描完了所有 0，会读到 sqcup。
• sqcup -> L (到 $q_4$): 这意味着这一轮扫描的 0 的总数是偶数（因为最后一步是划掉 0 并进入 $q_2$）。这是“正常”情况，所以准备返回左端开始下一轮。
• 在 $q_3$ 状态，如果读到 sqcup。
• sqcup -> R (到 $q_{reject}$): 这意味着总数是奇数且大于1。因为如果总数是1，机器会在 $q_1$ 第一次扫描时就找到唯一的 0，然后转移到 $q_2$，再读到 sqcup 并进入 $q_4$，最终接受。所以能在此处结束，说明数量是 3, 5, 7... 这样的奇数。因此拒绝。
• $q_4$ (返回左端):
• 0 -> L, x -> L (在 $q_4$ 循环): 不断向左移动，跳过所有 0 和 x。
• sqcup -> R (到 $q_5$): 当读到最左边的 sqcup 时（就是 $q_1$ 留下的标记），说明到头了。向右移动一格，进入 $q_5$ 准备下一轮。
• $q_5$ (新一轮的开始/最终检查):
• sqcup -> R (到 $q_{accept}$): 如果磁头右移后直接看到 sqcup，说明上一轮结束后，磁带上已经没有 0 了。这只可能在总数为1的情况下发生（唯一的0在q2时被跳过，然后进入q4，返回后在q5这里发现右边是空的）。所以接受。
• x -> R (在 $q_5$ 循环): 跳过所有已划掉的 x。
• 0 -> x, R (到 $q_2$): 找到了本轮第一个 0，划掉它（用 x），然后进入 $q_2$ 开始新一轮的“跳过-划掉”循环。注意，这里的实现和高层次描述的“划掉每隔一个”有点微妙差别，但核心思想（减半）是一致的。该实现是：每轮开始时先划掉一个，然后对剩下的进行“跳过-划-掉”操作。

1. 特殊设计说明:
   • 左端标记: 作者解释了用 sqcup 作为左端标记是为了简化状态图和字母表。一个更通用的方法是使用一个专门的标记符号，比如 $。
   • 状态图简写: 解释了 0 -> R 这类简写的含义。

这部分通过一个表格展示了图灵机 $M_2$ 在输入 "0000" 上的一系列格局变化。这个表格是前面状态图逻辑的具体体现。然而，鉴于我们刚刚发现状态图可能存在问题，这个表格的计算过程也变得可疑。 让我们仔细跟踪表格中的每一步，看看它遵循了什么逻辑。

第一列：第一轮扫描和返回

1. q_1 0000: 起始格局。
2. sqcup q_2 000: 遵循 $q_1 \xrightarrow{0 \to \sqcup, R} q_2$。划掉第一个0，进入 q2。
3. sqcup x q_3 00: 这里与状态图不符！ 状态图 q2 的 0 转移是 0 -> R，应该得到 sqcup 0 q_3 00。而表格中是 sqcup x q_3 00，这意味着 q2 的转移似乎是 0 -> x, R。
4. sqcup x 0 q_4 0: 这里是 q4，再次与状态图不符！
5. ...

重大发现 2：这个表格的计算序列与图 3.8 的状态图完全不匹配。

• 状态图：q2 跳过0，q3 划掉0。
• 表格似乎遵循的逻辑：q2 划掉0，q3 跳过0？不，更复杂。

让我们放弃状态图，只根据高层次描述和表格来推断算法。 高层次描述是“划掉每隔一个0”。

• 输入 0000:

1. q1 0000: 开始。
2. sqcup q2 000: 也许 q1 到 q2 是一个初始化，把第一个0换成了sqcup。
3. sqcup x q3 00: 这步非常奇怪。它在第二个位置写入了 x。
4. ...

结论：此处的示例和图、描述之间存在严重的内在矛盾。 这是一个很好的教学反例。

我们选择相信表格是正确的，因为它展示了一个最终接受 "0000" 的过程，这符合语言定义。 让我们尝试从表格反推状态图的逻辑：

根据表格反推的算法：

• Pass 1 (输入 "0000")

1. q1 0000 -> sqcup q2 000: (q1, 0) -> (q2, sqcup, R)。 划掉第一个0。
2. sqcup q2 000 -> sqcup x q3 00: (q2, 0) -> (q3, x, R)。 划掉第二个0。
3. sqcup x q3 00 -> sqcup x 0 q4 0: (q3, 0) -> (q4, 0, R)。 跳过第三个0。
4. sqcup x 0 q4 0 -> sqcup x 0 x q3 sqcup: (q4, 0) -> (q3, x, R)。划掉第四个0。
5. sqcup x 0 x q3 sqcup -> sqcup x 0 q5 x sqcup: (q3, sqcup) -> (q5, x, L)。 到了末尾，向左返回。
6. ...一路向左...
7. q5 sqcup x0x sqcup: 到达左边界。
   • Pass 2 (磁带 x0x 相关的部分)
8. sqcup q2 x0x sqcup: 开始第二轮。
9. ...
   • 这个过程过于复杂，且与状态图矛盾。最可能的情况是，示例的表格、状态图、高层次描述这三者中，至少有两个是相互矛盾的。

为了完成这个解释，我们将采取以下策略：假设表格是正确的，并逐行解释表格本身的变化，指出其与状态图的矛盾之处。

表格逐步解释 (假设表格为准)

1. q_1 0000: 起始格局。
2. sqcup q_2 000: 可能是初始化，将第一个0替换为空白符并向右移动。
3. sqcup x q_3 00: 这一步不符合状态图。似乎是在 q_2 状态下，将 0 替换为 x 并进入 q_3。
4. sqcup x 0 q_4 0: 在 q_3 状态下，跳过 0，进入 q_4。
5. sqcup x 0 x q_3 sqcup: 在 q_4 状态下，将 0 替换为 x，进入 q_3，并到达末尾。
6. sqcup x 0 q_5 x sqcup: 在 q_3 读到末尾 sqcup，向左移动，进入 q_5。
7. sqcup x q_5 0 x sqcup: q_5 状态下向左移动。
8. sqcup q_5 x 0 x sqcup: q_5 状态下向左移动。
9. q_5 sqcup x 0 x sqcup: q_5 状态下向左移动，直到碰到开头的 sqcup。
10. sqcup q_2 x 0 x sqcup: 碰到 sqcup 后，向右移动，进入第二轮扫描，状态回到 q_2。

(以上对应第一列和第二列开头)

这个过程非常晦涩，而且与一个清晰的“除以二”算法相去甚远。它更像是一个特定、硬编码的模式匹配过程。

最合理的解释：这个表格和这个状态图根本不是描述同一个图灵机的！让我们只看状态图，并用它来跑一遍0000。

• 输入 "0000" (根据图3.8)

1. q1 0000 -> sqcup q2 000
2. sqcup q2 000 -> sqcup 0 q3 00 (跳过)
3. sqcup 0 q3 00 -> sqcup 0x q2 0 (划掉)
4. sqcup 0x q2 0 -> sqcup 0x0 q3 sqcup (跳过)
5. 在 q3 读到 sqcup，进入 q_reject。

最终结论: 示例 3.7 中的高层次描述、状态图和计算表格三者互相矛盾。 状态图本身无法正确判定语言 A。表格展示了一个能接受 "0000" 的过程，但其逻辑与状态图和高层次描述都对不上。这是一个经典的教科书错误案例。

这部分内容为之前非形式化描述过的图灵机 $M_1$（用于判定 $\{w\#w\}$）提供了形式化的状态图，并解释了状态图的表示约定。

1. 七元组组件:
   • $Q$: 状态集被定义为 $q_1$到$q_8$以及接受和拒绝状态。
   • $\Sigma$: 输入字母表为 $\{0, 1, \#\}$。
   • $\Gamma$: 磁带字母表为 $\{0, 1, \#, x, \sqcup\}$，包含了划掉符号 x。
   • $\delta$: 由图3.10的状态图定义。
2. 状态图 (图 3.10) 逻辑解读:

这张图精确地实现了“之字形比较”算法。

• $q_1$ (开始一轮新的比较):
• 从左端开始，寻找第一个未被划掉的符号。
• 0 -> x, R (到 $q_2$): 读到 0，划掉，进入“记住0”的状态 $q_2$。
• 1 -> x, R (到 $q_3$): 读到 1，划掉，进入“记住1”的状态 $q_3$。
• # -> R (到 $q_8$): 如果直接读到 #，说明左边部分已经全部划掉，进入最终检查阶段 $q_8$。
• $q_2$ (刚划掉一个0，向右找#):
• 0,1 -> R (在 $q_2$ 循环): 跳过路上的 0 和 1。
• x -> R (在 $q_2$ 循环): 跳过之前划掉的 x。
• # -> R (到 $q_4$): 找到了 #，现在进入“准备匹配0”的状态 $q_4$。
• $q_3$ (刚划掉一个1，向右找#):
• 逻辑同 $q_2$，但最终会进入“准备匹配1”的状态 $q_5$。
• # -> R (到 $q_5$)
• $q_4$ (在#右侧，寻找匹配的0):
• x -> R (在 $q_4$ 循环): 跳过已匹配的 x。
• 0 -> x, L (到 $q_6$): 找到了匹配的 0！成功！划掉它，然后进入“向左返回”的状态 $q_6$。
• 如果读到 1 或 # (没有出向箭头): 拒绝！(隐式转移)
• $q_5$ (在#右侧，寻找匹配的1):
• 逻辑同 $q_4$，但要找的是 1。
• 1 -> x, L (到 $q_6$): 找到了匹配的 1！划掉，进入返回状态 $q_6$。
• 如果读到 0 或 # (没有出向箭头): 拒绝！
• $q_6$ (匹配成功，向左返回找#):
• 0,1,x -> L (在 $q_6$ 循环): 一路向左，跳过所有符号。
• # -> L (到 $q_7$): 找到了 #，进入“越过#返回左端”的状态 $q_7$。
• $q_7$ (越过#，返回左端起点):
• 0,1,x -> L (在 $q_7$ 循环): 继续一路向左。
• 当磁头试图移出左边界时，会停在原地。下一部如果读到 x 或 0/1 会继续在 $q_7$ 向左（实际停在原地）。这里缺少一个返回 $q_1$ 的机制，一个更完整的图应该在 $q_7$ 状态下，向左移动直到碰到磁带左边界（通过尝试左移但位置不变来检测），然后向右移动一格并转换到 $q_1$。这个图可能简化了这个返回过程，假设 q7最终能回到q1。一个常见的实现方式是：q7一路向左，直到读到sqcup（如果有左端标记的话），然后右移进入q1。
• $q_8$ (最终检查阶段):
• 当左边部分都划完后 (q1读到#)，进入q8。
• x -> R (在 $q_8$ 循环): 检查右边部分，跳过所有已划掉的 x。
• sqcup -> R (到 $q_{accept}$): 如果跳过所有 x 后，直接是空白符，说明右边部分也恰好都被划掉了。长度和内容都匹配！接受！
• 如果读到 0 或 1 (没有出向箭头): 说明右边比左边长，拒绝！

1. 图示约定说明:
   • 多符号标签: 0,1 -> R 是 0 -> R 和 1 -> R 的简写。
   • 隐式拒绝: 图中没有画出 q_{reject} 状态。任何在某个状态下，读到某个符号，却没有对应的出向箭头的情况，都默认转移到 q_{reject}。例如，在 $q_5$ 状态（期待匹配 1）时读到 0，图中没有相应箭头，所以机器拒绝。这是简化状态图的常用技巧。

这个例子展示了一个图灵机 $M_3$ 如何执行乘法运算来判定语言 $C = \{a^i b^j c^k \mid i \times j = k, i,j,k \ge 1\}$。

1. 目标语言:
   • $C = \{a^i b^j c^k \mid i \times j = k, i,j,k \ge 1\}$。
   • 这是一个由 a 串、b 串、c 串顺序组成的语言，且 c 的数量必须等于 a 的数量乘以 b 的数量。所有数量都至少为1。
   • 示例:
   • $i=2, j=3, k=6$: aabbbcccccc 属于 $C$。
   • $i=1, j=2, k=3$: abbccc 不属于 $C$。
   • $i=2, j=2, k=4$: aabbcccc 属于 $C$。
2. $M_3$ 的高层次算法描述:

这个算法可以看作是一个嵌套循环。外层循环处理 a，内层循环处理 b 和 c。

• 阶段 1: 格式检查:
• 这是一个预处理步骤。机器像一个有限自动机一样，从左到右扫描一遍输入。
• 它检查输入是否严格遵循 a...ab...bc...c 的格式。即，一堆 a 之后必须是一堆 b，之后必须是一堆 c。不能有 aba, acb 等交错形式。
• 如果格式不符，例如 aabccb 或者 aa，直接拒绝。 a+b+c+ 正则表达式描述了这个格式。

• 阶段 2: 复位:
• 将磁头移回磁带的最左端，为主要的计算做准备。

• 阶段 3: 内层循环 (处理一个 a):
• 这是算法的核心，执行一次“加 j”的操作。
• 划掉一个 a: 找到最左边的一个 a 并划掉它。这代表外层循环开始一次迭代 (我们用掉了一个 a)。
• b 和 c 的配对消除:

a. 机器向右移动，跳过所有 a 和已划掉的 b，找到第一个未划掉的 b，划掉它。

b. 再向右移动，跳过所有 b 和已划掉的 c，找到第一个未划掉的 c，划掉它。

c. 然后机器在 b 区和 c 区之间来回移动，每次各划掉一个 b 和一个 c。

• 内层循环的终止条件:
• 当所有的 b 都被划掉时，这个内层循环结束。
• 错误检查: 如果在划掉所有 b 之前，c 就已经用完了，这意味着 $k$ 不够大，$k$ 不可能是 $i \times j$，所以拒绝。

• 阶段 4: 外层循环控制与最终检查:
• 恢复 b: 当一轮内层循环（阶段 3）结束后，所有的 b 都被划掉了。为了下一轮外层循环能再次使用它们，需要将它们“恢复”。这可以通过用另一个标记（比如 y）划掉 b，然后在阶段4把所有 y 恢复成 b 来实现。
• 重复或终止:

a. 机器回到左端，如果还能找到未被划掉的 a，就回到阶段 3，开始新一轮的对 j 个 c 的划掉操作。

b. 如果所有的 a 都被划掉了（外层循环结束），就进入最终检查。

• 最终检查: 此时，我们已经划掉了 $i$ 次，每次划掉了 $j$ 个 c。总共划掉了 $i \times j$ 个 c。现在需要检查磁带上是否还有剩余的未被划掉的 c。
• 如果没有剩余的 c（所有的 c 也都被划掉了），说明 $k$ 恰好等于 $i \times j$。接受！
• 如果还有剩余的 c，说明 $k > i \times j$。拒绝。
• （$k < i \times j$ 的情况已经在阶段 3 中被排除了）。

这部分内容深入探讨了前述 $M_3$ 算法描述中一些阶段的实现细节和通用技术。

1. 阶段 1 (格式检查) 的实现:
   • 作者指出，这个阶段机器的行为模式和有限自动机非常相似。
   • 原因: 它只需要从左到右扫描一次，并且不需要在磁带上写入或修改任何内容。
   • 实现方式: 机器利用其有限的状态来记住已经看到的内容。例如，它可以有三个状态：“在a区”、“在b区”、“在c区”。
   • 从起始状态开始，读到 a 则保持在“在a区”。
   • 在“在a区”读到 b，则转换到“在b区”。
   • 在“在b区”读到 c，则转换到“在c区”。
   • 任何不符合这个顺序的输入（如在“在b区”读到a）都会导致拒绝。
2. 阶段 2 (返回左端) 的实现细节与挑战:
   • 问题: 图灵机的磁带是无限的，没有一个固有的“左端点”标记。机器如何知道自己已经回到了最开始的位置？
   • 右端的简易性: 找到右端很容易，因为输入后面紧跟着第一个空白符号 $\sqcup$，这是一个天然的分界符。
   • 技术一：放置左端标记 (Left-End Marker)
   • 方法: 在计算开始时，图灵机首先将磁带最左端的第一个符号（比如 a）替换成一个特殊的、带标记的版本（比如 a_marked 或 $a`），或者干脆用一个全新的符号（如 `$) 覆盖它（同时用状态记住原来的符号是a）。
   • 使用: 之后，每当需要返回左端时，只需让磁头一直向左移动，直到再次读到那个特殊的标记符号。
   • 示例: 文中提到示例 3.7（尽管该示例存在问题）就使用了 sqcup 来标记左端。

• 技术二：利用左边界的“撞墙”行为
• 方法: 这是一种更“巧妙”（cleverer）的方法，它利用了图灵机形式化定义中的一个特性：当磁头在最左端并试图再向左移动时，它会停在原地。
• 实现“左端检测器”:

1. 标记当前位置: 机器在当前磁头位置写入一个特殊符号（比如 $)，并用状态记住被替换掉的原始符号（比如 a）。
2. 尝试左移: 机器执行一次向左移动的操作。
3. 检查位置: 机器读取新位置的符号。
   • 如果读到的仍然是刚刚写入的特殊符号 $，说明磁头根本没有移动。这证明了当前位置就是最左端。
   • 如果读到的是其他符号，说明左移成功了，当前位置不是最左端。
4. 恢复: 无论检测结果如何，在继续下一步计算之前，机器都必须将磁带恢复原状（例如，将 $ 写回 a），以避免破坏数据。
5. 阶段 3 和 4 (主循环) 的实现:
   • 作者轻描淡写地说这些阶段的实现是“简单”（straightforward）的，每个阶段用“几个状态”就能完成。
   • 这暗示了像“划掉一个b”、“来回穿梭”、“恢复b”这些操作，虽然在高层次描述中是一句话，但在状态机层面，每一个都需要一组专门的状态来引导磁头的移动和读写。例如，“来回穿梭”至少需要一个“向右找c”的状态和一个“向左找b”的状态。

这个例子解决了一个更复杂的问题——元素互异性 (Element Distinctness)，展示了图灵机如何处理列表和执行两两比较。

1. 目标语言:
   • $E = \{\#x_1\#x_2\#...\#x_l \mid \text{每个 } x_i \in \{0,1\}^* \text{ 且 } x_i \neq x_j \text{ 对于每个 } i \neq j\}$
   • 语言 $E$ 包含由 # 分隔的二进制字符串列表，其中所有字符串必须互不相同。
   • 示例:
   • #01#10#00 属于 $E$。
   • #01#10#01 不属于 $E$，因为第一个和第三个字符串都是 01。
   • #0#1# 属于 $E$。
   • # (空列表) 或 #01# (单个元素的列表) 也属于 $E$。
2. $M_4$ 的高层次算法描述:

这是一个两重循环的比较算法。外层循环选择一个字符串 $x_i$，内层循环将其与所有后续字符串 $x_j (j>i)$ 进行比较。

• 核心工具: 算法使用两个“标记”来指示当前正在比较哪两个字符串。我们可以想象成一个“左指针”和一个“右指针”。
• 阶段 1: 初始化:
• 在磁带的第一个符号（即第一个 #）上放一个标记（我们称之为“左标记”）。
• 处理边界情况：如果输入为空（第一个符号是 sqcup），接受。如果第一个符号不是 #，格式错误，拒绝。

• 阶段 2: 初始化内层循环:
• 从左标记处向右扫描，找到下一个 #，在它上面放第二个标记（“右标记”）。
• 处理边界情况：如果在找到第二个 # 之前就遇到了空白，说明列表只有一个元素（或为空），它们自然是互异的，所以接受。

• 阶段 3: 比较两个字符串:
• 这是 $x_i$ 和 $x_j$ 的比较。这两个字符串分别位于“左标记”和“右标记”之后。
• 这个比较过程本身就是一个子算法，非常类似于示例 3.9 中比较 $w\#w$ 的“之字形”移动和划掉字符的过程。
• 如果发现两个字符串相等，立即拒绝。

• 阶段 4: 移动标记 (循环控制):
• 推进内层循环: 如果阶段 3 的比较结果是不相等，那么需要将 $x_i$ 与下一个字符串 $x_{j+1}$ 比较。这是通过将“右标记”移动到下一个 # 上来实现的。
• 移动右标记后，返回阶段 3 继续比较。
• 推进外层循环: 如果“右标记”在向右移动时，找不到下一个 # 了（遇到了空白），这说明内层循环结束了（$x_i$ 已经和所有它后面的 $x_j$ 都比较过了，且都不相等）。
• 此时，需要开始下一轮外层循环，即用 $x_{i+1}$ 去和它后面的字符串比较。
• 这是通过：

1. 将“左标记”移动到它右边的下一个 # 上。
2. 将“右标记”移动到这个新的“左标记”后面的第一个 # 上。
   • 最终接受条件: 如果在移动“左标记”后，无法为其找到一个“右标记”（因为后面没有更多的 # 了），这意味着所有可能的对 $(x_i, x_j)$ 都已经比较完毕，并且全都不相等。此时，接受。

• 阶段 5: 跳转: 返回阶段 3，用新的标记位置开始新一轮的字符串比较。

这部分内容是对前面几个示例，特别是示例 3.12 中使用的技术的总结，并对这些示例所属的语言类别给出了结论。

1. 标记磁带符号 (Marking Tape Symbols) 技术详解:
   • 概念: “在符号上方放置一个标记”是高层次描述中的说法。
   • 实际实现: 这并不是真的在符号“上方”做了什么，而是在图灵机的形式化模型中，通过扩展磁带字母表 $\Gamma$ 来实现的。
   • 方法:
2. 假设我们想标记符号 s。
3. 我们在磁带字母表 $\Gamma$ 中引入一个全新的符号，比如 s_dot 或简写为 ṡ。
4. “在 s 上放标记”这个动作，对应的图灵机操作就是：当磁头在 s 上时，执行一次写入操作，将 s 替换为 ṡ。
5. “移除标记”的操作就是将 ṡ 写回 s。
6. “检查标记”的操作就是让转移函数对 ṡ 有特定的响应。
   • 通用化: 如果我们想能标记磁带上的任何符号（比如 a, b, c, #），我们只需要在 $\Gamma$ 中为它们都创建一个“带点”的版本：$\{a, b, c, \#, \dot{a}, \dot{b}, \dot{c}, \dot{\#}, ...\}$。
   • 示例: 在 $M_4$ 中，为了标记 #，磁带字母表 $\Gamma$ 中需要同时包含 # 和一个新符号，比如 \#（带点的#）。
7. 对示例语言的分类结论:
   • 语言:
   • $A = \{0^{2^n}\}$ (示例 3.7)
   • $B = \{w\#w\}$ (示例 3.9)
   • $C = \{a^i b^j c^k \mid i \times j = k\}$ (示例 3.11)
   • $E = \{\#x_1\#...\#x_l \mid x_i \neq x_j\}$ (示例 3.12)
   • 结论: 所有这些语言都是可判定的 (decidable)。
   • 理由: 对于我们为这些语言设计的图灵机 ($M_2, M_1, M_3, M_4$)，它们的算法对于任何输入，都能在有限的步骤内完成，并最终停机进入 q_accept 或 q_reject 状态。它们从不循环。因此，这些图灵机都是判决机 (deciders)。根据定义，如果一个语言能被一个判决机判决，那它就是可判定的。
8. 重申语言类别的关系:
   • “所有可判定语言都是图灵可识别的”。这是一个重要的层级关系。
   • 理由: 判决机本身就是图灵机的一种特殊情况（行为更好的图灵机）。所以，如果一个语言是可判定的，就意味着存在一个判决机来判决它，而这个判决机也是一台图灵机，它识别这个语言。因此，该语言也必然是图灵可识别的。
9. 预告后续内容:
   • 作者指出了下一个挑战：“证明一种语言是图灵可识别但不可判定则更为困难。”
   • 这预示着我们将要遇到一类新的、更“奇怪”的问题，它们存在算法可以验证“是”的答案，但没有任何算法能保证对“不是”的答案给出回答（可能会永远算下去）。
   • 这个问题将在第4章中深入探讨，其核心就是著名的停机问题。