停机问题：程序能预测自己吗？


问题：给定程序 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 程序	编程	输出自身代码	可控自指

最后的思考

• 所有这些悖论都说明了：当一个系统试图描述自身时，往往会触及其极限
• 自指非常强大，但也极具风险
• 停机问题不仅是计算问题，更是逻辑深处的一面镜子

计算机科学

• 计算复杂性理论中的P, NP, NP Hard和NP完全问题
• 停机问题与悖论: 当逻辑凝视自身

英文：The Halting Problem and Its Paradoxical Cousins: When Logic Looks at Itself

本文一共 691 个汉字, 你数一下对不对.

¥ 打赏支持

扫描二维码，分享本文到微信朋友圈

相关文章：

1. 按揭贷款(房贷,车贷) 每月还贷计算器 去年给银行借了17万英镑 买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定 是比较常用的. 简单来说就是 每个月交的钱是...
2. 智能手机 HTC One M9 使用测评 虽然我对手机要求不高, 远远没有像追求VPS服务器一样, 但是怎么算来两年内换了四个手机, 先是三星 S4 用了一年多, 然后 Nokia Lumia 635 Windows Phone, 后来又是 BLU, 半年多前换了...
3. 同一台服务器上多个WORDPRESS站点的一些设置可以移出去 我自从把所有网站都挪到一处VPS服务器上 就发现很多事情省事很多 可以同时管理多个网站 包括 WORDPRESS博客. 比如我有四个WORDPRESS博客 然后我就把通用的一些资料给移出去 移到 HTTP或者HTTPS都不能直接访问的文件夹里这样就更安全许多. 文件 wp-conn.php 存储了 相同的数据库资料. 1 2...
4. 比特币最近波动有点大: 一天牛市一天熊 比特币10万美金以内都是最后上车的机会！ 比特币近期的价格波动可以归因于多个关键因素，包括地缘政治动态、监管变化以及加密行业内的重大安全事件。其中一个主要影响因素是美国前总统唐纳德·特朗普对乌克兰和加密货币监管的立场变化。据报道，特朗普再次当选，他可能会推动减少美国对乌克兰的支持，这可能会影响全球金融市场和风险偏好。同时，特朗普正在将自己塑造为亲加密货币的候选人，表示有意让美国成为一个更加友好的加密货币环境。这一立场引发了市场对监管政策可能发生变化的猜测，导致市场情绪在乐观和不确定性之间波动。 特朗普对俄乌战争的态度 美国第43届总统唐纳德·特朗普已经在2025年1月当选并正式上任（第二次），那么他的政策可能会对比特币价格的波动产生更加直接和显著的影响。他政府对乌克兰和加密货币监管的立场已经不再是猜测，而是正在实际塑造市场的关键力量。 特朗普（Donald Trump）减少美国对乌克兰的支持，全球投资者可能会预期地缘政治稳定性发生变化，从而增加对比特币作为避险资产的需求。同时，他的亲加密货币立场可能正在推动市场的乐观情绪。如果他的政府推出有利于加密行业的监管政策，例如明确的合规指南或减少监管审查，可能会吸引更多机构投资者进入市场，并促进更广泛的加密货币采用。然而，政策的快速变化也可能导致短期市场剧烈波动，因为市场需要时间来消化新的政策动向。 朝鲜黑客盗取Bybit交易所15亿美元的ETH 另一个显著影响比特币价格的事件是近期涉及朝鲜黑客组织“Lazarus”的15亿美元以太坊被盗案件。据报道，Bybit交易所（全球第二）这些被盗的ETH已经被清洗，此次大规模黑客攻击引发了人们对加密行业安全性的担忧。此类安全事件不仅会削弱投资者信心，还可能引发更严格的监管审查，导致短期市场动荡。此外，被盗资金的大规模流动和出售可能对市场流动性造成冲击，进一步加大价格波动。随着这些事件的持续发酵，比特币价格正受到政治决策、监管预期以及安全挑战等多重因素的影响。 与此同时，与朝鲜黑客组织 Lazarus 相关的 15 亿美元以太坊被盗事件仍在影响加密市场。由于这些被盗 ETH 已被清洗，人们对加密行业安全漏洞的担忧持续存在，同时也可能引发更严格的监管审查。政治、监管和安全等多重因素交织在一起，共同导致了比特币近期的剧烈价格波动。...
5. 老婆的配偶签证被拒 郁闷死了, 601镑签证费打水漂,一去不回!费钱费力. 去年12月份我请了律师拿到了永居.老婆是T1G签证的陪工签 (DEPENDENT VISA) 2016年4月份到期. 然后我就想说得趁早把她的签证转成配偶签(SPOUSE)这样她就可以尽快走五年永居的路线. 今天收到拒签信,原因是我没有提供 有工资进帐的那份银行帐单,我提供了我和我老婆的联名帐户, 但是工资并不是直接打到这个帐单上的.所以就这一点被拒了.完全不给解释,不给补材料的机会.601镑就这样再见了. 英国的签证寄出之后是先由另一个部门先收费, 收完费才正式审理,而且不管结果如何是不退钱的.后悔没让律师弄,也不至于到现在浪费这么多时间和金钱,签证还没过.由于原签证还没到期,所以还不能上述.估计只能等搬完家后年底请律师搞定这事. 真是郁闷, 600镑, 我可以再买一个IPHONE6,或者给我的新买的车换四个轮胎....
6. 公司给配了台高配DELL笔记本 早上例会结束的时候我顺便说了一句 我的笔记本有点慢, 当时我并不知道我的经理远程用电话也参加会议了(他全程在听), senior staff SE 对着电话说, “peter, you hear that? btw, my disks are...
7. 花钱让人换汽车钥匙的电池真是个智商税 今天想不到我这么聪明的人也被人狠狠的收了一把智商税. 今天被收智商税了, 去 Tesco 换车钥匙的电池. . 才发现如此的简单, 那人直接2分钟搞定2个, 然后收了我25英镑. . 服了. . 我还以为很复杂…… 网友说 “1....
8. 加个页面分享下拉选项 从 Leonax 的博客发现每篇博客有个分享选项,于是我就看源代码,可是后来发现一般人不太好发现怎么实现的, 用了JQUERY,并且代码是在一个JS文件的最后.索性自己实现,还好不难. 以上是通过 CHROME 浏览器 选择文字 并且通过 Inspect Element 来看动态生成的页面元素和代码,如果只查看源代码,你只会发现一个空的 span 元素. 其实只要把下面(一目了然)的JS代码放到页面模板中...