NOIP 提高组初赛 · NOIP 2007 提高组初赛试题 第 10 题

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

这道题考的是计算理论中图灵停机问题的不可判定性，拿到题先想：判断任意程序会不会死循环，等价于判断它会不会停机，而这是图灵证明无法通用解决的，所以任何编译系统都不可能做全量检测，直接锁定 A。

容易把死循环当成语法错误选 C，其实它是语义层面的逻辑错误，编译器只负责语法检查；也容易混淆死锁和死循环选 D，死锁是并发资源竞争问题，确实有检测手段，但死循环是单线程控制流问题，二者不可类比；还有人觉得有些编译器能检测就选 B 或 E，忽略了题目问的是“不存在一种算法对任意程序都能判断”，也就是通用判定器，局部检测或事后处理都不符合这个定义。

这道题考查的是计算理论中一个非常硬核的知识点——图灵停机问题（Halting Problem）。命题人挖坑很典型：把‘死循环’这个编程概念，直接映射到‘任意程序是否会终止’这个计算理论核心问题，然后让你判断是否存在一个通用算法能解决它。很多学生看到‘死循环’就本能地想‘编译器不是能报错吗？’，或者把‘死锁’和‘死循环’混为一谈，这都是因为没抓住题目的理论深度。

首先得把概念捋直白：死循环是指程序进入某个状态后，没有终止条件（或者条件永远为真），导致它无限执行下去。在 C++ 里 while(1) printf("*"); 就是典型例子。那怎么判断一个程序会不会死循环呢？从计算理论角度看，这完全等价于判断它是否会‘停机’——也就是程序在有限步内结束运行。图灵在 1936 年就用反证法证明了：不存在一个通用算法，能对‘任意程序及任意输入’给出正确回答（终止或不停机）。换句话说，停机问题是不可判定的。

命题人为什么这么考？因为这是计算机科学的基石之一，也是区分‘能做什么’和‘想当然以为能做’的关键。编译器确实能检测某些死循环，比如无限递归且无栈溢出保护、某些静态分析可发现的死循环，或者像 C++ 的 while(1) 这种显式写法。但这只是‘特定情况’的检测，不是‘通用判定器’。题目问的是‘不存在一种算法，对任何一个程序及相应的输入数据，都可以判断是否会出现死循环’，这个‘任何一个’就是关键——它要求算法必须覆盖所有可能，而图灵已经证明这不可能。

现在逐项拆解选项，看看陷阱在哪：

选项 A 说‘不存在一种算法，对任何一个程序及相应的输入数据，都可以判断是否会出现死循环，因而，任何编译系统都不做死循环检验’。前半句完全正确，后半句‘因而’是命题人的逻辑陷阱：虽然理论上不可能有通用检测器，但实际编译系统确实会做‘局部检测’，比如静态分析、递归深度限制、特定语法结构的检测等。所以 A 的后半句严格来说不成立——编译系统不是‘不做死循环检验’，而是‘不做通用死循环检验’。但这里要注意，题目问的是‘只有（ ）是正确的’，我们需要看哪个选项整体逻辑最严密。实际上，A 的前半句是对停机问题的正确陈述，而后半句的‘因而’是命题人故意加的误导性推论，但结合上下文和命题习惯，A 通常被视为正确选项，因为它的核心在于强调‘不存在通用算法’这一理论事实，而‘编译系统不做死循环检验’在这里应理解为‘不做通用死循环检验’，这是一种常见的命题表述方式，旨在突出理论上的不可能性。

选项 B 说‘有些编译系统可以检测出死循环’。这本身没错，但题目问的是‘只有（ ）是正确的’，B 只是部分正确，且没有触及‘不存在通用算法’这一核心，因此不能作为唯一正确答案。

选项 C 说‘死循环属于语法错误，既然编译系统能检查各种语法错误，当然也应该能检查出死循环’。这是典型的概念混淆！死循环是语义错误（逻辑错误），不是语法错误。语法错误是指代码不符合语言规范，比如缺少分号、括号不匹配等；而死循环是程序逻辑上的错误，代码本身语法完全正确，只是运行时不会终止。所以 C 错得离谱。

选项 D 说‘死循环与多进程中出现的“死锁”差不多，而死锁是可以检测的，因而，死循环也是可以检测的’。这也是概念混淆！死锁是并发编程中的资源竞争问题，确实有检测手段（如死锁图分析、超时检测等），但死循环是单线程控制流问题，二者根本不在一个维度。死锁可检测是因为它涉及资源分配图，而死循环是状态转移问题，图灵已经证明无法通用检测。所以 D 错得离谱。

选项 E 说‘对于死循环，只能等到发生时做现场处理，没有什么更积极的手段’。这同样忽略了局部检测的可能性，比如编译器可以检测 while(1) 这种显式写法，或者静态分析可以检测某些递归模式。所以 E 也不对。

综上所述，只有选项 A 在理论层面完全正确，尽管它的后半句在实际工程中有争议，但命题人显然是想考察图灵停机问题的不可判定性这一核心概念。因此，正确答案是 A。

从考频趋势来看，计算机发展史相关题目在 NOIP 提高组初赛中考过 29 题，覆盖 2007-2020 年，其中 2007 年考了 5 题，2008 年 6 题，2009 年 2 题，2010 年 2 题，2011 年 3 题，2012 年 9 题，2013 年 1 题，2020 年 1 题。分赛事统计：NOIP 提高组初赛 15 题，普及组 13 题，CSP 提高级 1 题。这类题目往往出现在初赛的理论部分，用来考察学生对计算机科学基础概念的理解。未来可能继续以类似形式考查图灵机的相关概念，如可判定性、递归函数等，但暂无足够依据预测具体年份或题型变化。建议学生在复习时不仅要记住结论，更要理解背后的理论依据，这样才能应对各种变式题目。