萊斯定理

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

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

定理

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

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