萊斯定理

是所有圖靈可計算函數構成的集合，

是

的一個非空真子集，即：

。將圖靈機以某種方式編碼，使得每一個

都唯一對應一個圖靈機

^[1]  。

則：集合

計算的函數在集合

中

是不可判定的。

遞歸可枚舉語言的所有非平凡（nontrival）性質都是不可判定的。“非平凡”是指，僅被部分遞歸可枚舉語言具有的特性。