Teorema de Rice

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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:

Dada una propiedad no trivial de las funciones parciales, no es computable determinar si una función arbitraria la posee o no.[1]

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

Introducción[editar]

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

Sea S un conjunto de lenguajes no trivial, es decir,

  1. existe una máquina de Turing que reconoce un lenguaje en S
  2. existe una máquina de Turing que reconoce un lenguaje no en S

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

En la práctica, esto significa que no hay una maquina 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.

Ejemplos[editar]

Según el teorema de Rice, si hay al menos una función computable en una clase particular C, de funciones computables y otra función computable que no esta en 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:

  • La clase de funciones computables que devuelven 0 para cada entrada, y su complemento.
  • La clase de funciones computables que devuelven 0 por lo menos para una entrada, y su complemento.
  • La clase de funciones computables que son constantes, y su complemento.

Aplicaciones[editar]

Las aplicaciones de teorema de Rice son numerosas. La primer 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.

Definición formal[editar]

Sea \phi\colon \mathbb{N} \to \mathbf{P}^{(1)} una numeración de Gödel de funciones computables; un mapa de los números naturales para la clase \mathbf{P}^{(1)} de funciones computables parcialmente unarias. Denotamos \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 \mathbf{P}^{(1)} que consiste en las funciones con esa propiedad. Así, dado un conjunto F \subseteq \mathbf{P}^{(1)}, de funciones computables \phi_e tiene la propiedad F si y solo si \phi_e \in F. Por cada propiedad F \subseteq \mathbf{P}^{(1)} hay un problema de decision asociado D_F de determinar, dado e, si \phi_e \in F.

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

Demostración[editar]

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 A no trivial. Eso quiere decir que hay al menos una función F_1 que la tiene, y una función F_2 que no la tiene. Supongamos ahora que tenemos un algoritmo R_A definido como

 R_a(n) = \begin{cases}
  1, & \mbox{si } F_n\ tiene\ la\ propiedad A \\
  0,  & en\ otro\ caso
\end{cases}

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

Otras demostraciones[editar]

Existen algunas maneras mas 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.

Véase también[editar]

Referencias[editar]

Notas[editar]

Enlaces externos[editar]