teorema de arroz
En la teoría de la computabilidad , el teorema de Rice establece que todas las propiedades semánticas no triviales de los programas son indecidibles . Una propiedad semántica es una sobre el comportamiento del programa (por ejemplo, el programa termina para todas las entradas), a diferencia de una propiedad sintáctica (por ejemplo, el programa contiene una instrucción if-then-else ). Una propiedad no es trivial si no es verdadera para todas las funciones computables parciales ni falsa para todas las funciones computables parciales.
El teorema de Rice también se puede expresar en términos de funciones: para cualquier propiedad no trivial de funciones parciales , ningún método general y efectivo puede decidir si un algoritmo calcula una función parcial con esa propiedad. Aquí, una propiedad de funciones parciales se llama trivial si se cumple para todas las funciones computables parciales o para ninguna, y un método de decisión efectivo se llama general si decide correctamente para cada algoritmo. El teorema lleva el nombre de Henry Gordon Rice , quien lo demostró en su disertación doctoral de 1951 en la Universidad de Syracuse .
(es decir, p no es ni uniformemente verdadero ni uniformemente falso para todos los lenguajes recursivamente enumerables).
Entonces es indecidible determinar para una máquina de Turing dada M , si el lenguaje reconocido por ella – L(M) – tiene la propiedad p .
En la práctica, esto significa que no existe una máquina que siempre pueda decidir si el lenguaje de una máquina de Turing dada tiene una propiedad particular no trivial. Los casos especiales incluyen, por ejemplo, la indecidibilidad de si el lenguaje reconocido por una máquina de Turing podría ser reconocido por una máquina más simple no trivial, como un autómata finito (es decir, es indecidible si el lenguaje de una máquina de Turing es regular ).
Es importante señalar que el teorema de Rice no se refiere a las propiedades de las máquinas o programas; se trata de propiedades de funciones y lenguajes. Por ejemplo, si una máquina funciona durante más de 100 pasos en una entrada particular es una propiedad decidible, aunque no es trivial. Dos máquinas diferentes que reconocen exactamente el mismo idioma pueden requerir un número diferente de pasos para reconocer la misma cadena de entrada. De manera similar, si una máquina tiene más de cinco estados es una propiedad decidible de la máquina, ya que el número de estados simplemente se puede contar. Para propiedades de este tipo, que se refieren a una máquina de Turing pero no al lenguaje reconocido por ella, el teorema de Rice no se aplica.
