Automata Theory 简明教程

Rice Theorem

Rice 定理指出，由图灵机识别的语言任何非平凡语义属性都是不可判定的。一个属性 P 是满足该属性的所有图灵机的语言。

Rice theorem states that any non-trivial semantic property of a language which is recognized by a Turing machine is undecidable. A property, P, is the language of all Turing machines that satisfy that property.

Formal Definition

如果 P 是一个非平凡属性而语言持有属性，Lp，由图灵机 M 识别，则 Lp = {<M> | L(M) ∈ P} 是不可判定的。

If P is a non-trivial property, and the language holding the property, Lp , is recognized by Turing machine M, then Lp = {<M> | L(M) ∈ P} is undecidable.

Description and Properties

  1. Property of languages, P, is simply a set of languages. If any language belongs to P (L ∈ P), it is said that L satisfies the property P.

  2. A property is called to be trivial if either it is not satisfied by any recursively enumerable languages, or if it is satisfied by all recursively enumerable languages.

  3. A non-trivial property is satisfied by some recursively enumerable languages and are not satisfied by others. Formally speaking, in a non-trivial property, where L ∈ P, both the following properties hold: Property 1 − There exists Turing Machines, M1 and M2 that recognize the same language, i.e. either ( <M1>, <M2> ∈ L ) or ( <M1>,<M2> ∉ L ) Property 2 − There exists Turing Machines M1 and M2, where M1 recognizes the language while M2 does not, i.e. <M1> ∈ L and <M2> ∉ L

Proof

假设一个属性P为非平凡的且 φ ∈ P。

Suppose, a property P is non-trivial and φ ∈ P.

由于P为非平凡的，所以至少有一门语言满足P，即L(M0) ∈ P，此图灵机为M0。

Since, P is non-trivial, at least one language satisfies P, i.e., L(M0) ∈ P , ∋ Turing Machine M0.

不妨设w是一个特定时刻的输入，N是一台图灵机，它遵循−

Let, w be an input in a particular instant and N is a Turing Machine which follows −

由输入x

On input x

  1. Run M on w

  2. If M does not accept (or doesn’t halt), then do not accept x (or do not halt)

  3. If M accepts w then run M0 on x. If M0 accepts x, then accept x.

一个函数将一个实例ATM = {<M,w>| M接受输入w}映射到一个N，使得

A function that maps an instance ATM = {<M,w>| M accepts input w} to a N such that

  1. If M accepts w and N accepts the same language as M0, Then L(M) = L(M0) ∈ p

  2. If M does not accept w and N accepts φ, Then L(N) = φ ∉ p

由于ATM是不可判定性的，并且它可以简化为Lp，因此Lp也是不可判定性的。

Since ATM is undecidable and it can be reduced to Lp, Lp is also undecidable.