Teorema de Rice

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
Teorema de Rice
Mestrado em Ciência da Computação 
Profa. Sandra de Amo 
*
Seja P um problema satisfazendo as seguintes condições:
Problema P
<M>
1. Os inputs de P são códigos de máquina de Turing
2. Existe um input <M1> tal que P responde positivamente a <M1> 
Problema P
<M1>
YES !
Problema P
<M2>
NO !
 Existe um input <M2> tal que P responde negativamente a <M2> 
 
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 A ≤ P 
 
TM
< M,w > < M’ > 
M’ = No input x faça
Execute M em w.
 Se M pára em qr, M’ pára em qr.
 Se M pára em qa, executa M1 em x
 Se M1 pára em qa, M’ pára em qa
 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
 ≤
Logo 
é indecidível 
Logo 
é indecidível 
P
*
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:
Seus inputs são códigos de MT
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* )
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
*
*
*
*
*
*
*