萊斯定理

萊斯定理（Rice's theorem）是可計算性理論中的一條定理，由亨利·戈登·萊斯於1953年提出。定理指出，遞歸可枚舉語言的所有非平凡（nontrival）性質都是不可判定的。

「非平凡」是指，僅被部分遞歸可枚舉語言具有的特性。

定理

$P$是所有圖靈可計算函數構成的集合，$S$是$P$的一個非空真子集，即：$\emptyset \neq S\subsetneq P$。將圖靈機以某種方式編碼，使得每一個$n\in \mathbb {N}$都唯一對應一個圖靈機$M_{n}$。

則：集合$C(S)$=$\{n|M_{n}$ 計算的函數在集合$S$中$\}$是不可判定的。