Automata Theory 简明教程
Rice Theorem
Rice 定理指出，由图灵机识别的语言任何非平凡语义属性都是不可判定的。一个属性 P 是满足该属性的所有图灵机的语言。
Description and Properties
-
语言的属性 P 仅仅是一组语言。如果任何语言属于 P (L ∈ P)，则称 L 满足属性 P。
-
如果没有任何递归可枚举语言满足它或所有递归可枚举语言都满足它，则一个属性被称为平凡的。
-
某些递归可枚举语言满足非平凡属性而其他语言则不满足。从形式上讲，在非平凡属性中，对于 L ∈ P，满足以下两个属性： Property 1 − 存在识别相同语言的图灵机 M1 和 M2，即 ( <M1>, <M2> ∈ L ) 或 ( <M1>,<M2> ∉ L ) Property 2 − 存在图灵机 M1 和 M2，其中 M1 识别语言而 M2 无法识别，即 <M1> ∈ L 且 <M2> ∉ L
Proof
假设一个属性P为非平凡的且 φ ∈ P。
由于P为非平凡的，所以至少有一门语言满足P，即L(M0) ∈ P，此图灵机为M0。
不妨设w是一个特定时刻的输入，N是一台图灵机，它遵循−
由输入x
-
Run M on w
-
如果M不接受（或不停止），则不接受x（或不停止）
-
如果M接受w，则在x上运行M0。如果M0接受x，则接受x。
一个函数将一个实例ATM = {<M,w>| M接受输入w}映射到一个N，使得
-
如果M接受w且N接受与M0相同语言，则L(M) = L(M0) ∈ p
-
如果M不接受w且N接受φ，则L(N) = φ ∉ p
由于ATM是不可判定性的，并且它可以简化为Lp，因此Lp也是不可判定性的。