Handout 8A

这部分是讲义的标题信息。

• Anum Ahmad 和 Zachary Thayer：这是讲义的作者。在学术材料中，通常会在开头标明作者，以明确内容的来源和责任人。
• COMS 3261 Fall 2024：这部分信息指明了该讲义所属的课程和学期。
• COMS 3261：是课程代码，通常代表“Computer Science”（计算机科学）的某个特定课程。这里的课程很可能是关于计算理论、自动机理论或形式语言的。
• Fall 2024：代表2024年秋季学期。这有助于将讲义置于特定的时间背景下，方便学生和老师按学期整理和查找资料。

这部分内容介绍了图灵机的核心概念和它相较于之前学习的计算模型（如有限自动机DFA/NFA、下推自动机PDA）的强大之处。

1. 核心论点：图灵机是一种极其强大的计算模型，它可以模拟任何其他“合理的”计算模型。这被称为邱奇-图灵论题（Church-Turing Thesis）的通俗说法。这个论题指出，任何能被算法解决的计算问题，都能被图灵机解决。换句话说，图灵机定义了“可计算”的上限。
2. 关键变化（与弱模型的对比）：
   • 无限纸带 (Infinite Tape)：这是图灵机最核心的特征之一。
   • 之前的模型：有限自动机（DFA/NFA）几乎没有内存（只有当前状态），下推自动机（PDA）有一个栈（stack），但访问方式受限（只能访问栈顶）。
   • 图灵机：拥有一个纸带（tape），这个纸带在概念上是向右无限延伸的。纸带被划分为一个个的格子，每个格子可以存储一个符号。输入字符串被放置在纸带的起始部分，后面跟着无限个空白符号（blank symbol, 通常记为 _ 或 ⊔）。
   • 意义：无限纸带等同于无限内存。这使得图灵机可以存储和处理任意数量的信息，不再像DFA那样受限于有限的状态，也不像PDA那样受限于栈的后进先出结构。
   • 直觉应用：因为有了无限内存，很多看似复杂的问题变得直观上可解。例如，要检查字符串w中是否恰好有67个'1'。对于DFA来说，如果状态数量少于67，是无法完成这个任务的（需要68个状态来计数0到67）。但对于图灵机，我们可以简单地在纸带的某个地方开辟一个“计数区”，每当读写头在输入区读到一个'1'，就去计数区将一个二进制数加一。最后，我们只需检查计数区的值是否为67。

• 读/写能力 (Read/Write Capability)：
• 之前的模型：DFA/NFA和PDA的读头只能读取输入，不能修改。
• 图灵机：它的带头（tape head）不仅可以读取当前格子上的符号，还可以写入一个新的符号来覆盖它。
• 意义：写入能力是实现“计算”的关键。它允许图灵机在纸带上进行草稿运算、标记已处理过的部分、存储中间结果。例如，在做加法 a+b 时，可以把 a 和 b 写在纸带上，然后通过一系列的擦除和写入操作，最终将结果 a+b 呈现在纸带上。
• 类比：将图灵机看作一个Python程序。Python程序可以读取变量的值，也可以修改变量的值（x = x + 1）。这种读写能力是所有现代计算机的基础。因此，一个判断问题能否被图灵机判定的直观方法是：你能不能写一个Python程序来解决它？如果能（并且保证程序对任何输入都会停止），那么这个问题就是图灵机可判定的。

• 不受限制的移动 (Unrestricted Movement)：
• 之前的模型：DFA/NFA/PDA的读头通常只能单向移动（从左到右）。
• 图灵机：带头在每一步操作后，可以选择向左（L）或向右（R）移动一个格子。
• 意义：双向移动意味着图灵机可以反复扫描输入、回顾之前处理过的内容。这对于需要多次访问数据的算法至关重要。例如，在判断一个字符串是否是回文 ww^R 时，图灵机可以先读取第一个字符，移动到字符串末尾，检查最后一个字符是否匹配，然后回到第二个字符，再移动到倒数第二个字符，如此反复，直到检查完整个字符串。

这部分通过三个层次的描述（形式化定义、实现级描述、高层描述）来举例说明如何构造和理解图灵机。

