4_可判定性4.2.ZH解释

这段话是本节的开篇，旨在引出“不可判定性”这一核心概念，并强调其在计算理论中的重要地位。

1. “在本节中，我们将证明计算理论中一个哲学上最重要的定理”:
   • 计算理论 (Computation Theory): 这是计算机科学的一个理论分支，研究计算的模型、算法的效率以及问题的可解性。它试图回答一些关于计算的根本问题，比如“什么问题是可以用计算机解决的？”
   • 哲学上最重要: 这句话强调了该定理的深远影响。它不仅仅是一个技术性的结论，更改变了我们对计算、计算机乃至宇宙极限的认知。它告诉我们，并非所有清晰定义的问题都能被机械地解决，这触及了知识和能力的边界。
   • 定理 (Theorem): 在数学和逻辑学中，定理是一个已被证明为真的陈述。这意味着我们将要看到一个严谨的、无懈可击的逻辑论证。
2. “存在一个特定的问题是算法不可解的”:
   • 问题 (Problem): 在计算理论中，一个问题通常被形式化地定义为一个关于输入和期望输出的关系。例如，“给定一个数，判断它是否是素数”就是一个问题。
   • 算法 (Algorithm): 算法是一系列明确的、有限的指令，用于解决一个特定的问题或执行一个计算。你可以把它想象成一份精确的食谱，只要按部就班，总能得到结果。
   • 不可解的 (Unsolvable) / 不可判定的 (Undecidable): 这两个词在这里基本是同义词。“算法不可解”意味着不存在任何一个算法，能够在有限时间内对该问题的所有可能输入都给出正确的“是”或“否”的答案。
3. “计算机看起来如此强大，你可能会认为所有问题最终都将迎刃而解”:
   • 这句话是在描述一种普遍存在的直觉或误解。随着科技的发展，计算机的处理能力越来越强，解决了无数复杂的问题，从天气预报到基因测序。这很容易让人产生一种信念，即只要有足够的时间和计算资源，任何问题都能被计算机解决。
4. “这里提出的定理表明计算机在根本上是受限制的”:
   • 这是本段的点睛之笔。它直接反驳了前一句话中的乐观想法。这种限制不是因为计算机不够快，或者内存不够大，而是一种根本性 (fundamental)的、逻辑上的限制。就像你无法画一个“圆的方块”一样，这种限制是内在于计算这个概念本身的。

这一段通过自问自答的方式，进一步阐述了“不可解问题”的现实意义，消除读者可能产生的“这只是纯理论，与我无关”的想法。

1. “什么样的问题是计算机不可解的？”:
   • 这是一个承上启下的设问。前一段告诉我们存在这样的问题，现在自然要问：它们到底长什么样？
2. “它们是深奥的，只存在于理论家的思想中吗？”:
   • 深奥的 (esoteric): 指的是那些非常专业、只有少数专家才能理解的概念。
   • 理论家的思想中: 暗示这些问题可能只是数学家或逻辑学家为了理论构建而发明的抽象游戏，与现实世界没有联系。
   • 这个问题是在主动回应读者的潜在疑虑。很多人会觉得，既然日常生活中计算机什么都能做，那么所谓的“不可解问题”肯定是一些非常奇怪、非常不切实际的“脑筋急转弯”。
3. “不是！”:
   • 一个斩钉截铁的否定。直接打破了前面的猜测。
4. “即使是一些人们想要解决的普通问题，也被证明是计算上不可解的。”:
   • 普通问题 (ordinary problems): 这里的“普通”是相对于“深奥”而言的。它指的是那些在软件工程、编程、人工智能等领域中实际出现，并且工程师们非常希望能够解决的问题。
   • 被证明是计算上不可解的: 再次强调，“不可解”是一个经过严格数学证明的确定性结论。
   • 这句话的重点是，不可解性并非阳春白雪，而是下里巴人。它就在我们日常的编程和软件开发工作中潜伏着。

这一段详细阐述了前文提到的“普通问题”之一——软件验证 (Software Verification)，并明确指出它的通用形式是不可解的。

1. “在一种不可解的问题中，你得到一个计算机程序和一个关于该程序应该做什么的精确规范”:
   • 这里开始描述一个具体场景。
   • 计算机程序 (Computer Program): 一段用某种编程语言（如Python, Java, C++）写成的代码。
   • 精确规范 (Precise Specification): 对程序预期行为的无歧义描述。这不仅仅是“这个程序要好用”这样的模糊描述，而是数学或逻辑上严格的定义。
   • “（例如，对数字列表进行排序）”: 这是一个规范的具体例子。更精确的规范可能是：“对于任意一个输入的整数列表L，程序必须输出一个列表L'，使得L'中的元素与L中的元素完全相同，并且对于L'中任意的两个相邻元素a, b，都有 a ≤ b”。
2. “你需要验证程序是否按规范执行（即，它是正确的）”:
   • 验证 (Verify): 检查或证明某物是否为真或准确。
   • 正确的 (Correct): 程序的实际行为完全符合其规范。
   • 这个任务就是软件工程中的“正确性验证”。
3. “由于程序和规范都是数学上精确的对象，你希望通过将这些对象输入到一台经过适当编程的计算机中来自动化验证过程。”:
   • 数学上精确的对象: 一个程序本质上是一串有限的符号序列，其语法和语义由编程语言严格定义。一个精确的规范也可以用形式化语言（如逻辑公式）来表示。因此，它们都可以被看作是数学对象。
   • 自动化验证过程: 既然程序和规范都是数学对象，我们自然会想，能不能写一个“超级分析程序”（我们称之为“验证器”），把待验证的“程序”和它的“规范”作为输入，然后这个“验证器”就能自动分析，并输出“是，此程序正确”或“否，此程序有误”。
4. “然而，你会感到失望。”:
   • 一个转折，预示着希望的破灭。
5. “软件验证的通用问题是计算机不可解的。”:
   • 这是本段的核心结论。
   • 通用问题 (General Problem): 这里的“通用”是关键。它指的是能够处理任意程序和任意规范的验证问题。
   • 不可解: 再次强调，不存在这样一个万能的、可以自动验证所有程序的“验证器”。

这段话是一个学习导航，为读者设定了本节及后续章节的学习目标。

1. “在本节和第5章中，你将遇到几个计算上不可解的问题”:
   • 这是一个内容预告。它告诉读者，我们将要学习的不是孤立的一个例子，而是一系列相关的不可解问题。这暗示了不可解性是一个普遍现象，并且这些问题之间可能存在关联。
   • 第5章通常会讨论“可归约性”(Reducibility)，这是一种证明其他问题不可解的核心技术。
2. “我们的目标是帮助你对不可解的问题类型形成一种感觉”:
   • 目标一：形成感觉 (Form a feeling)。这是一种高级的学习目标，超越了单纯的记忆和背诵。
   • “感觉”或直觉，意味着当读者将来遇到一个新问题时，能够凭经验和理解，敏锐地判断出“这个问题闻起来有点像个不可解问题”。
   • 不可解问题的类型: 这些问题通常具有一些共性，比如涉及到对任意计算过程行为的预测（如程序会不会停机、会不会访问某个内存地址）、涉及到无穷集合的性质判断、或者涉及到自我指涉（self-reference）的悖论。学习多个例子有助于归纳出这些共同特征。
3. “并学习证明不可解性的技术”:
   • 目标二：学习证明技术 (Learn proof techniques)。这是一个技能目标。
   • 不仅仅是知道“什么”是不可解的，更要掌握“如何证明”一个问题是不可解的。
   • 本节将介绍最根本的证明技术之一：对角化 (Diagonalization)。第5章将介绍归约 (Reduction)，即将一个已知不可解问题“转化”为新问题，从而证明新问题也是不可解的。

这一段正式引入了本节要证明其不可判定性的核心主角：语言 $A_{\mathrm{TM}}$。

1. “现在我们转向第一个确立特定语言不可判定性的定理”:
   • 这是一个清晰的过渡句，表明前面的引言结束，正式的理论内容开始。我们将要学习的是计算理论历史上的一个里程碑式的定理。
2. “判定图灵机是否接受给定输入字符串的问题”:
   • 这是对 $A_{\mathrm{TM}}$ 所代表的问题的非形式化描述。
   • 图灵机 (Turing Machine, TM): 计算的理论模型，可以看作是所有现代计算机的数学抽象。它有一个读写头、一条无限长的磁带和一个有限的状态控制器。
   • 接受 (accepts): 当一个图灵机在处理一个输入字符串后，最终进入一个预先指定的“接受状态”并停机，我们就说这个图灵机“接受”了这个字符串。
   • 问题核心: 给定任何一个图灵机 $M$ 的设计图和一个输入字符串 $w$，判断 $M$ 在输入 $w$ 上运行后，最终会不会停在接受状态。
3. “我们将其称为 $A_{\text {TM }}$，类似于 $A_{\text {DFA }}$ 和 $A_{\text {CFG }}$”:
   • 命名: $A_{\mathrm{TM}}$ 是这个问题的形式化语言名称。下标 TM 代表 图灵机，A 代表接受 (Acceptance)。
   • 类比:
   • $A_{\text{DFA}} = \{\langle B, w \rangle \mid B \text{ is a DFA and } B \text{ accepts } w\}$ 是判断一个确定性有限自动机（DFA）是否接受字符串 $w$ 的问题。
   • $A_{\text{CFG}} = \{\langle G, w \rangle \mid G \text{ is a CFG and } G \text{ generates } w\}$ 是判断一个上下文无关文法（CFG）是否能生成字符串 $w$ 的问题。
   • 这个类比很重要，因为它把新问题置于我们已知的知识体系中。
4. “但是，虽然 $A_{\text {DFA }}$ 和 $A_{\text {CFG }}$ 是可判定的， $A_{\text {TM }}$ 却不是”:
   • 这是一个关键的对比，突出了图灵机与 DFA、CFG 这类较弱计算模型之间的本质区别。
   • 可判定的 (Decidable): 意味着存在一个算法（本身也是一个图灵机），对于 $A_{\text{DFA}}$ 或 $A_{\text{CFG}}$ 的任何输入 $\langle \text{模型}, w \rangle$，都能在有限时间内停机，并给出正确的“是”或“否”的答案。我们可以写一个程序来模拟任何DFA或CFG，并且由于它们的能力受限（DFA没有无限内存，CFG的派生有特定结构），我们可以保证模拟过程或检查过程总会结束。
   • $A_{\text {TM }}$ 却不是: 这是本节要证明的核心论点。图灵机的能力太强大了（可以模拟任何计算机程序），以至于它可能会在某些输入上无限循环（永不停机）。正是这种“无限循环”的可能性，导致了我们无法创造一个万能的算法来判定它最终是否会接受。
5. “设 ...”:
   • 这是对 $A_{\mathrm{TM}}$ 的形式化定义。

这段话在正式开始证明 $A_{\mathrm{TM}}$ 不可判定之前，先退一步，证明了一个较弱但同样重要的性质：$A_{\mathrm{TM}}$ 是图灵可识别的。这个区分对于理解计算复杂性的层次至关重要。

