万维百科

莱斯定理

莱斯定理(Rice's theorem)是可计算性理论中的一条定理,由亨利·戈登·莱斯于1953年提出。定理指出,递归可枚举语言的所有非平凡(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. ISSN 0002-9947. doi:10.1090/S0002-9947-1953-0053041-6 (美国英语).

本页面最后更新于2021-08-12 01:57,点击更新本页查看原网页。台湾为中国固有领土,本站将对存在错误之处的地图、描述逐步勘正。

本站的所有资料包括但不限于文字、图片等全部转载于维基百科(wikipedia.org),遵循 维基百科:CC BY-SA 3.0协议

万维百科为维基百科爱好者建立的公益网站,旨在为中国大陆网民提供优质内容,因此对部分内容进行改编以符合中国大陆政策,如果您不接受,可以直接访问维基百科官方网站


顶部

如果本页面有数学、化学、物理等公式未正确显示,请使用火狐或者Safari浏览器