Teorema de Rice
Mestrado em Ciência da
Computação
Profa. Sandra de Amo
Seja P um problema satisfazendo as seguintes condições:
1. Os inputs de P são códigos de máquina de Turing
<M>
Problema P
2. Existe um input <M1> tal que P responde positivamente a <M1>
<M1>
Problema P
YES !
Existe um input <M2> tal que P responde negativamente a <M2>
<M2>
Problema P
NO !
3. Se L(M1) = L(M2) então <M1> ϵ P  <M2> ϵ P
(isto é, a resposta do problema só depende do que a máquina
faz e não do seu código)
Então P é indecidível
• O Teorema de Rice = “template geral” para provar que
certos problemas são indecidíveis
• Qualquer problema que se encaixa nas hipóteses do
teorema de Rice é indecidível.
• Assim:
- para provar que um certo problema P é indecidível:
1. “inventar” uma prova particular de indecidibilidade
algum problema indecidivel se reduz a P ?
OU
2. verificar que o problema satisfaz as hipóteses
do Teorema de Rice.
Prova:
• Considere a máquina M2 tal que L(M2) = ø (M2 não aceita nenhum string).
•
•
Caso 1: Suponhamos que <M2>  P
(isto é, P responde negativamente a <M2>)
Pela condição (2) sabemos que existe uma máquina <M1> tal que
<M1> ϵ P.
Mostremos que ATM ≤ P
< M,w >
< M’ >
M’ = No input x faça
1. Execute M em w.
2.
Se M pára em qr, M’ pára em qr.
3.
Se M pára em qa, executa M1 em x
4.
Se M1 pára em qa, M’ pára em qa
5.
Se M1 pára em qr, M’ pára em qr
Se M não aceita w então M’ não aceita nenhum input x.
Isto é: L(M’) = ø = L(M2) . Logo <M’> é instância negativa de P
Se M aceita w então M’ atua exatamente como M1.
Isto é: L(M’) = L(M1). Logo <M’> é instância positiva de P
Caso 2: Suponhamos que <M2> ϵ P (isto é, P responde positivamente a <M2>)
Consideramos o problema P
<M2>  P
Usando o mesmo argumento do Caso 1, mostramos que
A TM ≤ P
Logo
P
é indecidível
Logo
P
é indecidível
Exemplo de Aplicação do Teorema de Rice
Reg = {<M> : L(M) é regular}
Mostrar que Reg é indecidível.
Prova: Reg satisfaz as 3 condições do Teorema de Rice:
1.
Seus inputs são códigos de MT
2.
Existe uma MT M1 tal que L(M1) não é regular (basta considerar a MT tal
que L(M1) = palindromos
Existe uma MT M2 tal que L(M2) é regular (basta considera a MT tal que
L(M2) = 0*1* )
3.
Se M e M’ são duas MT tais que L(M) = L(M’) então
•
•
ou ambas estão em Reg (no caso de L(M) = L(M’) ser regular )
ou ambas não estão em Reg (no caso de L(M) = L(M’) não ser regular.
Alguns problemas indecidíveis não
verificam as condições do T. Rice:
P = {<M> | M pára em algum string w}
Mostre que a condição 3 do Teorema de Rice não
é verificada para o problema P.
Logo, não podemos utilizar o T. Rice para mostrar
que P é indecidível.
Precisamos utilizar a técnica da redução.
Realmente: Consideremos as seguintes M.T.
• M1
– entra em loop para todo string w ≠ 0,
– pára em qr qdo executada em w = 0
É claro que L(M1) = 
• M2
– entra em loop para todo string w
É claro que L(M2) = 
Logo: L(M1) = L(M2)
Mas : <M2> ϵ P
<M1> ϵ P