1. “$A_{\text {TM }}$ 是不可判定的。”:
   • 这是定理4.11的内容，一个断言。我们即将要证明它。
2. “在进行证明之前，我们首先观察到 $A_{\text {TM }}$ 是图灵可识别的。”:
   • 这是一个重要的铺垫。
   • 图灵可识别的 (Turing-recognizable): 一个语言 L 被称为图灵可识别的，如果存在一个图灵机 $M_{rec}$，对于任何属于 L 的字符串 $s$， $M_{rec}$ 在输入 $s$ 上会停机并接受。对于任何不属于 L 的字符串， $M_{rec}$ 或者停机并拒绝，或者永不停机（无限循环）。
   • 可判定 (Decidable) vs 可识别 (Recognizable) 的关键区别：
   • 判定器 (Decider): 对所有输入都必须停机，并给出明确的“接受”或“拒绝”。
   • 识别器 (Recognizer): 只需对它应该接受的输入保证停机并接受。对于它不接受的输入，它可以拒绝，也可以“用无限循环来表达拒绝”。
3. “因此，这个定理表明识别器比判定器更强大。”:
   • 这里的“更强大”指的是能处理的语言范围更广。
   • 所有可判定的语言都是图灵可识别的（因为判定器本身就是一个满足识别器定义的、更严格的图灵机）。
   • 而这个定理将证明，存在像 $A_{\mathrm{TM}}$ 这样图灵可识别但不可判定的语言。
   • 这就在可识别语言的集合和可判定语言的集合之间划出了一道鸿沟，证明了前者是一个比后者更大的集合。
4. “要求图灵机在所有输入上都停机限制了它能识别的语言种类。”:
   • 这句话从另一个角度解释了上面的观点。如果你对一个图灵机施加“必须在所有输入上停机”的约束（即要求它成为一个判定器），那么它能处理的语言集合就变小了。放松这个约束，允许它在某些输入上循环（成为一个识别器），它就能处理更多的语言。
5. “以下图灵机 $U$ 识别 $A_{\text {TM }}$。”:
   • 这里开始构造一个具体的图灵机 $U$，来证明 $A_{\mathrm{TM}}$ 确实是图灵可识别的。
6. “$U=$ ‘在输入 $\langle M, w\rangle$ 上...’”:
   • 这是对识别器 $U$ 的算法描述。$U$ 的工作是接收一个图灵机 $M$ 的编码和字符串 $w$。
   • 步骤1: “模拟 $M$ 在输入 $w$ 上的运行。” 这是核心操作。$U$ 就像一个虚拟机或解释器。它读取 $\langle M \rangle$ 的编码，然后在自己的磁带上建立起 $M$ 的状态、转移函数以及输入 $w$ 的初始布局，然后一步一步地按照 $M$ 的规则来更新磁带和状态。
   • 步骤2: “如果 $M$ 进入其接受状态，则接受；如果 $M$ 进入其拒绝状态，则拒绝。” $U$ 持续模拟，并监控被模拟的 $M$ 的状态。
   • 如果 $M$ 停机并接受，$U$ 也停机并接受。
   • 如果 $M$ 停机并拒绝，$U$ 也停机并拒绝。
7. “请注意，如果 $M$ 在 $w$ 上循环，这台机器...也会循环”:
   • 这是关键点。$U$ 的模拟是忠实的。如果 $M$ 陷入无限循环，$U$ 的模拟过程也永远不会结束，$U$ 自身也就陷入了无限循环。
   • 正因为存在这种“一起循环”的可能性，$U$ 才不是一个判定器。判定器被要求在所有输入上停机，但 $U$ 在输入是 $\langle M, w \rangle$ 且 $M$ 在 $w$ 上循环时，无法停机。
8. “这就是为什么这台机器不判定 $A_{\mathrm{TM}}$ 的原因。”:
   • 明确指出了 $U$ 只是一个识别器而非判定器。
9. “如果算法有某种方法来判定 $M$ 在 $w$ 上没有停机，它就可以在这种情况下拒绝。”:
   • 这里点明了从识别器升级到判定器所缺失的关键环节：需要一个“循环检测器”。
   • 一个假设的判定器 $H$ 的逻辑会是：先模拟 $M$ 在 $w$ 上的运行，同时运行一个“循环检测器”。如果 $M$ 接受了，就接受。如果 $M$ 拒绝了，就拒绝。如果“循环检测器”响了，报告说 $M$ 已经陷入无限循环，那么 $H$ 就可以自信地停机并拒绝。
10. “然而，算法没有办法做出这个判定，正如我们将看到的。”:
    • 预告了接下来的证明核心：我们将证明，这样一个通用的“循环检测器”（即解决停机问题的算法）是不可能存在的。

这一段是对刚刚介绍的图灵机 $U$ 的一个历史和概念性的补充说明，强调了它的重要地位。

1. “图灵机 $U$ 本身也很有趣。”:
   • 引起读者的注意，暗示 $U$ 的意义超越了仅仅作为证明 $A_{\mathrm{TM}}$ 可识别的工具。
2. “它是艾伦·图灵在1936年首次提出的通用图灵机的一个例子。”:
   • 艾伦·图灵 (Alan Turing): 英国数学家、逻辑学家，被誉为“计算机科学之父”和“人工智能之父”。
   • 1936年: 这是图灵发表奠基性论文《论可计算数及其在判定问题上的应用》的年份，这篇论文中首次提出了图灵机和通用图灵机的概念。
   • 通用图灵机 (Universal Turing Machine, UTM): 正是这个 $U$。它的革命性在于，图灵证明了可以建造一台单一的、固定的机器 ($U$)，它能模拟任何其他图灵机 ($M$)。
3. “这台机器被称为通用的，因为它能够根据对机器的描述来模拟任何其他图灵机。”:
   • 这里解释了“通用 (Universal)”的含义。
   • 在通用图灵机出现之前，人们对“机器”的理解是“功能单一”。比如，一个加法器只能做加法，一个乘法器只能做乘法。如果你想做一个新的计算，你就需要造一台新的、专门的机器。
   • 通用图灵机的突破在于，它把“做什么”（计算的逻辑，即程序 $M$）和“谁来做”（执行计算的物理设备 $U$）分开了。计算的逻辑 $M$ 被编码成数据（字符串 $\langle M \rangle$），作为“通用”机器 $U$ 的输入。
4. “通用图灵机在存储程序计算机的发展早期发挥了重要的作用。”:
   • 存储程序计算机 (Stored-program computer): 这是现代计算机体系结构的核心思想（也称为冯·诺依曼架构）。它的要点是，指令（程序）和数据都存储在同一个内存中，可以被CPU读取和执行。
   • 关联: 通用图灵机 $U$ 就是存储程序思想的理论模型。
   • $U$ 的控制器和磁带操作规则是固定的硬件（CPU）。
   • 写在磁带上的 $\langle M, w \rangle$ 就是存储在内存中的程序和数据。$U$ 通过读取 $\langle M \rangle$ 来决定下一步该做什么，这正是CPU读取和执行内存中的指令。
   • 这个理论概念为后来的工程师（如冯·诺依曼、莫奇利和埃克特）设计和建造第一代电子计算机（如ENIAC的后续机型EDVAC）提供了强大的理论基础和指导。

这段话介绍了即将用于证明定理4.11的核心数学工具——对角化方法，并追溯了其历史来源和原始动机。

1. “$A_{\text {TM }}$ 不可判定性的证明使用了一种称为对角化的技术”:
   • 开门见山，点明了证明所依赖的关键武器。对角化 (Diagonalization) 是一种非常巧妙且强大的证明技巧。
2. “该技术由数学家格奥尔格·康托尔于1873年发现”:
   • 格奥尔格·康托尔 (Georg Cantor): 德国数学家，集合论的创始人。他的工作彻底改变了数学家对“无限”的理解。
   • 1873年: 这是康托尔首次证明实数集不可数的年份，该证明中就使用了对角化。
   • 这句交代了技术的发明者和历史，说明我们正在借用一个来自纯数学领域的经典工具。
3. “康托尔关注的是测量无限集大小的问题”:
   • 阐明了对角化最初被发明出来要解决的问题：比较不同无限集合的大小。
   • 无限集 (Infinite Set): 包含无限多个元素的集合，例如自然数集 $\{1, 2, 3, \dots\}$。
4. “如果我们有两个无限集，我们如何判断一个是否比另一个大，或者它们是否大小相同？”:
   • 提出了比较无限集大小的挑战。这个问题的答案并不直观。例如，偶数集和整数集都是无限的，它们一样大吗？有理数集和实数集呢？
5. “对于有限集，当然，回答这些问题很容易。我们只需数数有限集中的元素，结果的数字就是它的大小。”:
   • 用有限集的情况作对比。对于有限集，比如 A = {苹果, 香蕉, 橙子}，B = {红, 绿}，我们可以通过计数来比较大小。A的大小是3，B的大小是2，所以A比B大。
6. “但是如果我们尝试数数无限集中的元素，我们将永远数不完！所以我们不能使用数数方法来判定无限集的相对大小。”:
   • 指出了传统计数方法的局限性。对于无限集，计数过程没有终点，因此无法得到一个具体的“数量”来进行比较。我们需要一种新的、不依赖于“数完”这个过程的方法。

这一段通过两个具体的无限集合例子，让上一段提出的抽象问题变得更加具体。

1. “例如，取偶数集和所有二进制字符串集”:
   • 给出了两个需要比较大小的无限集合。
   • 偶数集 (Set of even numbers): $\mathcal{E} = \{2, 4, 6, 8, \dots\}$。
   • 所有二进制字符串集 (Set of all binary strings): $\Sigma^*$ where $\Sigma = \{0, 1\}$。这个集合包含：$\{\epsilon, 0, 1, 00, 01, 10, 11, 000, \dots\}$ (其中 $\epsilon$ 代表空字符串)。
2. “这两个集都是无限的，因此都比任何有限集大”:
   • 这是一个基本观察。无论你取一个多大的有限集，比如包含1万亿个元素的集，你总能在偶数集或二进制字符串集中找到更多的元素。
3. “但其中一个是否比另一个大？”:
   • 这是核心问题。两个都是无限的，它们的大小关系如何？
   • 直觉上很难判断。偶数集看起来像是一条无限延伸的直线上的离散点。二进制字符串集似乎更“茂盛”，因为每个长度下都有多个字符串，而且长度可以无限增加。
4. “我们如何比较它们的相对大小？”:
   • 再次强调了比较方法的缺失，并引导读者思考解决方案。

这段话正式引入了康托尔解决无限集比较问题的核心思想：从“计数”转向“配对”。

1. “康托尔提出了一个相当巧妙的解决方案来解决这个问题”:
   • 预示着答案的揭晓。
2. “他观察到，如果一个集的元素可以与另一个集的元素配对，那么这两个有限集的大小相同。”:
   • 这里从我们熟悉的有限集开始，建立一个直观的基础。
   • 配对 (Paired off): 指的是建立一种一一对应关系。A集里的每一个元素都恰好对应B集里的一个元素，反之亦然，没有落下，也没有多余。
   • 例子: 一场舞会，如果每个男士都恰好找到一位女士做舞伴，没有男士剩下，也没有女士剩下，那么我们就知道男士和女士的人数是相同的。我们根本不需要去数具体有多少人。
