Rice定理

Rice定理指出，由圖靈機識別的任何語言的非平凡語義屬性都是不可判定的。屬性P是所有滿足該屬性的圖靈機的語言。

形式定義

如果P是一個非平凡屬性，並且持有該屬性的語言L_p由圖靈機M識別，則L_p = {<M> | L(M) ∈ P}是不可判定的。

描述和屬性

• 語言的屬性P只是一個語言集。如果任何語言屬於P（L ∈ P），則稱L滿足屬性P。

• 如果任何遞迴可列舉語言都不滿足該屬性，或者所有遞迴可列舉語言都滿足該屬性，則稱該屬性為平凡屬性。

• 非平凡屬性被一些遞迴可列舉語言滿足，而另一些語言不滿足。正式地說，在一個非平凡屬性中，其中L ∈ P，以下兩個屬性都成立

  • 屬性1 − 存在圖靈機M1和M2識別相同的語言，即（<M1>，<M2> ∈ L）或（<M1>，<M2> ∉ L）

  • 屬性2 − 存在圖靈機M1和M2，其中M1識別該語言而M2不識別，即<M1> ∈ L且<M2> ∉ L

證明

假設屬性P是非平凡的，並且φ ∈ P。

由於P是非平凡的，至少有一種語言滿足P，即L(M₀) ∈ P，∋圖靈機M₀。

令w為某個時刻的輸入，N是一個遵循以下規則的圖靈機：

在輸入x上

• 在w上執行M
• 如果M不接受（或不停止），則不接受x（或不停止）
• 如果M接受w，則在x上執行M₀。如果M₀接受x，則接受x。

一個將例項ATM = {<M,w>| M接受輸入w}對映到N的函式，使得

• 如果M接受w並且N接受與M₀相同的語言，則L(M) = L(M₀) ∈ p
• 如果M不接受w並且N接受φ，則L(N) = φ ∉ p

由於A_TM是不可判定的，並且可以將其歸約為Lp，因此Lp也是不可判定的。