跳转到内容

莱斯定理

维基百科,自由的百科全书

莱斯定理(Rice's theorem)是可计算性理论中的一条定理,由亨利·戈登·莱斯于1953年提出。[1]定理指出,递归可枚举语言的所有非平凡(nontrival)性质都是不可判定的。

“非平凡”是指,仅被部分递归可枚举语言具有的特性。

定理

[编辑]

是所有图灵可计算函数构成的集合,的一个非空真子集,即:。将图灵机以某种方式编码,使得每一个都唯一对应一个图灵机

则:集合= 计算的函数在集合是不可判定的。

參考文獻

[编辑]
  1. ^ Rice, H. G. Classes of recursively enumerable sets and their decision problems. 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) (美国英语).