笔记16-《程序员的数学》不可解问题

2026.10.30 16:30 下午

不可解问题
用 Ruby 验证
停机问题为什么无解

不可解问题

反证法
- 也叫归谬法：因其最后推出荒谬的结果
- 反证法不是直接证明命题，所以理解上稍有难度
- 思考题：为什么不存在「最大的整数」？
- 证明过程
  1. 假设存在「最大的整数」，记为 $M$
  2. 那么 $M+1$ 就比 $M$ 大
  3. 这与「 $M$ 是最大的整数」的假设相矛盾
  4. 因此，不存在最大的整数
- 关键在于要证明的命题是「不存在最大的整数」，所以反证法要假设它的否定形式成立，即「存在最大的整数」
- 「 $M$ 是最大的整数」和「 $M$ 不是最大的整数」都成立 → 产生矛盾
- 最大的整数要么存在要么不存在，只能是其中一种情况 → 证明了原命题
- 质数是无穷的（欧几里得证明）
  - 设所有质数的积 $Q = 2 \times 3 \times 5 \times 7 \times \cdots \times P + 1$
  - $Q$ 比任何质数都大 → $Q$ 不是质数
  - 但 $Q$ 除以 2、3、5、7、…、 $P$ 中任何一个余数都是 1（不能整除）→ 按质数定义， $Q$ 是质数
  - 「 $Q$ 不是质数」和「 $Q$ 是质数」都成立 → 矛盾 → 质数是无穷的
  - 注意这里的「 $Q$ $Q$ 是质数」是在「质数只有这些」这个假设下的推理，不是关于 $Q$ $Q$ 的实测结论
    - 实测会得到相反答案：这个 $Q$ 自己就是合数
    - 证明真正依赖的是「 $Q$ 不被任何已知质数整除」+「 $Q$ 比所有已知质数都大」这两条
- 反证法的注意事项
  - 从「要证明的命题的否定形式」出发，必须先假设错误的假设成立
  - 到引出矛盾结论为止的论证过程本身必须正确
    - 如果中途的论证出现错误，就不能得出「因为最初的假设错误，所以产生矛盾」的结论
  - 从错误的假设出发，还要想着推翻这个假设并进行正确的论证，这确实不太容易
可数
- 定义：集合的元素是有限的，或者集合中的所有元素都与正整数一一对应时，这个集合就被定义为可数（countable，enumerable）
  - 简言之：能按顺序第 1、第 2、第 3、第 4 来数元素的集合就是可数的
- 所有整数的集合是可数的
  - 重点在于正数和负数的交互编号
  - 将所有正整数都编完号之后再给负整数编号是行不通的 —— 正整数是无穷的，无法完成编号
- 所有有理数的集合是可数的
  - 可以给它们编号（按图 8-1 的方式）
  - 接下来只要按 1、2、3、4 的顺序编号，就能将 1 以上的整数和有理数一一对应起来
  - 不过得跳过重复出现的数
对角论证法
- 不可数集合：元素不能与 1 以上的整数一一对应的集合，无论采用什么对应规则，总会有「遗漏」的元素
- 所有整数数列的集合是不可数的
  - 整数数列的例子：0 以上的整数数列、0 以上的偶数数列、1 以上的奇数数列、斐波那契数列、全 0 数列、圆周率各位数组成的数列
  - 整数数列不一定是逐项递增的
  - 整数数列有无穷个，即「所有整数数列的集合」是无穷集
- 证明步骤
  - 假设「所有整数数列的集合是可数的」→ 就能排成一张无穷大的表
    - 第 1 个整数数列在第 1 行，第 2 个在第 2 行，…，第 $k$ 个在第 $k$ 行
    - 这个表实际上写不完，但无论给出多大的 $k$ ，总能够作出延伸至 $k$ 行的表
    - 这个「能够」就是假设「所有整数数列的集合是可数的」的意思
  - 按规则做出新的整数数列
    - 设第 1 个整数数列的第 1 个数 +1 所得的数为 $\alpha_1$ ，第 2 个的第 2 个数 +1 为 $\alpha_2$ ，…，第 $k$ 个的第 $k$ 个数 +1 为 $\alpha_k$
  - 这个新数列不包含在表中 —— 它在表的第 $k$ 行那个数列的第 $k$ 个位置上比表里的大 1
  - 矛盾 → 「所有整数数列的集合是可数的」不成立
不可解问题
- 什么是不可解问题：存在这样的问题，无论用什么方法都无法求出答案
- 停机问题
  - 停机问题（Halting Problem）：判断「某程序在给定数据下，是否会在有限时间内结束运行」
  - 程序是否会陷入无限循环，有时跟输入的数据有关 —— 例如 while (x > 0) 在 $x > 0$ $x > 0$ 时死循环， $x < 0$ $x < 0$ 时不会
    - 所以判断程序是否会结束时，除了程序代码还要考量输入的数据
  - 处理程序的程序：程序说白了就是计算机存储设备上的数据，所以处理程序也没什么特别的
    - 编译器：读取源代码，转换成机器语言（目标代码）的程序
    - 源代码检查器：读取源代码，告诉哪里用了不正确的命令、哪里会陷入无限循环、哪些命令肯定无法运行
    - 调试器：暂停运行中的程序、重新运行、告诉运行中的状态
  - 停机问题由图灵（Alan Turing，1912–1954）在 1936 年证明出来
