Teorema de Rice-Shapiro

En teoría de la computabilidad , el teorema de Rice-Shapiro es una generalización del teorema de Rice , llamado así por Henry Gordon Rice y Norman Shapiro . Afirma que cuando una propiedad semidecidible de funciones computables parciales es verdadera en una determinada función parcial, se puede extraer una subfunción finita tal que la propiedad siga siendo verdadera.

La idea informal del teorema es que la "única forma general" de obtener información sobre el comportamiento de un programa es ejecutar el programa y, debido a que un cálculo es finito, uno sólo puede probar el programa en un número finito de entradas.

Un teorema estrechamente relacionado es el teorema de Kreisel-Lacombe-Shoenfield-Tseitin , 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 un conjunto de funciones parciales computables tales que el conjunto de índices de P (es decir, el conjunto de índices e tales que φ _e ∈ P , para alguna numeración admisible fija φ ) es semidecidible . Entonces, para cualquier función parcial computable f , se cumple 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 en esos puntos).

Teorema de Kreisel-Lacombe-Shoenfield-Tseitin. ^[3]^{: 362}^[1]^[2]^[6]^[7]^[8] Sea P 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 tal que φ _e es total, devuelve 1 si φ _e ∈ P y 0 en caso contrario; D ( e ) no necesita definirse si φ _e no es total). Decimos que dos funciones totales f , g "concuerdan hasta n " si para todo k ≤ n se cumple que f ( k ) = g ( k ). Entonces, para cualquier función computable total f , existe n tal que para toda función computable total g que concuerde con f hasta n , f ∈ P ⟺ g ∈ P .

Discusión

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

El teorema de Rice se aplica a conjuntos decidibles de funciones parcialmente computables y concluye que deben ser triviales.
El teorema de Rice-Shapiro se aplica a conjuntos semidecidibles de funciones parcialmente computables y concluye que sólo pueden reconocer elementos en función de 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 al teorema de Rice-Shapiro.

Ejemplos

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

Termina en todas las entradas ( problema de detención universal );
Termina en 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.

Demostración del teorema de Rice-Shapiro

Sea P un conjunto de funciones computables parciales con un conjunto de índices semidecidibles.

Cerramiento ascendente

Primero demostramos que P es un conjunto cerrado hacia arriba , es decir, si f ⊆ g y f ∈ P , entonces g ∈ P (aquí, f ⊆ g significa que f es una subfunción de g , es decir, el gráfico de f está contenido en el gráfico de g ). La demostración utiliza un argumento diagonal típico de los teoremas de computabilidad.

