Teorema del arroz
El teorema de Rice establece que cualquier propiedad semántica no trivial de un lenguaje que sea reconocida por una máquina de Turing es indecidible. Una propiedad, P, es el lenguaje de todas las máquinas de Turing que satisfacen esa propiedad.
Definicion formal
Si P es una propiedad no trivial, y el lenguaje que contiene la propiedad, L p , es reconocido por la máquina de Turing M, entonces L p = {<M> | L (M) ∈ P} es indecidible.
Descripción y propiedades
La propiedad de los lenguajes, P, es simplemente un conjunto de lenguajes. Si alguna lengua pertenece a P (L ∈ P), se dice que L satisface la propiedad P.
Una propiedad se considera trivial si no es satisfecha por ningún lenguaje recursivamente enumerable o si es satisfecha por todos los lenguajes recursivamente enumerables.
Una propiedad no trivial es satisfecha por algunos lenguajes enumerables de forma recursiva y no satisfecha por otros. Hablando formalmente, en una propiedad no trivial, donde L ∈ P, se cumplen las dos propiedades siguientes:
Property 1 - Existen Máquinas de Turing, M1 y M2 que reconocen el mismo idioma, es decir (<M1>, <M2> ∈ L) o (<M1>, <M2> ∉ L)
Property 2 - Existen Máquinas de Turing M1 y M2, donde M1 reconoce el idioma mientras que M2 no, es decir <M1> ∈ L y <M2> ∉ L
Prueba
Supongamos que una propiedad P no es trivial y φ ∈ P.
Como, P no es trivial, al menos un lenguaje satisface P, es decir, L (M 0 ) ∈ P, ∋ Máquina de Turing M 0 .
Sea w una entrada en un instante particular y N es una máquina de Turing que sigue:
En la entrada x
- Ejecute M en w
- Si M no acepta (o no se detiene), entonces no acepte x (o no se detenga)
- Si M acepta w, ejecute M 0 en x. Si M 0 acepta x, entonces acepte x.
Una función que mapea una instancia ATM = {<M, w> | M acepta la entrada w} a una N tal que
- Si M acepta w y N acepta el mismo idioma que M 0 , entonces L (M) = L (M 0 ) ∈ p
- Si M no acepta w y N acepta φ, entonces L (N) = φ ∉ p
Dado que A TM es indecidible y puede reducirse a Lp, Lp también es indecidible.