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   un conjunto de lenguajes no trivial, es decir,

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

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

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.

Ejemplos

editar

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

Definición formal

editar

Sea   una numeración de Gödel de funciones computables; un mapa de los números naturales para la clase   de funciones computables parcialmente unarias. Denotamos   a la e-sima función computable parcial.

Identificamos cada propiedad que una función computable puede tener con el subconjunto   que consiste en las funciones con esa propiedad. Así, dado un conjunto  , de funciones computables   tiene la propiedad F si y solo si  . Por cada propiedad   hay un problema de decisión asociado   de determinar, dado e, si  .

El teorema de Rice dice que un problema de decisión   es decidible (también llamada recursivo o computable) si y solo si   o  .

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

 

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

Otras demostraciones

editar

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.

Véase también

editar

Referencias

editar

Enlaces externos

editar