1 讲义 9a - 可数性、图灵归约、不可判定性证明

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

• 讲义 9a：标识这是系列讲义中的第9个主题的a部分。在课程中，一个大的主题可能会被拆分成多个部分，例如 'a' 部分通常是介绍概念和问题，'b' 部分可能是解答。
• 可数性、图灵归约、不可判定性证明：这清晰地列出了本讲义将要涵盖的三个核心主题。
• 可数性 (Countability)：这是集合论中的一个基本概念，用来衡量集合的大小或“元素个数”。它帮助我们区分不同类型的无穷大，是理解计算理论中语言和图灵机数量的基础。
• 图灵归约 (Turing Reduction)：这是一种解决问题的方法论，即如果我们能解决问题B，那么我们也能解决问题A。这是衡量问题难度相对关系的核心工具，在不可判定性理论中至关重要。
• 不可判定性证明 (Undecidability Proofs)：这是计算理论的核心内容之一，旨在证明某些问题是计算机无法通过算法解决的。本讲义将介绍如何使用可数性和图灵归约来证明某些问题是不可判定的。
• Owen Keith 和 Owen Terry：讲义的作者。
• COMS 3261 2024年秋季：标识了这门课程的编号（COMS W3261，哥伦比亚大学计算机科学理论课程）、学期（2024年秋季）。

这段话给出了可数集的核心定义。

• 集合 (Set)：在数学中，集合是指由一些确定的、不同的对象（称为元素）组成的整体。例如，{1, 2, 3} 是一个集合。
• 有限的 (Finite)：一个集合如果其元素的个数是某个自然数（包括0），那么它就是有限的。例如，{a, b, c} 是一个有限集，它有3个元素。空集 {} 也是有限集。
• $|\mathbb{N}|$：这是一个关键符号。
• $\mathbb{N}$ 代表自然数集，通常指 {0, 1, 2, 3, ...}。这是一个无穷集合。
• $|S|$ 表示集合 $S$ 的基数 (Cardinality)，直观上就是集合中元素的数量。
• 所以，$|S|=|\mathbb{N}|$ 意味着集合 $S$ 和自然数集 $\mathbb{N}$ 的元素个数“一样多”。这里的“一样多”需要一个严格的定义，即下面会提到的双射。
• 可数 (Countable)：根据定义，一个集合被称为可数的，有两种情况：

1. 它是有限的。
2. 它的大小（基数）和自然数集 $\mathbb{N}$ 一样。这种集合也常被称为“可数无穷”或“可列举”的。
   • 不可数 (Uncountable)：如果一个集合既不是有限的，大小也和自然数集不同，那它就是不可数的。这意味着它的无穷“更大”一些。
   • 例子：
   • 整数集 $\mathbb{Z} = \{..., -2, -1, 0, 1, 2, ...\}$ 是可数的。虽然它看起来比 $\mathbb{N}$ “大”一倍，但实际上我们可以将它与 $\mathbb{N}$ 一一对应。
   • 有理数集 $\mathbb{Q}$（所有可以表示为分数 $p/q$ 的数）也是可数的。这可能更反直觉，因为在任何两个有理数之间都存在无穷多个有理数，但它们仍然可以被一一列举。

这是可数性的另一个定义，它从“表示”的角度出发，对于计算机科学尤其重要。

• 等价定义 (Equivalent Definition)：意味着这个定义与定义1在逻辑上是完全相同的。满足这个定义的集合必然满足定义1，反之亦然。
• 当且仅当 (if and only if)：这是一个强逻辑连接词，表示双向蕴含。
• 唯一的有限字符串 (a unique finite string)：这是核心。
• 字符串 (String)：由某个字母表中的字符组成的有限序列。例如，"hello"、"10110"、"a-b/c" 都是字符串。
• 有限 (Finite)：每个元素对应的字符串长度必须是有限的。
• 唯一 (Unique)：集合中不同的元素必须对应不同的字符串。这确保了描述的无歧义性。

这个定义将抽象的集合元素与具体、离散的“符号表示”联系起来。因为任何有限字符串都可以被计算机处理，所以这个定义暗示了：一个集合是可数的，当且仅当它的元素可以被计算机（原则上）表示和区分。

这段话形式化了“集合大小相等”的含义。

• 基数 (Cardinality)：我们再次遇到这个词。对于有限集，它就是元素个数。对于无穷集合，它是一个衡量“无穷大小”的抽象概念。
• $|S|=|T|$：这不是简单的数字相等，而是“基数相等”的声明。
• 双射 (Bijection)：这是一个数学术语，指一个满足以下两个条件的函数 $f$ 从集合 $S$ 射向集合 $T$：

1. 单射 (Injective)：$S$ 中不同的元素一定映射到 $T$ 中不同的元素。即，如果 $x \neq y$，那么 $f(x) \neq f(y)$。（没有“一对多”）
2. 满射 (Surjective)：$T$ 中的每一个元素都有一个（或多个）$S$ 中的元素与之对应。即，对于所有 $y \in T$，都存在 $x \in S$ 使得 $f(x)=y$。（$T$ 中没有“被遗漏”的）