Supongamos por contradicción que existen dos funciones f y g tales que f ∈ P , g ∉ P y f ⊆ g . 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 sobre p ( p puede acceder 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 sobre x (la entrada a p ), y si esto termina, entonces la tarea hace que p como un todo devuelva g ( x ).
La segunda tarea ejecuta un semialgoritmo que semicalcula f en x . Si devuelve verdadero, la tarea hace que p como un todo devuelva f ( x ).

Distinguimos dos casos.

Primer caso: φ _p ∉ P . La primera tarea nunca puede terminar, por lo tanto, el resultado de p está completamente determinado por la segunda tarea, por lo tanto φ _p es simplemente f , contradiciendo el supuesto f ∈ P .
Segundo caso: φ _p ∈ P . Si f no está definida en x , entonces la segunda tarea nunca puede terminar, por lo tanto p retorna g ( x ), o se repite si esta no está definida. Por otro lado, si f está definida en x , es posible que la segunda tarea termine y sea la primera en regresar. En ese caso, p retorna f ( x ). Sin embargo, dado que f ⊆ g , en realidad tenemos f ( x ) = g ( x ). Por lo tanto, vemos que φ _p es g . Esto contradice el supuesto g ∉ P .

Extraer una subfunción finita

A continuación, demostramos que si P contiene una función computable parcial f , entonces contiene una subfunción finita de f . Fijemos una función computable parcial f en P . Construimos un programa p que toma la entrada x y ejecuta los siguientes pasos:

Ejecutar x pasos de cálculo de un semialgoritmo que semidecide P , con p como entrada. Si esto devuelve verdadero, repetir indefinidamente.
De lo contrario, semicalcula f en x y, si esto termina, devuelve el resultado f ( x ).

Supongamos que φ _p ∉ P . Esto implica que el semialgoritmo para semidecidir P utilizado en el primer paso nunca devuelve verdadero. Entonces, p calcula f , y esto contradice el supuesto f ∈ P . Por lo tanto, debemos tener φ _p ∈ P , y el algoritmo para semidecidir P devuelve verdadero en p después de una cierta cantidad de pasos n . La función parcial φ _p solo se puede definir en entradas x tales que x ≤ n , y devuelve f ( x ) en tales entradas, por lo tanto, es una subfunción finita de f que pertenece a P .

Conclusión

Sólo queda reunir las dos partes de la demostración. Si P contiene una función computable parcial f , entonces contiene una subfunción finita de f por la segunda parte, y a la inversa, si contiene una subfunción finita de f , entonces contiene a f , porque está cerrada hacia arriba por la primera parte. De esta forma, el teorema queda demostrado.

Demostración del teorema de Kreisel-Lacombe-Shoenfield-Tseitin

Preliminares

Se dice que una función total es en última instancia cero si siempre toma el valor cero excepto para un número finito de puntos, es decir, existe N tal que para todo n ≥ N , h ( n ) = 0. Nótese que dicha función siempre es computable (se puede calcular simplemente verificando si la entrada está en una cierta lista predefinida y, de lo contrario, devolviendo cero). $h:\mathbb {N}\rightarrow\mathbb {N}$

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

Para todo k , φ _{U ( k )} es en última instancia cero;
Para toda función total h que en última instancia sea cero, existe k tal que φ _{U ( k )} = h ;
La función U es en sí misma totalmente computable.

Podemos construir U mediante técnicas estándar (por ejemplo, para aumentar N , enumerar funciones finalmente cero que estén limitadas por N y cero en entradas mayores que N ).

Aproximación mediante funciones en última instancia nulas

Sea P 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 φ _e es computable, decide si φ _e ∈ P .

Primero demostramos un lema: Para toda función total computable f , y para todo entero N , existe una función h en última instancia nula tal que h concuerda con f hasta N , y f ∈ P ⟺ h ∈ P .

Para demostrar este lema, fijemos una función computable total f y un entero N , y sea B el booleano f ∈ P. Construyamos un programa p que tome la entrada x y realice estos pasos:

Si x ≤ N entonces devuelve f ( x );
De lo contrario, ejecute x pasos de cálculo del algoritmo que decide P sobre p , y si esto devuelve B , entonces devuelva cero;
De lo contrario, devuelve f ( x ).

Claramente, p siempre termina, es decir, φ _p es total. Por lo tanto, la promesa de que P se ejecute en p se cumple.

Supongamos por contradicción que uno de f y φ _p pertenece a P y el otro no, es decir, ( φ _p ∈ P ) ≠ B . Entonces vemos que p calcula f , ya que P no devuelve B en p sin importar la cantidad de pasos. Por lo tanto, tenemos f = φ _p , contradiciendo el hecho de que uno de f y φ _p pertenece a P y el otro no. Este argumento prueba que f ∈ P ⟺ φ _p ∈ P . Luego, el segundo paso hace que p devuelva cero para x suficientemente grande , por lo que φ _p es en última instancia cero; y por construcción (debido al primer paso), φ _p concuerda con f hasta N . Por lo tanto, podemos tomar h = φ _p y el lema está probado.

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 una función computable total y sea B el booleano " f ∈ P ". Construyamos el programa p que toma la entrada x y ejecuta estos pasos:

Ejecute x pasos de cálculo del algoritmo que decide P sobre p .
Si esto devuelve B en una cierta cantidad de pasos n (que es como máximo x ), entonces busque en paralelo k tal que U ( k ) concuerde con f hasta n y ( U ( k ) ∈ P ) ≠ B . Tan pronto como se encuentre tal k , devuelva U ( k )( x ).
De lo contrario (si P no devolvió B en p en x pasos), devuelva f ( x ).

Primero demostramos que P devuelve B en p . Supongamos por contradicción que este no es el caso ( P devuelve ¬ B o P no termina). Entonces p realmente calcula f . En particular, φ _p es total, por lo que la promesa a P cuando se ejecuta en p se cumple, y P devuelve el booleano φ _p ∈ P , que es f ∈ P , es decir, B , contradiciendo la suposición.

Sea n el número de pasos que P da para regresar a B en p . Afirmamos que n satisface la conclusión del teorema: para toda función total computable g que concuerda con f hasta n , se cumple que f ∈ P ⟺ g ∈ P . Supongamos por contradicción que existe g total computable que concuerda con f hasta n y tal que ( g ∈ P ) ≠ B .

Aplicando nuevamente el lema, existe k tal que U ( k ) concuerda con g hasta n y g ∈ P ⟺ U ( k ) ∈ P . Para tal k , U ( k ) concuerda con g hasta n y g concuerda con f hasta n , por lo tanto U ( k ) también concuerda con f hasta n , y como ( g ∈ P ) ≠ B y g ∈ P ⟺ U ( k ) ∈ P , tenemos ( U ( k ) ∈ P ) ≠ B . Por lo tanto, U ( k ) satisface las condiciones del paso de búsqueda paralela en el programa p , a saber: U ( k ) concuerda con f hasta n y ( U ( k ) ∈ P ) ≠ B . Esto prueba que la búsqueda en el segundo paso siempre termina. Fijamos k como el valor que encuentra.

Observamos que φ _p = U ( k ). De hecho, o bien el segundo paso de p devuelve U ( k )( x ), o bien el tercer paso devuelve f ( x ), pero el último caso solo ocurre para x ≤ n , y sabemos que U ( k ) concuerda con f hasta n .

En particular, φ _p = U ( k ) es total. Esto hace que la promesa a P se cumpla en p , por lo tanto, P devuelve φ _p ∈ P en p .

Hemos encontrado una contradicción: por un lado, el booleano φ _p ∈ P es el valor de retorno de P en p , que es B , y por otro lado, tenemos φ _p = U ( k ), y sabemos que ( U ( k ) ∈ P ) ≠ B .

Perspectiva desde la topología efectiva

Para cualquier función unaria finita sobre números enteros, sea el 'truncado' de todas las funciones parcialmente recursivas que están definidas y concuerdan con , en el dominio de . ${\estilo de visualización \theta}$ $C(\theta )$ ${\estilo de visualización \theta}$ ${\estilo de visualización \theta}$

Equipe el conjunto de todas las funciones parcialmente recursivas con la topología generada por estos frusta como base . Tenga en cuenta que para cada frustum , el conjunto de índices es recursivamente enumerable. De manera más general, esto se cumple para cada conjunto de funciones parcialmente recursivas: ${\estilo de visualización C}$ $Ix(C)$ ${\estilo de visualización A}$

$Ix(A)$ es recursivamente enumerable solo si y solo si es una unión recursivamente enumerable de frusta. ${\estilo de visualización A}$

Aplicaciones

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

^ ab 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: Holanda Septentrional. págs. 290–297.
^ ab Tseitin, Grigori (1959). "Operadores algorítmicos en espacios métricos constructivos, completos y separables". Doklady Akademii Nauk . 128 : 49-52.
^ ab Rogers Jr., Hartley (1987). Teoría de funciones recursivas y 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 de la recursión clásica . Holanda Septentrional.
^ Moschovakis, Yiannis N. (junio de 2010). "El asombroso segundo teorema de recursión de Kleene" (PDF) . The Bulletin of Symbolic Logic . 16 (2).
^ Royer, James S. (junio de 1997). "Semántica vs. sintaxis vs. cálculos: modelos de máquina para funciones polinómicas de tipo 2 limitadas en el tiempo". Journal of Computer and System Sciences . 54 (3): 424–436. doi : 10.1006/jcss.1997.1487 .
^ Longley, Juan; Normann, Dag (2015). Computabilidad de orden superior . Saltador. pag. 441.doi : 10.1007 /978-3-662-47992-6.
^ 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. S2CID 8106333.
^ 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. S2CID 8618118.