这部分引出了图灵机的变体模型。核心思想是，我们可以对标准图灵机（单纸带，确定性）的结构进行一些修改，例如增加更多的纸带或引入非确定性。然而，一个惊人的结论是，这些变体虽然在设计算法时可能更方便、更直观，但它们在“能解决什么问题”这个根本层面上，其计算能力与最基础的标准图灵机是等价的。这意味着，任何一个多带图灵机能解决的问题，我们总能构造一个单带图灵机来解决它（尽管可能慢得多）；反之亦然。这进一步加强了邱奇-图灵论题的地位，表明“可计算性”这个概念是相当稳健的，不依赖于模型的具体细节。

这部分详细介绍多带图灵机并通过一个例子展示其应用。

这部分介绍了非确定性图灵机（NTM），并用图的可达性问题作为例子说明其工作原理和设计优势。

这道题要求我们追踪一个给定的输入-输出图灵机的运行过程，并推断它所计算的函数。输入-输出图灵机与我们之前看到的判定器或识别器略有不同，它的目标不是接受或拒绝，而是在停机时，将纸带上的内容作为输出。它通常只有一个停机状态 $q_{halt}$，而不是 $q_{acc}$ 和 $q_{rej}$。

首先，我们来分析这个图灵机的转移函数 $\delta$：

• 状态 $q_0$ 的行为:
• $\delta(q_0, 0) = (q_0, 0, R)$: 读到0，不变，向右移动。
• $\delta(q_0, 1) = (q_0, 1, R)$: 读到1，不变，向右移动。
• $\delta(q_0, \_) = (q_1, \_, L)$: 读到空白符，不变，状态变为 $q_1$，并向左移动。
• 总结 $q_0$: 这个状态的作用就是从左到右扫描整个输入字符串，直到找到字符串末尾的空白符。然后它切换到状态 $q_1$ 并把带头移动到输入串的最后一个字符上。

• 状态 $q_1$ 的行为:
• $\delta(q_1, 0) = (q_{halt}, 1, R)$: 读到0，将其翻转为1，然后进入停机状态 $q_{halt}$。
• $\delta(q_1, 1) = (q_1, 0, L)$: 读到1，将其翻转为0，保持在 $q_1$ 状态，并继续向左移动。
• $\delta(q_1, \_) = (q_{halt}, \_, L)$: 读到空白符（这意味着已经移动到了输入串的左边），进入停机状态 $q_{halt}$。
• 总结 $q_1$: 这个状态从右到左扫描字符串。如果遇到1，就翻转成0，继续向左。一旦遇到第一个0（从右边算起），就将其翻转成1，然后立即停机。如果在找到0之前就走到了字符串的开头（读到空白符），也停机。

• 整体行为分析:

1. 机器首先移动到输入二进制数的末尾。
2. 然后从右向左，将所有的 '1' 变为 '0'。
3. 当遇到第一个 '0' 时，将其变为 '1' 并停机。
4. 如果一路都是 '1'，直到字符串开头，那么所有的 '1' 都会变成 '0'，然后机器在字符串左边的空白处停机。

这正是二进制加一的操作！

这道题要求我们设计一个图灵机来实现著名的考拉兹猜想（Collatz conjecture）中的一步操作。我们需要给出实现级描述，这意味着我们不需要写出完整的7-元组，但需要清晰地描述纸带和带头的操作。使用多带图灵机可以大大简化设计。

我们将使用一个3带图灵机来解决这个问题。

• 纸带1: 输入/输出带。初始时包含#<x>，最终将包含计算结果。
• 纸带2: 计算带。用于执行算术运算的草稿空间。
• 纸带3: 辅助带。用于存储中间值，如 $x$ 的副本。

算法的实现级描述：

在输入 $w = \#\langle x \rangle$ 上：

1. 预处理和分支

a. 将带头1移动到字符串的末尾，检查 $\langle x \rangle$ 的最后一位。

b. 如果最后一位是 '0' ( $x$ 是偶数)，则进入偶数处理流程。

c. 如果最后一位是 '1' ( $x$ 是奇数)，则进入奇数处理流程。

1. 偶数处理流程 (计算 $x/2$)

a. 识别: $x$ 是偶数，其二进制表示以 '0' 结尾。

b. 计算: 二进制数除以2，相当于右移一位，即去掉末尾的'0'。

c. 操作:

i. 将带头1移动到 $\langle x \rangle$ 的最后一个字符 '0' 上。

ii. 将这个 '0' 擦除（替换为空白符 _）。

iii. 停机。纸带1上现在是 #<x/2>。

1. 奇数处理流程 (计算 $3x+1$)

