COMS W3261: 计算机科学理论

这部分内容介绍了计算理论中最基础、最核心的概念之一：集合 (Set)。集合是构建后续所有复杂概念（如字母表、字符串、语言、自动机等）的基石。

1. 什么是集合？
   • 集合就是一个“容器”或“袋子”，里面装着一些东西。
   • 这些“东西”被称为集合的元素 (elements)。
   • 一个集合的关键特征是它的确定性（一个对象要么在集合里，要么不在，没有模棱两可的情况）和无序性（元素之间没有先后顺序，{1, 2} 和 {2, 1} 是同一个集合）以及互异性（一个元素在集合中只出现一次，{1, 1, 2} 会被自动看作 {1, 2}）。
2. 元素可以是任何东西：
   • 符号 (symbols)：比如 {a, b, c}，这是字母表的基础。
   • 数字 (numbers)：比如 {0, 1, 2, 3}，这是自然数集的一部分。
   • 字符串 (strings)：比如 {"apple", "banana", "cherry"}。
   • 集合本身 (sets)：一个集合的元素也可以是另一个集合，比如 {{1, 2}, {3, 4}}。这个集合有两个元素，每个元素都是一个集合。这在定义幂集时非常重要。
3. 定义集合的方式：
   • 计算机科学中，我们需要用精确的、无歧义的方式来描述一个集合，所以这里介绍了三种主要方法。

这部分详细说明了三种定义或描述集合内容的常用方法。

1. 列举法 (Roster Notation):
   • 这是最直接的方法，尤其适用于元素数量不多的有限集合。
   • 你把集合中所有的元素一个一个地写出来，用逗号隔开，然后用大括号 {} 包围起来。
   • 例如:
   • $\{1\}$：表示只包含数字 1 的集合。
   • $\{1, 2, 3\}$：表示包含数字 1、2、3 的集合。
   • $\{\mathrm{a}, \mathrm{b}, \mathrm{c}\}$：表示包含符号 'a', 'b', 'c' 的集合。
2. 模式法 (Pattern Notation) / 省略号法:
   • 当集合是无限的，或者有限但元素太多不方便一一列举时，如果元素之间存在明显的规律，就可以使用这种方法。
   • 你写出开头的几个元素以展示规律，然后使用省略号 ... 来表示“照此规律继续下去”。
   • 例如:
   • $\{1, 2, 3, \ldots\}$：这通常表示所有正整数的集合（即 $\mathbb{Z}^+$）。规律是逐个加 1。
   • $\{1, 11, 111, \ldots\}$：这个集合的元素是由数字 1 组成的字符串，长度依次增加。
3. 描述法 / 构造法 (Set-Builder Notation):
   • 这是最强大、最精确的方法，尤其适用于描述无限集合或具有复杂成员资格规则的集合。
   • 格式通常是 {变量 | 对变量的描述或条件}。竖线 | 读作“使得 (such that)”。
   • 例如: $\left\{n \mid n=m^{2} \text{ for some } m \in \mathbb{N}\right\}$
   • {n | ...}: 这个集合由满足特定条件的元素 n 组成。
   • n = m^2: 条件是 n 必须是某个数的平方。
   • for some m ∈ ℕ: 那个“某个数” m 必须是自然数 (Natural Number, $\mathbb{N}=\{0, 1, 2, 3, ...\}$)。
   • 所以，这个集合是所有自然数的平方组成的集合，即 $\{0, 1, 4, 9, 16, \ldots\}$。

这部分引入了用于描述集合之间关系和进行集合运算的基本符号和操作。

1. 成员资格 (Membership):
   • 符号: $\in$
   • 含义: $x \in S$ 表示对象 x 是集合 S 的一个元素。
   • 这是判断一个对象和一个集合之间最基本的关系。
2. 子集 (Subset):
   • 符号: $\subseteq$
   • 含义: $T \subseteq S$ 表示集合 T 是集合 S 的一个子集。这意味着，T 里面的所有元素，都可以在 S 里面找到。
   • 这是一个集合与另一个集合之间的关系。
   • 注意区分 $\in$ 和 $\subseteq$。前者是元素与集合的关系，后者是集合与集合的关系。
3. 幂集 (Power Set):
   • 符号: $\mathcal{P}(X)$
   • 含义: $\mathcal{P}(X)$ 是一个特殊的集合，它的元素是原集合 X 的所有可能的子集。
   • 这是一个“集合的集合”。
   • 关键点:
   • 空集 $\varnothing$ (不含任何元素的集合) 永远是任何集合的子集，所以 $\varnothing \in \mathcal{P}(X)$。
   • 任何集合都是其自身的子集，所以 $X \in \mathcal{P}(X)$。
   • 如果集合 $X$ 有 n 个元素，那么它的幂集 $\mathcal{P}(X)$ 就有 $2^n$ 个元素。
4. 基本集合操作:
   • 并集 (Union): $A \cup B$
   • 含义: 把集合 A 和 B 的所有元素合并在一起，形成一个新的集合。重复的元素只保留一个。
   • 条件: 一个元素只要在 A 中 或者 (or) 在 B 中，它就在并集中。
   • 交集 (Intersection): $A \cap B$
   • 含义: 找出集合 A 和 B 共同拥有的元素，形成一个新的集合。
   • 条件: 一个元素必须同时在 A 中 并且 (and) 在 B 中，它才在交集中。
   • 差集 (Difference): $A \backslash B$
   • 含义: 从集合 A 中，移除所有也存在于集合 B 中的元素，剩下的元素形成一个新的集合。
   • 条件: 一个元素必须在 A 中 并且 (and) 不在 B 中。

这部分将集合的概念具体化，引入了计算理论的核心处理对象：字符串，以及如何将其他数学对象表示为字符串（即编码）。

1. 字母表 (Alphabet):
   • 定义: 字母表是一个特殊的集合，用符号 $\Sigma$ (Sigma) 表示。
   • 特征:
   • 非空: 字母表里至少要有一个符号。
   • 有限: 字母表里的符号数量是有限的。
   • 作用: 字母表规定了我们可以用来构建字符串的所有“合法字符”。
2. 字符串 (String):
   • 定义: 字符串是从字母表 $\Sigma$ 中选取符号并按一定顺序排列形成的有限序列。
   • 关键特征:
   • 有限性: 字符串的长度必须是有限的。
   • 有序性: 符号的顺序很重要。ab 和 ba 是两个不同的字符串。
   • 特殊字符串:
   • 空字符串 (empty string) $\varepsilon$ (Epsilon)：它是一个长度为 0 的特殊字符串，不包含任何符号。
3. 编码 (Encoding):
   • 核心思想: 图灵机等计算模型的输入本质上是字符串。为了让图灵机能处理各种数学对象（如数字、图、甚至其他图灵机），我们必须找到一种方法，将这些对象转换成字符串表示。这个转换过程就是编码。
   • 表示法: 如果 x 是一个数学对象（比如一个图 G），它的编码（一个字符串）通常被写作 $\langle x \rangle$（比如 $\langle G \rangle$）。
   • 编码的应用:
   • 整数: 可以用二进制 (如101) 或十进制 (5) 字符串表示。
   • 图: 可以编码为一个顶点列表和边列表的字符串，例如 ({v1,v2,v3},{(v1,v2),(v2,v3)})。
   • 计算模型: DFA、NFA、TM 本身就是由状态集、字母表、转移函数等组成的元组，这些组成部分都可以被系统地描述成一个长字符串。这就意味着一台图灵机可以把另一台图灵机的描述（编码）作为自己的输入来分析。这是可计算性理论（如停机问题）的核心。
