Teorema de Rice-Shapiro

En la teoría de la computabilidad , el teorema de Rice-Shapiro es una generalización del teorema de Rice , que lleva el nombre de Henry Gordon Rice y Norman Shapiro . Este teorema establece que cuando una propiedad semidecidible de funciones computables parciales se cumple en una determinada función parcial , se puede extraer una subfunción finita tal que la propiedad siga siendo cierta.

La idea informal del teorema es que la "única forma general" de obtener información sobre el comportamiento de un programa es ejecutarlo, y dado que un cálculo es finito, solo se puede probar el programa con un número finito de entradas.

Un teorema estrechamente relacionado es el teorema de Kreisel-Lacombe-Shoenfield-Tseitin (o teorema KLST ), que fue obtenido independientemente por Georg Kreisel , Daniel Lacombe y Joseph R. Shoenfield ^{[ 1 ]} , y por Grigori Tseitin ^{[ 2 ]} .

Declaración formal

Teorema de Rice-Shapiro. ^{[ 3 ]}^{: 482}^{[ 4 ]}^{[ 5 ]} Sea $P$ sea un conjunto de funciones computables parciales tales que el conjunto de índices de $P$ (es decir, el conjunto de índices $e$ de tal manera que $\phi _ {e}\en P$ , para alguna numeración admisible fija $\phi$ ) es semidecidible . Entonces, para cualquier función parcialmente computable $f$ , sostiene que $P$ contiene $f$ si y solo si $P$ contiene una subfunción finita de $f$ (es decir, una función parcial definida en un número finito de puntos, que toma los mismos valores que $f$ sobre esos puntos).

Teorema de Kreisel-Lacombe-Shoenfield-Tseitin. ^{[ 3 ]}^{: 362}^{[ 1 ]}^{[ 2 ]}^{[ 6 ]}^{[ 7 ]}^{[ 8 ]}^{: 440} Sea $P$ sea un conjunto de funciones computables totales tales que el conjunto de índices de $P$ es decidible con la promesa de que la entrada es el índice de una función computable total (es decir, hay una función computable parcial) $D$ que, dado un índice $e$ de tal manera que $\phi _{e}$ es total, devuelve 1 si $\phi _ {e}\en P$ y 0 en caso contrario; $D(e)$ no es necesario definirlo si $\phi _{e}$ no es total). Decimos que dos funciones totales $f$ , $g$ "aceptar hasta $n$ " si $f(k)=g(k)$ se aplica a todos $k\leq n$ . Entonces, para cualquier función computable total $f$ , existe $n$ de tal manera que para toda función computable total $g$ lo cual concuerda con $f$ hasta $n$ , tenemos $f\in P\iff g\in P$ .

Ejemplos

Según el teorema de Rice-Shapiro, no es ni semidecidible ni cosemidecidible si un programa dado:

Termina en todas las entradas ( problema de parada universal );
Finaliza con un número finito de entradas;
Es equivalente a otro programa fijo.

Según el teorema de Kreisel-Lacombe-Shoenfield-Tseitin, es indecidible si un programa dado, que se supone que siempre termina ,

Siempre devuelve un número par ;
Es equivalente a otro programa fijo que siempre termina;
Siempre devuelve el mismo valor.

Discusión

Los dos teoremas están estrechamente relacionados y también se relacionan con el teorema de Rice . Específicamente:

El teorema de Rice se aplica a conjuntos decidibles de funciones computables parciales , concluyendo que deben ser triviales.
El teorema de Rice-Shapiro se aplica a conjuntos semidecidibles de funciones parcialmente computables , concluyendo que solo pueden reconocer elementos basándose en un número finito de valores.
El teorema de Kreisel-Lacombe-Shoenfield-Tseitin se aplica a conjuntos decidibles de funciones computables totales , con una conclusión similar a la del teorema de Rice-Shapiro.

Es natural preguntarse qué se puede decir acerca de los conjuntos semidecidibles de funciones computables totales . Quizás sorprendentemente, estos no necesitan verificar la conclusión de los teoremas de Rice-Shapiro y Kreisel-Lacombe-Shoenfield-Tseitin. El siguiente contraejemplo se debe a Richard M. Friedberg . ^{[ 9 ]}^{[ 8 ]}^{: 444}

Dejar $Q$ sea el conjunto de funciones computables totales $f:\mathbb {N} \to \mathbb {N}$ de tal manera que $f$ no es la función cero constante y, definiendo $n$ ser el índice máximo tal que $f(n)$ es cero, existe un programa de código $e\leq n$ de tal manera que $\phi _{e}(i)$ está definido y es igual a $f(i)$ para cada $i\leq n+1$ . Dejar $P$ ser el conjunto $Q$ con la función de cero constante añadida.

