Lecture 13: Computability（可计算性）

目录 · ← l13 · l15 →

Lecture 13: Computability（可计算性）

概述

上一讲（Lecture 12）我们证明了程序可数、函数不可数，从而知道”存在无法由任何程序计算的问题”。但那个证明是非构造性的：它指不出到底是哪一个问题不可计算。本讲补上这一刀——我们把一个具体的、日常到不能再日常的问题抓出来示众：停机问题 (the Halting Problem)。给定程序 $P$ 与输入 $x$，能否判断 $P(x)$ 最终会不会停下来？Turing 在 1936 年证明：不能，而且不是”还没找到算法”，是数学上不存在这样的算法。整个证明只用两样工具：（1）自指 (self-reference)——程序本身也是字符串，可以作为另一个程序的输入；（2）对角线论证——和上一讲打倒实数用的是同一个手势。最后我们把这一招推广成两项通用技术：可判定 vs. 可识别 (decidable vs. recognizable) 的区分，以及归约 (reduction)。

核心概念的直观解释

自指 (Self-Reference)

• 定义：一个陈述、程序或公式如果指向自身（引用自己的内容、自己的代码、或自己的编号），就称为自指的。
• 直观解释（”它是什么意思？”）：自指是”照镜子”。日常语言里它产生悖论（”这句话是假的”）；在计算机里它产生强大的构造能力（程序可以分析自己）。为什么计算机里自指是合法的？因为程序和数据在物理上是同一种东西——都是比特串。一台计算机不区分”这是一段代码”还是”这是一份数据”，区别只在如何解释 (interpret) 这串比特。所以完全可以把一个程序的源码当作另一个程序的输入传给对方，甚至可以把它传给它自己。
• 具体示例：Halt(P, x) 中把 $P$ 当数据传入；Halt(P, P) 中把 $P$ 同时当程序和输入。这一步”看起来很怪”但完全合法，因为 $P$ 是一个比特串，字符串当然可以作为字符串的输入。

Quine（自打印程序）

• 定义：一个不读取任何输入、运行后输出自己的完整源代码的程序，称为 quine。（名字来自逻辑学家 Willard Van Orman Quine。）
• 直观解释：如果一段程序能输出自己，那么”程序的代码”和”程序产生的数据”之间就没有了界限。用自然语言可以做出这个魔术：

  版本 1（失败）：
    指令：  打印下面这句话：
            "打印下面这句话："
    输出：  打印下面这句话：
    ✗ 少了引号那一行，输出 ≠ 指令本身（指令有两行，输出只有一行）
  
  版本 2（失败）：
    指令：  把下面这句话打印两次：
            "把下面这句话打印两次："
    输出：  把下面这句话打印两次：
            把下面这句话打印两次：
    ✗ 长度对了，但第二行缺引号
  
  版本 3（成功）：
    指令：  把下面这句话打印两次，第二次带引号：
            "把下面这句话打印两次，第二次带引号："
    输出：  把下面这句话打印两次，第二次带引号：
            "把下面这句话打印两次，第二次带引号："
    ✓ 输出与指令逐字相同！
  

  关键在版本 3 的措辞：”第二次带引号”。它让程序同时输出”自己的指令部分”和”自己的数据部分”，两者拼起来恰好是完整的自己。

• 具体示例（真正的伪代码 quine）：官方 Note 给的极简伪代码是

  (Quine "s")
      (s "s")
  
  含义：程序 Quine 接收一个字符串 s，输出 (s "s") 这个调用式本身（把 s 当程序跑在 s 自己身上）。
  
  执行 (Quine "Quine")：
      Quine 收到 s = "Quine"，于是输出 (Quine "Quine")  ——正是刚才那条指令！
  

  这就是”自打印”的最小骨架：程序里没有写死自己的源码，而是写了一个”把自己名字代入自己”的模板，代入后恰好生成自己。

递归定理 (Recursion Theorem)

• 定义：设 $P(x,y)$ 是任意程序。则存在程序 $Q(x)$，使得对一切 $x$， \(Q(x)=P(x,Q),\) 其中第二个参数传入的是 $Q$ 自身的描述（源码）。
• 直观解释：递归定理说任何程序都可以被改造成”有自我意识”的版本——它在运行时能拿到自己的源码，就像人在做决定时能”想到自己正在思考”。它是 quine 存在性的通用保证：取 $P(x,y)=y$（忽略 $x$ 直接输出 $y$），则 $Q(x)=Q$，即 $Q$ 输出自己的源码 = quine。所以”任何编程语言里都能写 quine”不是巧合，而是定理。
• 具体示例：上面那个 (Quine "s") / (s "s") 就是递归定理的一个具体实现：它把”要打印的字符串”作为参数 $s$ 传进来，输出的 (s "s") 就是”$s$ 跑在 $s$ 自己身上”。$Q$ 的行为依赖于自己的描述，这正是 $Q(x)=P(x,Q)$ 的形式。

停机问题 (The Halting Problem)

• 定义：停机问题是如下判定问题：给定程序 $P$ 的源码与输入 $x$，判断 $P$ 在 $x$ 上运行是否会在有限步内终止（halts），还是会永远运行下去（loops）。
• 直观解释：这是编译器最想要的能力——如果编译器能预知”这段代码会不会死循环”，它就能警告程序员。这也是数学家最想要的能力——很多数学猜想（如哥德巴赫猜想）都可以改写成”某程序是否停机”，从而”判断停机”等价于”证明数学定理”。但 Turing 证明这个能力根本不可能存在：没有任何程序能对所有 $(P,x)$ 都给出正确答案。
• 具体示例：有些程序明显停机（x = 3+4 一行就结束），有些明显不停机（while(true){}）。真正难的是那些”行为复杂”的程序（比如”搜索最小的奇完全数，找到就停”——至今无人知道它会不会停）。停机问题的不可判定性说的是：不存在一个通用算法同时搞定所有情况，而不是”所有判断都做不到”（详见常见误区第 1 条）。

可判定 (Decidable) 与 可识别 (Recognizable)

• 定义：设 $L\subseteq\{0,1\}^$ 是一个语言（问题）。记 $\bar L=\{0,1\}^\setminus L$ 为它的补集 (complement)。
  • $L$ 是可判定的 (decidable)：存在程序 $M$，对每个输入 $w\in\{0,1\}^*$，$M(w)$ 都在有限步内终止，且输出 yes 当 $w\in L$、输出 no 当 $w\notin L$。（$M$ 是 $L$ 的判定器 (decider)，永远给正确答案，从不死循环。）
  • $L$ 是可识别的 (recognizable)（又称递归可枚举 / recursively enumerable）：存在程序 $M$，使得对每个 $w$：若 $w\in L$，则 $M(w)$ 在有限步内终止并输出 yes；若 $w\notin L$，则 $M(w)$ 可以永远运行下去（也可以输出 no，但不作要求）。
• 直观解释（”它是什么意思？”）：把判定问题想成”验票”。可判定 = 有一个尽职的验票员，任何票给他，他都当场给出”真/假”，绝不含糊。可识别 = 有一个”半尽职”的验票员：票是真的他一定认出来（等一会儿总会有结果）；票是假的，他可能永远举着票看下去，不给你任何答复。所以可识别是更弱的要求：它只保证”能确认 yes”，不保证”能确认 no”。
• 具体示例：$L_{\text{HALT}}=\{\langle P,x\rangle:P(x)\text{ 停机}\}$。直觉上它可识别：拿到 $\langle P,x\rangle$ 就用模拟器一步步跑 $P(x)$；若它真停机，跑有限步后我们就看到了，立刻输出 yes。但它不可判定（稍后证明），而且它的补贴 $\bar L_{\text{HALT}}$ 根本不可识别。

归约 (Reduction)

• 定义：设 $A,B$ 是两个问题。若”给定能解 $B$ 的算法，我能构造出解 $A$ 的算法”，则称 $A$ 归约到 $B$，记 $A\le B$（读作”$A$ 不比 $B$ 难多少”）。
• 直观解释：这是“难度传递”。它的用法有两种方向，务必要分清：
  • 正向用：若 $A\le B$ 且 $A$ 可解，则 $B$ 可解（”简单问题归约到难问题，难问题也简单了”——这是证明可解性的方向）。
  • 反向用（本讲的主力）：若 $A\le B$ 且 $A$ 不可解，则 $B$ 也不可解（”连简单问题都搞不定，难问题更别想”——这是证明不可解性的方向）。具体地说：假设 $B$ 有判定器，用它当子程序构造出 $A$ 的判定器，这就矛盾了。