4. 有效编码:
   • 概念: 对于一种编码方案，不是所有字符串都有意义。
   • 例子: 我们约定用 数字#数字 的格式来编码一对整数。
   • 字母表是 $\{0, 1, \dots, 9, \#\}$。
   • 123#321 是一个有效编码，它表示数对 (123, 321)。
   • ##，12#，#321 等都是无效编码，因为它们不符合我们约定的格式，没有对应的数学对象。

这部分定义了计算理论的核心研究对象——语言，以及它的基本集合运算——补集。

1. 语言 (Language):
   • 定义: 一个语言就是一个字符串的集合。
   • 前提: 一个语言中的所有字符串都必须构建于同一个字母表 $\Sigma$ 之上。
   • 本质: 语言就是从所有可能的字符串（这个全集通常记作 $\Sigma^*$）中，根据某个规则挑选出来的一个子集。
   • 计算理论的核心问题: 给定一个语言 L 和一个字符串 w，判断 w 是否属于 L（即 $w \in L$ ?）。这就是所谓的成员资格问题 (Membership Problem)。
   • 例子分析:
   • $\varnothing$: 空语言，它是一个集合，但是里面没有任何字符串。
   • $\Sigma^{*}$: 全语言，包含由字母表 $\Sigma$ 能构成的所有有限长度的字符串（包括空字符串 $\varepsilon$）。星号 * 在这里是克莱尼星号 (Kleene Star)，表示“零个或多个”的串联。
   • $A=\left\{w \in\{0,1\}^{*} \mid w\right.$ contains a 1$\}$: 这是一个在二进制字母表 $\{0,1\}$ 上的语言。规则是“字符串中至少包含一个 '1'”。例如, 1, 010, 111 属于 A, 但 0, 000, $\varepsilon$ 不属于 A。
   • $G_{C}=\{\langle G\rangle \mid G$ is a cyclic graph $\}$: 这是一个更抽象的语言。它的字母表是用来编码图的符号集合。它的字符串不是普通的文本，而是图的编码。如果一个字符串是一个有环图的有效编码，那么这个字符串就在这个语言里。
   • $M_{0110}=\{\langle M\rangle \mid M$ is a TM that accepts 0110\}: 这是一个关于图灵机的语言。它的字符串是图灵机的编码。如果一个字符串 $\langle M \rangle$ 所代表的图灵机 M 能够接受特定的字符串 "0110"，那么 $\langle M \rangle$ 就属于这个语言。
2. 语言的补集 (Complement of a Language):
   • 定义: 给定一个语言 $L$（它是 $\Sigma^*$ 的一个子集），它的补集 $\bar{L}$ 是所有“不在” $L$ 里的字符串组成的集合。
   • 前提: 补集是相对于全集 $\Sigma^*$ 而言的。
   • 集合论表示: $\bar{L} = \Sigma^* \backslash L$。
   • 例子分析:
   • $\bar{\varnothing}=\Sigma^{*}$: 空语言的补集是全语言。因为没有任何字符串在空语言里，所以所有字符串都在它的补集里。
   • $\overline{\Sigma^{*}}=\varnothing$: 全语言的补集是空语言。
   • 对于 $A = \{w \in \{0,1\}^* \mid w \text{ contains a 1}\}$，它的补集 $\bar{A}$ 是所有“不包含任何 '1'”的二进制字符串。这些字符串只能由 '0' 组成，包括空字符串 $\varepsilon$。所以 $\bar{A} = \{0^n \mid n \ge 0\} = \{\varepsilon, 0, 00, 000, \ldots\}$。
   • 对于 $G_C$ (有环图的编码)，它的补集 $\overline{G_C}$ 包含两种字符串：一种是无效的图编码（比如格式错误的字符串），另一种是无环图的有效编码。
   • 对于 $M_{0110}$ (接受 "0110" 的图灵机编码)，它的补集 $\overline{M_{0110}}$ 包含两种字符串：一种是无效的TM编码，另一种是那些“不接受” "0110" 的图灵机的有效编码。（“不接受”包括拒绝和循环）。

这部分介绍了计算理论中最终极的计算模型——图灵机 (Turing Machine, TM)，并定义了它与语言之间的两种核心关系：识别 (Recognize) 和 判定 (Decide)。

1. 图灵机的三种结果:
   • 接受 (Accept): 图灵机在有限步骤内完成计算，并进入一个特殊的“接受”状态。这通常表示输入字符串“是”我们想要的。
   • 拒绝 (Reject): 图灵机在有限步骤内完成计算，并进入一个特殊的“拒绝”状态。这通常表示输入字符串“不是”我们想要的。
   • 循环 (Loop): 图灵机永不停止，一直在无限地计算下去。它既不接受也不拒绝。
   • 停机 (Halt): 如果一个图灵机对于某个输入，最终结果是接受或拒绝，而不是循环，我们就说它停机了。
2. 识别器 (Recognizer):
   • 定义: 一个图灵机 M 如果能识别一个语言 L，意味着：
   • 对于任何在语言 L 中的字符串 w ($w \in L$)，M 最终一定会接受 w。
   • 对于任何不在语言 L 中的字符串 w ($w \notin L$)，M 永不接受 w。这里“永不接受”包含了两种可能：M 拒绝 w，或者 M 在 w 上循环。
   • 非对称性: 识别器对“是”的回答是明确的（一定会接受并停机），但对“否”的回答可能是不确定的（可能拒绝，也可能永远没有回音）。
   • 识别的语言: 对于一个图灵机 M，它所识别的语言被记为 $L(M)$，这个集合包含了所有能被 M 接受的字符串。
3. 判定器 (Decider):
   • 定义: 一个图灵机 M 如果能判定一个语言 L，意味着：
   • 对于任何在语言 L 中的字符串 w ($w \in L$)，M 最终一定会接受 w。
   • 对于任何不在语言 L 中的字符串 w ($w \notin L$)，M 最终一定会拒绝 w。
   • 对称性/确定性: 判定器对于任何输入，无论是“是”还是“否”，都必须在有限时间内给出明确的答复（接受或拒绝）。它从不循环。
   • 与识别器的关系:
   • 所有的判定器都是识别器。
   • 一个判定器就是一个“保证停机”的识别器。

这部分将图灵机的能力从“判断（是/否）”扩展到了“计算/转换”。

1. 什么是函数？
   • 在数学上，函数 $f: A \rightarrow B$ 是一个规则，它为定义域 A 中的每一个输入 x，都指定了值域 B 中唯一的一个输出 y，记为 $f(x)=y$。
   • 在这里，我们关注的函数是字符串到字符串的函数，即 $f: \Sigma^* \rightarrow \Sigma^*$。输入是一个字符串，输出也是一个字符串。
2. 什么是可计算函数 (Computable Function)？
   • 一个函数 f 是可计算的，如果我们可以设计一台图灵机 M 来“实现”这个函数。
   • “实现”的含义是：
   • 将输入字符串 x 写在图灵机的初始磁带上。
   • 启动图灵机 M。
   • M 最终必须停机。
   • 当 M 停机时，磁带上留下的内容不多不少，正好是字符串 $f(x)$。
3. 输入-输出图灵机:
   • 这是一个技术细节。标准的图灵机有接受/拒绝状态，用于判定语言。
   • 用于计算函数的图灵机通常没有接受/拒绝状态，只有一个停机状态 (Halt state)。它的目的不是说是或否，而是产出结果。
   • 在实践中，我们可以用标准图灵机来模拟它：比如约定，图灵机进入接受状态就意味着计算完成，此时磁带上的内容就是结果。
4. 与判定器的关系:
   • 判定一个语言 L，可以看作是计算一个特殊的特征函数 (characteristic function) $\chi_L$:
   • $\chi_L(w) = \text{"1"}$ 如果 $w \in L$
   • $\chi_L(w) = \text{"0"}$ 如果 $w \notin L$
   • 如果一个语言 L 是可判定的，那么它的特征函数 $\chi_L$ 就是一个可计算函数。我们可以构造一个图灵机，输入 w，如果判定结果是接受，就在磁带上擦掉所有内容写入 "1" 并停机；如果是拒绝，就写入 "0" 并停机。

这部分引入了一个更高层次的抽象概念：语言的集合 (Set of Languages)。这在讨论语言的性质和对语言进行分类时非常关键。

1. 从“字符串的集合”到“语言的集合”:
   • 我们已经知道，一个语言是字符串的集合。
   • 现在，我们可以把语言本身看作一个对象，然后把多个这样的对象（语言）放在一个更大的集合里，这个更大的集合就是“语言的集合”。
2. 例子分析:
   • $\{A\}$: 这是一个最简单的语言集合，它里面只有一个元素，这个元素就是语言 A。
   • $\{L \mid L \subseteq\{0,1\}\}$:
   • 这里的字母表是 $\Sigma=\{0,1\}$ 的一个子集，我们假设是 $\{0,1\}$ 本身。不，原文是 $L \subseteq \{0,1\}$。这意味着语言 L 中的字符串只能是 "0" 或 "1"。哦，我理解错了。$\{0,1\}$ 不是字母表，而是一个包含两个字符串 "0" 和 "1" 的语言。
   • 让我们重新分析：L 是 { "0", "1" } 这个语言的子集。
   • 一个集合的子集有哪些？这就要用到幂集的概念。
   • { "0", "1" } 的幂集是:
   • $\mathcal{P}(\{ \text{"0"}, \text{"1"} \}) = \{\varnothing, \{\text{"0"}\}, \{\text{"1"}\}, \{\text{"0"}, \text{"1"}\}\}$
   • 这四个集合本身都是语言。所以，这个语言集合就是 {\varnothing, {"0"}, {"1"}, {"0", "1"}}。它是一个包含四个语言的集合。
   • $\{L \mid L \subseteq \Sigma^* \text{ and } L \text{ is recognizable}\}$:
   • 这是一个非常重要的语言集合，它代表了所有图灵可识别语言的集合，通常记作 RE。
   • 它的元素是语言，筛选条件是“这个语言必须是可识别的”。
   • 类似的，我们有所有正则语言的集合，所有可判定语言的集合（记作 R）。
   • P 类 (Class P): $\{L \mid L \text{ can be decided in polynomial time}\}$
   • 这是复杂性理论中的一个核心概念。它是一个语言集合。
   • 它的元素是语言，筛选条件是“这个语言不仅是可判定的，而且存在一个判定器（图灵机），它能在多项式时间内完成判定”。
   • NP 类 (Class NP): $\{L \mid L \text{ can be verified in polynomial time}\}$
   • 这是另一个核心的复杂性类。它也是一个语言集合。
   • 筛选条件是“对于这个语言中的任何字符串，我们都可以在多项式时间内验证它的一个‘证据’（证书）”。
3. 棘手的例子分析:
   • 区分类型: 关键在于搞清楚集合里的元素是什么。
   • 字符串集合 (语言): 元素是字符串。例如 $L = \{\text{"a"}, \text{"b"}\}$。
   • 语言集合: 元素是语言。例如 $C = \{L_1, L_2\}$，其中 $L_1=\{\text{"a"}\}, L_2=\{\text{"b"}\}$。
   • $\{\varnothing\}$: 这是一个语言集合。它里面有一个元素，这个元素是空语言 $\varnothing$。它不是空的！
   • $\varnothing$: 这是空集。如果把它看作语言集合，它是一个不包含任何语言的集合。如果把它看作语言，它是一个不包含任何字符串的集合。上下文很重要。
   • $\{L \mid L \subseteq \Sigma^*\}$: 这是“所有语言的集合”，也就是全语言 $\Sigma^*$ 的幂集 $\mathcal{P}(\Sigma^*)$。这是一个极其巨大的集合。
   • $\{\Sigma^*\}$: 这是一个语言集合。它里面只有一个元素，这个元素是全语言 $\Sigma^*$。

这部分引入了衡量集合大小的概念——基数 (Cardinality)，并给出了比较两个集合大小的严格数学方法，特别是对于无限集合。

1. 基数是什么？
   • 基数就是集合中元素的数量。
   • 符号: 一个集合 S 的基数记作 $|S|$。
   • 对于有限集合: 这很简单，就是数一下有多少个元素。例如，如果 $S = \{a, b, c\}$，那么 $|S| = 3$。
2. 无限集合的基数:
   • 我们不能像数数一样去数无限集合的元素。那么，如何比较两个无限集合的大小呢？比如，整数多还是自然数多？
   • 核心思想: 德国数学家康托 (Cantor) 提出了一个天才的想法：如果两个集合的元素可以建立一个“一一对应”的关系，那么我们就说它们一样大。
   • 这个“一一对应”关系，在数学上就叫做双射 (Bijection)。
3. 双射 (Bijection):
   • 一个从集合 S 到集合 T 的函数 $f: S \rightarrow T$ 是一个双射，如果它同时满足两个条件：
   • 单射 (Injection): 不会“多对一”。即如果 $x_1 \neq x_2$，那么一定有 $f(x_1) \neq f(x_2)$。每个输入都对应一个独一无二的输出。
   • 满射 (Surjection): 不会“漏掉”。即对于集合 T 中的任何一个元素 y，我们总能在 S 中找到至少一个元素 x，使得 $f(x) = y$。
   • 双射的直观理解: 就像在舞会上，如果男士（集合 S）和女士（集合 T）能够正好配成一对对，不多不少，那么男士和女士的数量就是一样多的。函数 f 就是这个配对的规则。
   • 定义总结: 如果能在集合 S 和 T 之间找到一个双射函数，我们就定义它们具有相同的基数，记为 $|S| = |T|$。

这部分在上一节的基础上，给出了比较基数大小（≤）的定义，并引入了计算理论中最重要的基数分类：可数 (Countable) 与 不可数 (Uncountable)。

1. 比较基数:
   • 相等 ($|S|=|T|$): 存在从 S 到 T 的双射 (bijection)。
   • 小于等于 ($|S| \le |T|$): 存在从 S 到 T 的单射 (injection)。
   • 单射意味着“不重复”，即 S 中的每个元素都对应 T 中一个独一无二的元素。这就像把 S 中的所有元素都“塞进” T 中，并且没有两个 S 的元素被塞到同一个 T 的位置。这直观地说明了 T 的“容量”至少和 S 一样大。
   • 重要事实 ($S \subseteq T \implies |S| \le |T|$): 如果 S 是 T 的子集，那么 S 的大小自然不会超过 T 的大小。我们可以构造一个最简单的单射函数 $f(x) = x$。对于 S 中的每个 x，它本身也在 T 中，所以这个函数是合法的单射。
2. 可数集 (Countable Set):
   • 定义: 一个集合 S 是可数的，如果满足以下两个条件之一：
3. S 是有限集。
4. S 的基数与自然数集 $\mathbb{N} = \{0, 1, 2, 3, \ldots\}$ 的基数相等，即 $|S| = |\mathbb{N}|$。这种情况也称为可数无限 (countably infinite)。
   • 直观理解: 一个集合是可数的，意味着我们可以给它的所有元素“编号”，或者说，可以把它们排成一个（可能是无限的）列表，像 $e_0, e_1, e_2, \ldots$ 这样，不重不漏。这个列表的下标 (0, 1, 2, ...) 就来自自然数集 $\mathbb{N}$。这个列表过程本身就构造了一个从 $\mathbb{N}$ 到该集合的双射。
5. 不可数集 (Uncountable Set):
   • 定义: 如果一个集合不是可数的，那它就是不可数的。
   • 直观理解: 不可数集是如此“巨大”，以至于我们无法用自然数去给它的所有元素编号。你永远无法列出一个完整的列表来包含它的所有元素，无论你的列表有多长，总会有元素被遗漏。
6. 可数性的另一个视角:
   • 有限描述: 一个集合是可数的，等价于它的每个元素都可以用一个有限长度的字符串来描述。既然每个元素都能表示成一个字符串，而所有字符串的集合 $\Sigma^*$ 本身是可数的（见下文），那么这个集合自然也是可数的。
   • $\Sigma^*$ 是可数的: 我们可以按长度，再按字典序，将 $\Sigma^*$ 中的所有字符串排列成一个列表。例如，对于 $\Sigma=\{0, 1\}$:
   • 长度 0: $\varepsilon$
   • 长度 1: 0, 1
   • 长度 2: 00, 01, 10, 11
   • 长度 3: ...
   • 这个列表 $w_0=\varepsilon, w_1=0, w_2=1, w_3=00, \ldots$ 不重不漏地包含了所有二进制字符串，所以 $\Sigma^*$ 是可数的。

这个例子通过一个具体的构造性证明，展示了如何应用基数理论来证明两个无限集合的大小相等。这里要证明的是整数集 $\mathbb{Z}$ 和非负整数集 $\mathbb{Z}_{\ge 0}$（也就是自然数集 $\mathbb{N}$）是“一样大”的。

1. 证明目标: 证明 $|\mathbb{Z}| = |\mathbb{Z}_{\ge 0}|$。
2. 证明策略: 根据上一节的定义，我们可以选择两种主要策略：
   • 策略 A (双射): 构造一个从 $\mathbb{Z}$ 到 $\mathbb{Z}_{\ge 0}$ 的双射函数 f，并证明其单射性和满射性。
   • 策略 B (双向单射): 分别构造两个方向的单射函数：一个 $f_1: \mathbb{Z} \to \mathbb{Z}_{\ge 0}$ 和另一个 $f_2: \mathbb{Z}_{\ge 0} \to \mathbb{Z}$。根据 Cantor-Bernstein-Schroeder 定理，这同样能证明它们基数相等。
   • 这里的文本采用的是策略 B，虽然它构造的那个函数 f 实际上就是一个双射。
3. 构造函数:
   • 思路: 如何把所有整数（有正有负）不重不漏地映射到所有非负整数上？一个常见的想法是“交错”映射：把非负整数 (0, 1, 2, ...) 映射到偶数 (0, 2, 4, ...)，把负整数 (-1, -2, -3, ...) 映射到奇数 (1, 3, 5, ...)。
   • 函数定义:
   • 当输入 x 是非负整数时（0, 1, 2, ...），输出是 $2x$（0, 2, 4, ...），即所有的偶数。
   • 当输入 x 是负整数时（-1, -2, -3, ...），输出是 $1-2x$（3, 5, 7, ...）。咦，这里好像和我的想法有点出入，让我们代入算一下：
   • $f(-1) = 1 - 2(-1) = 3$
   • $f(-2) = 1 - 2(-2) = 5$
   • $f(-3) = 1 - 2(-3) = 7$
   • 它把负整数映射到了从3开始的奇数。那么数字1去哪了？让我们检查一下原文，原文是 $1-2x$。啊，如果 x < 0，-2x 是正偶数，1-2x 才是奇数。
   • 让我们换个更常见的函数来理解这个思路:
   • $g(0)=0, g(1)=2, g(2)=4, \ldots$ (映射到偶数)
   • $g(-1)=1, g(-2)=3, g(-3)=5, \ldots$ (映射到奇数)
   • 这个 g(x) 是一个完美的双射。原文中的 f(x) 似乎有点问题，因为它没有映射到1。让我们假设原文的 $1-2x$ 应该是 $-2x-1$ 或者类似能覆盖所有奇数的函数。不过，我们还是按照原文的逻辑来分析它的证明过程。
4. 证明过程 (按原文):
   • 第一步：证明 $|\mathbb{Z}| \le |\mathbb{Z}_{\ge 0}|$
   • 这需要证明存在一个单射 $f: \mathbb{Z} \to \mathbb{Z}_{\ge 0}$。
   • 原文声称它构造的 $f(x)$ 是单射的。
   • 证明单射性: 需要证明如果 $f(x) = f(y)$，那么必然 $x=y$。
   • 情况1: 如果 $f(x) = f(y)$ 是一个偶数，那么 x 和 y 必定都是 $\ge 0$ 的（因为只有上半部分规则产生偶数）。所以 $2x = 2y$，推出 $x=y$。
   • 情况2: 如果 $f(x) = f(y)$ 是一个奇数，那么 x 和 y 必定都是 $<0$ 的。所以 $1-2x = 1-2y$，推出 $-2x = -2y$，再次推出 $x=y$。
   • 情况3: 不可能一个偶数等于一个奇数。
   • 综上所述，只要 $f(x)=f(y)$，就一定有 $x=y$。所以 f 是单射的。
   • 根据定义，这证明了 $|\mathbb{Z}| \le |\mathbb{Z}_{\ge 0}|$。

• 第二步：证明 $|\mathbb{Z}| \ge |\mathbb{Z}_{\ge 0}|$
• 这需要证明存在一个单射 $g: \mathbb{Z}_{\ge 0} \to \mathbb{Z}$。
• 原文用了一个更简单的事实：$\mathbb{Z}_{\ge 0}$ 是 $\mathbb{Z}$ 的一个子集。
• 根据上一节的结论 "$S \subseteq T \implies |S| \le |T|$"，我们直接可以得到 $|\mathbb{Z}_{\ge 0}| \le |\mathbb{Z}|$，这等价于 $|\mathbb{Z}| \ge |\mathbb{Z}_{\ge 0}|$。

• 第三步：结论
• 既然我们证明了 $|\mathbb{Z}| \le |\mathbb{Z}_{\ge 0}|$ 和 $|\mathbb{Z}| \ge |\mathbb{Z}_{\ge 0}|$，根据 Cantor-Bernstein-Schroeder 定理，我们可以得出结论：$|\mathbb{Z}| = |\mathbb{Z}_{\ge 0}|$。

这部分内容和配图是为了梳理和澄清之前引入的各种关于集合大小的术语之间的逻辑关系。

1. 术语梳理:
   • 有限 (Finite): 元素个数是有限的。例如 $|\{a,b\}|=2$。
   • 无限 (Infinite): 不是有限的。
   • 可数无限 (Countably Infinite): 与自然数集 $\mathbb{N}$ 等大的无限集合。例如 $|\mathbb{Z}|=|\mathbb{N}|$。
   • 不可数无限 (Uncountably Infinite): 比自然数集 $\mathbb{N}$ 更大的无限集合。例如 $|\mathbb{R}| > |\mathbb{N}|$。也简称为不可数 (Uncountable)。
   • 可数 (Countable): 这是一个更宽泛的概念，它包括了所有有限集和所有可数无限集。
2. 图 1 解读:
   • 最外层的椭圆代表“所有集合”。
   • “所有集合”被一条竖线分成了两部分：左边的“有限集”和右边的“无限集”。这两部分互不相交，且并集是所有集合。
   • 在右边的“无限集”内部，又被分成了两部分：左边的“可数无限集”和右边的“不可数无限集”。
   • 图中用一个更大的椭圆框住了“有限集”和“可数无限集”，并标记为“可数集”。这清晰地表明了“可数 = 有限 或 可数无限”。
   • 图中“不可数无限集”也被标记为“不可数集”，说明“不可数”和“不可数无限”是同义词，因为不存在“有限的不可数集”。
3. 逻辑关系总结:
   • 集合 = 可数集 $\cup$ 不可数集
   • 可数集 = 有限集 $\cup$ 可数无限集
   • 无限集 = 可数无限集 $\cup$ 不可数集
   • 不可数集 = 不可数无限集

这部分是基数理论在计算理论中的第一个高潮应用。它使用康托对角线法 (Cantor's Diagonalization Argument) 的结论，通过简单的集合大小比较，直接证明了不可解问题的存在性。

1. 康托对角线法:
   • 这是一个著名的数学证明方法，由康托提出。
   • 其核心结论是：对于任何集合 X，其幂集 $\mathcal{P}(X)$ 的基数严格大于 X 本身的基数。即 $|X| < |\mathcal{P}(X)|$。
   • 应用到自然数集 $\mathbb{N}$ 上，我们得到 $|\mathbb{N}| < |\mathcal{P}(\mathbb{N})|$。
   • 因为 $|\mathbb{N}|$ 是可数无限的“标杆”，所以这个不等式意味着 $\mathcal{P}(\mathbb{N})$ 是不可数的。
   • $|S| < |T|$ 意味着不存在从 S 到 T 的满射 (surjection)。也就是说，你无法用 S 中的元素去“覆盖” T 中的所有元素，T 总是会有剩下的。
2. 应用于可识别性:
   • 核心论证步骤:
3. 确定“解决方案”的集合有多大。
4. 确定“问题”的集合有多大。
5. 比较两者的大小。
   • 步骤 1：解决方案有多大？
   • “解决方案”就是图灵机。我们要确定所有图灵机的集合 $\mathbb{M}$ 的基数。
   • 每个图灵机 M 都可以被编码为一个有限字符串 $\langle M \rangle$。
   • 这个编码过程 $f(M) = \langle M \rangle$ 是一个单射（不同的图灵机有不同的编码）。
   • 所以， $|\mathbb{M}| \le |\Sigma^*|$ (所有字符串的集合)。
   • 我们已经知道 $\Sigma^*$ 是可数的。
   • 因此，图灵机的集合 $\mathbb{M}$ 也是可数的。
   • 步骤 2：问题有多大？
   • “问题”就是语言。我们要确定所有语言的集合的基数。
   • 所有语言的集合，根据定义，就是 $\mathcal{P}(\Sigma^*)$ (所有字符串集合的子集的集合)。
   • 因为 $\Sigma^*$ 是可数无限的（等价于 $\mathbb{N}$），根据康托定理，它的幂集 $\mathcal{P}(\Sigma^*)$ 是不可数的。
   • 步骤 3：比较大小
   • 解决方案的集合 $\mathbb{M}$ 是可数的。
   • 问题的集合 $\mathcal{P}(\Sigma^*)$ 是不可数的。
   • 可数集严格小于不可数集。
6. 最终结论:
   • 我们有一个从图灵机集合 $\mathbb{M}$ 到语言集合 $\mathcal{P}(\Sigma^*)$ 的映射 $L$，它为每个图灵机 M 指定它所识别的语言 $L(M)$。
   • 由于定义域 $\mathbb{M}$ 是可数的，而值域 $\mathcal{P}(\Sigma^*)$ 是不可数的，这个映射不可能是满射。
   • “不可能是满射”意味着，在值域（所有语言的集合）中，必然存在一些语言，是没有任何图灵机（来自定义域）能够映射到它的。
   • 换句话说：存在一些语言，是任何图灵机都无法识别的。这些就是不可识别语言。
7. 基数总结表:
   • $\Sigma$ (字母表): 有限。
   • $\Sigma^*$ (所有字符串): 可数无限。
   • $L \subseteq \Sigma^*$ (任何一个语言): 最多是可数无限的（因为它是可数集 $\Sigma^*$ 的子集），也可能是有限的。所以是可数的。
   • $\mathbb{M}$ (所有图灵机): 可数无限。
   • $\mathcal{P}(\Sigma^*)$ (所有语言): 不可数。 (原文 P(5*) 疑似笔误，应为 $\mathcal{P}(\Sigma^*)$)

这部分给出了图灵机 (Turing Machine, TM) 的严格数学定义。图灵机是一个抽象的计算模型，旨在模拟任何计算机算法能做的事情。这个 7-元组定义了图灵机的所有组成部分及其规则。

1. $Q$ (状态集):
   • 定义: 一个有限的状态集合。
   • 作用: 状态代表了图灵机的“内存”。在任何时刻，图灵机都处于这些状态之一。例如，一个状态可能表示“正在寻找一个1”，另一个状态可能表示“已经找到了一个1，正在返回磁带开头”。因为集合是有限的，所以图灵机的“内部程序”是有限的。
2. $\Sigma$ (输入字母表):
   • 定义: 用于书写初始输入字符串的符号集合。
   • 约束: 它不能包含空白符 $\sqcup$。
   • 作用: 定义了图灵机要解决的问题所使用的字符集。例如，对于二进制字符串问题，$\Sigma=\{0,1\}$。
3. $\Gamma$ (磁带字母表):
   • 定义: 图灵机可以在其磁带上读写的符号集合。
   • 约束:
   • 它必须包含空白符 $\sqcup$。空白符代表磁带上未使用的格子。
   • 它必须包含整个输入字母表 ($\Sigma \subset \Gamma$)。这意味着图灵机至少能读懂输入，并且它还可以在磁带上写入一些额外的“草稿”符号。
   • 作用: 提供了图灵机的工作空间和工作符号。例如，为了标记某个位置，图灵机可以在磁带上写一个不在 $\Sigma$ 中的特殊符号，如 'X'。
4. $\delta$ (转移函数):
   • 定义: 这是图灵机的“程序”或“大脑”。它是一个函数，告诉图灵机在特定情况下该做什么。
   • 输入: $\delta$ 的输入是一个二元组 (当前状态, 当前磁带头下的符号)。
   • 输出: $\delta$ 的输出是一个三元组 (下一个状态, 要写入磁带的符号, 磁带头移动方向)。
   • 格式: $\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{\mathrm{L}, \mathrm{R}\}$
   • $Q \times \Gamma$: 当前状态和当前磁带符号。
   • $\rightarrow$: "映射到"。
   • $Q \times \Gamma \times \{\mathrm{L}, \mathrm{R}\}$: 新状态，要写入的新符号，以及移动方向（L代表向左，R代表向右）。
   • 例子: $\delta(q_1, 'a') = (q_2, 'b', R)$ 的意思是：“如果机器当前在状态 $q_1$，并且磁带头下方的符号是 'a'，那么：1. 将状态切换到 $q_2$；2. 在当前位置的磁带上写入 'b'；3. 将磁带头向右移动一格。”
5. $q_0$ (开始状态):
   • 定义: $Q$ 中的一个特殊状态。
   • 作用: 图灵机的计算总是从这个状态开始。
6. $q_{\text{accept}}$ (接受状态):
   • 定义: $Q$ 中的一个特殊状态。
   • 作用: 一旦图灵机进入这个状态，计算立即停止，并宣布接受输入。
7. $q_{\text{reject}}$ (拒绝状态):
   • 定义: $Q$ 中的一个特殊状态。
   • 约束: 它必须与接受状态不同 ($q_{\text{accept}} \ne q_{\text{reject}}$)。
   • 作用: 一旦图灵机进入这个状态，计算立即停止，并宣布拒绝输入。

这部分解释了为什么我们在描述图灵机时，可以并且应该从繁琐的形式化定义转向更易于理解的高级描述，并列举了哪些操作被认为是“合法的”高级操作。

1. 图灵机 = 算法:
   • 丘奇-图灵论题 (Church-Turing Thesis): 这是一个非常重要的哲学论点，而不是一个可以被证明的数学定理。它声称，任何我们直觉上认为的“可计算的”、“机械的”过程或“算法”，都可以被一台图灵机所模拟。
   • 实践意义: 这意味着，如果我们能用任何一种编程语言（如 Python, C++, Java）写出一个算法，或者用伪代码清晰地描述一个算法步骤，那么我们就有信心相信，存在一台等价的图灵机。这给了我们一个巨大的解放：我们不需要再纠结于具体的状态和转移函数，而是可以直接用类似编程的语言来描述图灵机的行为。
2. 高级描述 (High-Level Description):
   • 定义: 使用接近自然语言或伪代码的方式来描述图灵机的算法。
   • 目标: 关注算法的逻辑，而不是底层的实现细节。
   • 分层:
   • 形式化描述: 完整的 7-元组。
   • 实现级别描述: 描述磁带头如何移动、如何读写磁带，但不具体到状态。
   • 高级描述: 完全忽略磁带操作，直接描述算法逻辑，如同编写程序注释。
3. 允许的高级操作:
   • 这里的列表给出了一些可以被认为是“基本构建块”的操作，我们相信这些操作都可以被一个（可能很复杂的）图灵机子程序实现。
   • 变量和数据结构: 图灵机可以通过在磁带的特定区域存储和更新信息来模拟变量。列表和集合可以通过在磁带上用特殊符号分隔元素来表示。
   • 控制流: if-then-else 可以通过不同的状态路径来实现。循环可以通过跳转回之前的状态来实现。
   • 字符串和算术: 我们已经知道可以构造图灵机来做字符串复制、反转，以及整数的加减乘除。
   • 图操作: 给定一个图的编码（例如，邻接矩阵或邻接表的字符串形式），图灵机可以扫描这个字符串来模拟图算法，比如查找邻居或标记顶点（通过在编码字符串上做标记）。
   • 图灵机操作 (元操作): 这是最高级的操作。一台图灵机 U（通用图灵机）可以接收另一台图灵机 M 的编码 $\langle M \rangle$ 和一个输入 w，然后模拟 M 在 w 上的运行。这使得“调用”一个图灵机作为子程序成为可能。
4. 需要注意的微妙之处:
   • 停机问题: 当你的高级描述中包含“运行图灵机 M 在输入 w 上”这样的步骤时，你必须意识到这个步骤可能永远不会结束（如果 M 在 w 上循环）。
   • 构造中的处理: 如果你的算法依赖于一个子程序的返回结果，而这个子程序（一个被模拟的图灵机）可能会循环，那么你的整个算法也可能会卡住。因此，在设计归约或其他涉及模拟的算法时，必须明确如何处理这种潜在的无限循环。

这个例子通过一个非常经典的构造，深刻地揭示了识别器和判定器之间的关键区别，以及在构造图灵机时必须如何小心处理停机问题。

1. 构造的目标:
   • 给定一个图灵机 M，我们想构造一个新的图灵机 N，它的行为与 M “相反”。
   • “相反”的直接想法是：M 接受的，N 就拒绝；M 拒绝的，N 就接受。
2. 构造的算法 (高级描述):
   • N 的算法很简单：
3. 在输入 w 上，先完整地模拟 M 在 w 上的运行。
4. 等待 M 给出结果。
5. 如果 M 的结果是“接受”，N 就输出“拒绝”。
6. 如果 M 的结果是“拒绝”，N 就输出“接受”。
7. 分析构造 (分两种情况):

• 情况 1: M 是一个判定器 (Decider)
• 前提: 判定器对任何输入都保证停机（接受或拒绝）。
• 分析:
• 当 N 模拟 M 时，步骤 1 必然会在有限时间内结束。
• 如果 $w \in L(M)$，M 接受 w，于是 N 进入步骤 2，拒绝 w。
• 如果 $w \notin L(M)$，M 拒绝 w，于是 N 进入步骤 3，接受 w。
• 结论: N 接受所有不在 $L(M)$ 中的字符串，并拒绝所有在 $L(M)$ 中的字符串。N 也对所有输入都停机。因此，N 判定了 $L(M)$ 的补集 $\overline{L(M)}$。
• 重要推论: 如果一个语言 L 是可判定的，那么它的补集 $\bar{L}$ 也一定是可判定的。(可判定语言类对补集运算是封闭的)。

• 情况 2: M 只是一个识别器 (Recognizer)
• 前提: 识别器对于不属于其语言的输入，可能会拒绝，也可能会循环。
• 分析:
• 如果 $w \in L(M)$，M 接受 w，N 的步骤 1 会结束，然后 N 拒绝 w。这部分没问题。
• 如果 $w \notin L(M)$，现在有两种可能：
• (a) M 拒绝 w。那么 N 的步骤 1 结束，N 接受 w。
• (b) M 在 w 上循环。那么 N 在模拟 M 的步骤 1 中，也会跟着永远循环下去，永远到不了步骤 2 或 3。
• 最坏情况: 假设 M 是一个只识别 L 的图灵机，它对于所有 $w \notin L$ 的情况都循环。
• 在这种情况下，N 的行为变成：
• 对于 $w \in L$, N 拒绝 w。
• 对于 $w \notin L$, N 在 w 上循环。
• 结论: 这个 N 接受了哪些字符串？答案是：一个都没有。所以 $L(N) = \varnothing$。它识别了空语言。它并没有像我们期望的那样识别 $\bar{L}$。

1. 如何处理循环:
   • 这个例子说明，简单的“模拟然后翻转结果”的策略在面对可能循环的图灵机时会失效。
   • 文中提到了更高级的技术来处理这种情况，例如：
   • 交错运行 (Dovetailing): 如果要同时模拟两个可能循环的计算（比如 M 在 w 上和 M' 在 w' 上），你可以模拟 M 的第1步，然后模拟 M' 的第1步，然后 M 的第2步，M' 的第2步... 这样交替进行，确保如果其中任何一个能停机，你最终都能发现。
   • 这在证明“可识别语言对并集和交集封闭”时很有用。

这部分将通过一个非常简单的语言作为例子，来具体展示前面提到的三种不同层次的图灵机描述方法：形式化描述、实现级别描述和高级描述。

1. 目标语言:
   • $L = \{w \in \{0,1\}^* \mid w \text{ contains no 1's}\}$
   • 字母表: $\Sigma = \{0, 1\}$
   • 语言描述: 这个语言包含所有仅由 '0' 组成的二进制字符串，以及空字符串 $\varepsilon$。
   • 等价描述: $L = \{0^n \mid n \ge 0\}$。
   • 示例:
   • 属于 L 的字符串: $\varepsilon$, 0, 00, 0000
   • 不属于 L 的字符串: 1, 010, 11
2. 目标任务:
   • 为这个语言 L 设计一个图灵机。因为这个语言非常简单，我们可以轻易地设计出一个判定器（即一个对所有输入都停机的图灵机），这个判定器自然也是一个识别器。
   • 下面的内容将用三种不同的“画风”来描述同一个判定器。

这是描述图灵机最底层、最精确的方式。

1. 7-元组定义:
   • $Q = \{q_0, q_{\text{accept}}, q_{\text{reject}}\}$: 状态集。这里只需要一个工作状态 $q_0$ 加上两个终止状态。
   • $\Sigma = \{0, 1\}$: 输入字母表。
   • $\Gamma = \{0, 1, \sqcup\}$: 磁带字母表。这里我们不需要额外的草稿符号。
   • $\delta$: 转移函数，是核心。下面详细解释。
   • $q_0$: 开始状态。
   • $q_{\text{accept}}$: 接受状态。
   • $q_{\text{reject}}$: 拒绝状态。
2. 转移函数 $\delta$ 详解:
   • 算法思路: 从左到右扫描输入字符串。只要没遇到 '1'，就继续前进。如果遇到了 '1'，立刻拒绝。如果一路平安走到了字符串的末尾（即读到了空白符 $\sqcup$），就说明没有 '1'，于是接受。
   • $\delta(q_0, 0) = (q_0, 0, R)$:
   • 情况: 在开始状态 $q_0$ 读到了一个 '0'。
   • 动作: '0' 是允许的。保持在 $q_0$ 状态，把 '0' 写回磁带（实际上没变），然后磁带头向右 (R) 移动，继续检查下一个符号。
   • $\delta(q_0, 1) = (q_{\text{reject}}, 1, R)$:
   • 情况: 在开始状态 $q_0$ 读到了一个 '1'。
   • 动作: '1' 是不允许的。立刻跳转到拒绝状态 $q_{\text{reject}}$，计算停止。写入什么和向哪移动已经不重要了，因为机器已经停机。
   • $\delta(q_0, \sqcup) = (q_{\text{accept}}, \sqcup, L)$:
   • 情况: 在开始状态 $q_0$ 读到了空白符 $\sqcup$。
   • 动作: 这意味着我们已经成功扫描完了整个字符串而没有遇到任何 '1'。立刻跳转到接受状态 $q_{\text{accept}}$，计算停止。向左 (L) 移动是可选的，没有实际影响。
3. 状态图 (State Diagram) 解读:
   • 节点: 图中的圆圈代表状态 ($q_0, q_{\text{accept}}, q_{\text{reject}}$)。
   • 箭头: 代表状态之间的转移。
   • 箭头上的标签: 格式是 读入符号 -> 写入符号, 移动方向。
   • 从 $q_0$ 指向自己的箭头，标签是 $0 \to 0, R$。这对应了 $\delta(q_0, 0) = (q_0, 0, R)$。
   • 从 $q_0$ 指向 $q_{\text{reject}}$ 的箭头，标签是 $1 \to 1, R$。这对应了 $\delta(q_0, 1) = (q_{\text{reject}}, 1, R)$。
   • 从 $q_0$ 指向 $q_{\text{accept}}$ 的箭头，标签是 $\sqcup \to \sqcup, L$。这对应了 $\delta(q_0, \sqcup) = (q_{\text{accept}}, \sqcup, L)$。
   • 状态图是形式化描述的一种图形化表示，对于简单的图灵机来说更直观。

这是描述图灵机的中间层次，它关注磁带和磁带头的操作，但不涉及具体的状态名。

• “检查磁带是否为空，如果是则接受。”:
• 这对应了形式化描述中，机器一启动，如果读头下是空白符 $\sqcup$（意味着输入是空字符串 $\varepsilon$），就直接进入接受状态的情况。即 $\delta(q_0, \sqcup) = (q_{\text{accept}}, \dots)$。

• “重复以下操作：”:
• 这描述了一个循环，对应形式化描述中从 $q_0$ 状态到 $q_0$ 状态的自循环。

• “检查当前字符是否为 1，如果是则拒绝。”:
• 这对应了转移 $\delta(q_0, 1) = (q_{\text{reject}}, \dots)$。在循环的任何一步，只要碰到 '1'，就跳出循环并拒绝。

• “检查当前字符是否为空格，如果是则接受。”:
• 这对应了当字符串不为空时，在扫描完所有非空白字符后遇到空白符的情况。这也是循环的终止条件，并导向接受。

• “否则将磁头向右移动。”:
• “否则”在这里意味着当前字符既不是 '1' 也不是空白符。在我们的字母表 $\{0,1\}$ 中，那就只剩下 '0' 了。
• 这对应了转移 $\delta(q_0, 0) = (q_0, \dots, R)$。遇到 '0'，就继续循环（保持在 $q_0$），并将读头右移以检查下一个字符。

这是描述图灵机最高、最抽象的层次。它完全不关心图灵机的内部工作细节（状态、磁带），只陈述它要解决的算法问题和最终结果。

• “在输入 $x \in \{0,1\}^*$ 上”:
• 声明了图灵机 M 的输入类型。

• “检查 $x$ 是否包含任何 1”:
• 这是一个高度抽象的指令。我们相信（基于丘奇-图灵论题）这个检查过程可以被一台图灵机实现，但我们在这里不关心具体如何实现。它可能涉及一个从左到右的扫描循环，就像我们在前面两个描述中看到的那样。

• “如果是，则拒绝，否则接受”:
• 这直接说明了算法的判断逻辑和最终输出。
• “是”（包含 '1'）对应 $x \notin L$，结果是拒绝。
• “否则”（不包含 '1'）对应 $x \in L$，结果是接受。

这部分重新审视并深化了可识别性 (Recognizability) 的概念，强调了其核心特征和一些重要性质。

1. 可识别性的核心定义 (使用 DTM):
   • 一个语言 L 是可识别的 (Recognizable)，如果存在一个确定性图灵机 (DTM) M，它能做到：
   • 对于“是”的实例: 如果一个字符串 w 在 L 里 ($w \in L$)，M 必须在有限时间内停机并接受 w。
   • 对于“否”的实例: 如果一个字符串 w 不在 L 里 ($w \notin L$)，M 绝对不能接受 w。这意味着 M 要么停机并拒绝 w，要么永不停机（循环）。
   • 这个定义的关键在于其不对称性。它对“是”的回答给出了强有力的承诺（一定有答案），但对“否”的回答则没有（可能没答案）。
   • 可识别语言也被称为图灵可识别语言或递归可枚举语言 (Recursively Enumerable Language, RE)。
2. 在补集运算下不封闭:
   • 这是一个非常重要的性质。“不封闭”意味着，如果一个语言 L 是可识别的，我们不能保证它的补集 $\bar{L}$ 也一定是可识别的。
   • 经典例子: 停机问题 $A_{TM} = \{\langle M, x \rangle \mid M \text{ accepts } x\}$。
   • $A_{TM}$ 是可识别的。我们可以构造一个识别器 U（通用图灵机），它模拟 M 在 x 上的运行。如果 M 接受 x，U 就接受 $\langle M, x \rangle$。如果 M 拒绝或循环，U 也会跟着拒绝或循环。这符合识别器的定义。
   • $\overline{A_{TM}}$ (它的补集) 被证明是不可识别的。这意味着不存在任何图灵机能够识别 $\overline{A_{TM}}$。
3. 可识别性的等价定义 (使用 NTM):
   • 一个重要的定理是：一个语言能被确定性图灵机 (DTM) 识别，当且仅当它能被非确定性图灵机 (NTM) 识别。换句话说，在可识别性的层面上，非确定性没有增加额外的计算能力。
   • 用 NTM 定义可识别性: 一个语言 L 是可识别的，如果存在一个 NTM N，它能做到：
   • 对于“是”的实例: 如果 $w \in L$，那么在 N 的所有计算分支中，至少存在一个分支能够停机并接受 w。
   • 对于“否”的实例: 如果 $w \notin L$，那么 N 的所有计算分支都不能接受 w。（它们可以拒绝，也可以循环）。
   • 这个定义与 NTM 的接受机制完全一致，因此 NTM 接受的语言就是可识别语言。

这部分详细阐述了比可识别性更强的概念——可判定性 (Decidability)，并探讨了它与补集、非确定性的关系，以及使用 NTM 来构造判定器时的一个典型陷阱。

1. 可判定性的核心定义 (使用 DTM):
   • 一个语言 L 是可判定的 (Decidable)，如果存在一个确定性图灵机 (DTM) M，它对任何输入字符串 w 都保证在有限时间内停机，并给出明确的“是”或“否”的答案。
   • 如果 $w \in L$, M 接受 w。
   • 如果 $w \notin L$, M 拒绝 w。
   • 关键区别: 判定器从不循环。它总是能给出答案。
   • 可判定语言也被称为图灵可判定语言或递归语言 (Recursive Language, R)。
2. 重要的定理和性质:
   • 定理 1: $L \text{ is decidable} \iff L \text{ is recognizable and } \bar{L} \text{ is recognizable.}$
   • 直观解释 (=>): 如果 L 是可判定的，那么存在一个判定器 $M_L$。$M_L$ 本身就是一个识别器。同时，我们可以构造 $\bar{L}$ 的判定器 $M_{\bar{L}}$ (通过翻转 $M_L$ 的接受/拒绝状态)，所以 $\bar{L}$ 也是可判定的，因此也是可识别的。
   • 直观解释 (<=): 如果我们有 L 的识别器 $M_1$ 和 $\bar{L}$ 的识别器 $M_2$。为了判定一个输入 w，我们可以并行地（或交错地）同时运行 $M_1(w)$ 和 $M_2(w)$。因为 w 要么在 L 中，要么在 $\bar{L}$ 中，所以这两个识别器中必然有一个会在有限时间内停机并接受。
   • 如果 $M_1$ 先接受，我们就知道 $w \in L$，于是我们的判定器就接受 w。
   • 如果 $M_2$ 先接受，我们就知道 $w \in \bar{L}$ (即 $w \notin L$)，于是我们的判定器就拒绝 w。
   • 这个过程保证了总能停机并给出答案。
   • 在补集运算下封闭: 如果 L 是可判定的，那么 $\bar{L}$ 也是可判定的。这从上面的定理可以轻松推导出。
3. 可判定性的 NTM 定义与陷阱:
   • NTM 判定器定义: 一个 NTM N 是判定器，如果它对任何输入 w，所有计算分支都在有限时间内停机（接受或拒绝），并且：
   • 如果 $w \in L$，至少有一个分支接受。
   • 如果 $w \notin L$，所有分支都拒绝。
   • 陷阱示例: 尝试为 $A_{TM}$ 构造一个 NTM 判定器。
   • 算法思想: 非确定性地“猜”一个运行步数 k，然后模拟 M 在 x 上运行 k 步。如果 M 在这 k 步内接受了，那么 NTM 就接受。否则，这个分支就拒绝。
   • 表面上的正确性:
   • 如果 $M(x)$ 确实接受（比如在 $k_0$ 步），那么 NTM 只要“猜”对了 $k=k_0$ (或任何 $k \ge k_0$)，这个分支就会接受。
   • 如果 $M(x)$ 不接受（拒绝或循环），那么对于任何有限的 k，模拟 k 步后都不会发现它接受，所以所有这些分支都会拒绝。
   • 问题所在: “非确定性地选择 $k \ge 0$” 这一步本身就包含了无限的可能性。NTM 的一个计算分支可以是“猜 k=0”，另一个是“猜 k=1”，...，但它还有一个分支是“永远在猜测 k 的过程中”。如文中所述，这个非确定性选择可以被实现为一个循环，而这个循环本身可以永不退出。因此，这个 NTM 存在无限循环的分支，它不满足 NTM 判定器要求所有分支都停机的条件。所以这个构造失败了。
   • 经验法则: 使用 NTM 来做非确定性“猜测”时，如果猜测的对象来自一个无限集合（如此处的步数 k），要特别小心，这通常是引入无限循环的根源，因此不适用于构造判定器。如果猜测的对象来自一个有限集合（比如“非确定性地选择图中的一个顶点”），那么所有分支都必然是有限的，这种用法是安全的。

这部分是计算理论的核心技术——归约 (Reduction)。归约是用来证明新问题的不可判定性或不可识别性的主要工具。

1. 归约的直觉:
   • 归约是一种比较两个问题 A 和 B 难度关系的方法。
   • $A \le B$ 的核心意思是，我们可以利用一个解决 B 问题的“黑盒子”（子程序），来帮助我们解决 A 问题。
   • 这就好比说，“如果你能帮我把这堆苹果去核（问题B），那么我就能做出苹果派（问题A）”。这说明做苹果派的难度“小于等于”苹果去核的难度（假设其他步骤都很简单）。
   • 因此，$A \le B$ 意味着 B 至少和 A 一样难。如果 A 是一个已知的难题，那么 B 也不可能简单。
2. 两种归约的定义:
   • 图灵归约 ($A \le_T B$):
   • 这是一种非常通用的归约。它说，如果我们有一个能判定 B 的图灵机 $M_B$ (我们称之为一个神谕 (Oracle))，我们就可以构造一个能判定 A 的图灵机 $N^B$。
   • 这个 $N^B$ 在计算过程中，可以随时“调用” $M_B$ 这个黑盒子。它可以向 $M_B$ 提问：“某个字符串 y 在不在 B 里？”，并立即得到“是”或“否”的答案。$N^B$ 可以调用这个黑盒子任意多次。
   • 例子: $A_{TM} \le_T \overline{A_{TM}}$。假设有判定 $\overline{A_{TM}}$ 的神谕。要判定 $A_{TM}$ 的输入 $\langle M, w \rangle$，我们直接问神谕“$\langle M, w \rangle$ 是否在 $\overline{A_{TM}}$ 中？”。如果神谕回答“是”，我们就拒绝；如果回答“否”，我们就接受。我们只调用了一次神谕。
   • 映射归约 ($A \le_m B$):
   • 这是一种更严格、更受限的归约。
   • 它要求存在一个可计算函数 f，这个函数能把 A 问题的任何一个实例 x，转换成 B 问题的一个实例 $f(x)$。
   • 并且这个转换必须保持“是/否”答案的一致性：x 是 A 的“是”实例，当且仅当 $f(x)$ 是 B 的“是”实例。
   • 映射归约中，解决 A 的过程分为两步：
3. 用图灵机计算 $f(x)$。
4. 把 $f(x)$ 扔给解决 B 的黑盒子，B 的答案就是 A 的答案。
   • 与图灵归约的区别: 映射归约只能调用一次黑盒子，并且必须在所有计算的最后一步调用，且黑盒子的答案就是最终答案，不能再做任何后处理。而图灵归约可以在计算过程中多次调用黑盒子，并根据返回结果进行后续计算。
5. 重要的定理和推论:
   • 定理 2 (与补集的关系):
   • 图灵归约: $A \le_T B$ 和 $A \le_T \bar{B}$ 是等价的。因为如果有一个 B 的神谕，你总能通过反转其输出来得到一个 $\bar{B}$ 的神谕，反之亦然。
   • 映射归约: $A \le_m B \iff \bar{A} \le_m \bar{B}$。这是因为 $x \in A \iff f(x) \in B$ 等价于 $x \notin A \iff f(x) \notin B$。这个可计算函数 f 同时建立了 $\bar{A}$ 和 $\bar{B}$ 之间的归约。注意，$A \le_m B$ 通常并不意味着 $A \le_m \bar{B}$。
   • 定理 3 (传播“简单性”):
   • 如果 B 是可判定的，并且 A 能图灵归约到 B，那么 A 也是可判定的。（用一个简单的东西解决了一个更简单的东西）。
   • 如果 B 是可识别的，并且 A 能映射归约到 B，那么 A 也是可识别的。
   • 推论 4 (传播“困难性”): 这是我们使用归约最主要的方式！
   • 证明不可判定性: 要证明 B 是不可判定的，我们只需找到一个已知不可判定的问题 A (通常是 $A_{TM}$)，然后构造一个从 A 到 B 的归约 ($A \le_T B$ 或 $A \le_m B$)。如果 B 是可判定的，那么根据定理 3，A 也将是可判定的，这与 A 不可判定的前提矛盾。所以 B 必须是不可判定的。
   • 证明不可识别性: 要证明 B 是不可识别的，我们只需找到一个已知不可识别的问题 A (通常是 $\overline{A_{TM}}$)，然后构造一个从 A 到 B 的映射归约 ($A \le_m B$)。
6. 处理错误编码的提示:
   • 在构造映射归约 $f: A \to B$ 时，输入 x 可能是格式错误的（比如，A 是关于图灵机的问题，但 x 根本不是一个合法的图灵机编码）。
   • 对于这些格式错误的输入，它们肯定不属于 A。所以，我们只需要把它们映射到一个确定不属于 B 的实例 $y_{no} \notin B$。这样就满足了 $x \notin A \implies f(x) \notin B$ 的条件。
   • 这使得我们在证明的核心部分，可以只关注那些格式正确的输入。

这部分介绍了一个极其强大的“批量处理”工具——莱斯定理 (Rice's Theorem)，它可以一次性证明一大类关于图灵机的问题都是不可判定的。

1. 问题的模式:
   • 我们之前遇到的很多问题（语言）都是在问图灵机本身的一些特性。比如：
   • $A_{TM} = \{\langle M, w \rangle \mid \dots \}$: 这是问一个图灵机和一个输入。
   • $E_{TM} = \{\langle M \rangle \mid L(M) = \varnothing\}$: 这是问图灵机 M 所识别的语言是不是空语言。
   • $REGULAR_{TM} = \{\langle M \rangle \mid L(M) \text{ is regular}\}$: 这是问图灵机 M 所识别的语言是不是正则语言。
   • 莱斯定理关注的是后一类问题：只给一个图灵机的编码 $\langle M \rangle$，然后问它所识别的语言 $L(M)$ 是否具有某种“性质”。
2. 性质 (Property) 的形式化定义:
   • 一个关于图灵机的语言 P 被称为是一个“性质”，如果它只关心图灵机的行为（即它识别的语言），而不关心其实现（即具体的状态和转移函数）。
   • 形式化定义: 如果两个图灵机 $M_1$ 和 $M_2$ 识别同一个语言 ($L(M_1) = L(M_2)$)，那么它们的编码 $\langle M_1 \rangle$ 和 $\langle M_2 \rangle$ 必须要么都属于 P，要么都不属于 P。
   • 例子:
   • $P_1 = \{\langle M \rangle \mid L(M) \text{ contains '01'}\}$ 是一个性质。因为判断 $\langle M \rangle$ 是否在 $P_1$ 中，只取决于 $L(M)$，和 M 的内部构造无关。
   • $P_2 = \{\langle M \rangle \mid M \text{ has exactly 10 states}\}$ 不是一个性质。因为我们可以轻易构造两个图灵机 $M_1$ (有10个状态) 和 $M_2$ (有20个状态)，但它们都识别同一个语言（比如空语言）。那么 $\langle M_1 \rangle \in P_2$ 但 $\langle M_2 \rangle \notin P_2$，违反了定义。
3. 非平凡性质 (Non-trivial Property):
   • 一个性质 P 是非平凡的，如果它不是“空性质”也不是“全性质”。
   • $P \ne \varnothing$: 至少存在一台图灵机，它所识别的语言具有该性质。
   • $P \ne \{\text{all TM encodings}\}$: 至少存在一台图灵机，它所识别的语言不具有该性质。
   • 直观理解: “非平凡”意味着这个性质是有区分度的，不是所有语言都有或者所有语言都没有。例如，“识别的语言是否是可识别的”是一个平凡性质，因为所有图灵机识别的语言定义上就是可识别的。
4. 莱斯定理 (Theorem 5):
   • 内容: 任何关于图灵机所识别语言的非平凡性质都是不可判定的。
   • 威力: 这个定理是一个“超级武器”。只要我们能确定一个问题是在问图灵机语言的某个非平凡性质，我们就可以立刻宣称它是不可判定的，无需再做任何从 $A_{TM}$ 出发的归约。
   • 证明思路: 其标准证明就是从 $A_{TM}$ 归约到任意一个非平凡性质 P。
5. 精炼莱斯定理 (Rice's Theorem, Refined):
   • 这个更强的版本不仅告诉我们可判定性，还告诉我们可识别性。
   • 判断标准: 看一下“最简单”的图灵机 $M_\varnothing$（它识别空语言 $\varnothing$，比如一台启动后立刻拒绝所有输入的图灵机）是否满足这个性质。
   • Case 1: 如果 $M_\varnothing$ 满足性质 P (即 $\langle M_\varnothing \rangle \in P$)
   • 那么 P 是不可识别的。
   • 直觉: 这类性质通常是“负面”或“受限”的，比如“语言为空”、“语言不包含'01'”、“语言是有限的”。判断一个图灵机的语言是否有限是不可识别的，因为它需要你确保图灵机不会在无穷多个输入上接受。
   • Case 2: 如果 $M_\varnothing$ 不满足性质 P (即 $\langle M_\varnothing \rangle \notin P$)
   • 那么 P 的补集 $\bar{P}$ 是不可识别的。（注意，这并不直接告诉我们 P 的可识别性，但如果 P 本身是可识别的，那么根据 $co-RE$ 的性质，它就不是不可识别的）。
   • 直觉: 这类性质通常是“正面”或“存在性”的，比如“语言非空”、“语言包含'01'”、“语言是无限的”。例如，“语言非空”这个性质是可识别的（非确定性地猜一个 w 和步数 k，看 M 能否接受 w），但它的补集（“语言为空”）是不可识别的。

这个例子展示了如何使用 NTM 的“猜测”能力来优雅地解决图的可达性问题。

1. 问题定义:
   • 语言: 可达性 (REACHABILITY)
   • 输入: 一个图 G 的编码，以及两个顶点 s (起点) 和 t (终点)。
   • 问题: 图 G 中是否存在一条从 s 到 t 的路径？
2. NTM 算法 (高级描述):
   • 核心思想: 从起点 s 开始，非确定性地在图中“漫游”，看看能否“撞到”终点 t。
   • 步骤 1 & 2: 初始化。把当前位置设为 s，并标记 s 已经访问过（防止在两个顶点间来回走死循环）。
   • 步骤 3 & 4: 死胡同判断。如果当前顶点的所有邻居都已经被访问过了，说明从这条路走不通了，此计算分支拒绝。
   • 步骤 5 & 6: 非确定性的移动。这是算法的核心。从当前顶点的所有未被访问过的邻居中，“猜测”一个作为下一个要移动到的顶点。NTM 会分裂出多个分支，每个分支探索一个邻居。
   • 步骤 7: 终止条件。在移动到新的当前顶点后，检查它是不是终点 t。如果是，那么这个分支就成功了，接受输入。如果不是，就回到步骤 2，标记新顶点，继续探索。
3. 正确性分析 (Why this works):
   • 如果存在路径 ($w \in$ 可达性): 假设存在一条路径 $s \to v_1 \to v_2 \to \dots \to t$。那么，NTM 就存在一个“幸运的猜测”序列：在 s 时猜到 $v_1$，在 $v_1$ 时猜到 $v_2$，... 一路下去，最终猜到 t。在这个计算分支上，NTM 会在步骤 7 接受。根据 NTM 的接受定义，只要有一个分支接受，整个机器就接受。
   • 如果不存在路径 ($w \notin$ 可达性): 那么从 s 出发，无论怎么走都到不了 t。在 NTM 的所有计算分支中，每一次移动都是沿着图中实际存在的边进行的。因为没有路径到 t，所以没有任何一个分支能最终将当前顶点设置为 t。所有分支最终都会因为走到“死胡同”（步骤 4）而拒绝。因此，没有分支会接受，整个机器不接受。
4. 停机分析:
   • 这个 NTM 是一个判定器，因为它总是会停机。
   • 原因在于步骤 2 “将当前顶点标记为已访问”，以及步骤 6 只选择“未被标记的顶点”。
   • 一个计算分支的路径长度，最多只能经过图中的每个顶点一次。
   • 因为图 G 的顶点数量是有限的，所以任何一个计算分支的长度都是有限的。
   • 因此，机器不可能无限循环，它总是会在有限步内接受或拒绝。