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也是不可判定的。