莱斯定理

莱斯定理（Rice's theorem）是可计算性理论中的一条定理，由亨利·戈登·莱斯于1953年提出。定理指出，递归可枚举语言的所有非平凡（nontrival）性质都是不可判定的。

“非平凡”是指，仅被部分递归可枚举语言具有的特性。

定理

$P$是所有图灵可计算函数构成的集合，$S$是$P$的一个非空真子集，即：$\mathrm{\varnothing }\ne S⊊P$。将图灵机以某种方式编码，使得每一个$n\in \mathbb{N}$都唯一对应一个图灵机$M_n$。

则：集合$C(S)$=$\{n|M_n$ 计算的函数在集合$S$中$\}$是不可判定的。