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