双射结合了这两个条件，意味着 $S$ 和 $T$ 的元素之间可以建立一个完美的“一一对应”关系。

所以，这个定义的核心思想是：判断两个集合是否“一样大”的最终标准，不是靠直觉，而是看它们之间能否建立一个完美的一一配对。

这段是对定义3中提到的几个关键术语的正式回顾和定义。

• 函数 (Function) $f: S \rightarrow T$：这是一个规则，它为集合 $S$（定义域）中的每一个元素 $x$，都指定了集合 $T$（到达域）中一个唯一的元素 $y=f(x)$。
• 单射 (Injection / one-to-one)：
• 形式化定义：如果 f(x)=f(y) 那么 x=y。这是原命题的逆否命题形式，它等价于 如果 x ≠ y 那么 f(x) ≠ f(y)。
• 直观解释：不会出现多个输入映射到同一个输出的情况。就像发射箭矢，每支箭都射中不同的靶子。
• 满射 (Surjection / onto)：
• 形式化定义：对于所有 y in T，都存在 x in S 使得 f(x)=y。
• 直观解释：目标集合 $T$ 中的每一个元素都被“击中”了至少一次。靶场上的每个靶子都被至少一支箭射中了。
• 双射 (Bijection)：
• 定义：同时满足单射和满射。
• 直观解释：靶场上的箭和靶子不多不少，正好一一对应。每支箭射中一个靶子，每个靶子也只被一支箭射中。

这句话将我们对有限集的日常理解（“有n个东西”）与严格的集合论定义联系起来。

• 集合 S 具有 n 个元素：这是我们日常的、直观的说法。
• 当且仅当：强逻辑等价。
• 存在一个双射 $f:\{1,2, \ldots n\} \rightarrow S$：这是形式化的数学定义。
• $\{1,2, \ldots n\}$：这是一个标准的“标尺”集合，它有 $n$ 个元素。
• 双射的存在意味着集合 $S$ 的元素可以与 $1, 2, ..., n$ 这 $n$ 个数字一一对应，不多不少。这本质上就是在“数数”：第一个元素对应1，第二个对应2，……，第n个对应n。数完不多也不少。

所以，当我们在说“这个集合有5个元素”时，我们数学上的意思是，我们可以给这个集合的元素从1到5编号，并且刚好用完。

这个例子旨在证明一个反直觉的事实：整数和自然数一样多。它通过构造一个具体的双射函数来证明这一点。

• $|\mathbb{N}|=|\mathbb{Z}|$：这是要证明的结论，即自然数集和整数集的基数相等。
• $f: \mathbb{N} \rightarrow \mathbb{Z}$：我们正在构建一个从自然数到整数的映射。
• 函数定义：这是一个分段函数，根据输入 $n$ 的奇偶性来决定其输出。
• 如果 n 是偶数：$f(n) = n/2$。这部分负责生成所有的非负整数。
• 如果 n 是奇数：$f(n) = -(n+1)/2$。（注意：原文中是-(n-1)/2，这里按原文解释，但 -(n+1)/2 也能构造出类似映射，只是起点不同。我们以原文为准，-(n-1)/2 是错误的，应该是 -(n+1)/2 或者 -(n-1)/2 且 n 从1开始。假设原文-(n-1)/2是笔误，应为-(n+1)/2，我们按-(n+1)/2分析。如果按-(n-1)/2，则$f(1)=0, f(3)=-1, ...$，会与偶数部分的 $f(0)=0$ 重复，不是单射。让我们假定这是一个常见的构造，正确的应该是 -(n+1)/2。啊，发现原文是 -(n-1)/2，这在 $n=1,3,5,...$ 时产生 $0, -1, -2, ...$。而偶数部分 $n=0,2,4,...$ 产生 $0, 1, 2, ...$。这里 $f(0)=0$ 和 $f(1)=0$ 重复了。所以原文的函数是有问题的。一个正确的、常见的构造是：$f(n) = n/2$ (n偶数) 和 $f(n) = -( (n-1)/2 + 1 ) = -(n+1)/2$ (n奇数)。或者更简单的，将0,1,2,3,4,5... 映射到 0, 1, -1, 2, -2, 3...。这个映射就是：$f(0)=0, f(1)=1, f(2)=-1, f(3)=2, f(4)=-2, ...$。这可以用一个公式来写，比如 $f(n) = (-1)^n \lceil n/2 \rceil$。我们还是回到原文的公式，并指出它的瑕疵，然后解释其意图。）

让我们分析原文给出的公式：

$f(n)= \begin{cases}n / 2 & \text { 如果 } \mathrm{n} \text { 是偶数 } \\ -(n-1) / 2 & \text { 如果 } \mathrm{n} \text { 是奇数 }\end{cases}$

