形式陈述

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

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

不可判定。等价版本可对部分可计算函数的非平凡外延性质陈述。证明把接受问题编码进“是否获得该语义性质”。

直觉

只要问题真正询问程序所计算的对象，并且答案并非恒真或恒假，就不可能有一个算法对所有程序作出完备判定。

例子与边界

“$L(M)$$L(M)$ 是否为空、有限、正则或等于某个固定非平凡语言”都属于 Rice 定理范围。“$M$$M$ 是否有五个状态”是机器文本的语法性质，不适用；“$M$$M$ 是否在 100 步内停机”也可直接有限模拟，说明不能把所有程序问题都误称为 Rice 定理。定理只给不可判定性，不自动说明该索引集是否可识别或属于哪个算术层级。

推论与应用

Rice 定理把大量逐题归约压缩成统一原则，用于证明程序等价、语言性质和部分函数性质不可判定。实际静态分析因此必须限制语言、牺牲完备性或可靠性之一，或只给近似答案。

参考资料

• 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。