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 aquella 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 cada función computable parcial ni falsa para cada función computable parcial.
El teorema de Rice también se puede poner 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 las funciones parciales se llama trivial si es válida 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 tesis doctoral de 1951 en la Universidad de Syracuse .
Introducción
A continuación se muestra otra forma de enunciar el teorema de Rice que es más útil en la teoría de la computabilidad .
Sea S un conjunto de lenguajes que no es trivial, es decir
- existe una máquina de Turing que reconoce un lenguaje en S ,
- existe una máquina de Turing que reconoce un lenguaje no en S .
Entonces es indecidible para determinar si el lenguaje reconocido por un arbitrarias de la máquina de Turing mentiras en S .
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 la indecidibilidad de si una máquina de Turing acepta una cadena en 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, como un autómata finito .
Es importante notar que el teorema de Rice no dice nada acerca de aquellas propiedades de máquinas o programas que no son también propiedades de funciones y lenguajes. Por ejemplo, si una máquina se ejecuta durante más de 100 pasos en una entrada en particular es una propiedad decidible, aunque no es trivial. Al implementar exactamente el mismo lenguaje, dos máquinas diferentes pueden requerir un número diferente 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 simplemente se puede contar. Cuando una propiedad es del tipo que cualquiera de las dos máquinas puede tenerla o no, mientras sigue implementando exactamente el mismo lenguaje, la propiedad es de las máquinas y no del lenguaje, y el teorema de Rice no se aplica.
Usando la caracterización de Rogers de los sistemas de programación aceptables , el teorema de Rice puede esencialmente generalizarse de las máquinas de Turing a la mayoría de los lenguajes de programación de computadoras : no existe un método automático que decida con generalidad preguntas no triviales sobre el comportamiento de los programas de computadora.
Como ejemplo, considere la siguiente variante del problema de detención . Sea P la siguiente propiedad de las funciones parciales F de un argumento: P ( F ) significa que F está definida para el argumento '1'. Obviamente, no es trivial, ya que hay funciones parciales que se definen en 1, y otras que no están definidas en 1. El problema de 1-parada es el problema de decidir de cualquier algoritmo si define una función con esta propiedad, es decir, si el algoritmo se detiene en la entrada 1. Según el teorema de Rice, el problema de la parada 1 es indecidible. De manera similar, la cuestión de si una máquina de Turing T termina en una cinta inicialmente vacía (en lugar de con una palabra inicial w dada como segundo argumento además de una descripción de T , como en el problema de la detención total) sigue siendo indecidible.
Declaración formal
Dejar denotar los números naturales , y dejardenotar la clase de funciones computables unarias (parciales). Dejarser una numeración admisible de las funciones computables . Denotamos porla e- ésima función computable (parcial).
Identificamos cada propiedad que una función computable puede tener con el subconjunto deque consta de las funciones con esa propiedad. Por lo tanto, dado un conjunto, una función computable tiene propiedad si y solo si . Para cada propiedadhay un problema de decisión de membresía asociado de determinar, dado e , si.
El teorema de Rice establece que el problema de decisiónes decidible (también llamado recursivo o computable ) si y solo si o .
Ejemplos de
Según el teorema de Rice, si hay al menos una función computable parcial en una clase particular C de funciones computables parciales y otra función computable parcial que no está en C, entonces el problema de decidir si un programa en particular calcula una función en C es indecidible. Por ejemplo, el teorema de Rice muestra que cada uno de los siguientes conjuntos de funciones computables parciales es indecidible (es decir, el conjunto no es recursivo ni computable ):
- La clase de funciones computables parciales que devuelven 0 para cada entrada y su complemento.
- La clase de funciones computables parciales que devuelven 0 para al menos una entrada y su complemento.
- La clase de funciones computables parciales que son constantes y su complemento.
- La clase de funciones computables parciales que son idénticas a una función computable parcial dada y su complemento.
- La clase de funciones computables parciales que divergen (es decir, indefinidas) para alguna entrada y su complemento.
- La clase de índices para funciones computables que son totales. [1]
- La clase de índices para conjuntos enumerables recursivamente que son cofinitos.
- La clase de índices para conjuntos recursivamente enumerables que son recursivos.
Prueba por el teorema de recursividad de Kleene
Un corolario a la recursividad de Kleene teorema afirma que para cada numeración de Gödel de las funciones computables y cada función computable, hay un índice tal que devoluciones . (A continuación, decimos que "devoluciones" si alguno , o ambos y son indefinidos.) Intuitivamente, es un quine , una función que devuelve su propio código fuente (número de Gödel), excepto que en lugar de devolverlo directamente, pasa su número de Gödel a y devuelve el resultado.
Dejar ser un conjunto de funciones computables tales que . Luego están las funciones computables y . Suponga que el conjunto de índices tal que es decidible; entonces, existe una función que vuelve Si , y de lo contrario. Por el corolario del teorema de recursividad, hay un índice tal que devoluciones . Pero entonces, si, luego es la misma función que , y por lo tanto ; y si, luego es , y por lo tanto . En ambos casos, tenemos una contradicción.
Prueba por reducción del problema de la detención.
Boceto de prueba
Supongamos, para ser más concretos, que tenemos un algoritmo para examinar un programa py determinar infaliblemente si p es una implementación de la función de elevación al cuadrado, que toma un entero d y devuelve d 2 . La demostración funciona igual de bien si tenemos un algoritmo para decidir cualquier otra propiedad no trivial del comportamiento del programa (es decir, una propiedad semántica y no trivial), y se da en general a continuación.
La afirmación es que podemos convertir nuestro algoritmo para identificar programas de cuadratura en uno que identifique funciones que se detienen. Vamos a describir un algoritmo que toma entradas de un e i y determina si el programa a las paradas cuando se les da entrada i .
El algoritmo para decidir esto es conceptualmente simple: construye (la descripción de) un nuevo programa t tomando un argumento n , que (1) primero ejecuta el programa a en la entrada i (tanto a como i están codificados en la definición de t ), y (2) luego devuelve el cuadrado de n . Si a ( i ) se ejecuta indefinidamente, entonces t nunca llega al paso (2), independientemente de n . Entonces, claramente, t es una función para calcular cuadrados si y solo si el paso (1) termina. Puesto que hemos supuesto que podemos identificar infaliblemente programas para plazas de cálculo, podemos determinar si t , que depende de un e i , es un programa de este tipo, y que por cada una y yo ; así hemos obtenido un programa que decide si el programa a se detiene en la entrada i . Tenga en cuenta que nuestro algoritmo de decisión de detención nunca ejecuta t , sino que solo pasa su descripción al programa de identificación de cuadratura, que por supuesto siempre termina; dado que la construcción de la descripción de t también se puede hacer de una manera que siempre termina, la decisión de detener tampoco puede dejar de detenerse.
detiene (a, i) { definir t (n) { ai) devolver n × n } return is_a_squaring_function (t) }
Este método no depende específicamente de poder reconocer funciones que calculan cuadrados; siempre que algún programa pueda hacer lo que estamos tratando de reconocer, podemos agregar una llamada a a para obtener nuestra t . Podríamos haber tenido un método para reconocer programas para calcular raíces cuadradas, o programas para calcular la nómina mensual, o programas que se detienen cuando se les da la entrada "Abraxas" ; en cada caso, podríamos resolver el problema de la detención de manera similar.
Prueba formal
Para la prueba formal, se supone que los algoritmos definen funciones parciales sobre cadenas y están representados por cadenas. La función parcial calculada por el algoritmo representado por una cadena a se denota F a . Esta demostración procede por reductio ad absurdum : asumimos que hay una propiedad no trivial que es decidida por un algoritmo, y luego mostramos que se sigue que podemos decidir el problema de detención , que no es posible, y por lo tanto una contradicción.
Supongamos ahora que P ( a ) es un algoritmo que decide alguna propiedad no trivial de F a . Sin pérdida de generalidad, podemos suponer que P ( no-halt ) = "no", siendo no-halt la representación de un algoritmo que nunca se detiene. Si esto no es cierto, entonces se aplica a la negación de la propiedad. Dado que P decide una propiedad no trivial, se deduce que hay una cadena b que representa un algoritmo y P ( b ) = "sí". Entonces podemos definir un algoritmo H ( a , i ) de la siguiente manera:
- 1. construya una cadena t que represente un algoritmo T ( j ) tal que
- T primero simula el cálculo de F a ( i ),
- luego T simula el cálculo de F b ( j ) y devuelve su resultado.
- 2. devuelva P ( t ).
Ahora podemos mostrar que H decide el problema de la detención:
- Suponga que el algoritmo representado por a se detiene en la entrada i . En este caso F t = F b y, debido a que P ( b ) = "sí" y la salida de P ( x ) depende sólo de F x , se sigue que P ( t ) = "sí" y, por lo tanto, H ( a , i ) = "sí".
- Suponga que el algoritmo representado por a no se detiene en la entrada i . En este caso F t = F no-halt , es decir, la función parcial que nunca se define. Dado que P ( no-halt ) = "no" y la salida de P ( x ) depende sólo de F x , se sigue que P ( t ) = "no" y, por lo tanto, H ( a , i ) = "no".
Dado que se sabe que el problema de la detención es indecidible, esto es una contradicción y la suposición de que existe un algoritmo P ( a ) que decide una propiedad no trivial para la función representada por a debe ser falsa.
Conjuntos de índices y teoremas de Rice
El teorema de Rice se puede enunciar sucintamente en términos de conjuntos de índices:
Dejar ser una clase de funciones recursivas parciales con índice establecido . Luegoes recursivo si y solo si o .
Aquí es el conjunto de números naturales , incluido el cero .
Un análogo del teorema de Rice para conjuntos recursivos
Se puede considerar que el teorema de Rice afirma la imposibilidad de decidir efectivamente para cualquier conjunto enumerable recursivamente si tiene una determinada propiedad no trivial. [2] En esta sección, damos un análogo del teorema de Rice para conjuntos recursivos , en lugar de conjuntos recursivamente enumerables. [3] En términos generales, el análogo dice que si uno puede determinar efectivamente para cada conjunto recursivo si tiene una determinada propiedad, entonces sólo un número finito de enteros determina si un conjunto recursivo tiene la propiedad. Este resultado es análogo al teorema original de Rice, porque ambos resultados afirman que una propiedad es "decidible" sólo si se puede determinar si un conjunto tiene esa propiedad examinando como máximo un número finito (por no , para el teorema original), si pertenece al conjunto.
Dejar ser una clase (llamada juego simple y pensada como una propiedad) de conjuntos recursivos. Si es un conjunto recursivo, entonces para algunos , función computable es la función característica de . Nosotros llamamosun índice característico para. (Hay infinitamente muchos.) Digamos la clase es computable si hay un algoritmo (función computable) que decide por cualquier número entero no negativo (no necesariamente un índice característico),
- Si es un índice característico de un conjunto recursivo que pertenece a , entonces el algoritmo da "sí";
- Si es un índice característico de un conjunto recursivo que no pertenece a , entonces el algoritmo da "no".
Un conjunto extiende una cuerda de 0 y 1 si para cada (el largo de ), la el elemento de es 1 si ; y es 0 en caso contrario. Por ejemplo, extiende la cuerda . Una cuerdaestá ganando determinando si cada conjunto recursivo que se extiende pertenece a . Una cuerdaestá perdiendo determinando si ningún conjunto recursivo se extiende pertenece a .
Ahora podemos enunciar el siguiente análogo del teorema de Rice (Kreisel, Lacombe y Shoenfield, 1959, [4] Kumabe y Mihara, 2008 [5] ):
Una clase de conjuntos recursivos es computable si y solo si hay un conjunto recursivamente enumerable de perder cadenas determinantes y un conjunto enumerable recursivamente de ganar determinando cadenas de tal manera que cada conjunto recursivo extiende una cadena en .
Este resultado se ha aplicado a problemas fundamentales en la elección social computacional (más ampliamente, teoría algorítmica de juegos ). Por ejemplo, Kumabe y Mihara (2008, [5] 2008 [6] ) aplican este resultado a una investigación de los números de Nakamura para juegos simples en la teoría de juegos cooperativos y la teoría de la elección social .
Ver también
- Teoremas de incompletitud de Gödel
- Detener el problema
- Teoría de la recursividad
- Teorema de Rice-Shapiro
- Teorema de Scott-Curry , análogo al teorema de Rice en cálculo lambda
- La prueba de Turing
- Wittgenstein sobre reglas y lenguaje privado
Notas
- ^ Soare, Robert I. (1987). Conjuntos y grados recursivamente enumerables . Saltador. pag. 21 .
- ^ Un conjuntoes recursivamente enumerable si para algunos , dónde es el dominio (el conjunto de entradas tal que está definido) de . El resultado para conjuntos enumerables recursivamente se puede obtener a partir del de funciones computables (parciales) considerando la clase, dónde es una clase de conjuntos enumerables de forma recursiva.
- ^ Un conjunto recursivamente enumerablees recursivo si su complemento es recursivamente enumerable. Equivalentemente, es recursivo si su función característica es computable.
- ^ Kreisel, G .; Lacombe, D .; Shoenfield, JR (1959). "Funcionales recursivas parciales y operaciones efectivas". En Heyting, A. (ed.). Constructividad en Matemáticas . Estudios de Lógica y Fundamentos de las Matemáticas. Amsterdam: Holanda Septentrional. págs. 290-297.
- ^ a b Kumabe, M .; Mihara, HR (2008). "Computabilidad de juegos simples: una caracterización y aplicación al núcleo" . Revista de Economía Matemática . 44 (3–4): 348–366. arXiv : 0705.3227 . doi : 10.1016 / j.jmateco.2007.05.012 .
- ^ Kumabe, M .; Mihara, HR (2008). "Los números de Nakamura para juegos simples computables" . Elección social y bienestar . 31 (4): 621. arXiv : 1107.0439 . doi : 10.1007 / s00355-008-0300-5 .
Referencias
- Hopcroft, John E .; Ullman, Jeffrey D. (1979), Introducción a la teoría, los lenguajes y la computación de los autómatas , Addison-Wesley , págs. 185-192
- Rice, HG (1953), "Clases de conjuntos recursivamente enumerables y sus problemas de decisión", Transactions of the American Mathematical Society , 74 (2): 358–366, doi : 10.1090 / s0002-9947-1953-0053041-6 , JSTOR 1990888
- Rogers, Hartley Jr. (1987), Teoría de funciones recursivas y computabilidad efectiva (2da ed.), McGraw-Hill , §14.8
enlaces externos
- Weisstein, Eric W. "Teorema de Rice" . MathWorld .