a. 识别: $x$ 是奇数。计算 $3x+1$。我们知道 $3x+1 = (2x+x)+1$。在二进制中，$2x$ 就是 $x$ 左移一位（在末尾加一个'0'）。

b. 准备计算:

i. 将纸带1上 '#' 之后的内容 $\langle x \rangle$ 复制到纸带2和纸带3上。纸带2和纸带3现在都包含 $\langle x \rangle$。

c. 计算 $2x$:

i. 在纸带2的 $\langle x \rangle$ 末尾添加一个 '0'。现在纸带2上是 $\langle 2x \rangle$。

d. 计算 $2x+x$ (即 $3x$):

i. 现在我们需要执行二进制加法：(纸带2) + (纸带3)。这是一个标准的图灵机子程序。

ii. 使用纸带1作为输出区域（先清空原有内容）。

iii. 从右到左对齐纸带2和纸带3。

iv. 模拟手动的二进制加法，处理好进位，将结果逐位写在纸带1上。完成后，纸带1上是 $\langle 3x \rangle$。

e. 计算 $(3x)+1$:

i. 我们刚刚在纸带1上得到了 $\langle 3x \rangle$。现在需要对其加一。

ii. 调用练习题1中描述的二进制加一子程序（或者一个更完善的版本）。

iii. 在纸带1上，从右到左扫描 $\langle 3x \rangle$，将遇到的'1'翻转为'0'，直到遇到'0'或空白，将其翻转为'1'。

f. 格式化输出:

i. 确保纸带1的内容是 #<3x+1> 的形式。这可能需要移动纸带内容，在前面插入 '#'。一个更简单的做法是在步骤 d-i 中清空纸带1时，先在开头写好 '#'。

ii. 停机。

这道题要求我们证明语言 $L$ 是可判定的。这意味着我们需要构造一个图灵机 $D$ (一个判定器)，它能在有限时间内对任何输入 $\langle M, k \rangle$ 给出“接受”或“拒绝”的答案。

• 语言 L 的定义:
• 输入是一个二元组 $\langle M, k \rangle$，其中 $M$ 是一个图灵机的编码， $k$ 是一个正整数。
• 语言 $L$ 中的元素满足条件：存在一个输入字符串 $w$，使得图灵机 $M$ 在 $w$ 上运行时，其计算步数至少为 $k$。

• 证明思路:

我们要构建一个判定器 $D$ 来判定 $L$。$D$ 的输入是 $\langle M, k \rangle$。$D$ 的任务是回答：“是否存在一个输入 $w$ 能让 $M$ 跑上至少 $k$ 步？”

这里的关键词是“存在”。我们似乎需要搜索所有可能的输入字符串 $w$。但所有可能的输入字符串是无限多的，直接搜索是行不通的。我们需要找到一个界限。

让我们思考一下，什么情况下 $M$ 的运行步数会少于 $k$ 步？如果 $M$ 在所有输入 $w$ 上，都在 $k-1$ 步之内停机了（接受或拒绝），那么就不存在能让它运行至少 $k$ 步的输入。

关键洞见在于，一个图灵机在 $k$ 步内能做什么？

• 在 $k$ 步内，带头最多能从起始位置向左或向右移动 $k-1$ 格。
• 因此，在 $k$ 步之内，图灵机 $M$ 访问的纸带格子数量是有限的，最多是 $k$ 个格子（初始位置 + $k-1$ 次移动）。
• 这意味着，在 $k$ 步内，$M$ 的行为只受到纸带上它能访问到的那部分内容的影响。

考虑所有长度小于 $k$ 的输入字符串。为什么是这个界限？

• 如果 $M$ 在一个很长的输入 $w$ (长度 $\ge k$) 上运行，它在前 $k$ 步里，也只能看到 $w$ 的前 $k$ 个字符。
• 它的行为和在另一个输入 $w'$ ( $w$ 的前 $k-1$ 个字符) 上的前 $k$ 步是完全一样的。
• 更简单地，考虑空字符串 $\epsilon$ 作为输入。如果 $M$ 在 $\epsilon$ 上运行了至少 $k$ 步，那么我们就找到了一个满足条件的输入（即 $w=\epsilon$），于是 $\langle M, k \rangle \in L$。
• 如果 $M$ 在 $\epsilon$ 上运行了少于 $k$ 步就停机了，这还不够。我们还需要考虑别的输入。

