Teorema de Rice

En teoría de la computación, el teorema de Rice es un teorema enunciado por Henry Gordon Rice y luego generalizado junto con John Myhill y Norman Shapiro a lo que se conoce como el teorema de Rice–Shapiro. Básicamente se puede enunciar el teorema de la siguiente manera:

Es un típico problema de decisión que no se puede resolver, al igual que el problema de la parada.

Otra forma de expresar el teorema de Rice que es más útil en la teoría de la computación dice que:

Sea ${displaystyle S}$ un conjunto de lenguajes no trivial, es decir,

Entonces, es indecidible determinar si un lenguaje decidido por una máquina de Turing arbitraria se encuentra en ${displaystyle S}$.

En la práctica, esto significa que no hay una máquina que siempre pueda decidir si el lenguaje de una máquina de Turing dada tiene una propiedad no trivial particular. Los casos especiales incluyen la indecidibilidad de si una máquina de Turing acepta una cadena particular, si una máquina de Turing reconoce un lenguaje reconocible particular, y si el lenguaje reconocido por una máquina de Turing podría ser reconocido por una máquina no trivial más simple, tal como un autómata finito.

Es importante tener en cuenta que el teorema de Rice no dice nada acerca de las propiedades de las máquinas o programas que no son propiedades de las funciones y los lenguajes. Por ejemplo, si una máquina tiene una duración de más de 100 pasos en alguna entrada es una propiedad decidible, a pesar de que no es trivial. Implementando exactamente el mismo lenguaje, dos máquinas diferentes pueden requerir un diferente número de pasos para reconocer la misma entrada. De manera similar, si una máquina tiene más de 5 estados es una propiedad decidible de la máquina, ya que el número de estados puede ser contado simplemente. Cuando una propiedad es del tipo que cualquiera de las dos máquinas pueden o no tener, mientras implementan exactamente el mismo lenguaje, la propiedad es de las máquinas y no de la lengua, y el teorema de Rice no se aplica.

Usando caracterización de Rogers de Numeración admisible, el teorema de Rice esencialmente se puede generalizar a partir de máquinas de Turing para la mayoría de lenguajes de programación: no existe ningún método automático que decida con generalidad no triviales preguntas sobre el comportamiento de un programa BlackBox.

Según el teorema de Rice, si hay al menos una función computable en una clase particular ${displaystyle C}$, de funciones computables y otra función computable que no está en ${displaystyle C}$ entonces el problema de decidir si un determinado programa calcula una función en C es indecidible. Por ejemplo, el teorema de Rice demuestra que cada uno de los siguientes conjuntos de funciones computables es indecidible:

Las aplicaciones de teorema de Rice son numerosas. La primera aplicación que se nota a simple vista es que no es computable saber si una función arbitraria se detiene para algún valor de entrada (hay al menos una que sí lo hace, y otra que no, por lo que se trata de una propiedad no trivial). Otra aplicación que se puede dar a este teorema es saber que no es computable determinar si un programa es malicioso (que realizará acciones maliciosas como por ejemplo, escribir en cierta zona reservada de memoria, copiarse a sí mismo en otro programa, etc.). Esto no quiere decir que ningún programa malicioso sea detectable, sino que para cualquier procedimiento de detección fiable, siempre se puede definir un programa malicioso que lo burle.

Sea ${displaystyle phi colon mathbb {N} o mathbf {P} ^{(1)}}$ una numeración de Gödel de funciones computables; un mapa de los números naturales para la clase ${displaystyle mathbf {P} ^{(1)}}$ de funciones computables parcialmente unarias. Denotamos ${displaystyle phi _{e}:=phi (e)}$ a la e-sima función computable parcial.

Identificamos cada propiedad que una función computable puede tener con el subconjunto ${displaystyle mathbf {P} ^{(1)}}$ que consiste en las funciones con esa propiedad. Así, dado un conjunto ${displaystyle Fsubseteq mathbf {P} ^{(1)}}$, de funciones computables ${displaystyle phi _{e}}$ tiene la propiedad F si y solo si ${displaystyle phi _{e}in F}$. Por cada propiedad ${displaystyle Fsubseteq mathbf {P} ^{(1)}}$ hay un problema de decisión asociado ${displaystyle D_{F}}$ de determinar, dado e, si ${displaystyle phi _{e}in F}$.

El teorema de Rice dice que un problema de decisión ${displaystyle D_{F}}$ es decidible (también llamada recursivo o computable) si y solo si ${displaystyle F=emptyset }$ o ${displaystyle F=mathbf {P} ^{(1)}}$.

En la definición del teorema, una propiedad es no trivial si hay funciones que la tienen, y otras que no. La demostración del teorema se basa precisamente en explotar la posibilidad de resolver el problema de la parada si se tiene un reconocedor de propiedades no triviales. Así, si se supone una cierta propiedad ${displaystyle A}$ no trivial. Eso quiere decir que hay al menos una función ${displaystyle F_{1}}$ que la tiene, y una función ${displaystyle F_{2}}$ que no la tiene. Supongamos ahora que tenemos un algoritmo ${displaystyle R_{A}}$ definido como

${displaystyle R_{a}(n)={egin{cases}1,&{mbox{si }}F_{n} {mbox{tiene la propiedad A}}\0,&{mbox{caso contrario}}end{cases}}}$

Definiendo ahora un programa ${displaystyle T_{m},n(i)}$ que primero calcula ${displaystyle F_{n}(m)}$ y luego calcula ${displaystyle F_{1}(i)}$, valor que se devuelve como resultado. Puede verse que este programa devuelve lo mismo que ${displaystyle F_{1}(i)}$, y por lo tanto tiene la propiedad ${displaystyle A}$, sí y sólo si ${displaystyle F_{n}(m)}$ se para. Si ${displaystyle w(m,n)}$ es la codificación del programa ${displaystyle T_{m},n}$, entonces podemos definir un algoritmo para determinar la parada como ${displaystyle H(m,n)=R_{A}(w(m,n))}$. Como esto es imposible, por el problema de la parada, entonces no existe ${displaystyle R_{A}}$ (si la propiedad ${displaystyle A}$ fuera algo que ${displaystyle F_{n}(m)}$ cumple al no pararse, se hubiera podido hacer un razonamiento similar empleando ${displaystyle F_{2}}$ en lugar de ${displaystyle F_{1}}$).

Existen algunas maneras más de demostrar este teorema, la demostración anterior fue mediante una reducción del problema de la parada, también se puede demostrar mediante el teorema de recursión de Kleene por ejemplo.