myWiki/concepts/rice-theorem.md

title, created, updated, type, tags, sources

title	created	updated	type	tags	sources
Rice's Theorem	2026-07-02	2026-07-02	concept	computability verification theory

Rice's Theorem

Rice 定理：程序的任何非平凡语义性质都是不可判定的。

形式化

给定一个程序，不存在通用算法能够判定该程序是否满足任意非平凡的行为性质（即该性质非永真、非永假）。

对 Coding Agent 验证的意义

Rice 定理从可计算性理论层面支持了 verification-horizon 的核心论点：不存在完美的验证器，因为验证任意程序是否满足用户意图在理论上就是不可判定的。

在 test-driven-rewards 中，可执行测试只能覆盖有限的行为空间——程序的完整语义永远超出任何测试套件的能力范围。

参考

• verification-horizon
• verification-trilemma
• Rice, H. G. (1953). Classes of Recursively Enumerable Sets and Their Decision Problems