让我们换个角度，从图灵机的格局（configuration）来想。一个格局包含了当前状态、纸带内容、带头位置。

• 如果一个图灵机运行了 $k$ 步，它会经历 $k+1$ 个不同的格局。
• 如果一个图灵机在某个点重复了一个格局，它就会进入无限循环。
• 但是，我们关心的是步数，而不是停机。

回到关键点：在前 $k$ 步内，机器的行为只取决于它能扫描到的纸带部分。

• 这部分纸带的长度最多为 $k$。
• 因此，我们只需要考虑那些长度小于 $k$ 的输入字符串就足够了。任何更长的字符串，在前 $k$ 步的行为上，都与一个长度小于 $k$ 的前缀等价。
• 甚至，我们可以只考虑一个输入：空字符串 $\epsilon$。
• 为什么？因为纸带上除了输入，还有无限的空白符号_。
• 如果 $M$ 需要读一些非空白的符号才能运行得更久，我们可以认为这些符号是 $M$ 自己写到纸带上的。
• 想象一下，任何在某个输入 $w$ 上运行 $k$ 步的计算过程，我们都可以构造一个在空输入 $\epsilon$ 上运行的图灵机 $M'$ 来模拟它（$M'$ 先在纸带上写下 $w$，然后像 $M$ 一样运行）。
• 但题目给的是固定的 $M$。让我们重新思考。

一个更简单且正确的思路：

我们不需要搜索所有输入。我们只需要模拟 $M$ 在所有可能的短输入上的运行情况。但“多短”才够呢？

• 设 $M$ 的状态数为 $|Q|$，纸带字母表大小为 $|\Gamma|$。
• 在 $k$ 步内，图灵机可以产生的不同格局数量是巨大的，但我们不需要关心这个。
• 让我们回到最初的直觉：如果存在一个输入 $w$ 能让 $M$ 跑 $\ge k$ 步，那么 $M$ 在前 $k-1$ 步都没有停机。
• 我们可以尝试模拟 $M$ 在所有可能的输入上并行运行 $k$ 步。但这仍然是无限的。

最终的、正确的思路：有界模拟

• 我们不需要测试无限多的输入。我们只需要测试有限多个，并且模拟有限步。
• 判定器D的算法:

1. $D$ 接收输入 $\langle M, k \rangle$。
2. $D$ 系统地生成所有长度从 0 到 $k-1$ 的字符串。设 $M$ 的输入字母表为 $\Sigma$。这些字符串的数量是有限的。
3. 对于其中的每一个字符串 $w$：

a. $D$ 模拟 $M$ 在输入 $w$ 上的运行。

b. $D$ 在模拟的同时进行计数，最多模拟 $k$ 步。

c. 如果在模拟的 $k$ 步内，$M$ 没有停机（即没有进入 $q_{acc}$ 或 $q_{rej}$），这意味着 $M$ 在 $w$ 上的运行步数至少是 $k$。$D$ 立即停机并接受 $\langle M, k \rangle$。

1. 如果 $D$ 尝试了所有长度小于 $k$ 的字符串，并且在每个字符串上，$M$ 都在 $k$ 步内停机了，这意味着什么？这还不足以拒绝。因为可能存在一个长度为 $k$ 或更长的字符串能让 $M$ 运行更久。

让我们重新审视问题。我们需要证明的是可判定性。我们设计的判定器 $D$ 必须自己能停机。

关键在于：如果 $M$ 在所有长度小于 $k$ 的输入上都在 $k$ 步内停机，那么它在任何输入上都会在 $k$ 步内停机。

• 为什么这是真的？ 假设 $M$ 在一个长度 $\ge k$ 的输入 $w$ 上运行了 $k$ 步或更多。在前 $k$ 步中，$M$ 的带头最多只能扫描到从起始位置开始的 $k$ 个格子。它的行为完全由 $w$ 的前 $k-1$ 个字符（长度为 $k$ 的前缀）决定。设这个前缀为 $w'$。那么 $M$ 在输入 $w'$ 上的前 $k$ 步行为与在 $w$ 上完全相同。因此，如果 $M$ 在 $w$ 上运行了 $\ge k$ 步，它在 $w'$ （一个长度小于 $k$ 的字符串）上也必然运行了 $\ge k$ 步。
• 这就形成了一个矛盾。所以我们的假设“$M$ 在一个长度 $\ge k$ 的输入上运行了 $\ge k$ 步”是错误的。
• 结论：我们只需要检查所有长度小于 $k$ 的字符串就足够了！