3. “这种方法在不数数的情况下比较大小。”:
   • 强调了这个新方法的本质。它绕过了“计数”这个在无限情况下不可行的操作。
4. “我们可以将这个想法扩展到无限集。”:
   • 这是关键的一步，将有限世界里的直觉推广到无限世界。康托尔的巨大贡献在于，他不仅提出了这个想法，还严格地证明了这个推广是合理且富有成果的。
5. “更精确地说是这样的。”:
   • 引出下文的严格数学定义。

这一段给出了上一段“配对”思想的严格数学定义，引入了三个核心概念：一对一（单射）、满射和一一对应（双射）。

1. “假设我们有集合 $A$ 和 $B$ 以及一个从 $A$ 到 $B$ 的函数 $f$。”:
   • 函数 (Function) $f$: 建立从集合 A (定义域) 到集合 B (到达域) 的映射规则。对于 A 中的每一个元素，f 都指定了 B 中的一个对应元素。
2. “如果 $f$ 从不将两个不同的元素映射到同一个位置——也就是说，如果当 $a \neq b$ 时 $f(a) \neq f(b)$，则称 $f$ 是一对一的。”:
   • 一对一 (One-to-one / Injective): 这是对“不重复”的定义。
   • 直观解释: 从 A 出发的不同的“人”，必须到达 B 中不同的“座位”。不允许两个人抢同一个座位。
   • 例子: $f(x) = x+1$ 是一对一的，因为如果 $x_1 \neq x_2$，那么 $x_1+1 \neq x_2+1$。而 $f(x) = x^2$ （定义域为全体整数）不是一对一的，因为 $f(2)=4$ 且 $f(-2)=4$，两个不同的输入 2 和 -2 映射到了同一个输出 4。
3. “如果 $f$ 击中 $B$ 中的每个元素——也就是说，对于每个 $b \in B$，都存在一个 $a \in A$ 使得 $f(a)=b$，则称 $f$ 是满射的。”:
   • 满射 (Onto / Surjective): 这是对“不遗漏”的定义。
   • 直观解释: 集合 B 中的每一个“座位”都必须有来自 A 的“人”坐。不允许有空座。
   • 例子: 考虑从整数集 $\mathbb{Z}$ 到整数集 $\mathbb{Z}$ 的函数。$f(x) = x+1$ 是满射的，因为对于任何一个整数 $y$，我们总能找到一个整数 $x = y-1$ 使得 $f(x)=y$。而 $f(x) = 2x$ 不是满射的，因为它只能“击中”偶数，所有的奇数座位都空着。
4. “如果存在一个一对一的、满射的函数 $f: A \longrightarrow B$，则称 $A$ 和 $B$ 大小相同。”:
   • 这是康托尔对“大小相同”的正式定义。它要求找到一个函数 $f$，这个函数既满足一对一（不重复），又满足满射（不遗漏）。
5. “既是一对一又是满射的函数称为一一对应。”:
   • 一一对应 (Correspondence / Bijection): 这是对“完美配对”的数学术语。双射是另一个常用名。
   • 一一对应 = 单射 + 满射。
6. “在一一对应中， $A$ 的每个元素都映射到 $B$ 的一个唯一元素，并且 $B$ 的每个元素都有一个 $A$ 的唯一元素映射到它。”:
   • 用更通俗的语言重复了一遍一一对应的含义，强调了其“双向唯一性”。
7. “一一对应仅仅是将 $A$ 的元素与 $B$ 的元素配对的一种方式。”:
   • 回归到最初的直观思想，一个一一对应的函数 $f$ 就是一份描述了如何将 A 和 B 中元素进行完美配对的“配对清单”。

这一段是为一个概念提供多种常用术语，帮助读者在不同文献和语境中都能认出它们。

1. “单射 (injective) 代表一对一”:
   • 单射: 这是“one-to-one”在更形式化的数学语境中的标准术语。前缀 "in-" 可以理解为“注入”，每个源集合的元素被“注入”到目标集合的不同位置。
   • 记忆技巧: “单” -> 单独的，不扎堆。每个输入都对应单独的输出。
2. “满射 (surjective) 代表满射”:
   • 满射: 这是“onto”在数学中的标准术语。前缀 "sur-" (源自法语，意为 "on" 或 "over")，可以理解为函数的像“覆盖”了整个目标集合。
   • 记忆技巧: “满” -> 铺满了。输出覆盖了目标集合的每一个角落。
3. “以及双射 (bijective) 代表一对一和满射”:
   • 双射: 这是“correspondence” (一一对应) 在数学中的标准术语。前缀 "bi-" 意为“双”，表示它同时满足了单射和满射两个（“双”重）条件。
   • 记忆技巧: “双” -> 双重满足：既单射又满射。

这个例子应用了刚刚定义的“一一对应”来证明一个反直觉的结论：自然数和偶数的数量一样多。

1. “设 $\mathcal{N}$ 是自然数集 $\{1,2,3, \ldots\}$，设 $\mathcal{E}$ 是偶自然数集 $\{2,4,6, \ldots\}$。”:
   • 定义了两个要比较的无限集合。$\mathcal{N}$ (Natural numbers) 和 $\mathcal{E}$ (Even numbers)。
2. “使用康托尔对大小的定义，我们可以看到 $\mathcal{N}$ 和 $\mathcal{E}$ 具有相同的大小。”:
   • 提出结论：根据定义4.12，这两个集合大小相同。
3. “将 $\mathcal{N}$ 映射到 $\mathcal{E}$ 的一一对应 $f$ 简单地是 $f(n)=2 n$。”:
   • 为了证明大小相同，我们必须给出一个具体的一一对应函数。这里给出的函数是 $f(n) = 2n$。
   • 验证 $f(n)=2n$ 是否为一一对应 (双射):
   • 定义域: $\mathcal{N} = \{1, 2, 3, \ldots\}$
   • 到达域: $\mathcal{E} = \{2, 4, 6, \ldots\}$
   • 验证单射 (一对一): 假设 $n_1, n_2 \in \mathcal{N}$ 且 $n_1 \neq n_2$。那么 $2n_1 \neq 2n_2$，即 $f(n_1) \neq f(n_2)$。所以函数是单射的。
   • 验证满射 (满射): 对于到达域 $\mathcal{E}$ 中的任意一个偶数 $e$，我们总能在定义域 $\mathcal{N}$ 中找到一个数 $n = e/2$，使得 $f(n) = 2(e/2) = e$。因为 $e$ 是偶数，所以 $e/2$ 必然是一个自然数。所以函数是满射的。
   • 结论: 因为 $f(n)=2n$ 既是单射又是满射，所以它是一个一一对应。
4. “我们可以借助表格更容易地可视化 $f$。”:
   • 表格直观地展示了这个配对关系：1对2，2对4，3对6，等等。对于任何一个自然数 $n$，它都唯一地对应一个偶数 $2n$；对于任何一个偶数 $e$，它都唯一地对应一个自然数 $e/2$。
5. “当然，这个例子看起来很奇怪。”:
   • 承认这个结论与我们的日常直觉相冲突。
6. “直观上， $\mathcal{E}$ 似乎比 $\mathcal{N}$ 小，因为 $\mathcal{E}$ 是 $\mathcal{N}$ 的一个真子集。”:
   • 点明了冲突的来源。真子集 (Proper Subset) 是指一个子集，它不等于母集（即母集中至少有一个元素不在该子集中）。例如，所有的偶数都属于自然数，但有些自然数（奇数）不是偶数，所以 $\mathcal{E}$ 是 $\mathcal{N}$ 的真子集。在有限集中，真子集总是比母集小。
7. “但是，可以将 $\mathcal{N}$ 的每个成员与 $\mathcal{E}$ 的一个成员配对，所以我们声明这两个集的大小相同。”:
   • 重申了康托尔的定义是最终的评判标准。尽管直觉上感觉很怪，但既然我们找到了一个完美的配对方案（一一对应），我们就必须根据定义得出结论：它们大小相同。这揭示了无限集的一个奇特性质：一个无限集可以和它的真子集大小相同。

这个定义引入了一个非常重要的分类术语：可数集。

1. “如果集合 $A$ 是有限的...”:
   • 可数 (Countable) 的第一种情况是有限集。这很自然，任何有限的东西我们显然都是可以“数”的。例如，{a, b, c} 是可数的。
2. “...或者它与 $\mathcal{N}$ 的大小相同...”:
   • 可数的第二种情况，也是更核心的情况，是无限集中那些能与自然数集 $\mathcal{N} = \{1, 2, 3, \dots\}$ 建立一一对应的集合。
   • 这种集合被称为“可数无限”(countably infinite) 或“可列”(denumerable)。
3. “...则称 $A$ 是可数的。”:
   • 总结：可数集 = 有限集 $\cup$ 可数无限集。
   • “可数”的核心直觉是：一个集合是可数的，当且仅当你可以将它的所有元素排成一个列表（这个列表可以是有限的，也可以是无限的），不重不漏。
   • 将元素排成列表的过程，就是在与自然数集（1号位，2号位，3号位...）建立一一对应。
   • 列表中的第一个元素对应1，第二个元素对应2，以此类推。

这一段提出了一个比“偶数集”更反直觉的例子：证明正有理数集 $\mathcal{Q}$ 是可数的，即和自然数集 $\mathcal{N}$ 一样大。

1. “现在我们来看一个更奇怪的例子。”:
   • 预示着接下来的结论会更加挑战直觉。
2. “如果我们设 $\mathcal{Q}=\left\{\left.\frac{m}{n} \right\rvert\, m, n \in \mathcal{N}\right\}$ 为正有理数集， $\mathcal{Q}$ 看起来比 $\mathcal{N}$ 大得多。”:
   • 正有理数集 $\mathcal{Q}$ (Set of positive rational numbers): 所有可以表示为两个正整数 $m, n$ 之比 $\frac{m}{n}$ 的数。
   • 为什么看起来大得多?: 在数轴上，任意两个不相等的自然数之间（比如1和2）没有其他自然数。但任意两个不相等的有理数之间，都存在无限多个其他有理数（这称为稠密性）。例如，在 $1/3$ 和 $1/2$ 之间，有 $2/5, 3/7, ...$ 无数个有理数。这使得 $\mathcal{Q}$ 看起来比 $\mathcal{N}$ “密集”得多。
3. “然而，根据我们的定义，这两个集的大小相同。”:
   • 再次强调，必须以定义4.12（是否存在一一对应）为准绳，而不是直觉。
4. “我们给出一个与 $\mathcal{N}$ 的一一对应，以表明 $\mathcal{Q}$ 是可数的。”:
   • 点明了证明策略：只要能成功构造出一个一一对应，就证明了 $\mathcal{Q}$ 是可数无限的，从而与 $\mathcal{N}$ 大小相同。
5. “一个简单的方法是列出 $\mathcal{Q}$ 的所有元素。”:
   • 将构造一一对应的问题，转化为一个更具体的操作：能否将 $\mathcal{Q}$ 的所有元素不重不漏地排成一个无限列表。如果能，列表的第 $k$ 个元素就自然地与自然数 $k$ 构成了一一对应。
