萊斯定理(Rice's theorem)是可計算性理論中的一條定理,由亨利·戈登·萊斯於1953年提出。[1]定理指出,遞歸可枚舉語言的所有非平凡(nontrival)性質都是不可判定的。
「非平凡」是指,僅被部分遞歸可枚舉語言具有的特性。
定理
是所有圖靈可計算函數構成的集合,是的一個非空真子集,即:。將圖靈機以某種方式編碼,使得每一個都唯一對應一個圖靈機。
則:集合= 計算的函數在集合中是不可判定的。
參考文獻
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.