• 具体示例：本讲会证明”通用停机问题 $\le$ 简单停机问题（$P$ 是否在输入 $0$ 上停机）”，从而用”通用停机问题不可判定”推出”简单停机问题也不可判定”。

完整证明与推导（核心）

定理 13.1（说谎者悖论与 Barber 悖论：自指的悖论结构）

定理 13.1：下列两个陈述都是自指悖论 (self-referential paradox)：它们既不能为真，也不能为假。

• 说谎者悖论 (Liar’s Paradox)：$S=$”这句话是假的。”
• Barber 悖论 (Barber’s Paradox)：某村唯一的理发师宣布 $B=$”我给且只给所有不给自己刮胡子的人刮胡子。”

证明策略：分情形穷举 + 反证。每个悖论都只有两种可能（真/假，或刮/不刮），逐一分析，得出两种情形都导回自己的反面。这个证明的意义不在于它有多难，而在于它把”自指如何制造矛盾”的机械结构暴露出来——下一节我们会把这个结构逐字搬进程序世界。

逐步推导：

第一步（先看一个”不是悖论”的自指句）：”所有克里特岛人都是说谎者”，说这话的人正是一个克里特岛人。这句不是真悖论：若它为真，则该克里特人在说谎，于是它为假——这是一条有效的反驳，说明它只能是假。而它为假时毫无矛盾（”并非所有克里特岛人都说谎”完全合理）。所以它只排除了一种情形，不构成循环。

第二步（说谎者悖论的真悖论性）：令 $S=$”$S$ 是假的”。

• 情形 A：$S$ 为真。既然 $S$ 为真，那么 $S$ 所断言的内容就是事实；而 $S$ 断言的内容正是”$S$ 是假的”。所以 $S$ 为假。这是一个矛盾（$S$ 既真又假）。
• 情形 B：$S$ 为假。既然 $S$ 为假，那么 $S$ 所断言的内容不成立；而 $S$ 断言的是”$S$ 是假的”，其否定是”$S$ 是真的”。所以 $S$ 为真。这也是矛盾（$S$ 既假又真）。

两种情形都矛盾，所以 $S$ 既不能为真也不能为假。用真值表把机制摊开（$T(S)$ 表示”$S$ 为真”）：

  ┌───────────────┬──────────────────────────┬──────────────┬────────────┐
  │ 假设          │ 由该假设得到的事实        │ 事实的后果    │ 结论       │
  ├───────────────┼──────────────────────────┼──────────────┼────────────┤
  │ T(S) = 真     │ S 的内容"¬T(S)"成立      │ T(S) = 假    │ 矛盾       │
  │ T(S) = 假     │ S 的内容"¬T(S)"不成立    │ T(S) = 真    │ 矛盾       │
  └───────────────┴──────────────────────────┴──────────────┴────────────┘
         ↑ 两种假设都被自己的推论反驳 ⇒ 无解（不是"很难判断"，而是"没有真值可赋"）

  一句话：T(S) 的真值方程是  T(S) = ¬T(S)  ——没有任何布尔值能满足它。

第三步（Barber 悖论）：村中只有一位理发师 $b$，且他宣布 $B=$”我给且只给所有不给自己刮胡子的人刮胡子”。换成一个精确的数学命题：对村中每个男人 $m$， \(b\text{ 给 }m\text{ 刮胡子}\quad\Longleftrightarrow\quad m\text{ 不给自己刮胡子}.\qquad(\star)\) 现在问：$b$ 给自己刮胡子吗？同样只有两种情形：

• 情形 A：$b$ 给自己刮胡子。取 $m=b$ 代入 $(\star)$ 的左端——左端成立（$b$ 给 $b$ 刮）。由 $(\star)$ 知右端也必须成立，即”$b$ 不给自己刮胡子”。矛盾。
• 情形 B：$b$ 不给自己刮胡子。取 $m=b$ 代入 $(\star)$ 的右端——右端成立（$b$ 不给自己刮）。由 $(\star)$ 知左端也必须成立，即”$b$ 给自己刮胡子”。矛盾。

两种情形都矛盾。用表格摊开：

  ┌───────────────────────┬────────────────────────────────┬─────────────────┐
  │ 假设                  │ 由理发师的公告 (★) 推出        │ 结论            │
  ├───────────────────────┼────────────────────────────────┼─────────────────┤
  │ b 给自己刮胡子        │ 因为"给自己刮"，所以 b ∉ {不自己刮的人} │                 │
  │                       │ 但 (★) 说 b 只给 {不自己刮的人} 刮 ⇒ b 不给自己刮 │ 矛盾  │
  ├───────────────────────┼────────────────────────────────┼─────────────────┤
  │ b 不给自己刮胡子      │ 那么 b ∈ {不自己刮的人}        │                 │
  │                       │ 但 (★) 说 b 给所有 {不自己刮的人} 刮 ⇒ b 给自己刮  │ 矛盾  │
  └───────────────────────┴────────────────────────────────┴─────────────────┘
     两行都被推翻 ⇒ 满足 (★) 的理发师不存在（现实中的出路：村里没有这样的理发师，
     或理发师的公告本身就是假的。矛盾落在"公告为真"这个假设上。）

第四步（抽象出共同结构）：两个悖论是同一个方程的两个化身。令 $f(x)$ 表示”$x$ 的自我指涉谓词”（”$x$ 是假的” / “$x$ 给自己刮胡子”），悖论就来自 \(f(b)\ \Longleftrightarrow\ \neg f(b)\quad(\text{对自己}).\) 任何布尔值代入都失败。而这个方程正是下一节对角线论证要用的东西：它在程序世界的替身是”$P(P)$ 停机 $\iff$ $P(P)$ 不停机”。

【证明机制解说】：自指悖论的”灵光”在于让一个对象谈论自己。这一招为什么在语言里产生悖论、在数学里产生定理（下一节）？区别在于：语言允许”这句话是假的”这样自由的自指；而在形式化系统里，自指必须通过编码 (encoding) 实现——把”关于某个对象的话”编码成一个对象，再让对象引用该编码。Turing 的洞察就是：程序本身就是比特串，所以”程序分析程序”、”程序分析自己”都是合法操作。于是语言层面的悖论在程序层面变成了定理。

反例（如果适用）：把 Barber 的公告改成”我给所有村里人刮胡子”（去掉”不给自己刮胡子的人”这个限定），矛盾立刻消失：$b$ 给自己刮胡子，完全自洽。同样，把说谎者句改成”这句话是真的“，方程变成 $T(S)=T(S)$，任何真值都满足，不产生矛盾。“自指”本身不是悖论的来源；”自指 + 取反/否定自身”才是。

定理 13.2（停机问题不可判定）

定理 13.2：不存在程序 TestHalt，使得对一切程序 $P$ 与一切输入 $x$， \(\texttt{TestHalt}(P,x)=\begin{cases}\text{"yes"}, & \text{若 }P(x)\text{ 停机}\\ \text{"no"}, & \text{若 }P(x)\text{ 死循环}\end{cases}\) 即停机问题不可判定 (undecidable)。

证明策略：反证法 + 对角线论证（自指）。假设 TestHalt 存在；用它写一个”唱反调”的程序 Turing：喂它自己，若命中”停机”就故意死循环，若命中”死循环”就停机。最后考察 Turing(Turing)——两种情形都矛盾。这个证明与上一讲定理 12.7（Cantor 定理）结构完全同构：那里的”候选人 $f(a)$”换成”程序 $P_n$”，”翻转对角元素”换成”把停机行为取反”。

逐步推导：

第一步（反证假设）：假设存在满足定理所述行为的程序 TestHalt。注意它的定义域是所有的 $(P,x)$ 对，且必须总是终止并给出正确答案（这正是 Lecture 12 里”可判定”的意义）。

第二步（合法性检查：为什么 $P$ 可以当输入）：$P$ 是一台程序的源码，它是一个有限长的比特串。输入 $x$ 也是一个比特串。所以 $x:=P$ 完全合法，”$P$ 跑在 $P$ 上”是一个百分之百有定义的问题。这一步是自指得以可能的物理基础（程序即数据），本讲开头已经强调，这里正式用上：TestHalt(P, P) 是有意义的调用。