6. “我们必须确保 $\mathcal{Q}$ 的每个成员在列表中只出现一次。”:
   • 这是一个技术上的要点。因为同一个有理数可以有多种表示法，例如 $1/2 = 2/4 = 3/6$。在列表中，我们只能保留其中一个，比如最简形式 $1/2$，其他的重复项需要被跳过。

这一段详细描述了如何通过“对角线”方法将二维的有理数矩阵转化为一维的列表，从而证明有理数集是可数的。

1. “为了得到这个列表，我们制作一个包含所有正有理数的无限矩阵...”:
   • 策略: 将所有正有理数 $\frac{m}{n}$ 安排在一个二维的网格（矩阵）中。
   • 规则: 第 $i$ 行放所有分子为 $i$ 的数，第 $j$ 列放所有分母为 $j$ 的数。
   • 结果: 格子 $(i, j)$ 里的数就是 $\frac{i}{j}$。这个矩阵覆盖了所有可能的正有理数（尽管有重复）。
2. “现在我们将这个矩阵变成一个列表。”:
   • 任务是从这个二维的、无限大的矩阵中，按照某个顺序把所有元素“捡”出来，排成一队。
3. “一个（不好的）尝试方法是，用第一行中的所有元素开始列表...列表永远不会到达第二行。”:
   • 再次排除了按行或按列的简单方法。因为每一行、每一列都是无限的，一旦开始就无法结束，导致遗漏掉其他所有行/列。
4. “相反，我们列出对角线上的元素...从角落开始。”:
   • 提出了巧妙的解决方案：沿着对角线方向遍历。
   • 对角线定义: 这里的“对角线”指的是“左下到右上”方向的斜线。一条对角线上的所有元素 $(i, j)$ 的行号和列号之和 $i+j$ 是一个常数。
   • 第一条对角线: $i+j=2$, 只有 $(1,1)$ -> $\frac{1}{1}$。
   • 第二条对角线: $i+j=3$, 有 $(2,1), (1,2)$ -> $\frac{2}{1}, \frac{1}{2}$。
   • 第三条对角线: $i+j=4$, 有 $(3,1), (2,2), (1,3)$ -> $\frac{3}{1}, \frac{2}{2}, \frac{1}{3}$。
   • ...
5. “第一条对角线...第二条对角线...第三条对角线...”:
   • 逐步展示了遍历过程。关键在于，每一条对角线都是有限长的。第 $k$ 条对角线（$i+j=k+1$）上有 $k$ 个元素。
   • 因此，我们可以遍历完一条对角线，然后接着遍历下一条，保证我们总能前进到新的对角线。
6. “在第三条对角线中，出现了一个复杂情况...我们通过在出现重复时跳过一个元素来避免这种情况。”:
   • 处理了之前提到的重复表示问题。当遇到一个数，如 $\frac{2}{2}$，我们检查它化简后的形式 $\frac{1}{1}$ 是否已经在我们的列表中。
   • $\frac{1}{1}$ 在第一条对角线时已经被加入列表了，所以我们跳过 $\frac{2}{2}$。
   • 这个“检查并跳过”的步骤确保了最终的列表是“不重”的。
7. “以这种方式继续，我们得到 $\mathcal{Q}$ 的所有元素的列表。”:
   • 不重: 通过跳过重复项保证。
   • 不漏: 任何一个正有理数 $\frac{m}{n}$ 都位于这个无限矩阵的第 $m$ 行、第 $n$ 列。它属于 $i+j=m+n$ 这条对角线。因为我们的遍历方法会依次访问所有的对角线，所以任何一个有理数终将在有限的步骤内被我们访问到。
   • 结论: 既然我们能将 $\mathcal{Q}$ 的所有元素排成一个不重不漏的无限列表，那么 $\mathcal{Q}$ 就是可数的。

这一段是过渡，从证明了多个集合是“可数的”，转向引入“不可数”的概念，预示着存在一个大小的“新层次”。

1. “在看到 $\mathcal{N}$ 和 $\mathcal{Q}$ 的一一对应之后，你可能会认为任何两个无限集都可以被证明具有相同的大小。”:
   • 描述了一种在学习了前几个例子后可能产生的自然推断。我们已经看到了反直觉的例子（$\mathcal{N}$ 和 $\mathcal{E}$，$\mathcal{N}$ 和 $\mathcal{Q}$），它们都表明一些看起来“更大”的集合实际上和 $\mathcal{N}$ 一样大。这很容易让人觉得，也许所有无限集都一样大。
2. “毕竟，你只需要证明一个一一对应，这个例子表明确实存在令人惊讶的一一对应。”:
   • 解释了产生上述推断的原因。证明“一样大”只需要找到一个巧妙的一一对应即可。而证明有理数集可数的例子，展示了这种一一对应可以多么地“令人惊讶”和“反直觉”。如果连如此“稠密”的有理数集都能被“拉直”成一条线，那还有什么不能呢？
3. “然而，对于某些无限集，不存在与 $\mathcal{N}$ 的一一对应。”:
   • 一个巨大的转折，否定了前面的推断。这说明无限的世界里，大小确实是有不同等级的。
4. “这些集太大了。”:
   • 用非常直白的语言描述了原因。它们的“无限”程度，比自然数的“无限”程度要高一个层次，以至于你永远无法将它们与自然数一一配对。
5. “这样的集称为不可数。”:
   • 给出了这类“更大”的无限集的正式名称：不可数集 (Uncountable Set)。
   • 定义: 一个集合是不可数的，如果它是一个无限集，并且它不能与自然数集 $\mathcal{N}$ 建立一一对应。
   • 换句话说，你永远无法将一个不可数集的所有元素不重不漏地排成一个（无限）列表。

这段话明确指出了第一个即将被证明为不可数的集合——实数集 $\mathcal{R}$，并点明证明方法就是对角化。

1. “实数集就是一个不可数集的例子。”:
   • 给出了不可数集的第一个，也是最经典的一个范例。
2. “实数是具有小数表示的数字。”:
   • 给出了实数 (Real Numbers) 的一个直观定义。它可以是有限小数（如0.5）、无限循环小数（如1/3 = 0.333...），或者无限不循环小数（如 $\pi$）。
   • 在数轴上，实数与所有的点一一对应，没有任何“空隙”。
3. “数字 $\pi=3.1415926 \ldots$ 和 $\sqrt{2}=1.4142135 \ldots$ 是实数的例子。”:
   • 举了两个著名的无理数 (Irrational Numbers) 作为实数的例子。无理数是那些不能表示为两个整数之比的数，它们的小数表示是无限不循环的。正是这些“无限不循环”的数的加入，使得实数集从有理数集的可数“飞跃”到了不可数。
4. “设 $\mathcal{R}$ 是实数集。”:
   • 引入标准符号 $\mathcal{R}$ 来代表实数集。
5. “康托尔证明了 $\mathcal{R}$ 是不可数的。”:
   • 重申了这是康托尔的重大发现。
6. “在证明过程中，他引入了对角化方法。”:
   • 点明了对角化方法与证明实数集不可数之间的直接历史联系。之前我们用对角线遍历证明了有理数可数，现在我们将看到一个名字相似但思想有别的“对角化论证”来证明实数不可数。这是两种不同的技术。

这是康托尔对角化证明的开端。本段阐述了证明的整体思路——反证法。

1. “$\mathcal{R}$ 是不可数的。”:
   • 这是定理4.17的陈述，即我们要证明的结论。
2. “证明：为了表明 $\mathcal{R}$ 是不可数的，我们表明 $\mathcal{N}$ 和 $\mathcal{R}$ 之间不存在一一对应。”:
   • 根据定义4.14，证明“不可数”就是证明“不能与 $\mathcal{N}$ 建立一一对应”。这是一个否定性的证明目标。
3. “该证明采用反证法。”:
   • 反证法 (Proof by contradiction): 一种间接证明方法。要证明命题P为真，我们先假设P为假（即非P为真），然后从这个假设出发，通过一系列逻辑上无误的推导，得出一个矛盾（比如 $A$ 且 非$A$）。因为矛盾是不可能成立的，所以我们最初的假设（非P为真）必定是错误的。因此，P必须为真。
   • 这是证明“不存在”这类命题的强大工具。
4. “假设 $\mathcal{N}$ 和 $\mathcal{R}$ 之间存在一个一一对应 $f$。”:
   • 这是反证法的第一步：做出与结论相反的假设。
   • 我们假设 $\mathcal{R}$ 是可数的。这意味着，我们可以将所有的实数不重不漏地排成一个无限列表。这个列表就是一一对应 $f$ 的体现：
   • $f(1)$ = 列表中的第一个实数
   • $f(2)$ = 列表中的第二个实数
   • ...
   • $f(n)$ = 列表中的第n个实数
   • 这个假设意味着，这个列表包含了所有的实数。
5. “我们的任务是表明 $f$ 未能按其应有的方式工作。”:
   • 阐明了推导出矛盾的具体方向。我们要证明这个一一对应 $f$ （或者说这个列表）名不副实。
6. “为了使其成为一一对应， $f$ 必须将 $\mathcal{N}$ 的所有成员与 $\mathcal{R}$ 的所有成员配对。”:
   • 重申了一一对应的满射性质：$\mathcal{R}$ 中的每一个元素都必须在这个列表里出现。
7. “但我们将发现 $\mathcal{R}$ 中存在一个 $x$，它未与 $\mathcal{N}$ 中的任何事物配对，这将是我们的矛盾。”:
   • 这是整个证明的核心和最精彩的部分。
   • 策略: 我们将要构造一个特殊的实数 $x$。
   • 这个 $x$ 的构造方法将保证它与列表中的第一个数 $f(1)$ 不同，与第二个数 $f(2)$ 不同，与第 $n$ 个数 $f(n)$ 也不同... 最终，它与列表中的任何一个数都不同。
   • 矛盾:
   • 一方面，我们假设列表（由 $f$ 定义）已经包含了所有的实数。
   • 另一方面，我们又找到了一个实数 $x$，它不在这个列表中。
   • 一个集合不可能既“包含所有实数”，又“不包含实数 $x$”。这个矛盾说明我们最初的假设——“存在这样一个列表 $f$”——是错误的。
   • 因此，$\mathcal{R}$ 必然是不可数的。

这一长段是对角化论证的核心，它通过一个具体的例子，展示了如何构造那个特殊的、不存在于假设列表中的实数 $x$。

1. “我们通过实际构造 $x$ 来找到这个 $x$。”:
   • 这不是一个存在性证明（只证明存在但不指出是什么），而是一个构造性的证明（明确给出构造方法）。
2. “假设存在一一对应 $f$ ... 下表显示了...一些值”:
   • 根据反证法的假设，存在一个能列出所有实数的列表 $f$。这里为了便于理解，给出了这个假设列表的一个具体例子。
   • $f(1) = 3.14159\dots$
   • $f(2) = 55.55555\dots$
   • $f(3) = 0.12345\dots$
   • $f(4) = 0.50000\dots$
   • 这个列表只是一个示意，对角化的逻辑对任何可能的列表都成立。
