Rice 定理 | Codeboy's Blog

形式陈述

设 $\mathcal P$ 是图灵可识别语言的一个语义性质，即它只取决于机器识别的语言，而不取决于机器语法；并且 $\mathcal P$ 非平凡：有某台机器识别的语言具有该性质，也有某台机器识别的语言不具有。Rice 定理断言索引集

\{\langle M\rangle:L(M)\text{ 具有 }\mathcal P\}

不可判定。等价版本可对部分可计算函数的非平凡外延性质陈述。

证明先设 $\varnothing\notin\mathcal P$ 。由非平凡性，选取某个 $B\in\mathcal P$ 及识别器 $R_B$ 。对停机实例 $\langle M,w\rangle$ ，编译机器 $N_{M,w}$ ：收到输入 $y$ 后，先模拟 $M(w)$ ；若该模拟停机，再运行 $R_B(y)$ ，并在后者接受时接受。于是

L(N_{M,w})= \begin{cases} B,&M(w)\text{ 停机},\\ \varnothing,&M(w)\text{ 不停机}. \end{cases}

参数化定理保证从 $\langle M,w\rangle$ 生成这段代码的函数总可计算：只嵌入常量，不预先执行模拟。无效源编码映到空语言识别器。因此这是从停机问题到性质索引集的映射归约，后者不可能可判定。

若 $\varnothing\in\mathcal P$ ，对可识别语言类中的补性质 $\mathcal P^{\mathrm c}$ 使用前一段。补性质仍非平凡且不含空语言，所以它的索引集不可判定；若原性质可判定，在合法机器编码上翻转答案便能判定补性质，无效编码则直接拒绝，产生矛盾。这个分情况步骤避免假装能在永不停机分支中切换到任意指定行为。

直觉

Rice 定理把大量“这个程序算出的函数是否具有性质 $P$ ”的问题一次性归入不可判定：只要问题真正询问程序所计算的对象，答案既非对所有程序恒真也非恒假，就不存在对所有程序作出完备判定的算法。证明不是逐个分析性质，而是利用通用机器把某个已知不可判定行为嵌入程序语义：先让新程序等待源计算；停机才释放预选识别器，不停机便什么也不接受。空语言位于性质的哪一侧，决定直接使用该性质还是先取补性质。决定性条件是性质只依赖程序算什么，而不依赖代码怎么写。

例子与边界

“ $L(M)$ 是否为空、有限、正则、等于某个固定非平凡语言或包含字符串 101”都是非平凡语义性质，因此属于 Rice 定理范围并且不可判定。相反，“程序源码长度是否小于 $100$ ”“ $M$ 是否有五个状态或恰有三个状态”是机器文本的语法性质，可直接检查；“ $M$ 在给定输入上是否于 100 步内停机”也可做有限模拟。这些反例说明不能把所有程序问题都误称为 Rice 定理。定理本身只给不可判定性，不自动说明相应索引集是否可识别或属于哪个算术层级。

定理不意味着所有语义问题都不可处理：在有限状态机、总函数语言或受限类型系统中，相应性质可能可判定。它也不直接覆盖运行时间恰为多少步这类依赖具体实现的性质；应用前必须先确认性质对计算等价程序保持不变。

推论与应用

Rice 定理把大量逐题归约压缩成统一原则，用于证明程序等价、语言性质和部分函数性质不可判定。可接受编号说明索引如何指向程序行为，$s$-$m$-$n$ 定理提供有效代码参数化，Kleene 递归定理则可构造会引用自身索引的语义固定点；映射归约与停机问题构成另一条标准证明骨架。实际静态分析必须限制语言，或在可靠性与完备性之间取舍。

参考资料

Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Ch. 5, Rice theorem and semantic properties of recognizable languages。
Hartley Rogers Jr., Theory of Recursive Functions and Effective Computability, MIT Press, 1987，Chs. 11–12, index sets and Rice theorem。
Andrew Marks, Computability Theory, 2024，§3.3，空行为与补性质的分情况证明。

形式陈述 ​

反向链接

形式陈述