莱斯定理

${\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 \}}$是不可判定的。