3. “我们通过给出其小数表示来构造所需的 $x$。”:
   • 开始构造那个“捣蛋鬼”实数 $x$。我们一位一位地来确定它的小数部分。
   • 为了简化，我们构造的 $x$ 是一个 0 到 1 之间的小数。即使我们只证明 (0, 1) 区间内的实数是不可数的，也就足以证明整个实数集 $\mathcal{R}$ 是不可数的。
4. “我们的目标是确保对于任何 $n$， $x \neq f(n)$。”:
   • 明确了构造 $x$ 的唯一目标：让它和列表里的每一个数都不同。
5. “为了确保 $x \neq f(1)$，我们让 $x$ 的第一位数字与 $f(1)=3.14159 \ldots$ 的第一个小数位1不同。我们任意地将其设为4。”:
   • 关键步骤1: 盯着列表的第1行 ($f(1)$) 的小数点后第1位。
   • $f(1)$ 的小数点后第1位是 1。
   • 我们构造的 $x$ 的小数点后第1位就必须不等于1。我们可以选2, 3, 4, 5, 6, 7, 8 中任何一个，这里选了 4。
   • 现在我们知道 $x = 0.4...$。无论 $x$ 后面是什么，它的小数点后第1位是4，而 $f(1)$ 的是1，所以我们保证了 $x \neq f(1)$。
6. “为了确保 $x \neq f(2)$，我们让 $x$ 的第二位数字与 $f(2)=55.555555 \ldots$ 的第二个小数位5不同。我们任意地将其设为6。”:
   • 关键步骤2: 盯着列表的第2行 ($f(2)$) 的小数点后第2位。
   • $f(2)$ 的小数点后第2位是 5。
   • 我们构造的 $x$ 的小数点后第2位就必须不等于5。这里选了 6。
   • 现在 $x = 0.46...$。我们保证了 $x \neq f(2)$，因为它在小数点后第2位上与 $f(2)$ 不同。
7. “$f(3)=0.12 \underline{3} 45 \ldots$ 的第三个小数位是3，所以我们让 $x$ 是任何不同的数字——例如4。”:
   • 关键步骤3: 盯着列表的第3行 ($f(3)$) 的小数点后第3位。
   • $f(3)$ 的小数点后第3位是 3。
   • 我们构造的 $x$ 的小数点后第3位就必须不等于3。这里选了 4。
   • 现在 $x = 0.464...$。我们保证了 $x \neq f(3)$。
8. “以这种方式沿着 $f$ 表的对角线继续...”:
   • 命名来源: 这个过程被称为对角化，因为我们用来构造 $x$ 的每一位数字，都恰好是跟列表形成的矩阵的“对角线”上的数字（$f(1)$的第1位，$f(2)$的第2位，$f(3)$的第3位...）进行比较和作对。
9. “我们知道 $x$ 不是任何 $f(n)$，因为它与 $f(n)$ 在第 $n$ 个小数位上不同。”:
   • 一般化结论: 对于列表中的任意第 $n$ 个数 $f(n)$，我们构造的 $x$ 在小数点后第 $n$ 位上的数字，就是特意取得与 $f(n)$ 的小数点后第 $n$ 位不同。
   • 因此，$x$ 与 $f(1)$ 不同，与 $f(2)$ 不同，...，与 $f(n)$ 不同，... 它与列表中的每一个数都不同。
10. “（一个小问题出现了...我们在构造 $x$ 时从不选择数字0或9来避免这个问题。）”:
    • 这是一个技术上的严谨性处理。
    • 问题: 实数的小数表示不是唯一的。例如，$0.1999...$ 和 $0.2000...$ 其实是同一个数。
    • 风险: 如果我们构造的 $x$ 是 $0.4999...$，而列表中的某个 $f(k)$ 是 $0.5000...$，我们可能会错误地认为它们不同，但实际上它们是同一个数。
    • 解决方案: 在构造 $x$ 的每一位时，我们只从 {1, 2, 3, 4, 5, 6, 7, 8} 中选择，刻意避开 0 和 9。这样构造出来的 $x$ 就不可能以无限的0或9结尾，从而保证了它的小数表示是唯一的，避免了上述的歧义。

这一段将刚刚证明的关于集合大小的纯数学结论（实数集不可数），应用到计算理论中，得出了一个关于语言和图灵机的惊人推论。

1. “前面的定理对计算理论有着重要的应用。”:
   • 说明定理4.17（实数集不可数）不仅仅是一个数学趣闻，它将成为我们理论体系中的一个关键工具。
2. “它表明有些语言是不可判定的，甚至不是图灵可识别的...”:
   • 提出了一个比 $A_{\mathrm{TM}}$ 的不可判定性更强的结论：甚至存在图灵不可识别的语言。
   • 图灵不可识别 (Turing-unrecognizable): 意味着不存在任何图灵机，能够在该语言的所有成员上停机并接受。对于不属于该语言的字符串，机器可以拒绝或循环；但对于属于该语言的字符串，机器也可能拒绝或循环。这是一个比“不可判定”更强的“不可解”性质。
3. “...原因在于语言是不可数的，而图灵机只有可数个。”:
   • 这是整个论证的核心，一个简单的“鸽笼原理”应用。
   • 语言是不可数的: 所有可能的语言（字符串的集合）形成的集合，其“数量”是不可数的。
   • 图灵机只有可数个: 所有可能的图灵机，其“数量”是可数的。
   • 鸽笼原理 (Pigeonhole Principle): 如果你有 $n$ 个鸽笼和 $m$ 只鸽子，且 $m > n$，那么至少有一个鸽笼里有多于一只鸽子。在这里，语言是“鸽子”，图灵机是“鸽笼”。
4. “因为每台图灵机只能识别一种语言，并且语言的数量多于图灵机的数量，所以有些语言不被任何图灵机识别。”:
   • 将鸽笼原理应用到当前场景：
   • 每个图灵机 ($M$) 对应一个它能识别的语言 ($L(M)$)。我们可以把这看作是把一只叫“$M$”的鸽子放进一个叫“$L(M)$”的鸽笼里。
   • 我们有不可数多只“鸽子”（语言）。
   • 我们只有可数多间“鸽笼”（图灵机）。
   • 因为不可数远大于可数，所以必然有大量的“鸽子”（语言）没有自己的“鸽笼”（图灵机）。
5. “这样的语言是图灵不可识别的，正如我们在以下推论中所述。”:
   • 对这些没有图灵机能识别它们的语言，给出了正式的名称：图灵不可识别。
   • 预告了接下来会有一个正式的推论来总结这个论证。

这个推论是对上一段鸽笼原理论证的详细展开和形式化证明。它分为两大部分：证明图灵机集可数，和证明语言集不可数。

第一部分：证明所有图灵机的集合是可数的

1. “...任何字母表 $\Sigma$ 的所有字符串 $\Sigma^{*}$ 的集是可数的。”:
   • 基础: 任何程序/机器的描述，最终都是一个字符串。所以我们先证明所有可能的字符串是可数的。
   • 证明方法: 按长度排序（字典序）。
   • 长度为 0 的字符串: $\epsilon$
   • 长度为 1 的字符串: 0, 1
   • 长度为 2 的字符串: 00, 01, 10, 11
   • ...
   • 因为每个长度下的字符串数量都是有限的，我们可以把这些有限的组合一块一块地拼接起来，形成一个无限的列表。这就证明了 $\Sigma^*$ 是可数的。
2. “所有图灵机的集是可数的，因为每个图灵机 $M$ 都有一个编码成字符串 $\langle M\rangle$。”:
   • 每个图灵机的设计（状态、转移函数等）都可以用一种标准格式写成一个字符串，即 $\langle M\rangle$。这个字符串属于 $\Sigma^*$。
   • 所有可能的图灵机编码的集合，是所有字符串集合 $\Sigma^*$ 的一个子集。
   • 定理: 可数集的任何子集也都是可数的。（或者有限，或者可数无限）。
   • 因此，所有图灵机的集合是可数的。我们可以想象，在上面那个所有字符串的列表中，我们逐一检查每个字符串，如果它是一个合法的图灵机编码，就把它保留下来，否则就划掉。剩下的就是一个所有图灵机的列表。

第二部分：证明所有语言的集合是不可数的

1. “...所有无限二进制序列的集是不可数的。”:
   • 无限二进制序列: 一个无限长的0和1的序列，如 01101001...。
   • 设这个集合为 $\mathcal{B}$。
   • 证明方法: 使用与证明实数集不可数完全相同的对角化论证。
2. 假设 $\mathcal{B}$ 是可数的，即可以列出所有无限二进制序列 $b_1, b_2, b_3, \dots$。
3. 构造一个新的序列 $b_{new}$，使其第 $i$ 位与 $b_i$ 的第 $i$ 位相反（0变1，1变0）。
4. $b_{new}$ 与列表中的任何一个序列都不同，导出矛盾。
5. 因此 $\mathcal{B}$ 是不可数的。
6. “设 $\mathcal{L}$ 是字母表 $\Sigma$ 上的所有语言的集。我们通过给出与 $\mathcal{B}$ 的一一对应来表明 $\mathcal{L}$ 是不可数的...”:
   • 策略: 证明所有语言的集合 $\mathcal{L}$ 与所有无限二进制序列的集合 $\mathcal{B}$ 大小相同。既然 $\mathcal{B}$ 是不可数的，那么 $\mathcal{L}$ 也必然是不可数的。
7. “设 $\Sigma^{*}=\left\{s_{1}, s_{2}, s_{3}, \ldots\right\}$。”:
   • 我们已经知道所有字符串的集合 $\Sigma^*$ 是可数的，所以我们可以把它排成一个列表 $s_1, s_2, s_3, \dots$。
8. “$\mathcal{L}$ 中的每种语言 $A$ 在 $\mathcal{B}$ 中都有一个唯一的序列。该序列的第 $i$ 位是1，如果 $s_{i} \in A$，如果 $s_{i} \notin A$，则为0，这被称为 $A$ 的特征序列。”:
   • 这是构造一一对应的关键。
   • 对于任何一种语言 $A$ (它本质上是 $\Sigma^*$ 的一个子集)，我们可以构造一个无限二进制序列，称为它的特征序列 (Characteristic Sequence) $\chi_A$。
   • 构造规则: 看着排好序的字符串列表 $s_1, s_2, s_3, \dots$。
   • 如果 $s_1$ 在语言 $A$ 中，$\chi_A$ 的第1位就是1；否则是0。
   • 如果 $s_2$ 在语言 $A$ 中，$\chi_A$ 的第2位就是1；否则是0。
   • ...
   • 如果 $s_i$ 在语言 $A$ 中，$\chi_A$ 的第 $i$ 位就是1；否则是0。