第三步（构造唱反调的程序）：定义

  Turing(P):
      if TestHalt(P, P) = "yes" then
          loop forever          ← P 在自身上停机，我偏偏死循环
      else
          halt                  ← P 在自身上死循环，我偏偏停机

这就是”处处与自己的候选人唱反调”。它构造完成的前提仅仅是第一步的假设（TestHalt 可用作子程序）。

第四步（把 Turing 喂给自己）：考察 Turing(Turing)。注意 Turing 自己也是一台程序，所以把 Turing 作为 Turing 的输入是合法的。它要么停机要么不停机，只有两种可能：

• 情形 A：Turing(Turing) 停机。Turing 的代码里只有两处能停机：一是 else halt 分支，二是 TestHalt 本身返回。既然 Turing(Turing) 停机，它执行的一定是 else halt 分支，而这条分支被走到当且仅当 TestHalt(Turing, Turing) 返回了 "no"。但 TestHalt 的语义规定它返回 "no" 意味着 Turing(Turing) 死循环。所以 Turing(Turing) 应当死循环——与”它停机”矛盾。

• 情形 B：Turing(Turing) 不停机。Turing 的两个分支中，else halt 会立即停机，所以不停机只能来自 loop forever 分支，而这条分支被走到当且仅当 TestHalt(Turing, Turing) 返回了 "yes"。但 TestHalt 的语义规定返回 "yes" 意味着 Turing(Turing) 停机。所以 Turing(Turing) 应当停机——与”它不停机”矛盾。

两种情形都矛盾。用图把调用关系画清楚：

                    ┌──────────────────────────────────────────┐
                    │  假设存在的判定器  TestHalt(P, x)         │
                    │                                          │
                    │   输入：程序 P 的源码 + 输入 x            │
                    │   输出："yes"（P(x) 停机）                │
                    │         "no" （P(x) 死循环）              │
                    │   契约：总是终止，总是正确                 │
                    └────────────────┬─────────────────────────┘
                                     │ 当作子程序调用
                                     ▼
        ┌────────────────────────────────────────────────────────────┐
        │  唱反调的程序  Turing(P)                                   │
        │                                                            │
        │      ┌──────────────────────────┐                          │
        │      │ TestHalt(P, P) = "yes" ? │                          │
        │      └───────┬──────────┬───────┘                          │
        │         yes  │          │  no                              │
        │              ▼          ▼                                  │
        │      loop forever      halt                                │
        │      (故意不停)        (故意停)                             │
        └────────────────────────────┬───────────────────────────────┘
                                     │ 把 Turing 自己喂给自己
                                     ▼
                    ┌──────────────────────────────────┐
                    │       Turing(Turing)             │
                    │  即  TestHalt(Turing, Turing)    │
                    └───────────────┬──────────────────┘
                                    │
              ┌─────────────────────┴─────────────────────┐
              ▼                                           ▼
   ┌────────────────────────┐               ┌────────────────────────┐
   │ 假设 Turing(Turing) 停机│               │假设 Turing(Turing) 不停 │
   │ ⇒ 走了 else 分支        │               │ ⇒ 走了 loop 分支        │
   │ ⇒ TestHalt 返回 "no"    │               │ ⇒ TestHalt 返回 "yes"   │
   │ ⇒ 按 TestHalt 语义      │               │ ⇒ 按 TestHalt 语义      │
   │   Turing(Turing) 死循环 │               │   Turing(Turing) 停机   │
   │ ⇒ ✗ 矛盾                │               │ ⇒ ✗ 矛盾                │
   └────────────────────────┘               └────────────────────────┘

                    自指环：Turing 的输入就是 Turing 自己
                    ──► 对角线上那一格 (Turing, Turing)

第五步（收口）：两种可能都矛盾，说明构造 Turing 的前提——”TestHalt 存在”——是假的。故不存在能对所有 $(P,x)$ 正确判定停机的程序，停机问题不可判定。$\blacksquare$

【证明机制解说】：这个证明的全部力量来自“让程序吃自己”。请注意它和定理 13.1 的对应关系：说谎者句说”我是假的”，Turing 说”如果我说我停，我就不停；如果我说我不停，我就停”。两者都构造了一个满足 $X=\neg X$ 的对象，从而无解。与 Cantor 定理的对应更精确：

特别强调：这不是”我们还没找到算法”。定理说的是不存在这样的算法——它是对所有可能的程序（包括未来任何人能想出的任何程序）的否定。这个区别是”存在性证明”与”不可能性证明”的区别，也是数学最有力的地方：它一劳永逸地关上了一扇门，让后人不必徒劳地寻找。上一讲的计数论证已经告诉我们这样的结果是必然的（程序可数、函数不可数），本讲则把具体是哪一个抓了出来。

反例（如果适用）：试图用”加超时”绕过不可判定性是无效的。定义 TestHaltBounded(P,x,k)：跑 $P(x)$ 至多 $k$ 步，若停机返回 "yes"，否则返回 "don't know"。这是可判定的、完全合法的程序，但它没有解决停机问题——它在死循环的情形只能说 "don't know"，而不是 "no"。想把它变成判定器就必须在”跑了 $k$ 步还没停”时断言”永远不停”，而这个断言正是不可判定的核心。任何”有限等待”方案都只能得到”可识别”，得不到”可判定”。

定理 13.2 的延伸：对角化方法的统一视角

到这里我们已经见过三次”对角线”，它们是同一个技巧的三件外衣。把三者的结构并排放在一起，你会看到一个完全一致的模板：

  ┌──────────────┬──────────────────────┬────────────────────────┬──────────────────────────┐
  │              │  Cantor 定理          │  R 不可数              │  停机问题不可判定         │
  │              │  |A| < |P(A)|         │  (定理 12.8)           │  (定理 13.2)             │
  ├──────────────┼──────────────────────┼────────────────────────┼──────────────────────────┤
  │ 被列举的对象  │  子集 T ⊆ A          │  实数 x ∈ [0,1]        │  程序 P_i                │
  ├──────────────┼──────────────────────┼────────────────────────┼──────────────────────────┤
  │ 表格的形状    │  第 n 行 = f(n) 的    │  第 n 行 = f(n) 的     │  第 n 行 = P_n 在各输入   │
  │              │  特征向量 a_{n,k}     │  小数各位 d_k^{(n)}    │  上的停机行为 (H/L)      │
  ├──────────────┼──────────────────────┼────────────────────────┼──────────────────────────┤
  │ 对角线读法    │  a_{n,n}：n ∈ f(n)?  │  d_n^{(n)}             │  P_n 在 P_n 上停机吗?    │
  ├──────────────┼──────────────────────┼────────────────────────┼──────────────────────────┤
  │ "翻转"规则    │  令 n ∈ D ⟺ n ∉ f(n) │  s_n = d_n^{(n)} ± 1   │  Turing(P) 的行为与      │
  │              │                      │  （或取 {1..8} 中异值）│  P(P) 的停机性【相反】    │
  ├──────────────┼──────────────────────┼────────────────────────┼──────────────────────────┤
  │ 新对象的身份  │  D ⊆ A，是合法子集    │  s ∈ [0,1]，是合法实数 │  Turing 是合法程序       │
  │ （关键！）    │                      │                        │                          │
  ├──────────────┼──────────────────────┼────────────────────────┼──────────────────────────┤
  │ 矛盾          │  D 不在 f 的像中      │  s 不在列表中          │  Turing 不在 P_0,P_1,... │
  │              │  ⇒ f 不满射          │  ⇒ 列表不全            │  中 ⇒ TestHalt 不存在    │
  ├──────────────┼──────────────────────┼────────────────────────┼──────────────────────────┤
  │ 结论          │  |A| < |P(A)|        │  R 不可数              │  停机问题不可判定         │
  └──────────────┴──────────────────────┴────────────────────────┴──────────────────────────┘

  同一句话概括三次使用：
  ┌────────────────────────────────────────────────────────────────────────────┐
  │  ① 把对象排成无穷表（第 n 行对应"候选 n"）                                  │
  │  ② 沿对角线取 a_{n,n}，按规则【改动】它，造出一个新对象 X                   │
  │  ③ 验证 X 依然是"合法成员"              ← 最容易漏的一步，也是成败所在      │
  │  ④ X 在第 n 项上与候选 n 处处不同 ⇒ X 不在表中 ⇒ 表必不完整 ⇒ 矛盾          │
  └────────────────────────────────────────────────────────────────────────────┘

  三者的差别只在"第 ③ 步能不能过"：
    · Cantor 定理：D 由 A 的元素按条件筛出来，必然是 A 的子集      → 通过 ✓
    · R 不可数   ：任意数字序列都定义一个实数（先做无歧义约定）      → 通过 ✓
    · 停机问题   ：Turing 的伪代码合法，它确实是一台程序            → 通过 ✓
    · 反面对照 Q ：改对角位得到的数未必是有理数                      → 失败 ✗
                    （正因如此，Q 可数，它不是不可数集）

