上一个世纪的电脑
停机问题：程序能预测自己吗？
问题：给定程序 P 和输入 x，你能判断 P(x) 是否会停机，还是永远运行下去吗？
- 由阿兰·图灵于 1936 年提出
- 被证明为不可判定——不存在通用算法能解决所有情况
- 本质是自指问题：程序能分析另一个程序（甚至是自己）吗？
图灵的思想实验
假设：H(P, x) 判断 P(x) 是否停机
定义下面的Python函数：
def D(P):
if H(P, P):
while True: pass # 无限循环
else:
return 0 # 停机
那 D(D) 会发生什么？
- 如果 D(D) 停机 → 它应该陷入死循环
- 如果 D(D) 死循环 → 它应该停机
逻辑中的类比：自指悖论
1. 理发师悖论
- 理发师为所有“不自己刮胡子”的人刮胡子
- 那理发师给自己刮吗？
- 造成矛盾 —— 和 D(D) 的情况完全相同
2. 说谎者悖论
"这句话是假的。"
- 如果是真的 → 它就是假的
- 如果是假的 → 它就是真的
- 纯粹的自指，导致真假互相循环
3. 罗素悖论（集合论）
R = { x | x 是集合 且 x ∉ x }
- R ∈ R 吗？
- 如果是 → 不应该在 R 中
- 如果不是 → 应该在 R 中
4. Grelling–Nelson 悖论
异描述词 = 不描述自身的形容词
- “异描述词”是异描述词吗？
- 如果是 → 就不是；如果不是 → 就是
5. 哥德尔不完备性定理
"这句话无法被证明。"
- 如果能被证明 → 矛盾
- 如果不能证明 → 它是真的但系统无法证明
- 某些真理超出了系统本身的证明能力
6. Quine 程序
# Python 中的 Quine 示例
s = 's = {!r}\nprint(s.format(s))'
print(s.format(s))
- 输出自身源码的程序
- 体现了受控的自指结构
7. 决定性问题（Entscheidungsproblem）
- 希尔伯特问：是否存在一种通用方法判定一切数学命题的真假？
- 图灵与邱奇给出的答案：否
- 停机问题正是其不可判定性的关键依据
总结对照表
| 问题 | 领域 | 核心问题 | 结论 |
|---|---|---|---|
| 停机问题 | 计算机科学 | 程序是否能分析自身？ | 不可判定 |
| 理发师悖论 | 逻辑 | 自指导致矛盾 | 悖论 |
| 说谎者悖论 | 哲学 | 真假自指 | 悖论 |
| 罗素悖论 | 集合论 | 集合是否包含自身 | 矛盾 |
| 哥德尔定理 | 数学逻辑 | 不可证明真理 | 不完备 |
| Quine 程序 | 编程 | 输出自身代码 | 可控自指 |
最后的思考
- 所有这些悖论都说明了：当一个系统试图描述自身时，往往会触及其极限
- 自指非常强大，但也极具风险
- 停机问题不仅是计算问题，更是逻辑深处的一面镜子
计算机科学
英文：The Halting Problem and Its Paradoxical Cousins: When Logic Looks at Itself
强烈推荐
- 英国代购-畅购英伦
- TopCashBack 返现 (英国购物必备, 积少成多, 我2年来一共得了3000多英镑)
- Quidco 返现 (也是很不错的英国返现网站, 返现率高)
- 注册就送10美元, 免费使用2个月的 DigitalOcean 云主机(性价比超高, 每月只需5美元)
- 注册就送10美元, 免费使用4个月的 Vultr 云主机(性价比超高, 每月只需2.5美元)
- 注册就送10美元, 免费使用2个月的 阿里 云主机(性价比超高, 每月只需4.5美元)
- 注册就送20美元, 免费使用4个月的 Linode 云主机(性价比超高, 每月只需5美元) (折扣码: PodCastInit2022)
- PlusNet 英国光纤(超快, 超划算! 用户名 doctorlai)
- 刷了美国运通信用卡一年得到的积分 换了 485英镑
- 注册就送50英镑 – 英国最便宜最划算的电气提供商
- 能把比特币莱特币变现的银行卡! 不需要手续费就可以把虚拟货币法币兑换
微信公众号: 小赖子的英国生活和资讯 JustYYUK