9. 例子:
   • $\Sigma^*$ 的列表: $\epsilon, 0, 1, 00, 01, \dots$
   • 语言 $A$: 所有以0开头的字符串。$A = \{0, 00, 01, \dots\}$
   • 特征序列 $\chi_A$:
   • $s_1 = \epsilon$: 不在 $A$ 中 -> 第1位是 0。
   • $s_2 = 0$: 在 $A$ 中 -> 第2位是 1。
   • $s_3 = 1$: 不在 $A$ 中 -> 第3位是 0。
   • $s_4 = 00$: 在 $A$ 中 -> 第4位是 1。
   • $s_5 = 01$: 在 $A$ 中 -> 第5位是 1。
   • ...
   • 所以 $\chi_A = 01011...$
10. “函数 $f: \mathcal{L} \longrightarrow \mathcal{B}$ ... 是一个一一对应。”:
    • 我们定义一个函数 $f(A) = \chi_A$。
    • 一对一 (单射)?: 是。如果 $A_1$ 和 $A_2$ 是两种不同的语言，那么它们所包含的字符串集合必然不同。这意味着至少存在一个字符串 $s_k$，它在一个语言里而不在另一个里。因此，它们的特征序列 $\chi_{A_1}$ 和 $\chi_{A_2}$ 在第 $k$ 位上必然不同。
    • 满射 (满射)?: 是。对于任何一个无限二进制序列 $b \in \mathcal{B}$，我们都可以构造出一个对应的语言 $A_b$。构造方法是：如果 $b$ 的第 $i$ 位是1，就把字符串 $s_i$ 加入 $A_b$。这样构造出的 $A_b$ 的特征序列正好就是 $b$。
    • 既然是一一对应，且 $\mathcal{B}$ 是不可数的，那么 $\mathcal{L}$ 也是不可数的。

第三部分：结论

1. “因此，我们已经表明所有语言的集不能与所有图灵机的集建立一一对应。”:
   • 语言集: 不可数。
   • 图灵机集: 可数。
   • 一个不可数集和一个可数集之间不可能存在一一对应。
2. “我们得出结论，有些语言不被任何图灵机识别。”:
   • 应用鸽笼原理，得出最终结论。

这是证明 $A_{\mathrm{TM}}$ 不可判定性的核心部分的开始。本段采用反证法，首先清晰地陈述了与待证结论相反的假设。

1. “现在我们准备证明定理4.11，$A_{\mathrm{TM}}$ 语言的不可判定性”:
   • 经过前面关于可数性、不可数性和对角化的漫长铺垫，现在终于回到了本节最初的目标。
2. 公式 $A_{\mathrm{TM}}$:
   • 重申了我们要研究的语言的定义，提醒读者它的构成：所有“图灵机 $M$ 成功处理输入 $w$”的记录 $\langle M, w\rangle$ 组成的集合。
3. “证明：我们假设 $A_{\mathrm{TM}}$ 是可判定的并得到矛盾。”:
   • 明确了证明策略为反证法。
   • 待证结论: $A_{\mathrm{TM}}$ 是不可判定的。
   • 反证假设: $A_{\mathrm{TM}}$ 是可判定的。
4. “假设 $H$ 是 $A_{\mathrm{TM}}$ 的一个判定器。”:
   • 将上述抽象的假设具体化。如果 $A_{\mathrm{TM}}$ 是可判定的，那么根据可判定语言的定义，必然存在一个图灵机，我们称之为 $H$ (Hypothetical，假设的)，它能判定 $A_{\mathrm{TM}}$。
5. “在输入 $\langle M, w\rangle$ 上... 如果 $M$ 接受 $w$，则 $H$ 停机并接受。此外，如果 $M$ 不接受 $w$，则 $H$ 停机并拒绝。”:
   • 详细描述了判定器 $H$ 的完美功能。
   • 关键能力: 对于任何给定的图灵机 $M$ 和输入 $w$，$H$ 都能在有限时间内给出答案。
   • 回答正确:
   • 如果 $M$ 在 $w$ 上最终会接受，$H$ 就输出“接受”。
   • 如果 $M$ 在 $w$ 上最终会拒绝，或者 $M$ 会陷入无限循环，$H$ 都能洞察这一切，并最终停机输出“拒绝”。这就是 $H$ 最神奇的地方：它有能力检测出无限循环！
6. “换句话说，我们假设 $H$ 是一个图灵机，其中...”:
   • 用一个分段函数的形式，更数学化、更精确地总结了 $H$ 的行为。

这一段是对角化证明中至关重要的一步：利用假设存在的判定器 $H$，来构造一个新的、行为怪异的图灵机 $D$ (Diagonal or Devil)。$D$ 的设计充满了“自我指涉”和“唱反调”的意味。

1. “现在我们构造一个以 $H$ 为子程序的新图灵机 $D$。”:
   • 构造 (Construct): 我们正在设计一台新的机器。
   • 子程序 (Subroutine): 我们假设 $H$ 是一台存在的机器，所以我们可以在我们的新机器 $D$ 的设计中“调用”它，就像在编程中调用一个函数一样。$D$ 的内部逻辑包含了一个对 $H$ 的调用。
2. “这个新图灵机调用 $H$ 来判定当 $M$ 的输入是它自己的描述 $\langle M\rangle$ 时 $M$ 会做什么。”:
   • 这是 $D$ 的核心行为，也是“自我指涉”的第一次出现。
   • $D$ 的输入只有一个：一个图灵机 $M$ 的描述 $\langle M\rangle$。
   • $D$ 做的事情是，把这个输入 $\langle M\rangle$ 复制一份，形成一个输入对 $(\langle M\rangle, \langle M\rangle)$。
   • 然后，$D$ 把这个输入对喂给它的子程序 $H$。它是在问 $H$ 一个非常特殊的问题：“嗨，大师H，请帮我看看，如果让机器 $M$ 运行在它自己的描述 $\langle M \rangle$ 上，它会接受吗？”
   • 因为我们假设 $H$ 是万能的，所以 $H$ 总能给出一个“接受”或“拒绝”的答案。
3. “一旦 $D$ 获得此信息，它就会做相反的事情。”:
   • 这是 $D$ 的“捣蛋鬼”或“叛逆”天性的体现。$D$ 完全不关心 $M$ 到底做了什么，它只关心 $H$ 对此的看法，然后跟这个看法反着来。
4. “也就是说，如果 $M$ 接受，它就拒绝；如果 $M$ 不接受，它就接受。”:
   • 更准确地说，应该是：如果 $H$ 的结论是“$M$ 接受 $\langle M \rangle$”，那么 $D$ 就拒绝。如果 $H$ 的结论是“$M$ 不接受 $\langle M \rangle$”，那么 $D$ 就接受。
5. “以下是 $D$ 的描述。”:
   • 给出了 $D$ 的形式化算法描述。
6. "$D=$ ‘在输入 $\langle M\rangle$ 上...’”:
   • 输入: $\langle M \rangle$，一个图灵机的编码。
   • 步骤1: “在输入 $\langle M,\langle M\rangle\rangle$ 上运行 $H$。”
   • $D$ 准备 $H$ 的输入。$H$ 需要两个参数（一个机器，一个输入），$D$ 把自己的唯一输入 $\langle M\rangle$ 同时用作 $H$ 的两个参数。
   • $D$ 启动 $H$ 并等待结果。因为 $H$ 是判定器，所以这一步保证在有限时间内结束。
   • 步骤2: “输出与 $H$ 输出相反的结果。...”
   • $D$ 检查 $H$ 的输出。
   • 如果 $H$ 的输出是“接受”，$D$ 就进入自己的拒绝状态并停机。
   • 如果 $H$ 的输出是“拒绝”，$D$ 就进入自己的接受状态并停机。
   • 重要观察: 因为 $H$ 总是在有限时间内停机，并且 $D$ 在 $H$ 停机后只做一步简单的相反操作，所以 $D$ 本身也是一个判定器！$D$ 对于任何合法的输入 $\langle M \rangle$ 都会在有限时间内停机。

这一段首先安抚读者，解释“程序以自身为输入”这个概念的合理性，然后用一个分段函数精确总结了上一段构造的机器 $D$ 的行为。

1. “不要被在一个机器上运行它自己的描述这种概念所困扰！”:
   • 作者预见到读者可能会觉得这个概念很奇怪、很抽象，甚至有点“黑魔法”的感觉，所以主动站出来进行安抚和解释。
2. “这类似于运行一个程序并以它自己作为输入，这在实践中偶尔会发生。”:
   • 将抽象的理论概念与现实中的编程实践联系起来。
   • 任何程序，其本质都是存储在磁盘上的一个文件，一串二进制数据。因此，任何程序都可以像读取普通文本文件或图片文件一样，去读取另一个程序文件，包括它自己的文件。
3. “例如，编译器是一个翻译其他程序的程序。一个用 Python 编写的 Python 编译器，用它自己作为输入来运行也是有意义的。”:
   • 给出了一个非常经典和具体的例子：自举编译器 (Bootstrapping a compiler)。
   • 编译器 (Compiler): 一个将高级语言代码（如Python源码）翻译成低级语言代码（如机器码）的程序。
   • 场景: 假设你用Python语言写了一个新的、更牛的Python编译器，我们称之为 NewPythonCompiler.py。
   • 自举过程:
   • 这个过程就完美地诠释了“一个程序以自己为输入”的现实意义。
4. “总而言之，”:
   • 在消除了读者的疑虑之后，回到主线，对机器 $D$ 的功能给出一个最终的、简洁的数学描述。

这是整个证明的高潮和终点。通过将精心设计的“捣蛋鬼”机器 $D$ 应用于其自身，我们引爆了逻辑矛盾。

1. “当我们用它自己的描述 $\langle D\rangle$ 作为输入来运行 $D$ 时会发生什么？”:
   • 这是最关键的提问，是对角化论证的“将军”时刻。
   • 我们已经接受了“机器可以以自身描述为输入”。
   • $D$ 本身也是一个图灵机。因此，它的描述 $\langle D \rangle$ 是一个合法的字符串，可以作为任何图灵机的输入，当然也包括 $D$ 自己。
   • 我们现在就把 $D$ 的“照片” $\langle D \rangle$ 喂给 $D$ 自己。
2. “在这种情况下，我们得到...”:
   • 我们只需将上一段总结的 $D$ 的行为通式中的“$M$”替换为“$D$”，就可以得到 $D$ 在输入 $\langle D \rangle$ 时的行为。
   • $D$ 的通式是：$D(\langle M\rangle)$ 接受 $\iff$ $M$ 不接受 $\langle M \rangle$。
   • 将 $M$ 换成 $D$：$D(\langle D\rangle)$ 接受 $\iff$ $D$ 不接受 $\langle D \rangle$。
   • 这就得到了下面这个惊人的公式。

这一段是对刚刚完成的证明进行了一次简洁的复盘，提炼出了最核心的逻辑步骤和关系。

1. “让我们回顾一下这个证明的步骤。”:
   • 表明这是一个总结性的段落，帮助读者巩固理解。
2. “假设图灵机 $H$ 判定 $A_{\mathrm{TM}}$。”:
   • 步骤1: 整个反证法的起点，即假设存在一个能解决停机问题的判定器 $H$。
3. “使用 $H$ 构建一个图灵机 $D$，它接受输入 $\langle M\rangle$，其中 $D$ 接受其输入 $\langle M\rangle$ 当且仅当 $M$ 不接受其输入 $\langle M\rangle$。”:
   • 步骤2: 利用 $H$ 作为工具，构造出“捣蛋鬼”机器 $D$。这里对 $D$ 的行为描述得非常精确：$D(\langle M\rangle)$ 的结果与 $M(\langle M\rangle)$ 的结果正好相反。
