Teorema de Rice
Origem: Wikipédia, a enciclopédia livre.
Em ciência da computação, o teorema de Rice (também conhecido como o Teorema de Rice-Myhill-Shapiro), assim chamado em homenagem a Henry Gordon Rice, é um resultado importante da teoria das funções computáveis. Uma propriedade das funções parciais diz-se trivial se se verifica para todas as função parciais computáveis ou para nenhuma. O teorema diz que, para qualquer propriedade não trivial de funções parciais, a questão de saber se um dado algoritmo computa uma função parcial com essa propriedade é um problema indecidível.
[editar] Referências
- Rice, H. G. "Classes of Recursively Enumerable Sets and Their Decision Problems." Trans. Amer. Math. Soc. 74, 358-366, 1953.