• 偶数输入: $f(0)=0, f(2)=1, f(4)=2, ...$ -> 生成了 $\{0, 1, 2, ...\}$，即所有非负整数。
• 奇数输入: $f(1)=0, f(3)=-1, f(5)=-2, ...$ -> 生成了 $\{0, -1, -2, ...\}$，即所有非正整数。
• 问题：$f(0)=0$ 且 $f(1)=0$。这意味着它不是单射，所以这个函数本身并不能作为双射的证明。
• 意图：作者的意图是展示一种将自然数“展开”以覆盖所有整数的策略。这个策略是：用偶数自然数去覆盖正整数和0，用奇数自然数去覆盖负整数。这是一个正确的思路，只是公式写错了。

一个正确的双射函数应该是这样：

让我们用这个正确的函数来理解。

这个定理描述了可数集的一个重要封闭性质。

• 可数并集 (Countable Union)：我们取“可数个”集合，然后将它们合并。这里的“可数个”由下标 $n=1, 2, 3, ...$ 来体现。
• $\left\{E_{i}\right\}_{n=1}^{\infty}$：这是一个集合的序列，共有无穷多个集合：$E_1, E_2, E_3, ...$。
• 每个 $E_i$ 都是可数集：这是前提条件。也就是说，序列中的每一个集合，其自身要么是有限的，要么是可数无穷的。
• 并集 (Union) $\bigcup$：将所有这些集合 $E_i$ 中的元素汇集在一起，形成一个大的新集合 $S$，去掉重复的元素。
• 结论：这个大的新集合 $S$ 依然是可数的。

简而言之：可数个可数集合并在一起，其结果仍然是可数的。

这个定理描述了可数集关于笛卡尔积的封闭性。

• 有限积 (Finite Product)：指的是取有限个集合进行笛卡尔积操作。这里的 $n$ 是一个具体的有限数字。
• $E_{1}, \ldots, E_{n}$：这是有限的 $n$ 个集合，并且每个都是可数的。
• 笛卡尔积 (Cartesian Product) $E_1 \times E_2$：结果是一个由所有可能的有序对 $(a, b)$ 组成的集合，其中 $a \in E_1$ 且 $b \in E_2$。推广到 $n$ 个集合，就是所有可能的有序 $n$-元组 $(a_1, a_2, \ldots, a_n)$ 的集合。
• 结论：这个由所有 $n$-元组构成的集合仍然是可数的。

简而言之：有限个可数集的笛卡尔积是可数的。

这是一个非常直观的定理。

• $L$ 是一个可数集：这是我们的大前提。这意味着 $L$ 的元素可以被一一列举出来。
• 子集 (Subset) $S \subseteq L$：集合 $S$ 中的所有元素都来自于集合 $L$。$S$ 是从 $L$ 中“挑选”一部分元素组成的。
• 结论：这个子集 $S$ 也必然是可数的。

换句话说，可数集的子集不可能比可数“更大”。

证明思路（非严格）：

1. 因为 $L$ 是可数的，所以我们可以将它的所有元素排成一个列表（可能是有限或无限的）：$l_1, l_2, l_3, \ldots$。
2. 现在我们要为 $S$ 的元素也排一个列表。我们可以遍历 $L$ 的列表：
   • 看 $l_1$ 是不是在 $S$ 里？如果是，它就是 $S$ 列表的第一项。
   • 看 $l_2$ 是不是在 $S$ 里？如果是，它就是 $S$ 列表的下一项。
   • ...以此类推。
3. 通过这个过程，我们或者遍历完 $L$ 的所有元素（如果 $L$ 有限），或者可以一直进行下去。$S$ 的每一个元素都源自 $L$，所以它必然会在 $L$ 的列表中的某个位置出现，因此也必然会被我们加入到 $S$ 的新列表中。
4. 这样，我们就为 $S$ 的元素构建了一个列表，证明了 $S$ 是可数的。如果 $S$ 是有限的，列表会终止。如果 $S$ 是可数无穷的，列表会无限延续。

这是一个在计算机科学中极其重要的例子。

• 有限字母表 (Finite Alphabet) $\Sigma$：一个包含有限个符号的集合。例如，二进制字母表 $\Sigma = \{0, 1\}$，或者英文小写字母表 $\Sigma = \{a, b, \ldots, z\}$。
• $\Sigma^{*}$ (读作 "Sigma star")：表示由字母表 $\Sigma$ 中的符号所能构成的一切有限长度字符串的集合。这包括空字符串 $\epsilon$。
• 结论：$\Sigma^{*}$ 是可数的。这意味着，尽管我们可以构造出无限多个不同的字符串，但所有这些字符串的总体仍然可以被一一列举。

这是对“$\Sigma^{*}$ 是可数的”这一结论的正式证明，它巧妙地运用了定理1。

