莱斯定理

莱斯定理（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 \}}$ 是不可判定的。

參考文獻

1. Rice, H. G. . Transactions of the American Mathematical Society. 1953-02-01, 74 (2): 358–358 [2018-07-02]. ISSN 0002-9947. doi:10.1090/S0002-9947-1953-0053041-6. （原始内容存档于2021-05-07） （美国英语）.