萊斯定理

计算机定理

萊斯定理(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) (美國英語).