4. “最后，在 $D$ 上运行 $D$ 本身。”:
   • 步骤3: 触发悖论的关键动作，让 $D$ 对自己进行操作。
5. “因此，这些机器采取以下行动，最后一行是矛盾。”:
   • 下面三行是对三台机器（$H$, $D$, 和作用于自身的 $D$）行为的最终概括。
6. “- $H$ 接受 $\langle M, w\rangle$ 当且仅当 $M$ 接受 $w$。”:
   • 这是对判定器 $H$ 功能的定义。它是“诚实的预言家”。
7. “- $D$ 拒绝 $\langle M\rangle$ 当且仅当 $M$ 接受 $\langle M\rangle$。”:
   • 这是对机器 $D$ 行为的概括。注意，这里用“拒绝”来描述，它等价于前文的“如果 $M$ 接受 $\langle M \rangle$ 则拒绝，如果 $M$ 不接受 $\langle M \rangle$ 则接受”。如果 $M$ 接受， $D$ 就拒绝；如果 $M$ 不接受，$D$ 才接受。所以这行描述是准确的。它是“唱反调者”。
8. “- $D$ 拒绝 $\langle D\rangle$ 当且仅当 $D$ 接受 $\langle D\rangle$。”:
   • 将上一行的通用规则中的 $M$ 特例化为 $D$ 本身，直接得到了这个赤裸裸的矛盾。这个陈述在逻辑上是荒谬的，就像说“天下雨当且仅当天下不下雨”。

这一段通过引入一个二维表格，直观地揭示了刚刚完成的证明与康托尔对角化论证在结构上的相似性。

1. “定理4.11的证明中的对角化在哪里？”:
   • 一个设问。到目前为止，我们只看到了逻辑推导，并没有像之前证明实数不可数时那样明显地构造一个“沿着对角线”不同的对象。本段就是要揭示这个隐藏的对角化结构。
2. “当你检查图灵机 $H$ 和 $D$ 的行为表时，它就会变得显而易见。”:
   • 答案在于将机器的行为可视化。
3. “在这些表中，我们列出了所有图灵机（ $M_{1}, M_{2}, \ldots$）在行中，以及它们的所有描述（ $\left\langle M_{1}\right\rangle,\left\langle M_{2}\right\rangle, \ldots$）在列中。”:
   • 构建表格:
   • 行: 代表所有的图灵机。因为我们证明了图灵机集是可数的，所以我们可以将它们排成一个列表 $M_1, M_2, M_3, \dots$。
   • 列: 代表所有图灵机的编码。这些也是可数的，我们按与行相同的顺序列出 $\langle M_1 \rangle, \langle M_2 \rangle, \langle M_3 \rangle, \dots$。
   • 这个表格是一个无限大的方阵。
4. “条目说明给定行中的机器是否接受给定列中的输入。”:
   • 表格内容: 表格中第 $i$ 行、第 $j$ 列的条目，记录的是图灵机 $M_i$ 在输入 $\langle M_j \rangle$ 上的运行结果。
   • 这个表格描绘了一个“所有图灵机相互作用”的全景图。
5. “如果机器接受输入，则条目为“接受”，如果它拒绝或循环，则为空白。”:
   • 定义了表格条目的填写规则。这是 $M_i$ 的真实行为。
6. “我们编造了下图中的条目来说明这个想法。”:
   • 图4.19 展示了这个表格的一个假想的、具体的样子。
   • 解读图4.19:
   • (行1, 列1) 是 accept: 意味着 $M_1$ 接受输入 $\langle M_1 \rangle$。
   • (行1, 列2) 是 空白: 意味着 $M_1$ 不接受输入 $\langle M_2 \rangle$ (拒绝或循环)。
   • (行2, 列1) 是 accept: 意味着 $M_2$ 接受输入 $\langle M_1 \rangle$。
7. 表格的对角线:
   • 这张表的主对角线（从左上到右下）上的条目分别是：
   • (行1, 列1): $M_1$ 在输入 $\langle M_1 \rangle$ 上的行为。
   • (行2, 列2): $M_2$ 在输入 $\langle M_2 \rangle$ 上的行为。
   • (行 $i$, 列 $i$): $M_i$ 在输入 $\langle M_i \rangle$ 上的行为。
   • 对角线上的行为，正是机器“以自身描述为输入”时的行为，这是我们构造 $D$ 的关键所在。

这一段展示了假设存在的判定器 $H$ 会生成什么样的行为表格。

1. “在下图中，条目是在与图4.19对应的输入上运行 $H$ 的结果。”:
   • 图4.20 与 图4.19 的行列定义完全相同，但条目的含义不同。
   • 图4.19 的条目是“真实结果”（$M_i$ 对 $\langle M_j \rangle$ 的实际行为，可能是 accept 或 空白(拒绝/循环)）。
   • 图4.20 的条目是“判定器 $H$ 的预测结果”（$H$ 对输入 $\langle M_i, \langle M_j \rangle \rangle$ 的输出，只可能是 accept 或 reject）。
2. “因此，如果 $M_{3}$ 不接受输入 $\left\langle M_{2}\right\rangle$，则 $M_{3}$ 行和 $\left\langle M_{2}\right\rangle$ 列的条目为拒绝...”:
   • 解释了两个表格的关系。因为我们假设 $H$ 是一个完美的判定器，所以 $H$ 的输出必须与真实结果完全一致。
   • $H$ 接受 $\langle M_i, \langle M_j \rangle \rangle \iff M_i$ 接受 $\langle M_j \rangle$。
   • $H$ 拒绝 $\langle M_i, \langle M_j \rangle \rangle \iff M_i$ 不接受 $\langle M_j \rangle$ (包括拒绝或循环)。
   • 所以，图4.20 本质上是图4.19 的“填空版”。所有 空白 的地方都被 $H$ 准确地识别并填上了 reject。
3. 图4.20的解读:
   • 这是一个“完美”的表格，没有任何空白。每一格都有一个确定的 accept 或 reject 答案。
   • 它的存在，完全建立在“$H$ 存在”这个假设之上。
   • 对角线上的值现在是：
   • accept (在 (1,1) 处): $H$ 预测 $M_1$ 接受 $\langle M_1 \rangle$。
   • accept (在 (2,2) 处): $H$ 预测 $M_2$ 接受 $\langle M_2 \rangle$。
   • reject (在 (3,3) 处): $H$ 预测 $M_3$ 不接受 $\langle M_3 \rangle$。
   • reject (在 (4,4) 处): $H$ 预测 $M_4$ 不接受 $\langle M_4 \rangle$。

这是整个对角化可视化论证的最后一步，图穷匕见，矛盾被清晰地展示在表格中。

1. “在下图中，我们将 $D$ 添加到图4.20中。”:
   • 图4.21 是基于图4.20的扩展。
2. “根据我们的假设，$H$ 是一个图灵机，$D$ 也是。因此，它必须出现在所有图灵机的列表 $M_{1}, M_{2}, \ldots$ 中。”:
   • 这是至关重要的一步。既然 $D$ 是一个合法的图灵机，那么它必然是图灵机列表中的一员。
   • 假设 $D$ 就是列表中的第 $k$ 个图灵机 $M_k$。那么表格中就应该有一行是“$D$ 行”，也有一列是“$\langle D \rangle$ 列”。
3. “请注意， $D$ 计算的是对角线条目的相反。”:
   • 回顾 $D$ 的定义：$D(\langle M_i \rangle)$ 的结果是 $H(\langle M_i, \langle M_i \rangle \rangle)$ 的相反。
   • $H(\langle M_i, \langle M_i \rangle \rangle)$ 正是图4.20中对角线上第 $i$ 个条目的值。
   • 所以，$D$ 的行为（即 $D$ 这一行的数据）是通过“反转”图4.20的对角线来生成的。
   • 让我们来生成 $D$ 行：
   • 对角线第1个值是 accept -> $D$ 行第1列的值是 reject。
   • 对角线第2个值是 accept -> $D$ 行第2列的值是 reject。
   • 对角线第3个值是 reject -> $D$ 行第3列的值是 accept。
   • 对角线第4个值是 reject -> $D$ 行第4列的值是 accept。
   • ... 这就是图4.21中 $D$ 行的由来。
4. “矛盾发生在问号处，该处的条目必须与自身相反。”:
   • 问号在哪里？它在 $D$ 行和 $\langle D \rangle$ 列的交叉点。
   • 这个问号代表的值是 $H(\langle D, \langle D \rangle \rangle)$，也就是判定器 $H$ 对 $D$ 在自己描述上运行的预测结果。
   • 让我们来分析这个问号：
   • 从 $D$ 行的定义来看: $D$ 行的第 $D$ 列（即问号所在的这一格），是对角线上第 $D$ 个元素的反面。而对角线上第 $D$ 个元素，正是问号自己！所以，问号的值 = 非 问号的值。
   • 从 $D$ 机器本身的行为来看: 问号的值，是 $H$ 对 $D(\langle D \rangle)$ 的预测。而 $D(\langle D \rangle)$ 的行为，被定义为 $H(\langle D, \langle D \rangle \rangle)$ （即问号的值）的相反。所以，$D$ 的真实行为是问号的反面。因为 $H$ 必须做出正确的预测，所以问号必须等于 $D$ 的真实行为，也就是问号必须等于它自己的反面。
   • 结论: 无论从哪个角度看，问号所在格子的值都必须等于它自己的反面 (accept iff reject)。这是一个尖锐的、无法回避的逻辑矛盾。

这一段引入了计算理论中又一个重要的语言类别——图灵不可识别语言，并提出了一个关键定理，将可判定性与可识别性联系起来。

1. “在上一节中，我们展示了一种不可判定的语言——即 $A_{\text {TM }}$。”:
   • 回顾已知结论：$A_{\text{TM}}$ 是我们第一个证明了的不可判定语言。
2. “现在我们展示一种甚至不是图灵可识别的语言。”:
   • 提出新的、更高的目标：寻找一个连图灵可识别都做不到的语言。
   • 这标志着我们进入了“不可解问题”的更深层次。
   • 回顾:
   • 可判定: 存在一个图灵机，对所有输入都停机并给出“是”或“否”。
   • 可识别: 存在一个图灵机，对所有“是”的输入能停机并回答“是”，对“否”的输入可以回答“否”或无限循环。
   • 不可识别: 不存在任何图灵机能做到上述“可识别”的要求。
3. “请注意， $A_{\text {TM }}$ 不能用于此目的，因为我们已经证明 $A_{\text {TM }}$ 是图灵可识别的”:
   • 排除了一个可能的错误想法。$A_{\text{TM}}$ 虽然不可判定，但它属于“半可解”的图灵可识别语言类。我们需要找一个比它“更难”的语言。
