Teorema de arroz

Ajustar Compartir Imprimir Citar
Todas las propiedades no triviales y semánticas de los programas son indecibles

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 es no 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 eficaz puede decidir si un algoritmo calcula una función parcial con esa propiedad. Aquí, una propiedad de las 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 función. 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

Sea p una propiedad de un lenguaje formal L que no es trivial, sentido

  1. existe un lenguaje recurrentemente enumerable que tiene la propiedad p,
  2. existe un lenguaje recurrentemente enumerable que no tiene la propiedad p,

(es decir, p no es uniformemente verdadero ni uniformemente falso para todos los lenguajes recursivamente enumerables).

Entonces es indecidible determinar para una determinada máquina de Turing M, si el lenguaje reconocido por ella tiene la propiedad p.

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 p. 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 tener en cuenta que el teorema de Rice no se refiere a las propiedades de las máquinas o los 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.

Uso de Rogers' caracterización de sistemas de programación aceptables, el teorema de Rice puede generalizarse esencialmente 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 cuestiones 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 se define para el argumento '1'. Obviamente, no es trivial, ya que hay funciones parciales que están definidas en 1 y otras que no están definidas en 1. El problema de parada 1 es el problema de decidir de cualquier algoritmo si define un 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 1 detención 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

Vamos N{displaystyle mathbb {N} denotar los números naturales, y dejar P()1){displaystyle mathbf {} {{(1)} denota la clase de funciones computables (parciales). Vamos φ φ :: N→ → P()1){displaystyle phi colon mathbb {N} to mathbf {P} ^{(1)} ser una numeración admisible de las funciones computables. Denote by φ φ e:=φ φ ()e){displaystyle phi _{e}:=phi (e)} el eth (partial) computable function.

Nos identificamos cada uno propiedad que una función computable puede tener con el subconjunto de P()1){displaystyle mathbf {} {{(1)} que consiste en las funciones con esa propiedad. Así, dado un conjunto F⊆ ⊆ P()1){displaystyle Fsubseteq mathbf {} ^{(1)}, una función computable φ φ e{displaystyle phi _{e} tiene propiedades F{displaystyle F} si φ φ e▪ ▪ F{displaystyle phi _{e}in F}. Para cada propiedad F⊆ ⊆ P()1){displaystyle Fsubseteq mathbf {} ^{(1)} hay un problema de decisión de los miembros asociados DF{displaystyle D_{F} de determinar, dado e, si φ φ e▪ ▪ F{displaystyle phi _{e}in F}.

Teorema de arroz declara que el problema de la decisión DF{displaystyle D_{F} es decidable (también llamado recursivo o computableSi y sólo si F=∅ ∅ {displaystyle F=varnothing } o F=P()1){displaystyle F=mathbf {} {{(1)}.

Ejemplos

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):

Demostración por el teorema de recursión de Kleene

Un corolario al teorema de recursión de Kleene declara que por cada número de Gödel φ φ :: N→ → P()1){displaystyle phi colon mathbb {N} to mathbf {P} ^{(1)} de las funciones computables y cada función computable Q()x,Sí.){displaystyle Q(x,y)}, hay un índice e{displaystyle e} tales que φ φ e()Sí.){displaystyle phi _{e}(y)} retornos Q()e,Sí.){displaystyle Q(e,y)}. (En lo siguiente, decimos que f()x){displaystyle f(x)} "retornos" g()x){displaystyle g(x)} si f()x)=g()x){displaystyle f(x)=g(x)}, o ambos f()x){displaystyle f(x)} y g()x){displaystyle g(x)} son indefinidos.) Intuitivamente, φ φ e{displaystyle phi _{e} es una quine, una función que devuelve su propio código fuente (número de origen), excepto que en lugar de devolverlo directamente, φ φ e{displaystyle phi _{e} pasa su número de Gödel a Q{displaystyle Q} y devuelve el resultado.

Asumo de contradicción F{displaystyle F} es un conjunto de funciones computables tales que ∅ ∅ ل ل Fل ل P()1){displaystyle emptyset neq Fneq mathbf {P} {(1)}. Entonces hay funciones computables f▪ ▪ F{displaystyle fin F} y g∉ ∉ F{displaystyle gnotin F}. Supongamos que el conjunto de índices x{displaystyle x} tales que φ φ x▪ ▪ F{displaystyle phi _{x}in F} es decida; entonces, existe una función Q()x,Sí.){displaystyle Q(x,y)} que regresa g()Sí.){displaystyle g(y)} si φ φ x▪ ▪ F{displaystyle phi _{x}in F}, y f()Sí.){displaystyle f(y)} De lo contrario. Por el corolario al teorema de recidiva, hay un índice e{displaystyle e} tales que φ φ e()Sí.){displaystyle phi _{e}(y)} retornos Q()e,Sí.){displaystyle Q(e,y)}. Pero entonces, si φ φ e▪ ▪ F{displaystyle phi _{e}in F}, entonces φ φ e{displaystyle phi _{e} es la misma función que g{displaystyle g}, y por consiguiente φ φ e∉ ∉ F{displaystyle phi _{e}notin F.; y si φ φ e∉ ∉ F{displaystyle phi _{e}notin F., entonces φ φ e{displaystyle phi _{e} es f{displaystyle f}, y por consiguiente φ φ e▪ ▪ F{displaystyle phi _{e}in F}. En ambos casos, tenemos una contradicción.

Demostración por reducción del problema de la detención

Boceto de prueba

Supongamos, para concretar, que tenemos un algoritmo para examinar un programa p y determinar infaliblemente si p es una implementación de la función de elevar al cuadrado, que toma un número entero d y devuelve d2. La prueba 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 que elevan al cuadrado en uno que identifique funciones que se detengan. Describiremos un algoritmo que toma las entradas a y i y determina si el programa a se detiene cuando se le da la 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 para siempre, 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. Dado que asumimos que podemos identificar infaliblemente programas para calcular cuadrados, podemos determinar si t, que depende de a y i, es un programa de este tipo; 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 al cuadrado, que por suposición siempre termina; dado que la construcción de la descripción de t también se puede hacer de manera que siempre termine, la decisión-detención tampoco puede dejar de detenerse. 

 stops (a,i) {
t(n) {
a i)
 retorno n×n
}
 retorno 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 nuestro 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 detención de manera similar.

Prueba formal

Si tenemos un algoritmo que decide una propiedad no-trivial, podemos construir una máquina de Turing que decide el problema de detener.

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 representada por una cadena a se denota Fa. Esta prueba procede por reductio ad absurdum: suponemos que hay una propiedad no trivial que se decide por un algoritmo, y luego mostramos que se sigue que podemos decidir el problema de parada, 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 Fa. 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 esto vale para la negación de la propiedad. Dado que P decide una propiedad no trivial, se sigue 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. construir una cuerda t que representa un algoritmo T()j.
  • T primero simula la computación de Fa()i),
  • entonces T simula la computación de Fb()j) y devuelve su resultado.
2. Retorno P()t).

Ahora podemos demostrar que H decide el problema de detención:

Dado que se sabe que el problema de detención es indecidible, esto es una contradicción y la suposición de que hay un algoritmo P(a) que decide una propiedad no trivial porque la función representada por a debe ser falsa.

Teorema de Rice y conjuntos de índices

El teorema de Rice puede expresarse sucintamente en términos de conjuntos de índices:

Vamos C{displaystyle {fnMithcal}} ser una clase de funciones recursivas parciales con conjunto de índices C{displaystyle C}. Entonces... C{displaystyle C} es recursivo si y sólo si C=∅ ∅ {displaystyle C=varnothing } o C=N{displaystyle C=Mathbb {N}.

Aquí. N{displaystyle mathbb {N} es el conjunto de números naturales, incluyendo cero.

Un análogo del teorema de Rice para conjuntos recursivos

Uno puede considerar el teorema de Rice como afirmando la imposibilidad de decidir eficazmente por cualquier recursivamente enumerable establecer si tiene una determinada propiedad notrivial. En esta sección, damos una analogía del teorema de Rice para conjuntos recursivos, en lugar de conjuntos repetidamente enumerables. Roughly speaking, the analogue said that if one can effectively determine for every recursivo establecer si tiene una determinada propiedad, entonces sólo finitamente muchos enteros determinan si un conjunto recursivo tiene la propiedad. Este resultado es análogo al teorema original de Rice, ya que ambos resultados afirman que una propiedad es "decidable" sólo si se puede determinar si un conjunto tiene esa propiedad examinando por lo más finitamente muchos i{displaystyle i} (por no i{displaystyle i}, para el teorema original, si i{displaystyle i} pertenece al set.

Vamos W{displaystyle W. ser una clase (llamada juego simple y pensado como una propiedad) de conjuntos recursivos. Si S{displaystyle S. es un conjunto recursivo, entonces para algunos e{displaystyle e}, función computable φ φ e{displaystyle phi _{e} es la función característica S{displaystyle S.. Nosotros llamamos e{displaystyle e} a índice característico para S{displaystyle S.. (Hay infinitamente muchos e{displaystyle e}.) Digamos la clase W{displaystyle W. es computable si hay un algoritmo (función compatible) que decide para cualquier entero no negativo e{displaystyle e} (no necesariamente un índice característico)

Un juego S⊆ ⊆ N{displaystyle Ssubseteq mathbb {N} extensiones una cuerda τ τ {displaystyle tau } de 0's y 1's si por cada <math alttext="{displaystyle kk.Silencioτ τ Silencio{displaystyle k wontau Silencio}<img alt="k (la longitud de τ τ {displaystyle tau }), el k{displaystyle k}t elemento de τ τ {displaystyle tau } 1 si k▪ ▪ S{displaystyle kin S}; y es 0 de lo contrario. Por ejemplo, S={}1,3,4,7,...... }{displaystyle S={1,3,4,7,ldots } extiende la cadena 01011001{displaystyle 01011001}. Una cuerda. τ τ {displaystyle tau } es determinación si cada conjunto recursivo se extiende τ τ {displaystyle tau } pertenece W{displaystyle W.. Una cuerda. τ τ {displaystyle tau } es pérdida de determinación si no se extiende un conjunto recursivo τ τ {displaystyle tau } pertenece W{displaystyle W..

Ahora podemos enunciar el siguiente análogo del teorema de Rice:

Una clase W{displaystyle W. de conjuntos recursivos es computable si y sólo si hay un conjunto repetidamente enumerable T0{displaystyle T_{0} de perder cadenas de determinación y un conjunto repetidamente enumerable T1{displaystyle T_{1} de ganar cadenas de determinación tal que cada conjunto recursivo extiende una cadena en T0∪ ∪ T1{displaystyle T_{0}cup T_{1}.

Este resultado se ha aplicado a problemas fundamentales en la elección social computacional (más ampliamente, la teoría algorítmica de juegos). Por ejemplo, Kumabe y Mihara 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.