这个统一视角的价值：以后遇到任何”证明存在性/不可能性”的题目，先问自己——”能不能把候选对象排成表？能不能沿对角线造一个处处不同的新对象？这个新对象还在原来的集合里吗？” 三个问题都答”能”，对角线论证就能用。

定理 13.3（简单停机问题不可判定：归约示范）

定理 13.3：简单停机问题 (Easy Halting Problem) ——”给定程序 $P$，判断 $P$ 在输入 $0$ 上是否停机”——同样不可判定。

证明策略：归约。这里的直觉是：”如果不让它自指（只问输入 $0$，不问任意输入如 $P$ 自己），停机问题会不会变简单？”答案是不会。证明路线是反向用归约：假设简单停机问题可判定，则用它构造出通用停机问题的判定器；而通用停机问题已被证明不可判定，矛盾。这个证明的价值在于它是归约模板的第一个完整示范——后面所有”$X$ 不可判定”的证明都照这个模子刻。

逐步推导：

第一步（陈述假设）：假设存在程序 TestEasyHalt，满足 \(\texttt{TestEasyHalt}(P)=\begin{cases}\text{"yes"}, & \text{若 }P(0)\text{ 停机}\\ \text{"no"}, & \text{若 }P(0)\text{ 死循环}\end{cases}\)

第二步（构造辅助程序 $P^{\prime}$）：给定任意的程序 $P$ 与输入 $x$，构造一个新程序

  P'(y):
      return P(x)        ← 完全忽略自己的输入 y，把 P 和 x 硬编码(hard-wire)进去

也就是说，$P^{\prime}$ 把 $P$ 和 $x$ 的源码/取值写死在自己的代码里（这是合法的：程序源码是有限串，可以嵌进另一段源码里），并在被调用时执行 $P(x)$。

第三步（关键的等价性）：断言 \(P^{\prime}(0)\text{ 停机}\quad\Longleftrightarrow\quad P(x)\text{ 停机}.\) 证明：$P^{\prime}$ 忽略输入（无论收到什么都执行同样的 return P(x)），所以 $P^{\prime}(0)$ 的执行轨迹与 $P(x)$ 逐字相同。因此前者停机当且仅当后者停机。这一条是整个归约的支点，缺了它归约就断了。