• $\Sigma^n$：所有长度为 $n$ 的字符串的集合。
• 对于每个 $n \in \mathbb{N}$，$\Sigma^n$ 是有限的：
• 一个长度为 $n$ 的字符串有 $n$ 个位置。
• 每个位置都可以从 $\Sigma$ 中选择一个字符，有 $|\Sigma|$ 种选择。
• 根据乘法原理，总共的可能性是 $|\Sigma| \times |\Sigma| \times \ldots \times |\Sigma|$（共 $n$ 次），即 $|\Sigma|^n$。
• 因为 $\Sigma$ 是有限的 ($|\Sigma|$ 是一个有限数)，$n$ 也是有限的，所以 $|\Sigma|^n$ 是一个有限数。
• 因此，$\Sigma^n$ 是一个有限集。
• 回忆 $\Sigma^{*} = \bigcup_{n=0}^{\infty} \Sigma^{n}$：
• 这个公式是对 $\Sigma^{*}$ 的一个形式化定义。它说，“所有有限长度字符串的集合”等于“长度为0的字符串的集合”并上“长度为1的字符串的集合”并上“长度为2的字符串的集合”……一直并下去。
• $\Sigma^0 = \{\epsilon\}$ (长度为0的字符串，即空串)
• $\Sigma^1 = \Sigma$
• $\Sigma^2$ = 所有长度为2的字符串
• ...
• 是有限集合的可数并集：
• 我们正在合并 $\Sigma^0, \Sigma^1, \Sigma^2, \ldots$ 这一系列的集合。这是一个无穷序列，所以是“可数”个集合。
• 我们刚刚证明了，该序列中的每一个集合 $\Sigma^n$ 都是有限的。
• 因为有限集是可数集的一种特殊情况，所以这正是“可数集的可数并集”。
• 所以 $\Sigma^{*}$ 结果是可数的：这里直接引用了定理1的结论。既然 $\Sigma^{*}$ 满足定理1的前提，那么它必然也满足定理1的结论。

这部分列举了更多在计算理论中至关重要的可数集。

1. $\{\langle M\rangle \mid M \text{ 是一个 TM}\}$ 是可数的
   • TM: 图灵机 (Turing Machine) 的缩写，是计算理论中用于定义算法的一个数学模型。
   • $\langle M \rangle$: 表示对图灵机 $M$ 的一个编码 (Encoding)。任何一台图灵机（由其状态、字母表、转移函数等定义）都可以被描述成一个有限长度的字符串。
   • 为什么可数：这里直接应用了定义2（可以用唯一有限字符串表示的集合是可数的）。因为每个图リング机都能被编码成一个唯一的有限字符串，所以所有图灵机编码的集合，本质上就是所有字符串集合 $\Sigma^*$ 的一个子集。根据定理3，它必然是可数的。这意味着，尽管图灵机有无限多种，但我们可以给它们一一编号。
2. $\{ L \mid L \text{ 是可识别的} \}$ 和 $\{L \mid L \text{ 是可判定的} \}$ 是可数的
   • 可识别的语言 (Recognizable Language)：一个语言 $L$ 是可识别的，如果存在一个图灵机 $M$，当输入字符串 $w \in L$ 时，$M$ 会停机并接受；当 $w \notin L$ 时，$M$ 或者停机并拒绝，或者永不停机。
   • 可判定的语言 (Decidable Language)：一个语言 $L$ 是可判定的，如果存在一个图灵机 $M$（称为判定机），对于任何输入字符串 $w$，$M$ 总会停机，并且如果 $w \in L$ 则接受，如果 $w \notin L$ 则拒绝。
   • 为什么可数：
   • 每个可识别的语言都由至少一个图灵机来识别。
   • 我们可以建立一个从“图灵机”到“可识别语言”的映射：$f(\langle M \rangle) = L(M)$ (M所识别的语言)。
   • 这个映射是满射的（每个可识别语言都被映射到了），但不是单射的（多个不同的图灵机可以识别同一个语言）。
   • 因为所有图灵机的集合是可数的，作为其“像”的可识别语言集合的大小不会超过图灵机的集合的大小，因此也必然是可数的。（严格来说，这表明可识别语言的基数小于等于图灵机的基数，所以也是可数的）。
   • 所有可判定语言的集合是所有可识别语言的集合的一个子集。根据定理3，它也必须是可数的。
3. $\Sigma^{*}$ 的每个子集 $L \subseteq \Sigma^{*}$ 都是可数的
   • 这是一个严重错误的陈述。原文在这里应该是想表达别的意思，或者是一个巨大的笔误。
   • 正确的事实：$\Sigma^{*}$ 本身是可数的。根据定理3，$\Sigma^{*}$ 的任何一个子集 $L$ 也必然是可数的。这一点是对定理3的直接应用。
   • 可能的混淆：原文作者可能想和下一段“不可数集”中的“所有语言的集合是不可数的”做对比，但是这句话的表述是错误的，或者至少是极易误解的。一个语言 $L$ 就是 $\Sigma^*$ 的一个子集。这句话本身没问题，但是把它作为和前两条并列的“例子”，显得很奇怪。也许是想强调任何一个“具体的”语言都是可数的。但这不是一个有信息量的点。我们姑且按字面意思理解，并指出其与上下文的脱节。

