Teorema de Rice

Teorema de Rice

El teorema de Rice establece que cualquier propiedad semántica no trivial de un lenguaje reconocida por una máquina de Turing es indecidible. La propiedad P es el lenguaje de todas las máquinas de Turing que satisfacen esta propiedad.

Definicion formal

Si P es una propiedad no trivial y el lenguaje que contiene esta propiedad, Lp, es reconocido por la máquina de Turing M, entonces Lp = { | L (M) ∈ P} es indecidible.

Descripción y propiedades

• Una propiedad de los lenguajes P es simplemente una colección de lenguajes. Si alguna lengua pertenece a P (L ∈ P), se dice que L satisface la propiedad P.

• Se dice que una propiedad es trivial si no es satisfecha por ningún lenguaje enumerable recursivamente, o si es satisfecha por todos los lenguajes enumerados recursivamente.

• Algunos lenguajes enumerables de forma recursiva satisfacen una propiedad no trivial y otros no. Hablando formalmente, en la propiedad no trivial, donde L ∈ P, se cumplen las dos propiedades siguientes:

  • Propiedad 1 – Hay máquinas de Turing, M1 y M2, que reconocen el mismo idioma, es decir, cualquiera (, ∈ L), o (, ∉ L)

  • Propiedad 2 – Hay máquinas de Turing M1 y M2, donde M1 reconoce el idioma, pero M2 no, es decir ∈ L y ∉ L

Evidencia

Suponga que la propiedad P no es trivial y φ ∈ P.

Dado que P no es trivial, al menos un lenguaje satisface P, es decir, L (M0) ∈ P, ∋ máquina de Turing M0.

Sea w la entrada en un momento particular y N la máquina de Turing que sigue:

Entrada x

• Ejecute M en w
• Si M no acepta (o no se detiene), entonces no acepta x (o no se detiene)
• Si M acepta w, ejecute M0 en x. Si M0 toma x, entonces tome x.

Instancia de ATM de mapeo de funciones = { | M toma la entrada w} en N tal que

• Si M toma w y N toma el mismo idioma que M0, entonces L (M) = L (M0) ∈ p
• Si M no toma w y N toma φ, entonces L (N) = φ ∉ p

Dado que ATM es indecidible y puede reducirse a Lp, Lp también es indecidible.