4. “以下定理表明，如果一种语言及其补集都是图灵可识别的，那么该语言就是可判定的。”:
   • 这是本段最重要的部分，提出了一个核心定理（定理4.22）。
   • 补集 (Complement): 对于一个定义在字母表 $\Sigma^*$ 上的语言 $L$，它的补集 $\bar{L}$ 包含所有在 $\Sigma^*$ 中但不在 $L$ 中的字符串。$\bar{L} = \Sigma^* - L$。
   • 定理内容:
   • 设语言为 $A$。
   • 条件1: $A$ 是图灵可识别的。
   • 条件2: $\bar{A}$ (A的补集) 也是图灵可识别的。
   • 结论: 如果这两个条件同时满足，那么 $A$ 一定是可判定的。
5. “因此，对于任何不可判定的语言，它或它的补集都不是图灵可识别的。”:
   • 这是上述定理的逆否命题，逻辑上等价。
   • 定理 (原命题): (A可识别 AND $\bar{A}$可识别) $\implies$ A可判定。
   • 逆否命题: (A不可判定) $\implies$ NOT (A可识别 AND $\bar{A}$可识别)。
   • NOT (P AND Q) 等价于 (NOT P) OR (NOT Q)。
   • 所以逆否命题展开就是：如果 $A$ 是不可判定的，那么要么 $A$ 是不可识别的，要么 $\bar{A}$ 是不可识别的（或者两者都是）。
   • 这个推论给我们提供了一条寻找不可识别语言的明确路径：找到一个不可判定的语言，然后检查它和它的补集。
6. **“

回想一下，一种语言的补集是由所有不属于该语言的字符串组成的语言。如果一种语言是图灵可识别语言的补集，我们称之为协同图灵可识别的。”**:

• 协同图灵可识别 (co-Turing-recognizable): 这是一个新的术语定义。
• 语言 $L$ 是协同图灵可识别的 $\iff$ 其补集 $\bar{L}$ 是图灵可识别的。
• 直观意义:
• 对于一个可识别语言，我们能确切地验证“是”的答案（机器停机接受）。
• 对于一个协同图灵可识别语言，我们能确切地验证“否”的答案。因为要判断一个字符串 $w$ 是否属于 $L$，我们可以把它喂给 $\bar{L}$ 的识别器。如果这个识别器接受了 $w$，我们就百分之百确定 $w \in \bar{L}$，从而百分之百确定 $w \notin L$。
• 因此，定理4.22可以被重新表述为：一个语言是可判定的，当且仅当它既是图灵可识别的，又是协同图灵可识别的。

这一段给出了定理4.22的完整证明。证明分为两个方向。

第一部分：证明 "如果 $A$ 可判定，则 $A$ 和 $\bar{A}$ 都可识别"

1. “证明：我们需要证明两个方向。”:
   • “当且仅当” (if and only if) 的证明标准，需要分别证明 P -> Q 和 Q -> P。
2. “首先，如果 $A$ 是可判定的...”:
   • 这是第一个方向的证明（从“可判定”推向“可识别且协同可识别”）。
   • 假设: $A$ 是一个可判定语言。这意味着存在一个判定器 $M_A$，它在任何输入上都停机，并且接受 $A$ 中的字符串，拒绝不在 $A$ 中的字符串。
3. “...我们可以很容易地看到 $A$ 和它的补集 $\bar{A}$ 都是图灵可识别的。”:
   • 证明 $A$ 可识别: 因为 $M_A$ 是一个判定器，它本身就满足识别器的定义（对属于A的字符串停机并接受）。所以 $A$ 是图灵可识别的。
   • 证明 $\bar{A}$ 可识别: 我们可以基于 $M_A$ 构造一个 $\bar{A}$ 的判定器 $M_{\bar{A}}$。$M_{\bar{A}}$ 的逻辑是：在输入 $w$ 上运行 $M_A$；如果 $M_A$ 接受，则 $M_{\bar{A}}$ 拒绝；如果 $M_A$ 拒绝，则 $M_{\bar{A}}$ 接受。因为 $M_A$ 总停机，所以 $M_{\bar{A}}$ 也总停机，它是一个判定器。既然 $\bar{A}$ 是可判定的，它自然也是图灵可识别的。
   • 结论: 这个方向的证明比较直接，因为可判定性是比可识别性更强的性质。

第二部分：证明 "如果 $A$ 和 $\bar{A}$ 都可识别，则 $A$ 可判定"

1. “另一方面，如果 $A$ 和 $\bar{A}$ 都是图灵可识别的...”:
   • 这是更关键、更具构造性的第二个方向。
   • 假设:
   • $A$ 是图灵可识别的，意味着存在一个识别器 $M_1$。
   • $\bar{A}$ 也是图灵可识别的，意味着存在一个识别器 $M_2$。
2. “以下图灵机 $M$ 是 $A$ 的判定器。”:
   • 目标: 利用 $M_1$ 和 $M_2$ 作为“零件”，来构造一个更强大的机器 $M$，并证明 $M$ 是 $A$ 的判定器。
3. "$M=$ ‘在输入 $w$ 上...’”:
   • 描述了新机器 $M$ 的算法。
   • 步骤1: “在输入 $w$ 上并行运行 $M_{1}$ 和 $M_{2}$。”:
   • 这是整个构造的核心技巧。我们不能先运行 $M_1$ 再运行 $M_2$，因为如果 $w \notin A$， $M_1$ 可能会无限循环，导致我们永远没有机会运行 $M_2$。
   • 并行 (In parallel): 图灵机是单线程的，如何实现“并行”？通过轮流模拟 (Dovetailing)。
   • $M$ 的磁带被分成两部分（或使用两条磁带）。
   • 在第一条磁带上，模拟 $M_1$ 在 $w$ 上的一步计算。
   • 在第二条磁带上，模拟 $M_2$ 在 $w$ 上的一步计算。
   • 再回到第一条磁带，模拟 $M_1$ 的第二步。
   • 再回到第二条磁带，模拟 $M_2$ 的第二步。
   • ...如此交替进行。

• 步骤2: “如果 $M_{1}$ 接受，则接受；如果 $M_{2}$ 接受，则拒绝。”:
• 在并行模拟的过程中，$M$ 不断检查 $M_1$ 和 $M_2$ 的状态。
• 只要发现 $M_1$ 进入了接受状态，$M$ 就立刻停止整个模拟，自己进入接受状态并停机。
• 只要发现 $M_2$ 进入了接受状态，$M$ 就立刻停止整个模拟，自己进入拒绝状态并停机。（因为 $M_2$ 接受 $w$ 意味着 $w \in \bar{A}$，也就是 $w \notin A$）。

1. “现在我们表明 $M$ 判定 $A$。”:
   • 验证 $M$ 的功能:
   • M是否总停机?:
   • 任何一个字符串 $w$，要么属于 $A$，要么属于 $\bar{A}$。
   • 如果 $w \in A$，$M_1$ 根据定义保证会在有限步骤后接受。
   • 如果 $w \in \bar{A}$，$M_2$ 根据定义保证会在有限步骤后接受。
   • 所以，对于任何输入 $w$，两个模拟中必然有一个会在有限时间内结束。一旦有一个结束，$M$ 就会停机。
   • 结论：$M$ 总是在有限时间内停机，所以它是一个判定器。
   • M是否正确判定A?:
   • 如果 $w \in A$，$M_1$ 会先接受（$M_2$ 可能循环或拒绝），此时 $M$ 接受 $w$。正确。
   • 如果 $w \notin A$ (即 $w \in \bar{A}$)，$M_2$ 会先接受（$M_1$ 可能循环或拒绝），此时 $M$ 拒绝 $w$。正确。
   • 最终结论: 我们成功地构造了一个 $A$ 的判定器 $M$。因此，如果一个语言和它的补集都是图灵可识别的，那么这个语言就是可判定的。证明完毕。

这是本节的收尾，利用刚刚证明的定理4.22，轻松地推导出了第一个图灵不可识别语言的具体例子。

1. “$\overline{A_{\text {TM }}}$ 是图灵不可识别的。”:
   • 这是推论4.23的陈述。
   • $\overline{A_{\text {TM }}}$ 是 $A_{\text {TM }}$ 的补集。它是由所有满足“图灵机 $M$ 不接受字符串 $w$”的编码对 $\langle M, w \rangle$ 组成的集合。
2. “证明：我们知道 $A_{\text {TM }}$ 是图灵可识别的。”:
   • 前提1: 这是我们在本节开头部分就已经证明了的。我们构造了通用图灵机 $U$ 作为 $A_{\text {TM }}$ 的识别器。
3. “如果 $\overline{A_{\text {TM }}}$ 也是图灵可识别的...”:
   • 前提2 (反证法的假设): 我们假设 $\overline{A_{\text {TM }}}$ 是图灵可识别的。
4. “...那么 $A_{\text {TM }}$ 将是可判定的。”:
   • 应用定理4.22: 定理4.22说：如果一个语言($A_{\text {TM }}$)和它的补集($\overline{A_{\text {TM }}}$)都是图灵可识别的，那么这个语言($A_{\text {TM }}$)就是可判定的。
   • 基于前提1和前提2，我们直接应用这个定理，得出结论：$A_{\text {TM }}$ 是可判定的。
5. “定理4.11告诉我们 $A_{\text {TM }}$ 是不可判定的...”:
   • 矛盾来源: 我们刚刚推导出的结论“$A_{\text {TM }}$ 是可判定的”，与本节的核心定理4.11“$A_{\text {TM }}$ 是不可判定的”发生了直接的、尖锐的矛盾。
6. “...所以 $\overline{A_{\mathrm{TM}}}$ 必然不是图灵可识别的。”:
   • 结论: 既然我们的推导导致了矛盾，那么一定是某个前提出了问题。
   • 前提1“$A_{\text {TM }}$ 是图灵可识别的”是我们已经证明了的事实，没有问题。
   • 定理4.22也是我们刚刚证明了的，没有问题。
   • 那么问题只能出在前提2，即我们的反证法假设“$\overline{A_{\text {TM }}}$ 是图灵可识别的”上。
   • 这个假设必须是错误的。
   • 因此，$\overline{A_{\text {TM }}}$ 必然不是图灵可识别的。证明完毕。

首先，我们需要分析给定的DFA $M$。

• 状态: $\{q_1, q_2\}$
• 起始状态: $q_1$
• 接受状态: $\{q_2\}$
• 字母表: $\{0, 1\}$
• 转移函数:
• $\delta(q_1, 0) = q_1$
• $\delta(q_1, 1) = q_2$
• $\delta(q_2, 0) = q_1$
• $\delta(q_2, 1) = q_2$

这个DFA接受什么样的语言？

• 要想到达接受状态 $q_2$，必须输入一个 '1'。
• 一旦到达 $q_2$，只要后续输入是 '1'，就会停留在 $q_2$。
• 如果从 $q_2$ 输入一个 '0'，会回到 $q_1$。
• 因此，这个DFA接受所有以 '1' 结尾的字符串。$L(M) = \{w \mid w \text{ ends with a 1}\}$。

现在我们逐一回答问题。

a. $\langle M, 0100\rangle \in A_{\mathrm{DFA}}$ 吗？

• 问题含义: 判断DFA $M$ 是否接受字符串 "0100"。
• 模拟运行: