Teorema de Rice

En teoria de la computació, la teorema de Rice és una teorema enunciada per Henry Gordon Rice i després generalisat junt en John Myhill i Norman Shapiro a lo que es coneix com el teorema de Rice–Shapiro. Bàsicament es pot enunciar la teorema de la següent manera:

Donada una propietat no trivial de les funcions parcials, no és computable determinar si una funció arbitrària la posseïx o no.

És un típic problema de decisió que no es pot resoldre, de la mateixa manera que el problema de la parada.

Introducció

Una atra forma d'expressar la teorema de Rice que és més útil en la teoria de la computació diu que:

Siga $S$ un conjunt de llenguages no trivial, és dir,

1. existix una màquina de Turing que reconeix un llenguage en $S$
2. existix una màquina de Turing que reconeix un llenguage no en $S$

Llavors, és indecidible determinar si un llenguage decidit per una màquina de Turing arbitrària es troba en $S$.

En la pràctica, açò significa que no hi ha una màquina que sempre puga decidir si el llenguage d'una màquina de Turing donada té una propietat no trivial particular. Els casos especials inclouen la indecidibilidad de si una màquina de Turing accepta una cadena particular, si una màquina de Turing reconeix un llenguage reconeixible particular, i si el llenguage reconegut per una màquina de Turing podria ser reconegut per una màquina no trivial més simple, tal com un autómata finito.

És important tindre en conte que la teorema de Rice no diu res sobre les propietats de les màquines o programes que no són propietats de les funcions i els llenguages. Per eixemple, si una màquina té una duració de més de 100 passos en alguna entrada és una propietat decidible, a pesar de que no és trivial. Implementant exactament el mateix llenguage, dos màquines diferents poden requerir un diferent número de passos per a reconéixer la mateixa entrada. De manera similar, si una màquina té més de 5 estats és una propietat decidible de la màquina, ya que el número d'estats pot ser contat simplement. Quan una propietat és del tipo que qualsevol de les dos màquines poden o no tindre, mentres implementen exactament el mateix llenguage, la propietat és de les màquines i no de la llengua, i la teorema de Rice no s'aplica.

Usant caracterisació de Rogers de Numeració admissible, la teorema de Rice essencialment es pot generalisar a partir de màquines de Turing per a la majoria de llenguages de programació: no existix cap método automàtic que decidixca en generalitat no trivials preguntes sobre el comportament d'un programa BlackBox.

Eixemples

Segons la teorema de Rice, si hi ha a lo manco una funció computable en una classe particular $C$, de funcions computables i una atra funció computable que no està en $C$ llavors el problema de decidir si un determinat programa calcula una funció en C és indecidible. Per eixemple, la teorema de Rice demostra que cada u dels següents conjunts de funcions computables és indecidible:

• La classe de funcions computables que tornen 0 per a cada entrada, i el seu complement.
• La classe de funcions computables que tornen 0 per lo manco per a una entrada, i el seu complement.
• La classe de funcions computables que són constants, i el seu complement.

Vore també

• Teoremes de incompletitud de Gödel
• Problema de la parada
• Teoria de la computabilidad

Notes

• Plantilla:Cite document.

• Rice, H. G. "Classes of Recursively Enumerable Sets and Their Decision Problems." Trans. Amer. Math. Soc. 74, 358-366, 1953.
• Plantilla:Cite document.