这部分介绍了与可数集相对的概念：不可数集，即“更大”的无穷。

1. 所有实数的集合 $\mathbb{R}$ 是不可数的
   • 实数 (Real Number) $\mathbb{R}$: 包括所有有理数（如 1/2, -3）和无理数（如 $\pi, \sqrt{2}$）。
   • 不可数 (Uncountable): 意味着无法将所有实数与自然数一一对应。实数的无穷比自然数的无穷“更密集”、“更大”。
   • 对角线论证 (Diagonalization Argument): 这是康托尔（Cantor）发明的经典证明方法。
   • 思路：假设实数是可数的，那么我们可以把它们都列在一个列表里。
2. $r_1 = n_1 . d_{11} d_{12} d_{13} \dots$
3. $r_2 = n_2 . d_{21} d_{22} d_{23} \dots$
4. $r_3 = n_3 . d_{31} d_{32} d_{33} \dots$

...

• 现在，我们构造一个新的实数 $X$。$X$ 的小数部分第 $i$ 位，我们刻意让它与列表上第 $i$ 个实数的第 $i$ 位小数不同。例如，如果 $d_{ii}$ 是1，我们就让 $X$ 的第 $i$ 位是2；如果 $d_{ii}$ 不是1，我们就让 $X$ 的第 $i$ 位是1。
• 这个新构造出来的实数 $X$ 与列表中的任何一个实数 $r_i$ 都至少在第 $i$ 位小数上不同。
• 因此，$X$ 是一个不在列表中的实数。这与我们“列表包含了所有实数”的初始假设相矛盾。
• 结论：实数集是不可数的。

1. 所有语言的集合...是不可数的
   • 语言 (Language): 在计算理论中，一个语言被定义为 $\Sigma^*$ 的一个子集。
   • 所有语言的集合: 就是 $\Sigma^*$ 的所有子集的集合。这正是幂集 (Power Set) 的定义，记作 $\mathbb{P}(\Sigma^*)$。
   • 为什么不可数: 这同样可以用对角线论证证明。
   • $\Sigma^*$ 是可数的，我们可以将其所有字符串列成一队: $w_1, w_2, w_3, \dots$。
   • 假设所有语言的集合是可数的，我们也可以把它们列出来: $L_1, L_2, L_3, \dots$。
   • 我们可以构建一个二维表格，行代表语言，列代表字符串。格点 $(i, j)$ 的值是1如果 $w_j \in L_i$，是0如果 $w_j \notin L_i$。
   • 现在，我们构造一个新的语言 $L_D$ (对角线语言)。对于每个字符串 $w_i$，$w_i \in L_D$ 当且仅当 $w_i \notin L_i$ (即表格对角线上的值取反)。
   • 这个新语言 $L_D$ 和列表中的任何一个语言 $L_i$ 都不同（至少在是否包含 $w_i$ 这个问题上不同）。
   • 因此，$L_D$ 是一个不在列表中的语言，与我们“列表包含了所有语言”的假设矛盾。
   • 结论：所有语言的集合是不可数的。
2. 自然数的幂集 $\mathbb{P}(\mathbb{N})$...是不可数的
   • 幂集 $\mathbb{P}(S)$: 集合 $S$ 的所有子集构成的集合。
   • 这个结论是前一个结论的数学抽象。证明方法完全一样，只是把 $\Sigma^*$ 换成 $\mathbb{N}$。康托尔定理表明，任何集合 $S$ 的幂集 $\mathbb{P}(S)$ 的基数都严格大于 $S$ 的基数，即 $|S| < |\mathbb{P}(S)|$。
   • 因为 $\mathbb{N}$ 是可数无穷的，所以它的幂集 $\mathbb{P}(\mathbb{N})$ 必然是不可数的。

这是图灵归约（也叫图灵可约性）的定义，是比较问题难度的核心工具。

• 语言A 和 语言B: 在这里代表两个不同的判定问题。判定一个字符串是否属于某个语言，就是一个判定问题。
• 归约 (Reduction): 核心思想是“问题的转化”。我们试图用解决B的方法来解决A。
• 预言机 (Oracle): 这是一个非常重要的抽象概念。你可以把它想象成一个“黑盒子”，你向它询问任何关于语言B的问题，它都能瞬间给出正确的是/否答案。具体来说，对于任何字符串 $w$，你可以问“$w$ 是否在B中？”，这个预言机会立刻回答“是”或“否”。我们不关心这个黑盒子内部是如何实现的，我们只假设我们拥有了它。
• 判定机来判定A: 我们要构造一个新的图灵机，我们称之为 $M_A$。这个 $M_A$ 的目标是判定语言A。
• $A \leq_T B$ 的含义: 如果我们拥有一个能解决问题B的魔法工具（预言机），我们就能利用这个工具造出一个解决问题A的常规算法（判定机 $M_A$）。$M_A$ 在运行过程中，可以随时向B的预言机提问，并利用其答案来继续自己的计算，最终对输入（关于A的问题）给出正确的是/否答案。