第四步（用简单判定器解通用问题）：定义

  Halt(P, x):
      P' = (构造如上：P'(y) { return P(x) })
      return TestEasyHalt(P')

正确性：由第三步，TestEasyHalt(P') 返回 "yes" $\iff$ $P^{\prime}(0)$ 停机 $\iff$ $P(x)$ 停机。所以 Halt 正是通用停机问题的判定器，并且它总是终止（因为 TestEasyHalt 总是终止）。

第五步（矛盾收口）：Halt 的存在与定理 13.2 直接冲突。故第一步的假设为假，TestEasyHalt 不存在，简单停机问题不可判定。$\blacksquare$

归约的方向示意：

   我们要证「简单停机问题」不可判定
        │
        │  反向归约：把已知不可判定的问题搬过来
        ▼
   ┌───────────────────────────────────────────────────────────────┐
   │  若 TestEasyHalt 存在                                          │
   │      ⇒ 可由它构造 Halt（通用停机判定器）  ← 归约的核心一步      │
   │      ⇒ 通用停机问题可判定                                      │
   │  但通用停机问题【已证不可判定】(定理 13.2)                      │
   │      ⇒ 矛盾 ⇒ TestEasyHalt 不存在                               │
   └───────────────────────────────────────────────────────────────┘

   注意"难度传递"的方向：
        Halt(P,x)  ⟶  P'(y): return P(x)  ⟶  TestEasyHalt(P')
        （任意输入）      （归一旦硬编码）      （只问输入 0）
    既然"任意输入"能归约到"只问输入 0"，说明后者并不比前者简单。

【证明机制解说】：归约的”灵光”是“硬编码”（hard-wiring）。$\texttt{TestEasyHalt}$ 只能问”$P$ 在 $0$ 上停不停”，而我们想问”$P$ 在 $x$ 上停不停”。解决办法是把 $x$ 编进程序本身，让新程序对任何输入都表现得像”$P$ 跑在 $x$ 上”，于是”$P$ 在 $x$ 上停机”这个问题被翻译成了“$P^{\prime}$ 在 $0$ 上停机”。这是计算机科学里最基本的手法之一：参数化 (parameterization)——把变元固定到代码里，换取形式上的匹配。想通这一点，后面所有不可判定性证明都变得机械：只需设计一个”硬编码转换器”，让难问题的新输入变成易问题能接受的输入。

反例（如果适用）：注意归约的方向不能反。我们证明了”通用停机 $\le$ 简单停机”，从而推出”简单停机不可判定”。若反过来只证明”简单停机 $\le$ 通用停机”（这当然成立），什么也得不出——因为把一个不可判定问题归约到一个不可判定问题上，或者把一个可判定问题归约到一个不可判定问题上，都不产生关于后者难度的信息。“$A\le B$ 且 $A$ 不可判定 ⟹ $B$ 不可判定”是唯一可用的形式，方向搞反是归约证明中最常见的致命错误。

定理 13.4（停机问题可识别但不可判定；补集不可识别）

定理 13.4：令 $L_{\text{HALT}}=\{\langle P,x\rangle:P(x)\text{ 停机}\}$。

• (a) $L_{\text{HALT}}$ 是可识别的，但不可判定。
• (b) 若语言 $L$ 与它的补集 $\bar L$ 都可识别，则 $L$ 可判定。
• (c) 因此 $\overline{L_{\text{HALT}}}=\{\langle P,x\rangle:P(x)\text{ 死循环}\}$ 不可识别（否则与 (a)(b) 矛盾）。

证明策略：(a) 用模拟器给出可识别性（构造性证明），不可判定性直接引用定理 13.2。(b) 是并行运行 (dovetailing) 技巧，是本讲最重要的通用工具之一：把两个半判定器交错着跑，因为两个方向必有一个会终止，所以整体必然终止。(c) 是 (b) 的逆否应用。

逐步推导：

(a) 第一步（可识别性：模拟器给出 yes）：构造

  RecognizeHalt(P, x):
      simulate P on x       ← 一步一步地跑，永不设步数上限
      if it halts then
          output "yes"      ← 只要 P(x) 真的停机，这里必被执行

正确性分析：

• 若 $\langle P,x\rangle\in L_{\text{HALT}}$（$P(x)$ 停机），则模拟在有限步后结束，程序输出 "yes" 并终止 ✓
• 若 $\langle P,x\rangle\notin L_{\text{HALT}}$（$P(x)$ 死循环），则模拟永远运行下去，从不输出 "no" —— 这违反判定器的要求（判定器必须终止并给正确答案），但符合识别器的要求（识别器对不在语言中的输入无义务）✓

所以 $L_{\text{HALT}}$ 可识别。

(a) 第二步（不可判定性）：假设 $L_{\text{HALT}}$ 可判定，则存在判定器 D，它在所有输入上终止且正确判定 $P(x)$ 是否停机——这正是定理 13.2 中被证明不存在的 TestHalt。矛盾。故 $L_{\text{HALT}}$ 不可判定。

(b) 第一步（陈述假设）：设 $L$ 与 $\bar L$ 都可识别，$M_L$ 是 $L$ 的识别器，$M_{\bar L}$ 是 $\bar L$ 的识别器。按定义：

• 若 $w\in L$，则 $M_L(w)$ 在有限步内停机并输出 "yes"（$M_{\bar L}(w)$ 可能永远跑下去）。
• 若 $w\in\bar L$，则 $M_{\bar L}(w)$ 在有限步内停机并输出 "yes"（$M_L(w)$ 可能永远跑下去）。

(b) 第二步（构造并行判定器）：

  DecideL(w):
      for k = 1, 2, 3, ... :
          run M_L(w) for k steps        ← 交错地推进两侧
          if it output "yes" then return "yes"
          run M_Lbar(w) for k steps
          if it output "yes" then return "no"
      ← 永远不会真的到达"无路可走"的状态

关键设计意图：不要”先跑 $M_L$ 跑到底、跑不完再跑 $M_{\bar L}$”——那样如果 $M_L$ 死循环就永远轮不到 $M_{\bar L}$。正确做法是每一轮给两侧各分配有限步数，并把轮数 $k$ 递增。这样两台机器都被无限多次地推进（这个技巧叫 dovetailing（燕尾交织）），任何一台一旦停下就会被立刻发现。

(b) 第三步（正确性：必在有限步内终止）：任取 $w$。因为 $L\cup\bar L=\{0,1\}^*$，必有 $w\in L$ 或 $w\in\bar L$，两者恰有一成立。

• 若 $w\in L$：$M_L(w)$ 在某个有限步数 $T$ 内停机输出 "yes"。当循环进行到 $k\ge T$ 时，run M_L(w) for k steps 会真的跑到 $M_L(w)$ 的历史终点（因为前面各轮的步数已经累计推进过；在 dovetailing 实现中把每轮步数累加，或直接用 $k$ 步的全新模拟并缓存已完成的机器状态）。于是判定器输出 "yes" 并终止。答案正确。
• 若 $w\in\bar L$：同理，$M_{\bar L}(w)$ 在有限步 $T^{\prime}$ 内输出 "yes"，判定器在某轮 $k\ge T^{\prime}$ 输出 "no" 并终止。答案正确。

两种情形都在有限步内终止并给出正确答案，所以 DecideL 是 $L$ 的判定器，$L$ 可判定。

（实现细节说明：为了让”跑 $k$ 步”真的线性推进，通常把每台机器实现成带状态保存的逐步模拟器：维护一个”已经推进的步数”计数器，第 $k$ 轮把 $M_L$ 多推进一步、把 $M_{\bar L}$ 多推进一步。这样第 $k$ 轮结束时两台机器都恰好推进了 $k$ 步，且没有重复计算。这个实现是标准做法，此处只需把握”交错推进、两侧都不被饿死”这一要点。）

(c)（补集不可识别）：反证。若 $\overline{L_{\text{HALT}}}$ 可识别，则由 (a) 第一步 $L_{\text{HALT}}$ 也可识别，于是由 (b) 得 $L_{\text{HALT}}$ 可判定，与 (a) 第二步矛盾。故 $\overline{L_{\text{HALT}}}$ 不可识别。$\blacksquare$

表格总结 $L_{\text{HALT}}$ 与 $\overline{L_{\text{HALT}}}$ 的地位：

  ┌───────────────────────────────────┬──────────────┬──────────────┐
  │                                   │  L_HALT      │  L_HALT 的补 │
  ├───────────────────────────────────┼──────────────┼──────────────┤
  │ 可识别 (recognizable)             │     ✓        │     ✗        │
  │ 可判定 (decidable)                │     ✗        │     ✗        │
  │ 存在「总是终止并正确」的程序      │     ✗        │     ✗        │
  │ 存在「说 yes 时一定对」的程序     │     ✓        │     ✗        │
  └───────────────────────────────────┴──────────────┴──────────────┘

  为什么补集不可识别（直觉版）：
    要确认 ⟨P,x⟩ 死循环，你必须证明「它永远不停」——
    而任何有限的模拟都只说明「到目前还没停」，永远推不出「永远不停」。
    这与围棋里"确认某方必胜"需要看完整棵博弈树是同一类困难。

【证明机制解说】：(b) 的”并行运行”技巧之所以重要，是因为它给出了“可识别 + 补集可识别 = 可判定”这条升级通道。它的证明只需要一个观察：两个”半个判定器”合起来就是一个完整的判定器，因为”是”与”否”两侧总有一侧的机器会终止。这个观察把”判定”这个强要求分解成两个弱要求，非常实用：要证某语言可判定，你可以分别写两个识别器（一个认 yes、一个认 no），然后用 dovetailing 粘起来。反过来，(c) 给出了一个证明”不可识别”的通用手段：若要证 $\bar L$ 不可识别，只需证 $L$ 可识别但不可判定。这个”逆否用法”在后面做题时反复出现。

反例（如果适用）：“交错推进”不能省成”轮流跑到底”。若把 DecideL 写成

  DecideL_wrong(w):
      run M_L(w) until it halts      ← 若 M_L 死循环，就永远卡在这里
      if output "yes" then return "yes"
      run M_Lbar(w) until it halts
      if output "yes" then return "no"

那么当 $w\in\bar L$ 而 $M_L(w)$ 恰好死循环时，程序永远卡在第一行，尽管 $M_{\bar L}$ 早就能给出答案。并行（交错）与串行（顺序）在这里有天壤之别：交错保证了”两侧都被无限推进”，串行则让一侧可能永久饿死。这是本讲最容易写错的一处代码。

定理 13.5（归约方法：更多不可判定问题）

定理 13.5：下列问题都不可判定：

1. 输出 0 问题：给定程序 $Q$ 与输入 $x$，判断 $Q(x)$ 是否（在停机的前提下）输出 0。
2. 输出任意内容问题：给定程序 $Q$，判断它是否曾经输出过任何东西。
3. 等价性问题：给定两台程序 $Q_1,Q_2$，判断它们是否对所有输入产生相同输出（即 $Q_1\equiv Q_2$）。
4. 更一般地，任何 $A$，只要通用停机问题可归约到 $A$（即 HALT $\le A$），都不可判定。

证明策略：全部用归约模板：设 $A$ 待证，”假设 $A$ 有判定器 → 构造 HALT 的判定器 → 与定理 13.2 矛盾”。核心工作只有一个：为每个 $A$ 设计合适的硬编码转换器，把任意 $(P,x)$ 变成一个 $A$ 能接受的输入，且变换后的”$A$-性质”恰好等价于”$P(x)$ 停机”。

逐步推导：

（1）输出 0 问题：假设有判定器 OutputsZero(Q, x)（正确判定 $Q(x)$ 是否输出 0；若 $Q(x)$ 不停机，按约定它不输出 0，故判定器返回 "no"）。构造

  Halt(P, x):
      Q' = ( Q'(y) { P(x); return 0 } )    ← 先跑 P(x)（可能死循环），停了就返回 0
      return OutputsZero(Q', 0)

正确性分析：

• 若 $P(x)$ 停机：$Q^{\prime}$ 执行完 $P(x)$ 后返回 0，所以 $Q^{\prime}$ 输出 0，OutputsZero 返回 "yes" ✓
• 若 $P(x)$ 死循环：$Q^{\prime}$ 卡在执行 $P(x)$ 上，永远到不了 return 0，所以 $Q^{\prime}$ 不输出任何东西，更没有输出 0，OutputsZero 返回 "no"（由 OutputsZero 的判定器契约，它必须终止并回答）✓

于是 Halt 是通用停机判定器，矛盾。故 OutputsZero 不存在。

（2）输出任意内容问题：假设有判定器 OutputsAnything(Q)。构造

  Halt(P, x):
      Q' = ( Q'(y) { P(x); print "hello" } )
      return OutputsAnything(Q')

若 $P(x)$ 停机，$Q^{\prime}$ 打印 "hello"（输出过东西）；若 $P(x)$ 死循环，$Q^{\prime}$ 从不打印。故 OutputsAnything(Q') 恰好回答 $P(x)$ 是否停机。矛盾。

（3）等价性问题：设 Z 是”无论输入什么都立刻死循环”的程序：

  Z(y):
      loop forever

假设有判定器 Equiv(Q1, Q2)。构造

  Halt(P, x):
      Q' = ( Q'(y) { P(x); return 1 } )     ← 注意：P(x) 停机时 Q' 返回 1
      return not Equiv(Q', Z)

正确性分析：

• 若 $P(x)$ 停机：$Q^{\prime}$ 对所有输入 $y$ 都先跑完 $P(x)$ 再返回 1，即 $Q^{\prime}$ 是一个”处处返回 1 的终止程序”。而 Z 处处死循环，从不返回。两者行为不同，所以 Equiv(Q',Z) = 假，取反得 "yes" ✓
• 若 $P(x)$ 死循环：$Q^{\prime}$ 对所有输入都死在 $P(x)$ 上，与 Z 的行为完全一致（两者处处不停机、处处无输出），所以 Equiv(Q',Z) = 真，取反得 "no" ✓

于是 Halt 是通用停机判定器，矛盾。这里 $Q^{\prime}$ 的输入 $y$ 被完全忽略（这叫忽略输入 (ignoring input)），是为了让”$Q^{\prime}$ 与 $Z$ 是否处处相同”这个全称性质能被 $P(x)$ 的停机性完全决定。

（4）一般化：以上三例的模板完全相同，可以抽象成一句话：找到一个”从 $(P,x)$ 到 $A$ 的实例”的可计算变换，使得变换后的实例落在 $A$ 中 $\iff$ $P(x)$ 停机。 这个变换在可计算性理论里叫多一归约 (many-one reduction)。掌握模板后，看到任何”程序的性质”问题，第一反应应该是：能不能把一个已知的坏性质硬编码进去？

  归约模板总结（背下来）

    已知不可判定：  HALT
        │
        │ ① 假设目标问题 A 有判定器 D_A
        │ ② 设计转换器 f：(P,x) ↦ (A 的一个实例)   ← 硬编码 P、x
        │ ③ 证明等价性：f(P,x) ∈ A  ⟺  P(x) 停机
        │ ④ 写出 HALT 的判定器：D_HALT(P,x) = D_A(f(P,x))
        │ ⑤ 与 HALT 不可判定矛盾 ⇒ A 不可判定

    每个 A 的不同之处只在于第 ② 步的那段"硬编码代码"怎么写。

【证明机制解说】：归约方法把”证明不可判定”从智力挑战降级为工程任务。你不用再设计新的对角线论证（那需要灵光），只需机械地设计一个转换器。这是可计算性理论（以及复杂性理论中证明 NP-难）中最核心的思维模式。判定”两个程序等价”不可判定这一点尤其重要——它是编译器”优化”的根本障碍：编译器无法在一般情况下判断”我的优化会不会改变程序行为”，所以所有实际优化都是保守的（只在能证明等价时才动手）。

反例（如果适用）：归约必须保证转换器自身是可计算的，否则论证无效。例如，”设 $Q^{\prime}$ = 若 $P(x)$ 停机则返回 0，否则返回 1”这种把整个停机问题答案直接写进程序的做法不是可计算的转换（你无法算出该答案是哪一个）。合法的转换只能是”把 $P$ 和 $x$ 的源码嵌进去”，让 $Q^{\prime}$ 在运行时才去执行 $P(x)$。区分”编译时算出来”与”运行时算出来”，是归约证明的关键纪律。

定理 13.6（Gödel 不完全性定理：经由停机问题的证明）

定理 13.6（Gödel 不完全性定理，1930/1931）：任何足够强以形式化算术的形式系统 $F$，若一致 (consistent)，则不完全 (incomplete)：存在一条关于自然数的真命题 $S$，在 $F$ 中既不能证明 $S$，也不能证明 $\neg S$。

证明策略：反证法 + 归约到停机问题。假设算术既一致又完全，则对任意 $(P,x)$，命题”$P(x)$ 停机”要么可证要么其否定可证。因为证明是有限二进制串，全体证明可数（这正是 Lecture 12 定理 12.5 的用武之地），所以可以逐个枚举所有证明、机械地检查它是否证明了目标命题。于是得到一个停机问题的判定器——矛盾。

逐步推导：

第一步（Gödel 式的自指骨架，Gödel 编号）：先看最强的那个想法：构造一条语句 \(S(F)=\text{"这句话在 }F\text{ 中不可证明。"}\) 两种情形：

• 情形 A：$S(F)$ 可证。既然 $F$ 的推理规则可靠（推出的都是真命题——这里需要 $F$ 一致），$S(F)$ 就是真的，即”$S(F)$ 不可证”。所以 $S(F)$ 既在 $F$ 中可证、又（作为真命题）不可证，矛盾 ⇒ $F$ 不一致。
• 情形 B：$S(F)$ 不可证。那么 $S(F)$ 所断言的内容成立，即 $S(F)$ 是真命题；而它不可证。于是 $F$ 中存在真而不可证的命题 ⇒ $F$ 不完全。

于是”要么不一致、要么不完全”。要把这个骨架变成定理，就必须真的造出 $S(F)$——这需要一套把”符号、公式、证明”都编码成自然数的机制（Gödel 编号 (Gödel numbering)），使”$x$ 是命题 $y$ 的一个证明”成为算术里的一条可判定的陈述。这是 Gödel 原始证明中最艰苦的技术部分，CS70 只做骨架介绍。

第二步（用停机问题绕开 Gödel 编号 —— 更简洁的证明）：我们换个路子，直接反证。假设 $F$ 既一致又完全。

第三步（把停机写成算术命题）：固定 $P$ 与 $x$，定义命题 \(S_{P,x}=\text{"程序 }P\text{ 在输入 }x\text{ 上停机。"}\) 关键观察：$S_{P,x}$ 可以写成纯算术的语言。具体形式是 \(S_{P,x}\ \equiv\ \exists z\ \bigl(z\ \text{编码了 }P\text{ 在 }x\text{ 上的一段合法停机执行序列}\bigr).\) 为什么可以？因为”$P$ 在 $x$ 上执行一步”是一个极其机械、完全确定的操作（读当前状态、按转移规则改状态）。把所有中间状态按顺序列出来，拼成一个长长的二进制串 $z$，那么”$z$ 是一段合法的执行序列、以停机状态结尾”这件事，就可以用纯算术的加减乘除、逻辑联结词与量词逐位检验（”第 $i$ 段编码的状态与第 $i+1$ 段编码的状态符合 $P$ 的转移规则”）。这个 $z$ 就是见证 (witness)：$S_{P,x}$ 的真假由”是否存在这样的 $z$”决定。

第四步（用完全性造判定器）：由第三步，每个 $S_{P,x}$ 都是算术命题，故（因其真假有定）它或真或假。由”$F$ 完全”的假设，必存在 $F$ 中 $S_{P,x}$ 的证明，或 $F$ 中 $\neg S_{P,x}$ 的证明（二者恰有其一，因为”$F$ 一致”排除了两者都有）。又由”$F$ 一致”，只有真的那个才会有证明，所以：

找到一个 $S_{P,x}$ 的证明 $\iff$ $S_{P,x}$ 为真 $\iff$ $P(x)$ 停机； 找到一个 $\neg S_{P,x}$ 的证明 $\iff$ $S_{P,x}$ 为假 $\iff$ $P(x)$ 死循环。

第五步（枚举证明 —— 这里用上 Lecture 12 的可数性）：证明是有限的二进制串（一串符号序列，按约定编码成比特）。由 Lecture 12 定理 12.5，所有有限串之集可数，故所有可能的证明可数，可以排成一列 $q_0,q_1,q_2,\dots$。而且”$q$ 是否是 $S_{P,x}$ 的一个合法证明”是机械可检验的（逐行核对推理规则、核对最后一行是否是目标命题）——这是”证明与计算之间的深刻联系”的直接体现。

第六步（程序 Search）：

  Search(P, x):
      for every proof q:                    ← 枚举可数多个证明
          if q is a proof of S_{P,x}     then output "yes"
          if q is a proof of ¬S_{P,x}    then output "no"

正确性：由第四步，两种证明必有一种存在，所以 Search 迟早找到它并终止（枚举过程在有限步内到达那个证明）。因此 Search 是通用停机问题的判定器。

第七步（收口）：Search 的存在与定理 13.2 矛盾。所以初始假设”$F$ 既一致又完全”为假——足够强的形式系统不可能既一致又完全。$\blacksquare$

两种证明的对照：

  ┌────────────────────────┬──────────────────────────────────────────────┐
  │ Gödel 原始证明          │ 经由停机问题的证明（本讲）                    │
  ├────────────────────────┼──────────────────────────────────────────────┤
  │ 需构造 S(F)="我不可证"  │ 不需要构造自指语句本身                        │
  │ 需 Gödel 编号（技术重）  │ 只需"把执行序列编码成整数"（直觉自然）        │
  │ 一万象：逻辑自身          │ 一万象：可计算性                              │
  │ 核心工具：自指           │ 核心工具：自指 + 可数性（定理 12.5）+ 归约     │
  └────────────────────────┴──────────────────────────────────────────────┘
  两者都指向同一句话：足够强的系统里，总有些真理逃出证明之外。

【证明机制解说】：这个证明是整门课”讲次之间互相咬合”的最佳例证。它同时用到了：Lecture 12 的可数性（证明只有可数多个，才能枚举）、Lecture 12 的编码思想（把执行序列编码成整数 $z$）、Lecture 13 的停机问题不可判定（最终的矛盾来源）、以及 Lecture 13 的归约模板（”若能搜索证明就能解停机 ⇒ 矛盾”）。特别值得品味的是”见证 $z$“这一步：它把”$P$ 是否停机”这个看似关于过程的问题，化归成了”存在一个有限的证据”这个关于算术存在量词的问题。把动态的过程静态化成有限的证据链，是可计算性理论里最有威力的翻译术。

反例（如果适用）：定理不适用于”太弱”的系统。例如只含等式公理、不含乘法的系统无法表达足够的算术，”完全性”就可能成立。同时注意定理的结论是析取式（”要么不一致，要么不完全”），而不是”一定不完全”——一个实际系统可能选择”不完全但一致”（这是我们所期望的，算术就是这样），但理论上不能排除某个系统”完全但不一致”（那样的系统毫无价值，因为从假命题可以推出一切，包括它的否定）。不要把定理的结论误读成”算术是不一致的”或”算术是完全的”。

与经典问题的联系

1. 编译器优化与静态分析的极限

编译器最想做的三件事，全都撞在不可判定性上：

• “这段代码有死循环吗？” —— 停机问题本身，不可判定（定理 13.2）。
• “这两个函数语义相同吗？我能把调用 $f$ 优化成调用 $g$ 吗？” —— 等价性问题，不可判定（定理 13.5(3)）。
• “这个程序是病毒吗？” —— 需要判断”程序是否执行了某些危险行为”，可归约到停机/输出类问题，不可判定。

工程上的应对完全是被定理逼出来的：

• 保守近似：只做”能证明安全”的优化（如常量折叠、死代码消除在局部可判定），其余一律不动。这保证优化不会改变程序语义（可证明的正确性），代价是放过很多优化机会。
• 加超时/步数上限：把不可判定问题降级为可判定问题——TestHaltBounded(P,x,k) 是可判定的，但它在”$k$ 步内没停”时只能说 "don't know"。这正是”可识别但不可判定”在工程上的落地形态：能确认 yes，不能确认 no。
• 领域限制：对语法做限制（如禁止 goto、强制结构化控制流）使某些性质变得可判定。这把”不可判定”变成”在一个受约束的子语言上可判定”，是程序分析（如抽象解释）的核心策略。
• “是否有过输出” vs. “输出什么”：定理 13.5(2) 说”是否曾输出过任何东西”都不可判定——这直接解释了为什么编译器的副作用分析（判断函数有没有 I/O）不能做到完美，只能保守估计。

2. 与”证明检查 vs. 证明搜索”的联系（自动定理证明）

定理 13.6 的证明揭示了一个极其重要的不对称：

• 证明检查是容易的：给定一个候选证明 $q$ 和命题 $S$，”$q$ 是不是 $S$ 的合法证明”可以机械地、在正比于 $\vert q\vert $ 的时间内验证。
• 证明搜索是困难的：从零找到那个证明 $q$，可能需要无穷的时间（Search 会一直跑下去，直到碰巧找到）。

这个不对称是自动定理证明 (automated theorem proving) 与交互式证明助手 (proof assistant，如 Coq / Lean) 存在的全部理由。后者让人类提供”证明在哪里”的高层线索，机器负责机械地检查——把不可判定的搜索工作交给人，把可判定的检查工作交给机器。这也解释了为什么数学论文的验证比数学定理的发现容易得多。更进一步，这个不对称还通向交互式证明系统 (interactive proof systems) 和零知识证明 (zero-knowledge proof)——”验证比生成容易”正是现代密码学协议设计的杠杆（与 Lecture 6 的 RSA 中”加密容易、解密需要私钥”形成呼应）。

3. 与”压缩”和”信息”的联系

定理 13.2 的证明依赖于”程序即数据”（程序是有限串，可以作为输入）。这个同一性也是信息压缩理论的基础：任何可计算的过程都可以被编码成一个有限描述。Lecture 12 已证明程序可数、函数不可数，从而存在无法被任何有限程序描述的”随机”对象——这正是 Kolmogorov 复杂性理论中”不可压缩串”存在的理由。CS70 只擦边，但方向已经指明：可计算性 = 可压缩性 = 有限描述的能力。

4. 与算法正确性证明的联系（Gale–Shapley 的对照）

Lecture 11 的 Gale–Shapley 算法是一个总是终止的程序，且它终止后的输出（稳定匹配）可以被证明正确。这类”构造性存在性证明”（先写算法，再证它停机且正确）在本讲形成了鲜明的对照：停机问题的意义在于不是所有程序都能享有这种保证。一个实用推论：当你写下一个新算法时，”它是否对每个输入都终止”这件事，不能指望有通用工具帮你自动验证，必须靠人给出数学论证（如势函数/递减量）。这是 Lecture 11 教”证明算法终止”、以及 L03 归纳法在算法分析中反复出现的根本原因。

与其他讲次的关联

• 与 Lecture 12（Countability）：本讲是 L12 的直接续章，三处咬合极其具体：
  1. 程序可数：L12 定理 12.5 证明 $\{0,1\}^*$ 可数，而程序就是有限比特串，所以程序可排成 $P_0,P_1,P_2,\dots$——这是停机问题对角表的前提。
  2. 函数不可数：L12 定理 12.7 的 Cantor 定理给出 $\vert \mathbb{N}\vert <\vert \mathcal{P}(\mathbb{N})\vert =\vert \{0,1\}^\infty\vert $，从而函数比程序多，保证不可计算问题的存在。
  3. 同一个对角线手势：L12 定理 12.7 的 $D=\{a:a\notin f(a)\}$ 与本讲 Turing(P) 的”行为与 $P(P)$ 相反”是同一构造；L12 定理 12.8 的”翻转对角位”也是同一构造。
  4. 证明可数性是关键零件：定理 13.6 第六步”枚举所有证明”直接用 L12 定理 12.5。
• 与 Lecture 1（Propositional Logic）：说谎者悖论的分析（定理 13.1）本质上是命题逻辑里”一个命题不能既真又假”这一基本原则的应用。”Every statement is either true or false”（排中律）与”不能同时为真为假”（矛盾律）在本讲被用来排除所有情形，从而暴露悖论。此外”$x$ 是 $S$ 的证明”这种谓词化表述也依赖 L01 的量化语言。
• 与 Lecture 2（Proof Techniques II）：定理 13.2、13.3、13.5 全部是反证法 (proof by contradiction)，且定理 13.5 系列还用了逆否推理（”若 $A\le B$ 且 $A$ 不可判定，则 $B$ 不可判定”）。L02 教的”分情形”在定理 13.1 中被用来穷举”真/假”两种情形。
• 与 Lecture 3（Induction）：定理 13.4(b) 的 dovetailing 论证中”第 $k$ 轮推进 $k$ 步”，以及”某个有限 $T$ 之后必然触发”的推理，都是 L03 建立的“无限过程由无限多个有限阶段组成”这一直觉的延续——与 L12 定理 12.2、12.3 的”按有限块分层”是同一思维。
• 与 Lecture 4–L06（Modular Arithmetic / RSA）：RSA 的安全性依赖于单向性（加密容易、无密钥解密难），而本讲的不可判定性是更深一层的”不可能”：不是”计算上困难”，而是”数学上不存在算法”。两者构成了”密码学困难性”与”可计算性不可能性”的对比。另外，定理 13.6 中”把执行序列编码成整数”的技术，与 L04–L06 中”把信息编码成模 $m$ 的剩余类”是同一种”用数字表示结构”的手法。
• 与 Lecture 7–L08（Polynomials / Secret Sharing / ECC）：多项式插值给出的是构造性的存在性证明（”一定存在唯一的次数 $\le t-1$ 的多项式穿过给定点，而且可以显式算出来”）；Berlekamp–Welch 译码算法的正确性也建立在”多项式根数不超过次数”这一可判定的代数事实上。把这些与本讲的”定理 13.6 是非构造性的不可能性证明”并置，可以看清数学证明的两种气质。
• 与 Lecture 9–L10（Graphs）：图论中的许多问题（如”某个图是否可 3-着色”）是可判定的（有限搜索空间）；但图灵机停机问题不可判定。更有意思的是，“给定图灵机 $M$，判断它是否会访问某个特定状态” 也可归约到停机问题，从而不可判定——这说明”在无限状态空间中做可达性分析”是不可能有通用算法的。这与 L09–L10 中在有限图上做 BFS/DFS 可达性（总是可判定、且是多项式时间）形成鲜明对照：有限 vs. 无限的差别，就是可判定 vs. 不可判定的差别。
• 与 Lecture 11（Stable Matching）：Gale–Shapley 是一个被证明终止的算法（存在性证明是构造性的）。本讲的范畴与它正好互补：停机问题告诉我们，不存在通用方法判定任意程序是否终止，所以 L11 那种”为算法找势函数证明终止”的人工工作是不可避免的。
• 与 Lecture 14（Counting）及之后：定理 13.6 的关键一步是”所有证明可数”，这用的是 L12 而非 L14。但本讲与 L14 有一个方法论上的共同点：都是”把对象编码成有限串/整数”的技术。L14 的计数法则（乘法法则、双射计数）在有限集上枚举对象，本讲在可数集上枚举对象——后者是前者的无穷版。
• 与 Lecture 15+（Probability）：一个值得记住的母题——不可判定性意味着”随机化”不能解决一切。L15 之后我们会看到随机化算法（如 L20 的哈希、L23 的集中不等式）如何用随机性换取效率；但停机问题不可判定是确定性结论，随机算法也救不了它（随机算法也是一个程序，它的终止性同样受定理 13.2 约束）。

关键要点

1. 自指是引擎：程序即数据（有限比特串），所以”程序吃自己”合法。这是 quine、递归定理、说谎者悖论、Barber 悖论、停机问题证明的共同物理基础。构造自指矛盾的通式是让对象满足 $X=\neg X$（”$P(P)$ 停机 $\iff$ $P(P)$ 不停机”），这种方程无解。
2. 停机问题不可判定（定理 13.2）：不存在程序对所有 $(P,x)$ 正确判定停机。证明是反证 + 对角线：假设 TestHalt，构造 Turing(P) = “与 $P(P)$ 的停机性相反”，则 Turing(Turing) 两种情形都矛盾。这是”不存在性”证明，不是”困难”或”尚未解决”。
3. 可识别是比可判定更弱的要求：可判定 = 总是终止且总正确；可识别 = 只在 yes 时保证终止并答对，no 时可能死循环。$L_{\text{HALT}}$ 可识别但不可判定（模拟器给出 yes；不可判定性引用定理 13.2）。
4. “可识别 + 补集可识别 = 可判定”（定理 13.4b）：把两个半判定器用 dovetailing（交错推进） 并行跑起来，因为两侧必有一侧终止，所以整体必终止。由此得 $\overline{L_{\text{HALT}}}$ 不可识别。注意必须交错，不能串行（串行会让一侧永久饿死）。
5. 归约模板（定理 13.5）：证 $A$ 不可判定，就假设 $A$ 有判定器，设计一个可计算的硬编码转换器把 $(P,x)$ 变成 $A$ 的实例，使得”转换后的实例 $\in A$ $\iff$ $P(x)$ 停机”，从而解出停机问题，矛盾。方向绝不能反：”$A\le B$ 且 $A$ 不可判定 ⟹ $B$ 不可判定”。
6. Gödel 不完全性定理可以经由停机问题证明（定理 13.6）：若算术既一致又完全，则”$P(x)$ 停机”这个算术命题必有证明或反证；而证明可数（L12 定理 12.5）、可机械检验，于是枚举所有证明就得到停机判定器，矛盾。足够强的形式系统不可能既一致又完全。

常见误区与注意事项

1. 把”停机问题不可判定”误读成”我们无法判断任何程序是否停机”。大错。 不可判定指的是不存在一个通用算法处理所有输入。事实上：
   • x = 3+4 显然停机（我们一眼就看出）；
   • while(true){} 显然不停机；
   • 对于每个固定的程序 $P$，命题”$P$ 停机与否”本身是有确定答案的（要么真要么假），只是没有一个算法能对所有 $P$ 统一给出答案。 类比：不存在一个通式解所有五次方程（Abel–Ruffini），但 $x^5-1=0$ 的解我们完全知道。“没有通用方法” ≠ “每个个案都无法判断”。
2. 把自指当成”作弊”或”不合法的构造”。把程序当输入接收是完全合法的操作，因为程序就是比特串。”程序 $P$ 跑在 $P$ 自己身上”和”字符串 $s$ 出现在字符串 $s$ 里”一样自然。若不接受这一点，就等于否认可编程性本身（编译器必须能把源码当数据读取）。拒绝自指就破坏了整个证明的基础，而自指恰恰是完全正当的。
3. 混淆可判定与可识别。$L_{\text{HALT}}$ 可识别（模拟器），但不可判定。区别在于：识别器的”no”答案是不可信的——它可能是”永远不回答”，而不是”回答 no”。做题时看到”程序对 $w\notin L$ 会死循环”，要立刻意识到这只是识别器而非判定器。
4. 在补集论证中把”并行”写成”串行”。DecideL 必须交错推进两个机器（第 $k$ 轮各推进 $k$ 步）。若写成”先把 $M_L$ 跑到底，再跑 $M_{\bar L}$”，则当 $M_L$ 死循环时会永久卡住，即使 $M_{\bar L}$ 能给出答案。dovetailing 的要点是”两侧都不被饿死”。
5. 归约中忘了证明”转换器可计算”，或把归约方向搞反。前半句：像”令 $Q^{\prime}$ 为：若 $P(x)$ 停机则返回 0，否则死循环”这样的描述在元语言里看似构造了 $Q^{\prime}$，但真正构造 $Q^{\prime}$ 需要一个能判断 $P(x)$ 是否停机的过程，那正是我们要证不存在的东西；合法写法是把 $P$ 和 $x$ 的源码嵌入 $Q^{\prime}$，让 $Q^{\prime}$ 运行时执行 $P(x)$——转换器本身必须是一个能写出来的程序。后半句：要证 $B$ 不可判定，必须把已知不可判定的 $A$ 归约到 $B$（$A\le B$，即”若 $B$ 可解则 $A$ 可解”）；若写成”若 $A$ 可解则 $B$ 可解”，什么也得不出来。记忆法：把”不可判定性”从已知处搬向未知处。
6. 把 Gödel 不完全性定理的结论读成”算术是不一致的”，或把”停机”与”输出”混为一谈。前者的结论是析取：”要么不一致，要么不完全”；对算术这类我们相信一致的系统，结论落在”不完全”上（存在真而不可证的命题），误读成”什么都不能证明”或”数学不可靠”都是过度解读。后者：$L_{\text{HALT}}$ 可识别（跑下去看到它停就知道了），但”$Q(x)$ 是否输出 0”甚至”$Q$ 是否曾输出任何东西”都不可判定（定理 13.5(1)(2)）——因为后者的”no”需要断言”永远不输出”，比”某时刻停下来”强得多。“能确认发生”与”能确认永不发生”是两个不同难度的问题。

思考题（带答案）

Q1. 设 TestHalt(P, x) 是假设存在的停机判定器。请（a）逐行写出 Turing(P) 的伪代码；（b）对下面这个具体的小程序 Foo 分析 Turing(Foo) 的行为，说明它为什么与 Foo 的行为相反；（c）说明 Turing(Turing) 为什么必然矛盾。

  Foo(y):
      halt            ← 无论输入什么都立刻停机

Q2. 判断正误并说明理由：

（a）”停机问题不可判定，所以没有任何程序能判断任何特定程序是否停机。” （b）”$L_{\text{HALT}}$ 可识别，所以我们可以写一个程序，对死循环的输入最终输出 no。” （c）”若 $L$ 可识别，则 $\bar L$ 也可识别。” （d）”既然我们把通用停机问题归约到了简单停机问题，说明简单停机问题比通用停机问题更难。”

Q3. 用归约证明：”给定程序 $Q$ 与输入 $x$，判断 $Q(x)$ 是否恰好输出 0” 不可判定。要求写出（a）假设的判定器 OutputsZero 的契约；（b）从 $(P,x)$ 到 $Q^{\prime}$ 的硬编码转换器；（c）停机性等价性的分析；（d）矛盾如何收口。