最终的判定器 D 的实现级描述:

在输入 $\langle M, k \rangle$ 上：

1. 从 $M$ 的描述中提取其输入字母表 $\Sigma$。
2. 构造一个所有长度从 0 到 $k-1$ 的 $\Sigma$ 上的字符串的列表。这个列表是有限的。
3. 对于这个列表中的每一个字符串 $w$：

a. 模拟 $M$ 在输入 $w$ 上运行，最多 $k$ 步。

b. 如果在模拟过程中，$M$ 的步数达到了 $k$（即在 $k-1$ 步后仍未停机），那么我们找到了一个能让 $M$ 运行至少 $k$ 步的输入。因此，接受 $\langle M, k \rangle$ 并停机。

1. 如果对于列表中的所有字符串 $w$，$M$ 都在 $k$ 步之内停机了，那么根据我们上面的论证，对于任何输入，$M$ 都会在 $k$ 步内停机。因此，不存在能让 $M$ 运行至少 $k$ 步的输入。所以，拒绝 $\langle M, k \rangle$ 并停机。

为什么 D 是一个判定器？

• 步骤1和2是有限的。
• 步骤3的循环次数是有限的。
• 循环体内的模拟（步骤3a）也是有界的，最多模拟 $k$ 步。
• 因此，无论在哪种情况下，判定器 $D$ 总会在有限时间内完成其计算并停机（接受或拒绝）。
• 所以，语言 $L$ 是可判定的。

这道题要求我们证明，如果 $L$ 是一个可识别语言，那么经过 9/10 运算后得到的新语言 $9/10(L)$ 也是可识别的。我们需要从高层和实现级两个层面给出证明。

• 语言定义:
• $L$ 是可识别的，意味着存在一个图灵机 $M$ 识别它。
• $9/10(L)$ 的输入是10个用#分隔的字符串 $\langle x_1\#x_2\#...\#x_{10} \rangle$。
• 该输入属于 $9/10(L)$ 的条件是：这10个字符串中，至少有9个属于语言 $L$。

• 证明思路:

我们需要构造一个新的图灵机 $M'$ 来识别 $9/10(L)$。由于 $L$ 只是可识别的，这意味着 $M$ 在处理不属于 $L$ 的字符串时可能会永不停机。这就要求我们必须使用交替模拟（Dovetailing）的技巧。

这道题是上一题的泛化版本。不再是固定的9和10，而是任意给定的 $m$ 和 $n$。我们需要证明可识别语言对这个更通用的 m/n 运算也是封闭的。