- 证明步骤
  1. 假设可以写出判断程序 HaltChecker
    - $\text{HaltChecker}(p, d)$ 返回 true 表示「将 $d$ 输入 $p$ 时， $p$ 会在有限时间内结束运行」，false 表示不会
  2. 写出 SelfLoop 程序
    - halts = HaltChecker(p, p); 然后 if (halts) { while (1 > 0) {...} }
    - 注意两次输入到 HaltChecker 中的都是 $p$
  3. 推导出矛盾 —— 把 SelfLoop 自身传入 SelfLoop
    - 情况 1：SelfLoop(SelfLoop) 会结束运行 → 意味着 HaltChecker 返回 false → 意味着 SelfLoop(SelfLoop) 不会结束 → 矛盾
    - 情况 2：SelfLoop(SelfLoop) 陷入无限循环 → 意味着 HaltChecker 返回 true → 意味着 SelfLoop(SelfLoop) 会结束 → 矛盾
  - 两种情况都矛盾 → 假设「能写出 HaltChecker」必然产生矛盾 → 无法编写出 HaltChecker 这样的程序
- 写给尚未理解的读者
  - GoldChecker(n)：从偶数 $n$ 开始逐个检查能否写成两个质数之和，不能则输出 $n$ 并结束
  - 调用 HaltChecker(GoldChecker, 4) 会怎样？
    - 返回 true → 意味着存在不能写成两个质数之和的 $n$ → 否定了哥德巴赫猜想
    - 返回 false → 意味着程序永不结束 → 哥德巴赫猜想正确
  - 如果存在 HaltChecker，就能解决许多尚未解决的问题（费马大定理、哥德巴赫猜想等）
    - 严格来说 HaltChecker 只判断有没有解，并不显示有解时的解是什么
  - 作者声明：以上内容不是证明，而是「感性地讲解」写出 HaltChecker 不可能
- 不可解问题有很多
  - 停机问题不依赖特定编程语言 —— 解决它的程序「无论用什么语言都写不出来」
  - 许多判断程序运行问题都是不可解问题，可用停机问题的证明方法证明
课后对话
- 老师：假设世界人口总数为 100 亿，将所有人编号需要多少位数？
- 学生：10 位有 1024 人…嗯，300 位左右吧？
- 老师：不，34 位就足够了
- 学生：这就够了吗？
- 老师：即使给宇宙中所有的原子编号，也不需要 300 位哦

用 Ruby 验证

# 反证法：质数无穷（欧几里得）
def primes_below(n)
  (2...n).select { |x| (2...x).none? { |d| x % d == 0 } }
end

primes = primes_below(100)
q = primes.inject(1) { |a, p| a * p } + 1

puts "质数(100以内) = #{primes.size} 个"
puts "Q = 质数积+1 = #{q}"
puts "Q 能被列表中任一质数整除? #{(primes.any? { |p| q % p == 0 })}"
puts "Q 大于列表中所有质数? #{q > primes.max}"
puts "Q 实际是质数吗? #{(2...q).none? { |d| q % d == 0 }}"

puts "100亿人编号需要 #{Math.log2(10_000_000_000).ceil} 位"
puts "2^34 = #{2**34} > 1e10 ? #{2**34 > 10_000_000_000}"
puts "2^33 = #{2**33} > 1e10 ? #{2**33 > 10_000_000_000}"

输出：

质数(100以内) = 25 个
Q = 质数积+1 = 2305567963945518424753102147331756071
Q 能被列表中任一质数整除? false
Q 大于列表中所有质数? true
Q 实际是质数吗? false
100亿人编号需要 34 位
2^34 = 17179869184 > 1e10 ? true
2^33 = 8589934592 > 1e10 ? false

停机问题为什么无解

作者在证明里用的是「C 语言式代码」，但他特意声明：停机问题不依赖特定的编程语言。

真正精妙的地方在 SelfLoop 那个结构 —— 它把「判断」变成了「自我指涉」：

SelfLoop(p) 调用 HaltChecker(p, p)
  若 HaltChecker 说「会结束」→ SelfLoop 死循环（与「会结束」矛盾）
  若 HaltChecker 说「不会结束」→ SelfLoop 立即返回（与「不会结束」矛盾）

无论 HaltChecker 怎么回答，答案都会反过来否定自己。这不是「算得慢」或「数据太大」—— 是逻辑上根本不存在那个函数。

这个技巧叫对角论证法，和本章前面证明「所有整数数列的集合不可数」用的是同一招：

步骤	不可数证明	停机问题证明
假设	所有整数数列可数（能排成表）	存在 HaltChecker
构造	新数列，在表的第 $k$ 行第 $k$ 个数上加 1	SelfLoop，把自身传给自己
结果	新数列不在表里 → 矛盾	两种情况都矛盾
结论	整数数列集合不可数	HaltChecker 不存在

同一个证明结构，两次使用。 这是本章最值得记住的东西 —— 可数性和停机性看起来毫不相干，但它们都栽在「把自己塞进自己」这个动作上。

而作者诚实地标注了那段哥德巴赫讨论的限度：「以上内容并不是证明，而是『感性地讲解』写出 HaltChecker 是不可能的。」一个数学家主动标出自己哪一步只是启发式，这个动作本身就值得学 —— 第 7 章说过「有限不等于可行」，这一章补上了第三句：不可行也不等于不可解，两者都要单独证明。

学习 :分类
不可解问题 :标签