查看“︁莱斯定理”︁的源代码

莱斯定理（Rice's theorem）是[[可计算性理论]]中的一条定理，由亨利·戈登·莱斯于1953年提出。<ref>{{Cite journal|title=Classes of recursively enumerable sets and their decision problems|url=https://www.ams.org/journals/tran/1953-074-02/S0002-9947-1953-0053041-6/home.html|last=Rice|first=H. G.|date=1953-02-01|journal=Transactions of the American Mathematical Society|issue=2|doi=10.1090/S0002-9947-1953-0053041-6|volume=74|pages=358–358|language=en-US|issn=0002-9947|access-date=2018-07-02|archive-date=2021-05-07|archive-url=https://web.archive.org/web/20210507002330/https://www.ams.org/journals/tran/1953-074-02/S0002-9947-1953-0053041-6/home.html}}</ref>定理指出，[[递归可枚举语言]]的所有非平凡（nontrival）性质都是[[可判定性|不可判定]]的。

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

== 定理 ==
<math>P</math>是所有图灵可计算函数构成的集合，<math>S</math>是<math>P</math>的一个非空真子集，即：<math>\emptyset\neq S \subsetneq P</math>。将图灵机以某种方式编码，使得每一个<math>n\in \mathbb{N}</math>都唯一对应一个图灵机<math>M_n</math>。

则：集合<math>C(S)</math>=<math>\{n|M_n</math> 计算的函数在集合<math>S</math>中<math>\}</math>是不可判定的。

==參考文獻==
{{Reflist}}

[[Category:数学定理]]
[[Category:自动机]]
[[Category:计算模型]]
[[Category:图灵机]]