• 语言定义:
• $L$ 是一个可识别语言，被图灵机 $M$ 识别。
• m/n(L) 的输入是一个元组 $\langle (m, n, x_1\#...\#x_n) \rangle$。
• 输入属于 m/n(L) 的条件是：在 $n$ 个子字符串 $x_1, \dots, x_n$ 中，至少有 $m$ 个属于语言 $L$。

• 证明思路:

我们同样需要构造一个新的图灵机 $M'$ 来识别 m/n(L)。由于 $m$ 和 $n$ 是输入的一部分，而不是固定的常数，$M'$ 必须能动态地处理任意数量的子串和任意的目标计数值。

高层描述:

判定器 $M'$ 的高层描述:

在输入 $w = \langle (m, n, x_1\#x_2\#...\#x_n) \rangle$ 上：

1. 解析输入: 首先，解析输入 $w$，提取出数字 $m$ 和 $n$，并识别出 $n$ 个子字符串 $x_1, x_2, \dots, x_n$。
2. 并行模拟: 并行地在所有 $n$ 个子字符串 $x_1, x_2, \dots, x_n$ 上模拟图灵机 $M$。
3. 计数与接受: 维护一个接受计数器 accept_count，初始为0。每当任何一个对 $x_i$ 的模拟进入接受状态时，就将 accept_count 加一。
4. 检查条件: 在每次计数器增加后，都检查 accept_count 的值是否等于 $m$。如果等于 $m$，立刻停机并接受输入 $w$。

为什么这个高层描述是正确的？

这个逻辑与练习题4完全相同，只是将固定的9和10换成了变量 $m$ 和 $n$。

• 如果 $w \in m/n(L)$: 至少有 $m$ 个 $x_i$ 属于 $L$。这些 $x_i$ 上的模拟最终都会被 $M$ 接受。因此，accept_count 最终会达到 $m$，$M'$ 会接受 $w$。
• 如果 $w \notin m/n(L)$: 属于 $L$ 的子字符串数量严格小于 $m$。因此 accept_count 永远无法达到 $m$。$M'$ 永远不会接受 $w$。
• 结论: $M'$ 识别 m/n(L)。

如何用图灵机实现这个高层描述？

虽然题目只要求高层描述，但我们可以思考一下其实现。

• 需要一个能处理任意 $n$ 个并行任务的图灵机。一个固定的 $k$ 带图灵机无法胜任，因为 $n$ 是变量。
• 我们需要一个能模拟无限带或动态数量带的图灵机。这可以通过在单条纸带上使用复杂的编码来实现。
• 单带实现思路:

1. 纸带布局: 将单条纸带划分为多个部分。例如：
   • #####...##accept_count#
   • 用来存储第 $i$ 个模拟的状态，包括 $x_i$ 的内容和 $M$ 在其上的模拟状态（如 $M$ 的当前状态、带头位置等）。
2. 解析输入: $M'$ 首先读取 $m$ 和 $n$，并将 $n$ 个子串 $x_i$ 设置到对应的 区域。
3. 交替模拟循环:

a. $M'$ 的带头从左到右扫描整个纸带。

b. 当经过 <xi_config> 区域时，它读取该模拟的当前状态，并根据 $M$ 的转移函数模拟 $M$ 运行一步，然后更新 <xi_config> 区域。

c. 如果这次模拟使 $M$ 进入接受状态，并且该区域没有被标记过“已接受”，$M'$ 就移动到 accept_count 区域，将其加一。

d. 然后，$M'$ 检查 accept_count 是否等于 $m$。如果是，接受。

e. 完成对所有 $n$ 个配置的一步模拟后，将带头移回左端，开始新一轮的扫描。

这个单带实现是复杂但可行的，它证明了即使面对动态数量的并行任务，图灵机模型依然有能力处理。

这道题要求我们证明语言 CYCLE 是可判定的。这意味着我们需要设计一个算法（可以被一个图灵机实现），该算法对于任何输入的图 $G$，都能在有限时间内停机，并准确地回答 $G$ 中是否存在圈。

• 语言定义:
• CYCLE 是一系列图的编码 $\langle G \rangle$。
• 一个图 $G$ 的编码 $\langle G \rangle$ 属于 CYCLE，当且仅当 $G$ 中至少包含一个圈。
• 圈 (Cycle): 一个路径，其起点和终点是同一个顶点，并且路径中至少包含一条边。（对于简单图，通常要求圈的长度至少为3）。

• 证明思路:

我们需要给出一个判定器 $D$ 的算法。输入是图 $G$ 的编码，例如邻接矩阵或邻接表。既然要判定，算法必须保证对任何图都停机。图是有限的（有限的顶点和边），所以我们可以系统地搜索。

一个检测圈的经典算法是深度优先搜索 (DFS)。

使用深度优先搜索 (DFS) 的高层算法:

判定器 $D$ 的高层描述:

在输入 $\langle G \rangle$ 上，其中 $G=(V, E)$ 是一个图，V是顶点集，E是边集：

1. 初始化一个空的“已访问”集合 visited，用于在单次DFS中记录路径上的顶点。
2. 初始化一个空的“完全探索过”集合 fully_explored，用于记录已经完成DFS的顶点，避免重复工作。
3. 对图中的每一个顶点 u in V:

a. 如果 u 在 fully_explored 中，跳过，处理下一个顶点。

b. 调用一个 DFS 辅助函数 DFS-Visit(u, parent=null)。DFS-Visit 的逻辑如下：

i. 将当前顶点 v 添加到 visited 集合中（表示 v 在当前搜索路径上）。

ii. 对于 v 的每一个邻居 w:

• 如果 w 在 visited 集合中，并且 w 不是 v 的父节点（对于无向图），那么我们找到了一个返祖边 (back edge)，这意味着图中存在一个圈。立即停机并接受。
• 如果 w 不在 visited 集合中，递归调用 DFS-Visit(w, parent=v)。如果在任何递归调用中发现了圈（即返回“接受”），则将“接受”信号向上传递，最终停机并接受。

iii. 当一个顶点的所有邻居都探索完毕后，将它从 visited 集合中移除（回溯），并加入 fully_explored 集合。

1. 如果遍历了所有顶点，并且所有DFS调用都正常结束而没有找到圈，那么图中不存在圈。停机并拒绝。

为什么这个算法是一个判定器？

• 图 $G$ 的顶点数 $|V|$ 和边数 $|E|$ 都是有限的。
• 主循环（步骤3）最多执行 $|V|$ 次。
• DFS 算法（DFS-Visit）会访问每个顶点和每条边最多一到两次（取决于图的表示法和有向/无向）。visited 和 fully_explored 集合确保了没有无限循环。
• 总的计算步数是关于 $|V|$ 和 $|E|$ 的多项式级别，例如 $O(|V|+|E|)$。
• 因此，该算法对任何有限图输入，总是在有限时间内停机并给出正确的“接受”或“拒绝”答案。所以 CYCLE 是可判定的。

本部分将对整个讲义的核心内容进行总结和回顾。讲义Handout 8A主要介绍了计算理论的基石——图灵机，并探讨了与之相关的可判定性和可识别性的概念。通过形式化定义、变体模型和一系列练习题，讲义旨在建立一个关于“什么是可计算的”以及“如何证明一个问题是可计算的”的坚实理解。

讲义的核心始于图灵机相较于旧模型（如DFA, PDA）的三个革命性突破：

1. 无限纸带：提供了无限的内存，打破了有限自动机在存储能力上的根本限制。
2. 读/写能力：允许机器在计算过程中修改其“内存”，这是执行真正意义上“计算”的基础，而不仅仅是识别模式。
3. 双向移动：使得机器可以反复访问和处理数据，为需要来回参考信息的复杂算法提供了可能。

这三者共同构成了邱奇-图灵论题的基础，即任何直觉上可计算的函数都可以由一个图灵机来计算。

讲义通过三个层次来描述图灵机，展示了在不同场景下与图灵机打交道的方式：

1. 形式化描述 (7-元组)：最底层、最精确的定义，是理论的基石，但在实践中极其繁琐。
2. 实现级描述：用自然语言描述带头的移动和纸带的操作，是在精确性和可读性之间的最佳平衡点，是设计算法时最常用的方式。
3. 高层描述：用纯粹的算法思想来描述，完全忽略机器细节。这在讨论一个问题是否“可计算”时非常有用，让我们能专注于问题本身的核心逻辑。

讲义介绍了两种重要的图灵机变体：

1. 多带图灵机：拥有多条独立的纸带，极大地方便了需要并行处理、比较或存储多份数据的算法设计。它就像一个拥有多块草稿板的程序员。
2. 非确定性图灵机 (NTM)：允许一步有多种可能的走向，其“猜测并验证”的模型极大地简化了搜索类问题的算法设计。它就像一个能瞬间派出无数分身探索所有可能路径的侦探。

最关键的结论是：这些变体在计算能力上与最基础的单带确定性图灵机是等价的。它们能解决的问题集合完全相同，变体的优势在于提供更强大、更直观的算法设计工具，但并未突破“可计算”的边界。

通过练习题，讲义深刻地揭示了两个核心概念的区别：

• 图灵可识别语言 (Turing-recognizable)：存在一个图灵机，对于属于该语言的输入，它会接受；对于不属于的，它可能拒绝，也可能永不停机。
• 图灵可判定语言 (Turing-decidable)：存在一个图灵机（称为判定器），对于任何输入，它总能在有限时间内停机，并给出明确的接受或拒绝。

关键区别：判定器必须对所有输入都保证停机。所有可判定语言都是可识别的，但反之不成立（例如，停机问题$A_{TM}$是可识别但不可判定的）。

讲义中的练习题集中展示了证明可判定性和封闭性的几种核心技巧：

1. 直接构造 (Direct Construction)：为问题设计一个具体的、保证停机的算法（如练习6用DFS检测圈）。这是证明可判定性最直接的方法。
2. 交替模拟 (Dovetailing)：在处理多个可能永不停机的计算时（如练习4、5），通过轮流模拟每一步来保证所有计算都有机会向前推进。这是证明可识别语言封闭性的关键技巧。
3. 有界模拟 (Bounded Simulation)：将一个看似无限的搜索问题（“是否存在一个输入...”）转化为一个在有限集合上的、有步数限制的有限过程（如练习3）。这是证明某些特定类型的语言可判定的巧妙方法。