Teorema do Arroz
O teorema de Rice afirma que qualquer propriedade semântica não trivial de uma linguagem que é reconhecida por uma máquina de Turing é indecidível. Uma propriedade, P, é a linguagem de todas as máquinas de Turing que satisfazem essa propriedade.
Definição formal
Se P for uma propriedade não trivial e a linguagem que detém a propriedade, L p , for reconhecida pela máquina de Turing M, então L p = {<M> | L (M) ∈ P} é indecidível.
Descrição e propriedades
A propriedade das linguagens, P, é simplesmente um conjunto de linguagens. Se alguma linguagem pertence a P (L ∈ P), diz-se que L satisfaz a propriedade P.
Uma propriedade é chamada de trivial se não for satisfeita por nenhuma linguagem recursivamente enumerável ou se for satisfeita por todas as linguagens recursivamente enumeráveis.
Uma propriedade não trivial é satisfeita por algumas linguagens recursivamente enumeráveis e não é satisfeita por outras. Falando formalmente, em uma propriedade não trivial, onde L ∈ P, ambas as seguintes propriedades são válidas:
Property 1 - Existem máquinas de Turing, M1 e M2 que reconhecem o mesmo idioma, ou seja (<M1>, <M2> ∈ L) ou (<M1>, <M2> ∉ L)
Property 2 - Existem máquinas de Turing M1 e M2, onde M1 reconhece o idioma enquanto M2 não, ou seja, <M1> ∈ L e <M2> ∉ L
Prova
Suponha que uma propriedade P não seja trivial e φ ∈ P.
Como P não é trivial, pelo menos uma linguagem satisfaz P, ou seja, L (M 0 ) ∈ P, ∋ Máquina de Turing M 0 .
Seja w uma entrada em um determinado instante e N é uma Máquina de Turing que segue -
Na entrada x
- Execute M em w
- Se M não aceitar (ou não parar), então não aceite x (ou não pare)
- Se M aceita w, execute M 0 em x. Se M 0 aceita x, então aceite x.
Uma função que mapeia uma instância ATM = {<M, w> | M aceita a entrada w} para um N tal que
- Se M aceita w e N aceita a mesma linguagem que M 0 , então L (M) = L (M 0 ) ∈ p
- Se M não aceita w e N aceita φ, então L (N) = φ ∉ p
Como A TM é indecidível e pode ser reduzido para Lp, Lp também é indecidível.