从“程序会不会停”说起：停机问题为何不可判定-北京尧图网络

进度条卡在 99%风扇狂转任务管理器里那个进程的 CPU 占用一路飙红你等了五分钟它还在原地打转。那一刻你多半会冒出一个念头要是能有个工具提前告诉我这程序跑起来到底会不会死循环、永不退出该多好。这个听起来特别实用的需求正是计算机科学里最出名的问题——停机问题给定一个程序和一份输入判断这个程序拿到这份输入之后是会正常结束还是会一直跑下去。表面看这像是多招几个程序员总能解决的工程问题但结论非常反直觉不存在一个普适算法能做到这件事。不是目前技术不够强是这件事在逻辑上就不可判定。这篇文章不会像教材那样先扔一堆定义而是直接把不可判定的原因摊开用一个反证法加自我指涉的程序一步一步把你推到矛盾面前。看完你就能明白为什么所有标签上写着万能的检测器都只能是想象以及这个结论在写代码、做测试、搞静态分析时到底意味着什么。哪怕你只写过几行代码也能跟着走完全程。1. 一上来先讲清楚停机问题到底在问什么1.1 一句话版本和立刻能懂的例子停机问题的标准问法是给定程序 P 和输入 IP 在收到 I 之后会不会在有限的步骤内结束这里的结束是指程序走完所有指令、正常返回至于结果是算对了还是算错了停机问题完全不关心。换句话说只要程序不卡住、不无限循环它就算停机。拿几个特别简单的例子程序 Aprint(hello)。不管给什么输入它都立刻打印然后退出明显停机。程序 Bwhile True: pass。不管给什么输入它都永远空转明显不停机。程序 C读入一个数 n从 1 加到 n然后返回和。在 n 有限的条件下循环有限会停机。程序 D读入一个大于 1 的奇数 n就把它变成 3n1否则除以 2循环直到变成 1。这个程序对所有整数是不是都会停至今没有完全定论数学界把它归类为猜想级别的问题。前三个例子人肉看一眼就能判断。但真正的问题不是这一个一个地聊而是能不能写一个通用程序 H让它接收任意程序任意输入的组合自动输出会停还是不会停注意这里的任意二字。这就是停机问题最让人挠头的地方——不是问某个具体程序会不会停而是问一个新的程序能不能处理所有程序。就像你希望的不是请几个保安盯住几扇门而是发明一种保安能看住所有可能出现的门。1.2 这个问题和我们写代码的日常有什么关系写业务代码的时候停机问题听起来像学院派才会关心的学术名词。但落到实际场景里你会发现它无处不在。你在 CI 流水线里挂了一个测试任务希望代码合并前自动跑一遍。如果某个测试用例触发了一个死循环整个流水线就会卡住不动。你的第一反应是加一个超时时间比如 5 分钟跑不完就杀掉进程。这其实就是在说我没法保证它一定会停所以用外部强制手段兜底。又比如你在做一个代码分析工具想帮同事找出可能导致卡死的代码。扫描完整个项目后你应该给哪些文件打警告哪些文件放过去如果试图做一个 100% 不漏报的工具让每个死循环都被自动揪出来那么停机问题的结论会直接让这个工具破产——因为这个程序是否死循环本身就是停机问题的变体。所以你会发现不管是大厂还是个人项目跟程序会不会停有关的工具几乎都只追求两件事一是尽早发现明显的循环问题二是用超时、资源限制来兜底。没有人真的承诺我能判断任意程序是否停机。理解了停机问题你才会明白这不是大家偷懒而是数学上不允许。2. 不可判定的核心思路先假设能再让它自己证明不能2.1 假设存在一个万能判定器要证明不存在一个算法能解决停机问题最干净的办法是反证法先假设存在一个这样的算法然后推出矛盾。为了方便描述给它起个名字叫判定器 H。H 的输入是两样东西一个是程序 P另一个是输入数据 I。H 的工作非常简单如果 P(I) 最终会停机H 返回halt如果 P(I) 永远跑不完H 返回loop。关键在于H 是万能的对任何语言写出的任何程序、任何可能的输入它都保证给出正确答案而且它自己必然在有限时间内结束。这段话听着有点像我给你推荐一个工具它能检测所有 bug直觉上很爽但正是这个所有给了我们反击的空间。2.2 构造一个专门唱反调的程序有了这个 H我们可以写出下面这个程序 T名字怎么叫都行我习惯叫它逆行者def H(program, input_data): # 这是假设存在的万能判定器 # 传入 program 这个程序的一段描述以及 input_data # 如果 program(input_data) 会停机返回 halt # 如果 program(input_data) 会永远运行返回 loop pass # 注意我们只是假设它有实现 def T(program): # T 接收一个程序 program然后把 program 当作输入传给 H if H(program, program) loop: # 如果 H 说 program 在自己身上会死循环 # 那 T 就直接结束也就是主动停机 return 0 else: # 如果 H 说 program 在自己身上会停机 # 那 T 就故意进入死循环不停机 while True: pass这里有一个初学者总会卡住的地方程序怎么能输入程序其实很容易任何源代码都是一段文本文本当然可以作为字符串传给另一个程序。所以H(program, program)的意思是把一段程序描述当作数据问 H 这个程序被运行在那样一份数据上时会不会停。这一点在理论里完全成立在现实中也不难理解——你把一段代码丢给一个函数让它去分析这种事每天都在发生。2.3 把判定器逼到死角无论它说什么都是错的现在我们自己拿起 T问 H 一个问题H(T, T)应该是什么逐步推假如H(T, T)返回halt。也就是说判定器确定地认为把 T 自己当作输入来运行T 会停机。可是当 T 真正运行起来它进了 else 分支因为H(program, program) ! loop程序会走到while True: pass永远空转。于是H 说它停机它实际上不停机H 错了。假如H(T, T)返回loop。判定器认为T 吃下自己之后会死循环。可是T 看到 H 的结论是loop就会走进 if 分支执行return 0立刻停机。于是H 说它不停机它实际上停机了H 又错了。两种可能性都被堵死只要 H 存在T 的行为就和 H 给出的答案相反。唯一合理的解释就是H 不存在。这个程序 T 是我们凭空造出来的不依赖任何高级语言特性也没有用黑魔法就是一个普通函数而它能够在任何自称万能的判定器面前玩你说东我往西的游戏。所以最初的假设——存在万能停机判定器——一定是错的。提示把程序当作输入再让程序去递归地分析程序分析程序是这个反证法的灵魂。它本质上和理发师悖论同构理发师宣称只给所有不给自己刮胡子的人刮胡子那他自己给自己刮吗无论怎么回答都会违反他自己的规则。T 程序就是那个反向的理发师专门刺穿H 能处理一切程序这句话。3. 把推演在代码现场完整走一遍3.1 判定器应该长什么样可能有人会说上面只是用一个没实现的 H 占位符这不太有说服力。所以这一节我们把推演做得更实一些。假设我们要实现这个万能判定器它面对的是某种确定的程序语言 L。它的接口大概是输入program_text一段合法的 L 语言源代码文本input_text一段输入数据文本注意这个输入数据也可以是别的程序文本因为程序本质上就是文本。输出halt如果把program_text编译执行喂给input_text执行过程会在有限步内结束loop如果这个过程永不结束。H 必须是最理想的那种工具不依赖推测不靠超时猜测不抽样不把异常当成死循环。它是数学意义上的完美判定在它返回halt的时候全世界任何一个人去跑这个程序都一定能在有限时间内看到程序退出在它返回loop的时候没有人能等到程序退出因为它就是不会退出。许多人第一次学停机问题时会想那如果 H 运行了 1 亿步还没得出结论能不能先返回loop不能。因为一个程序可能非常慢慢到需要 10 亿步才退出1 亿步的观测根本不足以区分很慢但最终会停机和永远不会停机。所以 H 必须在逻辑上保证正确而不是在经验上给出猜测。3.2 为什么这个证明一定要用对角线结构接下来把证明背后的几何直觉讲出来因为它比代码本身更值得记。把所有可能的程序排成一个列表P0, P1, P2, P3…… 把所有可能的输入也排成一个列表I0, I1, I2, I3…… 理论上它们都能被枚举出来因为程序是文本文本编码成数字可以按字典序排。现在画一张巨大的表格行是程序列是输入。每个格子里填这个程序在这个输入上最终会停机吗。假如 H 存在它就能完美地替我们填写整张表格的每个格子程序 Pi 在输入 Ij 上会不会停机H 都能算出来。对角线上的格子也就是 Pi 在输入 Ii 上的结果是这张表里最特别的一串。现在构造一个全新的程序 D它的行为规则是翻到表格的对角线如果 Pk 在 Ik 上会停机那么 D(Pk) 就去死循环如果 Pk 在 Ik 上不会停机那么 D(Pk) 就立即停机。换句话说D 的作用就是把对角线上每一个已经填好的答案全部反转。然后再回过头问D 自己也是众多程序之一它应该排在表格的某一行比如第 d 行。那么第 d 行、第 d 列这个格子也就是对角线上对应 D 自己的那个格子应该填什么如果 H 说halt也就是认为 D 在 D 上会停机那么按照 D 的规则它会故意死循环——违背了 H。如果 H 说loop那么 D 又会立刻停机——还是违背了 H。无论 H 怎么填到了 D 这一行都会反转。就好像表格里有一行程序的每个格子都和你原来的预计相反而这一行程序本身也处在表格之中于是整个系统的完整性当场被戳穿。这种沿对角线取反的方法是数学里经典的对角线论证法。核心在于你构造的挑剔对象总是从目标系统自身开刀把系统给它的判定结果反着执行。于是系统不可能既完整、又永远正确。3.3 把矛盾现场用伪代码再演示一遍为了更直观把运行现场写成伪代码步骤你拿到一份T.py的源码。调用假设的H(T.py, T.py)若返回halt预测 T 在 T 上会停机。若返回loop预测 T 在 T 上会死循环。实际运行T.py并把T.py的源码作为输入传给它如果第 2 步是haltT.py 会执行while True: pass永远不结束。如果第 2 步是loopT.py 会执行return 0立刻结束。对比第 2 步和第 3 步发现两者永远相反。这里有一个关键点T 在运行的时候又调用了一次 H。有人会问这难道不会导致递归死循环吗并不会。因为 H 被假定为万能且必然在有限时间内返回答案T 也只是根据 H 的返回值做一个简单分支要么死循环要么返回。真正会死循环的只有H 预测为停机的那个分支而这正是故意安排的。所以整个论证是严格自洽的没有依赖分析者看错了或超时了这类小概率因素。4. 别以为只是个别问题一大片问题都跟着不可判定4.1 核心工具归约如果摊开讲你会发现停机问题不是孤立的一个难题。计算机科学里有一个非常重要的思维工具叫归约意思是如果我能用问题 B 的解法来解决问题 A那么问题 A 的难度就不会超过问题 B。反过来如果问题 A 是著名的不可判定问题而 A 又能归约到问题 B那么 B 也一定是不可判定的——否则我可以先解 B再解 A这跟 A 不可判定矛盾。停机问题就是一个很好的公理级不可判定问题。很多看起来更贴近工程的需求只要仔细推都能变成先帮我判断停机。4.2 几个典型的不可判定问题第一个是万能 Bug 检测器。假设有人推出一个工具号称能分析任意程序、任意输入并准确告诉你这个程序跑起来会不会抛异常、会不会越界、会不会出错。这个工具如果真的存在就可以用它反推停机问题先写一个包装程序 W如果原程序 P 在输入 I 上停机W 就返回正常结果如果 P 不停机W 就去读一块非法内存。于是用万能 Bug 检测器检测 W 在 I 上是否有 Bug就等价于检测 P(I) 是否停机。由于停机问题不可解万能 Bug 检测器也不存在。第二个是程序等价性检测器。假如有工具能判断任意两个程序是否行为等价——对同样的输入给同样的输出——那它也能解决停机问题构造一个永远输出空结果然后停机的程序和一个如果不停机就什么都不输出的程序判断它们是否等价。等价性问题足够强结果也一样不可判定。第三个是给定某个字符串程序最终会不会输出它。这个可以直接做归约让程序在停机之后打印特定字符串在不停机时打印不了。于是判断会不会输出这个字符串等价于判断会不会停机。这些不可判定问题都有一个共同点它们都在问所有程序的某种普遍性质。这不是现在做不到是未来任何一天都做不到。4.3 工程上真正在用的是有界版本看到这里可能有人会泄气那程序分析还有什么用别急工程界早就找到了一条折中的路我们不去追求判定永远和任意程序而是判定在限定步数内会不会停或者这个具体程序类型能不能被抽象解释全覆盖。有界停机问题的定义是给定程序和输入以及一个上限 N如果程序能在 N 步内停机返回会停否则返回没能在 N 步内停。这个变体是可判定的——直接真跑 N 步就行了。代价是它只有单方向的保证如果它说会停那是真的会停如果它说没检测到不代表程序真的会永远运行可能只是超过 N。但工程上这种宁可漏掉也不误报的做法非常有价值配合超时机制、资源配额、模糊测试和代码审查已经能抓住大部分真实死循环风险。注意有界停机只保证报停是真的停不保证没报停就一定不停。接受这个不完全性是工程工具能落地的关键。理解停机问题不可判定不是在说我们要放弃治疗而是在说完美普适的自动判断不存在可工程里我们本来就生活在各种折中方案之中想明白这一点反而让人踏实。5. 新手最容易踩的四个误区5.1 误区一现在计算机这么强应该能解决了吧会有这个错觉是因为我们总以为难是计算资源不够。但停机问题不是因为跑得慢才无解而是因为逻辑上根本不存在着一个算法。不管 CPU 快一万倍还是量子计算机普及只要它还遵循可计算的逻辑这个不存在的算法就不会冒出来。可以类比你在寻找最简分数形式的圆的周长除以直径的精确值。这不是计算精度不够的问题这是无限不循环小数永远无法写成两个整数之比。技术进步不会改变这个数学事实。停机问题和它同级别属于结构上无解。5.2 误区二既然不可判定静态分析和测试工具都是白搭这句话只对了一半。不可判定针对的是任意程序、所有性质。现实中你遇到的大部分代码尤其是生产环境中的业务代码往往是受限的、模式化的。静态分析工具、编译器优化、类型检查器都能在有限范围内做大量有效的保证。比如一门带类型系统的语言编译器可以保证这个变量不可能为空或这个类型不会混用这并不违反停机问题因为它们没有试图回答任意程序的所有行为而是在一个定义良好的抽象层上做保守的近似。可以把静态分析想成我不检查地球上所有生物的寿命但我能给某几个物种规定生命周期模型没有覆盖一切但能解决很多具体问题。5.3 误区三停机问题和 NP 难题是一回事这是我在讨论时遇到最多的混淆。NP 难题的意思是存在一个算法可以解决它只是时间在最坏情况下长得离谱而停机问题的情况更基本——不存在算法。拿旅行商问题来说虽然暴力枚举需要指数时间但理论上你总能写一个算法去枚举所有路径最终找到答案。而且如果 P 真的等于 NP还会找到多项式时间的解法。所以 NP 难题是可判定的它的难只是资源层面的。停机问题连慢慢算完的机会都没有因为不存在任何通用步骤能得到答案。5.4 误区四既然不可判定那就没有任何程序能判断会不会停恰恰相反。可判定性讨论的是对所有程序都正确的通用算法是否存在而单个程序往往非常简单。比如一个只有顺序语句、没有循环的程序可以直接判定它会停机一个循环变量单调递减且存在有限下界的程序也可以判定会停机。这正是半可判定概念的价值关于会停机这件事如果程序真的会停那么理论上存在一个不断模拟它执行的过程你花足够多时间就一定能看到它停下来如果它永远不停这个过程就不会结束。停机集合是可枚举的但不是可判定的。许多理论模型里我们愿意接受这种是就成功不是就一直等的半答案因为它仍然比没有强。6. 如果想给别人讲明白这三个比喻很好用6.1 比喻一一个自信的判卷机想象老师有一种判卷机能自动判定任何一道题的答案是否正确。学生淘气在试卷上写了一道题请判卷机回答这句话本身是对的还是错的。判卷机说对这句话就变成了悖论判卷机说错反而证明这句自己说自己错的话是对的。判卷机发现自己的规则无法处理这种自我指涉的题目。停机问题的 T 程序做的事就是给万能判定器出一道自我指涉的编程题。6.2 比喻二一面声称能照见所有镜子的镜子如果一面镜子说我能映照世界上所有镜子不管是凸面镜、凹面镜、哈哈镜。你可能会问那这面镜子能不能映照出它自己如果它照不出自己它显然不是所有镜子如果它照得出来那照出来的内容里又包含了这面镜子本身于是画面里还应该有镜子照镜子的镜子……无穷递归。这个比喻不严格等价但它能让人记住所有这个词在自我指涉面前有多脆弱。6.3 比喻三预言机拒绝预言自己如果你有一个预言机能回答任何是/否的问题。你可以问它你在回答我这个问题时会不会给出否作为答案这会让预言机陷入两难。它若答是那它就必须作答否若答否又等于承认它给出了否这个答案和是冲突。停机问题不是这个想法的普通版本但精神一致一个声称能判定所有程序行为的机器总有一个程序能把它自己的判定结果反转。7. 我自己的几个学习与教学体会7.1 从玩文字游戏到看清反证法我最早学停机问题的时候第一反应是这个证明是不是玩了个文字游戏H 本来就不存在所以 T 的代码里那个假如 H 存在的调用是空中楼阁凭什么用一个不存在的函数来论证事情后来我才想通这正是反证法的意义我们不是真的在写一个能运行的 T而是在做思想实验——如果 H 存在T 就存在而 T 的存在必然导致矛盾。所以 H 不可能存在。这个先借一把想象中的剑然后让这把剑反过来刺穿主人的结构贯穿了几乎所有不可判定性证明也是理解这个问题的钥匙。7.2 动手实验让判定器在有限世界里碰壁真正让我彻底开窍的是自己动手实现了一个只处理有限程序集合的迷你判定器。我把它限制为只处理 10 行以内的无循环程序它当然能判定出结果然后我给它加入一个程序调用自身的例子看着它在有限集合里也出现了无法回答的边界问题。这个亲手触碰边界的过程比看十遍教材都管用。强烈建议你也试试拿动态语言写一个 checker让它只分析一段限定语法的小语言然后往里丢自我调用的样例你会很快明白不可判定性到底卡在哪一步。至于对写代码的启发我的体会是写循环的时候尽量把退出条件写得显式、有限、可证。不要依赖运行一段时间自然就好了这种模糊期许也不要把不确定的递归深度藏在回调里。停机问题不会直接帮你写出更快的代码但它会提醒你很多事情不能靠一个万能工具解决得靠设计时就把边界定清楚。了解边界在哪里本身就是一种生产力。

从“程序会不会停”说起：停机问题为何不可判定

相关推荐

TSN 与 PROFINET、EtherCAT 是什么关系？从网络分层理解工业通信技术

用 Swift 和 SpriteKit 打造可二次开发的 Flappy Bird 工程样板

脑机接口（BCI）硬核对决：NextMind 9通道多电极 vs 脑智科技 VisionBCI 单通道干电极

更多资讯

流放之路 Path of Building 完全上手指南：5 个阶段跑通你的第一个 Build，天赋树与伤害计算一次讲清

MySQL数据可视化核心概念与性能优化实战指南

基于深度学习的智能仓储异常检测系统实践

易排盘V3.0紫微斗数排盘引擎集成指南：参数配置、批量排盘与避坑实践

Windows下giflib 4.1.6静态库集成与OSG GIF插件开发避坑指南

STM32F103C8T6 控制 L298N 驱动直流电机：从接线到PWM调速与闭环避坑指南

今日更新

防关联浏览器哪个好？三款产品实测差异解析

2026钢铁行业AI转型系统选型对比：多基地排产、大宗原燃料采购与质量追溯，六家厂商能力差异在哪里

影刀RPA深度实战：大模型Fine-tuning定制RPA专用Prompt与指令生成

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？