萊斯定理

萊斯定理（Rice's theorem）是可計算性理論中的一條定理，由亨利·戈登·萊斯於1953年提出。

基本介紹

• 中文名：萊斯定理
• 外文名：Rice's theorem
• 分類：wulidingl

定理

是所有圖靈可計算函式構成的集合， 是 的一個非空真子集，即： 。將圖靈機以某種方式編碼，使得每一個 都唯一對應一個圖靈機 。

則：集合 計算的函式在集合 中 是不可判定的。

特性

遞歸可枚舉語言的所有非平凡（nontrival）性質都是不可判定的。“非平凡”是指，僅被部分遞歸可枚舉語言具有的特性。