这段话解释了记号 $\leq_T$ 的直观含义。

• A 比 B "更容易"（或相等）: 这个直观理解是核心。$A \leq_T B$ 意味着解决 A 的难度不超过解决 B 的难度。我们可以把 B 看作一个子程序或一个库，A 的解决方法可以调用 B。如果 B 本身就是一个简单的程序，那么 A 调用它也不会变得更复杂。
• 本质上...: 这句话是对上述直观理解的形式化转述，并引出了归约最重要的用途。
• 如果 B 是可判定的，那么 A 也是可判定的: 这是图灵归约的“正面”用法。
• B 可判定 $\implies$ 存在一个总能停机的图灵机 $M_B$ 来解决 B。
• $A \leq_T B$ $\implies$ 存在一个带 B-预言机的判定机 $M_A^{\text{oracle}}$ 来解决 A。
• 现在，我们可以把 $M_A^{\text{oracle}}$ 里的“预言机”替换成真实的判定机 $M_B$。当 $M_A^{\text{oracle}}$ 需要查询预言机时，它就去调用 $M_B$ 这个子程序。因为 $M_B$ 总会停机并给出答案，所以整个新的、不带预言机的图灵机 $M_A'$ 也总会停机。
• 因此，$M_A'$ 成为了 A 的一个判定机，证明了 A 是可判定的。

这是对上一段思想的正式定理陈述。

• 前提1: $A \leq_T B$ (问题A的解决可以依赖于问题B的解决)。
• 前提2: B 是可判定的 (问题B本身有一个算法可以解决)。
• 结论: A 也是可判定的 (问题A也一定有算法可以解决)。

这个定理说明可判定性这个“好性质”是可以通过图灵归约“传递”的，从“更难或一样难的”问题传递给“更容易或一样容易的”问题。

这是本讲义最重要的工具之一。

• 逆否命题 (Contrapositive): 逻辑学中的一个基本原理。一个命题 “如果 P 则 Q” ($P \rightarrow Q$)，其逆否命题是 “如果 非Q 则 非P” ($\neg Q \rightarrow \neg P$)。这两个命题是逻辑等价的。
• 应用到定理4:
• P = "$A \leq_{T} B$ 且 B 是可判定的"
• Q = "A 是可判定的"
• 非Q ($\neg Q$) = "A 不是可判定的"，即 "A 是不可判定的"。
• 非P ($\neg P$) = "并非 ($A \leq_{T} B$ 且 B 是可判定的)"。它等价于 "如果 $A \leq_{T} B$ 成立，那么 B 必然不是可判定的"。
• 推论1的陈述:
• 前提1: $A \leq_T B$ (我们成功地将一个已知不可判定的问题 A 归约到了我们想研究的新问题 B 上)。
• 前提2: A 是不可判定的 (这是一个已知事实，例如 A 就是停机问题 $A_{TM}$)。
• 结论: B 也是不可判定的。

[证明思路]

这是一个反证法：

1. 假设 B 是可判定的。
2. 我们已知 $A \leq_T B$。
3. 根据定理4，如果 $A \leq_T B$ 且 B 是可判定的，那么 A 也是可判定的。
4. 这与我们已知 “A 是不可判定的” 相矛盾。
5. 因此，最初的假设“B 是可判定的”必须是错误的。
6. 结论：B 必须是不可判定的。

这句话是对推论1的用途和威力的一个总结和欢呼。

它强调了归约法是一种可重复使用的、强大的技术，它让我们能够从一个已知的不可判定的“种子”问题出发，不断扩大我们所知道的不可判定问题的版图。

这里列出了四个计算理论中“臭名昭著”的不可判定语言，它们是后续归约证明的常用起点。

1. $A_{TM}$ (The Acceptance Problem for TMs)
   • 定义: 这个语言的“字符串”是形如 $\langle M, w \rangle$ 的对，其中 $\langle M \rangle$ 是一个图灵机的编码，$w$ 是一个输入字符串。
   • 问题: 给定一个图灵机 $M$ 和一个输入 $w$，问 $M$ 是否会接受 $w$？
   • 状态: 这是最核心的不可判定问题之一，通常是第一个被证明的。它的不可判定性是用对角线论证直接证明的。它甚至不是可识别的补集，即 $\overline{A_{TM}}$ 是不可识别的。
2. $E_{TM}$ (The Emptiness Problem for TMs)
   • 定义: 这个语言的“字符串”是图灵机的编码 $\langle M \rangle$。
   • 问题: 给定一个图灵机 $M$，问它所接受的语言 $L(M)$ 是否为空集？换句话说，是否存在任何一个字符串能被 $M$ 接受？
   • 状态: 不可判定。通常通过将 $A_{TM}$ 归约到它来证明。
