NOIP 普及组初赛 · NOIP 2007 普及组初赛试题 第 13 题

一个无法靠自身的控制终止的循环成为“死循环”，例如，在 C++ 语言程序中，语句 while(1) printf("*"); 就是一个死循环，运行时它将无休止地打印 * 号。下面关于死循环的说法中，只有（  ）是正确的。

这道题考的是计算理论里最硬核的‘停机问题’。拿到题先别想编译器功能，直接回忆图灵证明：不存在通用算法能判断任意程序会不会死循环，所以任何声称‘能检测’的说法都是错的。

最容易错选B，觉得有些编译器确实能报‘死循环’，但那是针对特定代码模式（比如while(true)且无break）的静态分析，不是通用判定，题目问的是理论上的‘任何一个程序’，所以B不成立。C错把死循环当成语法错误，语法只管写没写对，不管逻辑对不对，死循环是逻辑/语义层面的无限运行，编译器根本管不着。D则混淆了死锁和死循环，死锁是资源分配图的问题，理论上可判定，而死循环对应停机问题，数学上不可判定，两者不是一回事。

考点与核心概念

这道题考查的是计算理论中的‘停机问题’（Halting Problem）。简单说，就是：是否存在一个通用的算法，输入任意程序和任意输入数据，能准确判断这个程序最终会不会停下来（即会不会陷入死循环）。

图灵在1936年用反证法证明了这样的算法不存在。证明的核心思路非常巧妙：假设存在一个算法H(P, I)，它能判断程序P在输入I下是否终止。然后我们构造一个‘捣乱’的程序D，它调用H来判断自己是否会终止，如果H说‘会终止’，D就进入死循环；如果H说‘不会终止’，D就立刻停止。显然，D的行为和H的预言总是相反，这就产生了矛盾。因此，假设不成立，停机问题是不可判定的。

相关的理论术语需要搞清楚：

• 可判定问题：存在算法能在有限步内给出确定的‘是’或‘否’。
• 半可判定：如果是‘是’，算法能跑完给出答案；如果是‘否’，算法可能永远跑不下去。
• 不可判定：不存在任何算法能在有限步内对所有情况给出答案。

死循环（无限运行）正是停机问题的反面，属于不可判定范畴。

命题视角

命题人特别喜欢在这个点上挖坑，主要就三个方向： 1. 混淆‘特定检测’与‘通用判定’：比如选项B说‘有些编译系统可以检测’，听起来很合理，因为编译器确实能报一些明显的死循环。但题目问的是‘任何一个程序’，这是理论上的全称量词，B显然偷换了概念。 2. 把逻辑错误当成语法错误：选项C说死循环是语法错误，这是典型的常识陷阱。语法只管代码写得对不对（比如括号配对、类型匹配），不管程序逻辑会不会跑飞。 3. 张冠李戴：选项D把死锁和死循环混为一谈。死锁是多进程/多线程抢资源导致的，理论上可以用资源分配图检测；死循环是单程序无限运行，属于停机问题，两者理论基础完全不同。