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: Seaun conjunto de lenguajes no trivial, es decir, Entonces, es indecidible determinar si un lenguaje decidido por una máquina de Turing arbitraria se encuentra enEn 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.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.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á enentonces el problema de decidir si un determinado programa calcula una función en C es indecidible.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.de funciones computables parcialmente unarias.a la e-sima función computable parcial.Identificamos cada propiedad que una función computable puede tener con el subconjuntoque consiste en las funciones con esa propiedad.hay un problema de decisión asociadode determinar, dado e, siEn 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 propiedadEso quiere decir que hay al menos una función, valor que se devuelve como resultado.Como esto es imposible, por el problema de la parada, entonces no existecumple al no pararse, se hubiera podido hacer un razonamiento similar empleandoExisten 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.