3. $H ALT_{TM}$ (The Halting Problem for TMs)
   • 定义: 和 $A_{TM}$ 类似，输入是一个对 $\langle M, w \rangle$。
   • 问题: 给定一个图灵机 $M$ 和一个输入 $w$，问 $M$ 在输入 $w$ 上是否会停机（无论是接受还是拒绝）？
   • 状态: 不可判定。这是最著名的不可判定问题，通常说的“停机问题”就是指它。它的不可判定性和 $A_{TM}$ 密切相关，可以相互归约。
4. $EQ_{TM}$ (The Equivalence Problem for TMs)
   • 定义: 输入是两个图リング机的编码 $\langle M_1, M_2 \rangle$。
   • 问题: 给定两个图灵机 $M_1$ 和 $M_2$，问它们所接受的语言是否完全相同？即 $L(M_1) = L(M_2)$？
   • 状态: 不可判定。这是一个非常“难”的不可判定问题，甚至连可识别和共-可识别都不是。通常通过将 $E_{TM}$ 归约到它来证明。

这部分是练习题，要求应用前面学到的归约知识。

练习1：证明 $H ALT_{TM} \leq_T A_{TM}$

• 目标: 证明停机问题可以归约到接受问题。
• 思路: 我们要构造一个判定机 $M_{HALT}$，它使用一个能判定 $A_{TM}$ 的预言机 $O_{A_{TM}}$ 来判定 $HALT_{TM}$。
• 构造 $M_{HALT}$:

1. $M_{HALT}$ 接收输入 $\langle M, w \rangle$。
2. 它首先向预言机查询 "$ \langle M, w \rangle \in A_{TM}$?"。
3. 如果预言机回答“是”，说明 $M$ 接受 $w$。接受必然意味着停机。所以 $M_{HALT}$ 直接输出“是”（停机）。
4. 如果预言机回答“否”，说明 $M$ 不接受 $w$。但这可能是因为 $M$ 拒绝 $w$（停机），也可能是因为 $M$ 在 $w$ 上无限循环。我们还需要区分这两种情况。
5. 为了解决这个问题，我们需要一个更巧妙的构造。让我们反过来证明 $A_{TM} \leq_T HALT_{TM}$，这个方向更直接。
   • 证明 $A_{TM} \leq_T HALT_{TM}$:
   • 构造判定机 $M_{A}$，它使用能判定 $HALT_{TM}$ 的预言机 $O_{HALT}$。
   • $M_A$ 接收输入 $\langle M, w \rangle$。
   • 首先问预言机 "$ \langle M, w \rangle \in HALT_{TM}$?"。
   • 如果回答“否”，说明 $M$ 在 $w$ 上无限循环，那它肯定没有接受 $w$。$M_A$ 直接输出“否”。
   • 如果回答“是”，说明 $M$ 在 $w$ 上一定会停机。既然如此，我们就可以安全地在 $M_A$ 内部模拟 $M$ 在 $w$ 上的运行。因为保证会停，所以模拟也一定会结束。模拟结束后，看 $M$ 的最终状态是接受还是拒绝，$M_A$ 跟着输出同样的结果即可。
   • 这样，我们就用 $O_{HALT}$ 解决了 $A_{TM}$ 问题。所以 $A_{TM} \leq_T HALT_{TM}$。
6. 现在回到原题 $HALT_{TM} \leq_T A_{TM}$。这个方向的构造需要一点技巧。
   • 构造判定机 $M_{HALT}$，使用预言机 $O_{A_{TM}}$。
   • $M_{HALT}$ 接收输入 $\langle M, w \rangle$。
   • 它需要修改原始的图灵机 $M$。构造一个新的图灵机 $M'$。$M'$ 的行为如下：
   • $M'$ 在输入 $x$ 上模拟 $M$ 在输入 $w$ 上的行为。
   • 如果 $M$ 在 $w$ 上接受，$M'$ 就接受 $x$。
   • 如果 $M$ 在 $w$ 上拒绝，$M'$ 就进入一个无限循环。
   • 这个构造是有问题的。我们需要一个能同时检测接受和拒绝的预言机。
   • 一个正确的构造是这样的：
   • 在 $M_{HALT}$ 中，对于输入 $\langle M, w \rangle$，我们构造一个新的图灵机 $M'$。
   • $M'$ 模拟 $M$ 在 $w$ 上的运行。
   • 如果 $M$ 在模拟中进入了接受状态，那么 $M'$ 立刻停机并接受。
   • 如果 $M$ 在模拟中进入了拒绝状态，那么 $M'$ 也立刻停机并接受！
   • 现在，$M'$ 会接受当且仅当 $M$ 在 $w$ 上停机（无论是接受还是拒绝）。
   • $M_{HALT}$ 构造出 $\langle M' \rangle$ 后，向预言机查询 "$ \langle M', w' \rangle \in A_{TM}$?" (这里的 $w'$ 可以是任意字符串，因为 $M'$ 的行为与它自己的输入无关)。
   • 如果预言机回答“是”，说明 $M'$ 接受了，意味着 $M$ 停机了。$M_{HALT}$ 输出“是”。
   • 如果预言机回答“否”，说明 $M'$ 没有接受，意味着 $M$ 无限循环了。$M_{HALT}$ 输出“否”。
   • 这样就完成了证明。