Por un lado, $P$ contiene la función cero constante por definición, sin embargo no hay $n$ de tal manera que si un total computable $g$ coincide con la función cero constante hasta $n$ entonces $g\in P$ . De hecho, dado $n$ , podemos definir una función total $g$ al establecer $g(n+1)$ a algún valor mayor que cada $\phi _ {e}(n+1)$ para $e\leq n+1$ de tal manera que $\phi _ {e}(n+1)$ se define y $g(n')=0$ para $n'\neq n+1$ . La función $g$ es cero excepto en el valor $n+1$ , por lo tanto computable, coincide con la función cero hasta $n$ , pero no pertenece a $P$ por construcción.

Por otro lado, dado un programa $e$ y una promesa de que $\phi _{e}$ es total, es posible decidir parcialmente si $\phi _ {e}\en P$ mediante la integración, ejecutando una tarea para decidir parcialmente. $\phi _{e}\in Q$ , lo cual claramente se puede hacer, y otra tarea es decidir parcialmente si $\phi _{e}(k)=0$ a pesar de $k\leq e$ Esto es correcto porque la función cero es detectada por la segunda tarea y, a la inversa, si la segunda tarea devuelve verdadero, entonces o bien $\phi _{e}$ es cero, o $\phi _{e}$ es solo cero hasta un índice $n$ , que debe satisfacer $e\leq n$ , que por definición de $Q$ implica que $\phi _{e}\in Q$ .

Demostración del teorema de Rice-Shapiro

Dejar $P$ Sea un conjunto de funciones parcialmente computables con un conjunto de índices semidecidible. Demostramos las dos implicaciones por separado.

Cierre hacia arriba

Primero demostramos que si $f$ es una subfunción finita de $g$ y $f\in P$ entonces $g\in P$ . La hipótesis de que $f$ Es finito, de hecho, no sirve para nada.

La demostración utiliza un argumento diagonal típico de los teoremas de computabilidad. Construimos un programa. $p$ de la siguiente manera. Este programa toma una entrada $x$ . Utilizando una técnica de ensamblaje estándar , $p$ ejecuta dos tareas en paralelo.

La primera tarea ejecuta un semialgoritmo que semidecide $P$ en $p$ él mismo ( $p$ puede obtener acceso a su propio código fuente mediante el teorema de recursión de Kleene ). Si esto finalmente devuelve verdadero, entonces esta primera tarea continúa ejecutando un semialgoritmo que semicalcula $g$ en $x$ (la entrada a $p$ ), y si eso termina, entonces la tarea hace $p$ como un todo regresa $g(x)$ .
La segunda tarea ejecuta un semialgoritmo que semicalcula $f$ en $x$ Si esto devuelve verdadero, entonces la tarea realiza $p$ como un todo regresa $f(x)$ .

Si $\phi _{p}\notin P$ , la primera tarea nunca puede terminar, por lo tanto el resultado de $p$ está totalmente determinado por la segunda tarea, por lo tanto $\phi _{p}$ es simplemente $f$ , una contradicción. Esto demuestra que $\phi _{p}\in P$ .

Por lo tanto, ambas tareas son relevantes; sin embargo, debido a $f$ es una subfunción de $g$ y la segunda tarea regresa $f(x)=g(x)$ cuando $f(x)$ se define, mientras que la primera tarea devuelve $g(x)$ cuando se define, el programa de hecho calcula $g$ , es decir, $\phi _{p}=g$ y por lo tanto $g\in P$ .

Extracción de una subfunción finita

Por el contrario, demostramos que si $P$ contiene una función computable parcial $f$ , entonces contiene una subfunción finita de $f$ Vamos a arreglarlo. $f\in P$ Construimos un programa $p$ que toma entrada $x$ y ejecuta los siguientes pasos:

Correr $x$ pasos de cálculo de un semialgoritmo que semidecide $P$ , con $p$ él mismo como entrada. Si este semialgoritmo termina y devuelve verdadero, entonces entra en un bucle indefinido.
De lo contrario, semicomputación $f$ en $x$ y si esto termina, devuelve el resultado. $f(x)$ .

Supongamos que $\phi _{p}\notin P$ . Esto implica que el semialgoritmo para la semidecisión $P$ utilizado en el primer paso nunca devuelve verdadero. Luego, $p$ calcula $f$ y esto contradice la suposición $f\in P$ Por lo tanto, debemos tener $\phi _{p}\in P$ y el algoritmo para la semidecisión $P$ devuelve verdadero en $p$ después de un cierto número de pasos $n$ . La función parcial $\phi _{p}$ solo se puede definir en las entradas $x$ de tal manera que $x\leq n$ y regresa $f(x)$ en tales entradas, por lo que es una subfunción finita de $f$ que pertenece a $P$ .

Prueba del teorema de Kreisel-Lacombe-Shoenfield-Tseitin

Preliminares

Una función total $h:\mathbb {N} \to \mathbb {N}$ Se dice que es en última instancia cero si siempre toma el valor cero excepto para un número finito de puntos, es decir, existe $N$ de tal manera que $h(n)=0$ a pesar de $n\geq N$ Tenga en cuenta que dicha función siempre es computable (se puede calcular simplemente comprobando si la entrada está en una lista predefinida determinada y, en caso contrario, devolviendo cero).

Nosotros arreglamos $U$ una enumeración computable de todas las funciones totales que en última instancia son cero, es decir, $U$ es tal que:

A pesar de $k$ , la función $\phi _{U(k)}$ en última instancia es cero;
Para toda la función total $h$ que en última instancia es cero, existe $k$ de tal manera que $\phi _{U(k)}=h$ ;
La función $U$ es en sí mismo totalmente computable.

Podemos construir $U$ mediante técnicas estándar (por ejemplo, para aumentar $N$ , enumerar funciones que en última instancia son cero y que están acotadas por $N$ y cero en entradas mayores que $N$ ).

Aproximación mediante funciones que terminan siendo cero

Dejar $P$ sea como en el enunciado del teorema: un conjunto de funciones computables totales tales que existe un algoritmo que, dado un índice $e$ y una promesa de que $\phi _{e}$ es total, decide si $\phi _{e}\in P$ .

Primero demostramos un lema: Para toda función computable total $f$ y para todos los enteros $N$ , existe una función que en última instancia es cero $h$ de tal manera que $h$ está de acuerdo con $f$ hasta $N$ , y $f\in P\iff h\in P$ .

Para demostrar este lema, fijemos una función computable total. $f$ y un número entero $N$ y dejar $B$ ser el booleano $f\in P$ . Crea un programa $p$ que toma entrada $x$ y toma las siguientes medidas:

Si $x\leq N$ luego regresar $f(x)$ ;
De lo contrario, corre $x$ pasos de cálculo del algoritmo que decide $P$ en $p$ y si esto regresa $B$ , entonces devuelve cero;
De lo contrario, devuelva $f(x)$ .

Claramente, $p$ siempre termina, es decir, $\phi _{p}$ es total. Por lo tanto, la promesa de $P$ seguir corriendo $p$ se cumple.

Supongamos por contradicción que uno de $f$ y $\phi _{p}$ pertenece a $P$ y el otro no, es decir, $(\phi _{p}\in P)\neq B$ . Entonces vemos que $p$ calcula $f$ , desde $P$ no regresa $B$ en $p$ sin importar la cantidad de pasos. Por lo tanto, tenemos $f=\phi _{p}$ , contradiciendo el hecho de que uno de $f$ y $\phi _{p}$ pertenece a $P$ y el otro no. Este argumento demuestra que $f\in P\iff \phi _{p}\in P$ . Luego, el segundo paso hace $p$ devolver cero para suficientemente grande $x$ , de este modo $\phi _{p}$ es en última instancia cero; y por construcción (debido al primer paso), $\phi _{p}$ está de acuerdo con $f$ hasta $N$ Por lo tanto, podemos tomar $h=\phi _{p}$ y el lema queda demostrado.

Prueba principal

Con el lema anterior, ahora podemos demostrar el teorema de Kreisel-Lacombe-Shoenfield-Tseitin. Nuevamente, fijemos $P$ como en el enunciado del teorema, sea $f$ sea una función totalmente computable y dejemos que $B$ ser el booleano " $f\in P$ ". Construye el programa $p$ que toma entrada $x$ y ejecuta estos pasos:

Correr $x$ pasos de cálculo del algoritmo que decide $P$ en $p$ .
Si esto regresa $B$ en un cierto número de pasos $n$ (que es como máximo $x$ ), luego buscar en paralelo $k$ de tal manera que $U(k)$ está de acuerdo con $f$ hasta $n$ y $(U(k)\in P)\neq B$ . Tan pronto como tal $k$ Se encuentra, regresa $U(k)(x)$ .
De lo contrario (si $P$ no regresó $B$ en $p$ en $x$ pasos), regresar $f(x)$ .

Primero demostramos que $P$ devoluciones $B$ en $p$ Supongamos por contradicción que este no es el caso ( $P$ devoluciones $\lnot B$ , o $P$ no termina). Entonces $p$ realmente calcula $f$ . En particular, $\phi _{p}$ es total, por lo que la promesa de $P$ cuando se ejecuta en $p$ se cumple y $P$ devuelve el valor booleano $\phi _{p}\in P$ , que es $f\in P$ , es decir, $B$ , lo cual contradice la suposición.

Dejar $n$ sea el número de pasos que $P$ tarda en regresar $B$ en $p$ Afirmamos que $n$ satisface la conclusión del teorema: para toda función computable total $g$ lo cual concuerda con $f$ hasta $n$ , sostiene que $f\in P\iff g\in P$ Supongamos por contradicción que existe $g$ total computable que concuerda con $f$ hasta $n$ y tal que $(g\in P)\neq B$ .

Aplicando el lema nuevamente, existe $k$ de tal manera que $U(k)$ está de acuerdo con $g$ hasta $n$ y $g\in P\iff U(k)\in P$ . Dado que ambos $U(k)$ y $f$ estar de acuerdo con $g$ hasta $n$ , $U(k)$ también está de acuerdo con $f$ hasta $n$ y desde entonces $(g\in P)\neq B$ y $g\in P\iff U(k)\in P$ , tenemos $(U(k)\in P)\neq B$ . Por lo tanto, $U(k)$ satisface las condiciones del paso de búsqueda paralela en el programa $p$ , a saber: $U(k)$ está de acuerdo con $f$ hasta $n$ y $(U(k)\in P)\neq B$ Esto demuestra que la búsqueda en el segundo paso siempre termina. Lo solucionamos. $k$ ser el valor que encuentra.

Observamos que $\phi _{p}=U(k)$ De hecho, cualquiera de los dos pasos es el segundo paso de $p$ devoluciones $U(k)(x)$ o el tercer paso regresa $f(x)$ , pero este último caso solo ocurre para $x\leq n$ y sabemos que $U(k)$ está de acuerdo con $f$ hasta $n$ .

En particular, $\phi _{p}=U(k)$ es total. Esto hace la promesa de $P$ seguir corriendo $p$ cumplido, por lo tanto $P$ devoluciones $\phi _{p}\in P$ en $p$ .

Hemos encontrado una contradicción: por un lado, el booleano $\phi _{p}\in P$ es el valor de retorno de $P$ en $p$ , que es $B$ y por otro lado, tenemos $\phi _{p}=U(k)$ y sabemos que $(U(k)\in P)\neq B$ .

Perspectiva desde la topología efectiva

Para cualquier función unaria finita $\theta$ en enteros, sea $C(\theta )$ denotan el 'tronco de tronco' de todas las funciones recursivas parciales que están definidas y coinciden con $\theta$ , en $\theta$ dominio de.

Equipar el conjunto de todas las funciones recursivas parciales con la topología generada por estos troncos como base . Nótese que para cada tronco $C$ , el conjunto de índices $Ix(C)$ es recursivamente enumerable. De manera más general, se cumple para cada conjunto. $A$ de funciones parcialmente recursivas:

$Ix(A)$ es recursivamente enumerable si y solo si $A$ es una unión recursivamente enumerable de troncos de pirámide.

Aplicaciones

El teorema de Kreisel-Lacombe-Shoenfield-Tseitin se ha aplicado a problemas fundamentales en la teoría de la elección social computacional (más ampliamente, en la teoría de juegos algorítmica ). Por ejemplo, Kumabe y Mihara ^{[ 10 ]}^{[ 11 ]} 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 .

Notas

1 2 Kreisel, Georg ; Lacombe, Daniel ; Shoenfield, Joseph R. (1959). "Funcionales recursivos parciales y operaciones efectivas". En Heyting, Arend (ed.). Constructividad en matemáticas . Estudios de lógica y fundamentos de las matemáticas. Ámsterdam: North-Holland. pp. 290–297 .
1 2 Tseitin, Grigori (1959). "Operadores algorítmicos en espacios métricos separables completos constructivos". Doklady Akademii Nauk . 128 : 49-52.
1 2 Rogers Jr., Hartley (1987). Teoría de las funciones recursivas y la computabilidad efectiva . MIT Press. ISBN 0-262-68052-1.
↑ Cutland, Nigel (1980). Computabilidad: una introducción a la teoría de funciones recursivas . Cambridge University Press.; Teorema 7-2.16.
↑ Odifreddi, Piergiorgio (1989). Teoría clásica de la recursión . North Holland.
↑ Moschovakis, Yiannis N. (junio de 2010). "El asombroso segundo teorema de recursión de Kleene" (PDF) . The Bulletin of Symbolic Logic . 16 (2): 189– 239. doi : 10.2178/bsl/1286889124 .
↑ Royer, James S. (junio de 1997). "Semántica vs. Sintaxis vs. Computaciones: Modelos de máquinas para funcionales de tiempo polinomial acotado de tipo 2" . Journal of Computer and System Sciences . 54 (3): 424–436 . doi : 10.1006/jcss.1997.1487 .
1 2 Longley, John; Normann, Dag (2015). Computabilidad de orden superior . Teoría y aplicaciones de la computabilidad. Springer. doi : 10.1007/978-3-662-47992-6 . ISBN 978-3-662-47991-9.
^ Friedberg, Richard M. (1958). "Un contraejemplo relativo a funciones recursivas". Cuentas de resultados de la Academia de Ciencias . 247 : 852–854 .
↑ Kumabe, M.; Mihara, HR (2008). "Los números de Nakamura para juegos simples computables" . Social Choice and Welfare . 31 (4): 621. arXiv : 1107.0439 . doi : 10.1007/s00355-008-0300-5 . S2CID 8106333 .
↑ Kumabe, M.; Mihara, HR (2008). "Computabilidad de juegos simples: una caracterización y aplicación al núcleo" . Journal of Mathematical Economics . 44 ( 3–4 ): 348–366 . arXiv : 0705.3227 . doi : 10.1016/j.jmateco.2007.05.012 . S2CID 8618118 .

[kls-1] 1 2 Kreisel, Georg ; Lacombe, Daniel ; Shoenfield, Joseph R. (1959). "Funcionales recursivos parciales y operaciones efectivas". En Heyting, Arend (ed.). Constructividad en matemáticas . Estudios de lógica y fundamentos de las matemáticas. Ámsterdam: North-Holland. pp. 290–297 .

[tseitin-2] 1 2 Tseitin, Grigori (1959). "Operadores algorítmicos en espacios métricos separables completos constructivos". Doklady Akademii Nauk . 128 : 49-52.

[rogers-3] 1 2 Rogers Jr., Hartley (1987). Teoría de las funciones recursivas y la computabilidad efectiva . MIT Press. ISBN 0-262-68052-1.

[cutland-4] Cutland, Nigel (1980). Computabilidad: una introducción a la teoría de funciones recursivas . Cambridge University Press.; Teorema 7-2.16.

[odifreddi-5] Odifreddi, Piergiorgio (1989). Teoría clásica de la recursión . North Holland.

[moschovakis-6] Moschovakis, Yiannis N. (junio de 2010). "El asombroso segundo teorema de recursión de Kleene" (PDF) . The Bulletin of Symbolic Logic . 16 (2): 189– 239. doi : 10.2178/bsl/1286889124 .

[royer-7] Royer, James S. (junio de 1997). "Semántica vs. Sintaxis vs. Computaciones: Modelos de máquinas para funcionales de tiempo polinomial acotado de tipo 2" . Journal of Computer and System Sciences . 54 (3): 424–436 . doi : 10.1006/jcss.1997.1487 .

[longley-normann-8] 1 2 Longley, John; Normann, Dag (2015). Computabilidad de orden superior . Teoría y aplicaciones de la computabilidad. Springer. doi : 10.1007/978-3-662-47992-6 . ISBN 978-3-662-47991-9.

[friedberg-9] Friedberg, Richard M. (1958). "Un contraejemplo relativo a funciones recursivas". Cuentas de resultados de la Academia de Ciencias . 247 : 852–854 .

[nakamura-numbers-10] Kumabe, M.; Mihara, HR (2008). "Los números de Nakamura para juegos simples computables" . Social Choice and Welfare . 31 (4): 621. arXiv : 1107.0439 . doi : 10.1007/s00355-008-0300-5 . S2CID 8106333 .

[simple-games-11] Kumabe, M.; Mihara, HR (2008). "Computabilidad de juegos simples: una caracterización y aplicación al núcleo" . Journal of Mathematical Economics . 44 ( 3–4 ): 348–366 . arXiv : 0705.3227 . doi : 10.1016/j.jmateco.2007.05.012 . S2CID 8618118 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]