练习2：证明 $L=\{\langle M, D\rangle \mid \ldots L(M)=L(D)\}$ 是不可判定的

• 目标: 证明判断一个图灵机语言是否等价于一个DFA语言是不可判定的。
• 思路: 我们要从一个已知的不可判定问题（比如 $A_{TM}$ 或 $E_{TM}$）归约到 $L$。这里选择从 $E_{TM}$ 归约到 $L$ 更方便。即证明 $E_{TM} \leq_T L$。
• 构造: 假设我们有一个能判定 $L$ 的预言机 $O_L$。我们要构造一个判定机 $M_E$ 来判定 $E_{TM}$。

1. $M_E$ 接收输入 $\langle M \rangle$。
2. $M_E$ 需要判断 $L(M)$ 是否为空。
3. $M_E$ 构造一个非常简单的 DFA，$D_{empty}$，它不接受任何字符串，即 $L(D_{empty}) = \emptyset$。
4. 现在，$M_E$ 手里有了 $\langle M \rangle$ 和 $\langle D_{empty} \rangle$。它可以将这对输入 $\langle M, D_{empty} \rangle$ 喂给预言机 $O_L$。
5. $M_E$ 询问预言机：“$L(M) = L(D_{empty})$ 吗？”
6. 如果预言机回答“是”，这意味着 $L(M) = \emptyset$。所以 $M_E$ 输出“是”（$M$ 的语言为空）。
7. 如果预言机回答“否”，这意味着 $L(M) \neq \emptyset$。所以 $M_E$ 输出“否”。
   • 结论: 我们成功地利用 $O_L$ 解决了 $E_{TM}$ 问题。因此，$E_{TM} \leq_T L$。因为我们已知 $E_{TM}$ 是不可判定的，根据推论1，L也必须是不可判定的。

练习3：证明 $A \leq_{T} B, \bar{A} \leq_{T} B, A \leq_{T} \bar{B}, \bar{A} \leq_{T} \bar{B}$ 等价

• 目标: 证明图灵归约对于语言及其补集是对称的。
• 思路: 我们需要证明这四者之间可以互相推导。
• 证明 $A \leq_T B \implies \bar{A} \leq_T B$:
• 假设 $A \leq_T B$。存在一个带B-预言机的判定机 $M_A$ 来判定A。
• 我们可以构造一个判定机 $M_{\bar{A}}$，它也使用B-预言机。
• $M_{\bar{A}}$ 在输入 $w$ 上，完全模拟 $M_A$ 在 $w$ 上的行为。
• 当 $M_A$ 将要输出“是”时，$M_{\bar{A}}$ 反转结果，输出“否”。
• 当 $M_A$ 将要输出“否”时，$M_{\bar{A}}$ 反转结果，输出“是”。
• 因为 $M_A$ 是判定机，它总会停机。所以 $M_{\bar{A}}$ 也总会停机。$M_{\bar{A}}$ 正好判定了 $\bar{A}$。
• 因此 $\bar{A} \leq_T B$。
• 证明 $\bar{A} \leq_T B \implies A \leq_T B$: 理由同上，反向操作即可。
• 证明 $A \leq_T B \implies A \leq_T \bar{B}$:
• 假设 $A \leq_T B$。存在一个带B-预言机的判定机 $M_A$。
• 我们现在只有一个 $\bar{B}$ 的预言机。
• 构造一个判定机 $M'_{A}$，它使用 $\bar{B}$-预言机。
• $M'_{A}$ 模拟 $M_A$。当 $M_A$ 需要查询B预言机“$w \in B$?”时，$M'_{A}$ 就去查询$\bar{B}$预言机“$w \in \bar{B}$?”。
• 如果 $\bar{B}$预言机回答“是”，$M'_{A}$ 就知道 $w \notin B$，于是把“否”这个答案告诉正在模拟的 $M_A$。
• 如果 $\bar{B}$预言机回答“否”，$M'_{A}$ 就知道 $w \in B$，于是把“是”这个答案告诉正在模拟的 $M_A$。
• 本质上，$M'_{A}$ 用 $\bar{B}$预言机完美地模拟了一个B预言机。所以 $M'_{A}$ 能完成 $M_A$ 的所有工作，从而判定A。
• 因此 $A \leq_T \bar{B}$。
• 组合: 通过以上两条，我们可以证明四者之间的任意转换。例如，要证明 $A \leq_T B \implies \bar{A} \leq_T \bar{B}$：
• $A \leq_T B \implies \bar{A} \leq_T B$ (第一条证明)
• $\bar{A} \leq_T B \implies \bar{A} \leq_T \bar{B}$ (第二条证明，把 A 换成 $\bar{A}$)
• 所以 $A \leq_T B \implies \bar{A} \leq_T \bar{B}$。