Teorema de recursividad de Kleene

Teorema de la teoría de la computabilidad

En teoría de la computabilidad , los teoremas de recursividad de Kleene son un par de resultados fundamentales sobre la aplicación de funciones computables a sus propias descripciones. Los teoremas fueron demostrados por primera vez por Stephen Kleene en 1938 ^[1] y aparecen en su libro de 1952 Introducción a las metamatemáticas . ^[2] Un teorema relacionado, que construye puntos fijos de una función computable, se conoce como teorema de Rogers y se debe a Hartley Rogers, Jr. ^[3]

Los teoremas de recursividad se pueden aplicar para construir puntos fijos de ciertas operaciones en funciones computables , generar quines y construir funciones definidas mediante definiciones recursivas .

Notación

El enunciado de los teoremas se refiere a una numeración admisible de las funciones recursivas parciales , de manera que la función correspondiente al índice sea . ${\displaystyle \varphi }$ ${\displaystyle e}$ ${\displaystyle \varphi _{e}}$

Si y son funciones parciales de los números naturales, la notación indica que, para cada n , o y están definidos y son iguales, o bien y ambos no están definidos. ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle F\simeq G}$ ${\displaystyle F(n)}$ ${\displaystyle G(n)}$ ${\displaystyle F(n)}$ ${\displaystyle G(n)}$

Teorema del punto fijo de Rogers

Dada una función , un punto fijo de es un índice tal que . Tenga en cuenta que la comparación de entradas y salidas aquí no se realiza en términos de valores numéricos, sino en términos de sus funciones asociadas. ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle e}$ ${\displaystyle \varphi _{e}\simeq \varphi _{F(e)}}$

Rogers describe el siguiente resultado como "una versión más simple" del (segundo) teorema de recursividad de Kleene. ^[4]

Teorema del punto fijo de Rogers  :  si es una función total computable, tiene un punto fijo en el sentido anterior. ${\displaystyle F}$

Prueba del teorema del punto fijo

La prueba utiliza una función computable total particular , definida de la siguiente manera. Dado un número natural , la función genera el índice de la función computable parcial que realiza el siguiente cálculo: ${\displaystyle h}$ ${\displaystyle x}$ ${\displaystyle h}$

Dada una entrada , primero intente calcular . Si ese cálculo devuelve un resultado , entonces calcule y devuelva su valor, si corresponde. ${\displaystyle y}$ ${\displaystyle \varphi _{x}(x)}$ ${\displaystyle e}$ ${\displaystyle \varphi _{e}(y)}$

Por lo tanto, para todos los índices de funciones computables parciales, si está definido, entonces . Si no está definida, entonces es una función que no está definida en ninguna parte. La función se puede construir a partir de la función computable parcial descrita anteriormente y el teorema smn : para cada uno , es el índice de un programa que calcula la función . ${\displaystyle x}$ ${\displaystyle \varphi _{x}(x)}$ ${\displaystyle \varphi _{h(x)}\simeq \varphi _{\varphi _{x}(x)}}$ ${\displaystyle \varphi _{x}(x)}$ ${\displaystyle \varphi _{h(x)}}$ ${\displaystyle h}$ ${\displaystyle g(x,y)}$ ${\displaystyle x}$ ${\displaystyle h(x)}$ ${\displaystyle y\mapsto g(x,y)}$

Para completar la prueba, sea cualquier función computable total y construya como se indicó anteriormente. Sea un índice de la composición , que es una función total computable. Luego por la definición de . Pero, porque es un índice de , y por lo tanto . Por la transitividad de , esto significa . Por lo tanto para . ${\displaystyle F}$ ${\displaystyle h}$ ${\displaystyle e}$ ${\displaystyle F\circ h}$ ${\displaystyle \varphi _{h(e)}\simeq \varphi _{\varphi _{e}(e)}}$ ${\displaystyle h}$ ${\displaystyle e}$ ${\displaystyle F\circ h}$ ${\displaystyle \varphi _{e}(e)=(F\circ h)(e)}$ ${\displaystyle \varphi _{\varphi _{e}(e)}\simeq \varphi _{F(h(e))}}$ ${\displaystyle \simeq }$ ${\displaystyle \varphi _{h(e)}\simeq \varphi _{F(h(e))}}$ ${\displaystyle \varphi _{n}\simeq \varphi _{F(n)}}$ ${\displaystyle n=h(e)}$

Esta prueba es una construcción de una función recursiva parcial que implementa el combinador Y.

Funciones sin punto fijo

Una función tal que para todos se llama libre de punto fijo . El teorema del punto fijo muestra que ninguna función computable total está libre de punto fijo, pero hay muchas funciones no computables sin punto fijo. El criterio de integridad de Arslanov establece que el único grado de Turing recursivamente enumerable que calcula una función libre de punto fijo es 0′ , el grado del problema de detención . ^[5] ${\displaystyle F}$ ${\displaystyle \varphi _{e}\not \simeq \varphi _{F(e)}}$ ${\displaystyle e}$

El segundo teorema de recursividad de Kleene

El segundo teorema de recursión es una generalización del teorema de Rogers con una segunda entrada en la función. Una interpretación informal del segundo teorema de la recursividad es que es posible construir programas autorreferenciales; consulte "Aplicación a quines" a continuación.

El segundo teorema de la recursividad . Para cualquier función recursiva parcial existe un índice tal que . ${\displaystyle Q(x,y)}$ ${\displaystyle p}$ ${\displaystyle \varphi _{p}\simeq \lambda y.Q(p,y)}$

El teorema se puede demostrar a partir del teorema de Rogers dejando ser una función tal que (una construcción descrita por el teorema de Smn ). Luego se puede verificar que un punto fijo de esto sea un índice según sea necesario. El teorema es constructivo en el sentido de que una función computable fija asigna un índice para al índice . ${\displaystyle F(p)}$ ${\displaystyle \varphi _{F(p)}(y)=Q(p,y)}$ ${\displaystyle F}$ ${\displaystyle p}$ ${\displaystyle Q}$ ${\displaystyle p}$

Esto se puede ampliar aún más a funciones computables con esta declaración:

Sea una función computable total. Entonces, existe un programa tal que . ${\displaystyle f:\mathbb {N} \rightarrow \mathbb {N} }$ ${\displaystyle e_{0}\in \mathbb {N} }$ ${\displaystyle \phi _{e_{0}}=\phi _{(f_{(}e_{0}))}}$

Básicamente, esto significa que si tomamos un programa y aplicamos una transformación efectiva de forma extensiva (por ejemplo, reemplazar instrucciones como sucesor, saltar, eliminar líneas), siempre habrá un programa que no se modifique mediante la transformación de la función. , incluso antes o después.

Por lo tanto, este teorema puede interpretarse de la siguiente manera: “dado cualquier procedimiento efectivo para transformar programas, siempre hay un programa tal que, cuando es modificado por el procedimiento, hace exactamente lo que hizo antes, o es imposible escribir un programa que cambie el comportamiento extensivo de todos los demás programas”.

Comparación con el teorema de Rogers

El segundo teorema de recursividad de Kleene y el teorema de Rogers pueden demostrarse, de forma bastante sencilla, el uno del otro. ^[6] Sin embargo, una prueba directa del teorema de Kleene ^[7] no hace uso de un programa universal, lo que significa que el teorema es válido para ciertos sistemas de programación subrecursiva que no tienen un programa universal.

Aplicación a quines

Un ejemplo clásico que utiliza el segundo teorema de recursividad es la función . El índice correspondiente en este caso produce una función computable que genera su propio índice cuando se aplica a cualquier valor. ^[8] Cuando se expresan como programas de computadora, dichos índices se conocen como quines . ${\displaystyle Q(x,y)=x}$ ${\displaystyle p}$

El siguiente ejemplo en Lisp ilustra cómo el corolario in se puede producir efectivamente a partir de la función . La función en el código es la función de ese nombre producida por el teorema de Smn . ${\displaystyle p}$ ${\displaystyle Q}$s11

Qse puede cambiar a cualquier función de dos argumentos.

( setq Q ' ( lambda ( x y ) x )) ( setq s11 ' ( lambda ( f x ) ( lista ' lambda ' ( y ) ( lista f x ' y )))) ( setq n ( lista ' lambda ' ( x y ) ( lista Q ( lista s11 'x 'x ) 'y ))) ( setq p ( eval ( lista s11 n n )))                                  

Los resultados de las siguientes expresiones deben ser los mismos. ${\displaystyle \varphi }$ p(nil)

( eval ( lista p nil ))   

Q(p, nil)

( eval ( lista Q p nil ))    

Aplicación a la eliminación de la recursividad.

Supongamos que y son funciones computables totales que se utilizan en una definición recursiva de una función : ${\displaystyle g}$ ${\displaystyle h}$ ${\displaystyle f}$

${\displaystyle f(0,y)\simeq g(y),}$

${\displaystyle f(x+1,y)\simeq h(f(x,y),x,y),}$

El segundo teorema de recursividad se puede utilizar para demostrar que tales ecuaciones definen una función computable, donde la noción de computabilidad no tiene por qué permitir, prima facie, definiciones recursivas (por ejemplo, puede definirse mediante μ-recursión o por Turing) . máquinas ). Esta definición recursiva se puede convertir en una función computable que asume que es un índice de sí misma, para simular la recursividad: ${\displaystyle \varphi _{F}(e,x,y)}$ ${\displaystyle e}$

${\displaystyle \varphi _{F}(e,0,y)\simeq g(y),}$

${\displaystyle \varphi _{F}(e,x+1,y)\simeq h(\varphi _{e}(x,y),x,y).}$

El teorema de la recursividad establece la existencia de una función computable tal que . Por tanto, satisface la definición recursiva dada. ${\displaystyle \varphi _{f}}$ ${\displaystyle \varphi _{f}(x,y)\simeq \varphi _{F}(f,x,y)}$ ${\displaystyle f}$

Programación reflexiva

La programación reflexiva o reflexiva se refiere al uso de la autorreferencia en los programas. Jones presenta una visión del segundo teorema de la recursividad basada en un lenguaje reflexivo. ^[9] Se muestra que el lenguaje reflexivo definido no es más fuerte que un lenguaje sin reflexión (porque se puede implementar un intérprete para el lenguaje reflexivo sin utilizar la reflexión); luego, se demuestra que el teorema de la recursividad es casi trivial en el lenguaje reflexivo.

El primer teorema de recursividad.

Mientras que el segundo teorema de recursividad trata sobre puntos fijos de funciones computables, el primer teorema de recursividad está relacionado con puntos fijos determinados por operadores de enumeración, que son un análogo computable de las definiciones inductivas. Un operador de enumeración es un conjunto de pares ( A , n ) donde A es un ( código para a) conjunto finito de números y n es un único número natural. A menudo, n se verá como un código para un par ordenado de números naturales, particularmente cuando las funciones se definen mediante operadores de enumeración. Los operadores de enumeración son de importancia central en el estudio de la reducibilidad de la enumeración .

Cada operador de enumeración Φ determina una función desde conjuntos de naturales hasta conjuntos de naturales dados por

${\displaystyle \Phi (X)=\{n\mid \exists A\subseteq X[(A,n)\in \Phi ]\}.}$

Un operador recursivo es un operador de enumeración que, cuando se le da la gráfica de una función recursiva parcial, siempre devuelve la gráfica de una función recursiva parcial.

Un punto fijo de un operador de enumeración Φ es un conjunto F tal que Φ( F ) = F . El primer teorema de enumeración muestra que se pueden obtener puntos fijos de manera efectiva si el operador de enumeración en sí es computable.

Primer teorema de recursividad . Se mantienen las siguientes afirmaciones.

1. Para cualquier operador de enumeración computable Φ existe un conjunto recursivamente enumerable F tal que Φ( F ) = F y F es el conjunto más pequeño con esta propiedad.
2. Para cualquier operador recursivo Ψ existe una función computable parcial φ tal que Ψ(φ) = φ y φ es la función computable parcial más pequeña con esta propiedad.

El primer teorema de la recursividad también se llama teorema del punto fijo (de la teoría de la recursividad). ^[10] También existe una definición que se puede aplicar a funcionales recursivos de la siguiente manera:

Sea un funcional recursivo. Entonces tiene un punto mínimo fijo que es computable, es decir ${\displaystyle \Phi :\mathbb {F} (\mathbb {N} ^{k})\rightarrow (\mathbb {N} ^{k})}$ ${\displaystyle \Phi }$ ${\displaystyle f_{\Phi }:\mathbb {N} ^{k}\rightarrow \mathbb {N} }$

1) ${\displaystyle \Phi (f_{\phi })=f_{\Phi }}$

2) tal que se cumple que ${\displaystyle \forall g\in \mathbb {F} (\mathbb {N} ^{k})}$ ${\displaystyle \Phi (g)=g}$ ${\displaystyle f_{\Phi }\subseteq g}$

3) es computable ${\displaystyle f_{\Phi }}$

Ejemplo

Al igual que el segundo teorema de recursividad, el primer teorema de recursividad se puede utilizar para obtener funciones que satisfagan sistemas de ecuaciones de recursividad. Para aplicar el primer teorema de recursividad, las ecuaciones de recursividad primero deben reformularse como un operador recursivo.

Considere las ecuaciones de recursividad para la función factorial f :

$${\displaystyle {\begin{aligned}&f(0)=1\\&f(n+1)=(n+1)\cdot f(n)\end{aligned}}}$$

ffff ${\displaystyle (\varnothing ,(0,1))}$

A continuación, para cada n y m , Φ contendrá el par . Esto indica que, si f ( n ) es m , entonces f ( n + 1) es ( n + 1) m , de modo que el par ( n + 1, ( n + 1) m ) está en la gráfica de f . A diferencia del caso base f (0) = 1 , el operador recursivo requiere cierta información sobre f ( n ) antes de definir un valor de f ( n + 1) . ${\displaystyle (\{(n,m)\},(n+1,(n+1)\cdot m))}$

El primer teorema de recursividad (en particular, la parte 1) establece que existe un conjunto F tal que Φ( F ) = F . El conjunto F estará formado íntegramente por pares ordenados de números naturales, y será la gráfica de la función factorial f , como se desee.

La restricción a ecuaciones de recursividad que pueden reformularse como operadores recursivos garantiza que las ecuaciones de recursividad realmente definan un punto mínimo fijo. Por ejemplo, considere el conjunto de ecuaciones de recursividad:

$${\displaystyle {\begin{aligned}&g(0)=1\\&g(n+1)=1\\&g(2n)=0\end{aligned}}}$$

gggg

Bosquejo de prueba del primer teorema de recursividad

La prueba de la parte 1 del primer teorema de recursividad se obtiene iterando el operador de enumeración Φ comenzando con el conjunto vacío. Primero, se construye una secuencia F _k , para . Sea F ₀ el conjunto vacío. Procediendo inductivamente, para cada k , sea F _{k + 1} . Finalmente, se considera que F es . El resto de la prueba consiste en una verificación de que F es recursivamente enumerable y es el punto menos fijo de Φ. La secuencia F _k utilizada en esta prueba corresponde a la cadena de Kleene en la prueba del teorema del punto fijo de Kleene . ${\displaystyle k=0,1,\ldots }$ ${\displaystyle F_{k}\cup \Phi (F_{k})}$ ${\textstyle \bigcup F_{k}}$

La segunda parte del primer teorema de recursividad se deriva de la primera parte. El supuesto de que Φ es un operador recursivo se utiliza para demostrar que el punto fijo de Φ es la gráfica de una función parcial. El punto clave es que si el punto fijo F no es la gráfica de una función, entonces hay algún k tal que F _k no es la gráfica de una función.

Comparación con el segundo teorema de recursividad

En comparación con el segundo teorema de recursividad, el primer teorema de recursividad produce una conclusión más sólida, pero sólo cuando se satisfacen hipótesis más estrechas. Rogers utiliza el término teorema de recursividad débil para el primer teorema de recursividad y teorema de recursividad fuerte para el segundo teorema de recursividad. ^[3]

Una diferencia entre el primer y el segundo teorema de recursión es que se garantiza que los puntos fijos obtenidos por el primer teorema de recursión serán puntos menos fijos, mientras que los obtenidos a partir del segundo teorema de recursión pueden no ser puntos menos fijos.

Una segunda diferencia es que el primer teorema de recursividad sólo se aplica a sistemas de ecuaciones que pueden reformularse como operadores recursivos. Esta restricción es similar a la restricción a operadores continuos en el teorema del orden del punto fijo de Kleene . El segundo teorema de la recursividad se puede aplicar a cualquier función recursiva total.

Teorema generalizado

En el contexto de su teoría de la numeración, Ershov demostró que el teorema de recursión de Kleene es válido para cualquier numeración precompleta . ^[11] Una numeración de Gödel es una numeración precompleta en el conjunto de funciones computables, por lo que el teorema generalizado produce el teorema de recursión de Kleene como un caso especial. ^[12]

Dada una numeración precompleta , entonces para cualquier función computable parcial con dos parámetros existe una función computable total con un parámetro tal que ${\displaystyle \nu }$ ${\displaystyle f}$ ${\displaystyle t}$

${\displaystyle \forall n\in \mathbb {N} :\nu \circ f(n,t(n))=\nu \circ t(n).}$

Ver también

• Semántica denotacional , donde se utiliza otro teorema del punto mínimo fijo con el mismo propósito que el primer teorema de recursividad.
• Combinadores de punto fijo , que se utilizan en el cálculo lambda con el mismo propósito que el primer teorema de recursividad.
• El lema diagonal es un resultado estrechamente relacionado en la lógica matemática.

Referencias

• Ershov, Yuri L. (1999). "Parte 4: Matemáticas y Teoría de la Computabilidad. 14. Teoría de la numeración". En Griffinr, Edward R. (ed.). Manual de teoría de la computabilidad. Estudios de lógica y fundamentos de las matemáticas. vol. 140. Ámsterdam: Elsevier . págs. 473–503. ISBN 9780444898821. OCLC  162130533 . Consultado el 6 de mayo de 2020 .
• Jones, Neil D. (1997). Computabilidad y complejidad: desde una perspectiva de programación . Cambridge, Massachusetts : MIT Press . ISBN 9780262100649. OCLC  981293265.
• Kleene, Stephen C. (1952). Introducción a las Metamatemáticas. Biblioteca Matemática. Editorial de Holanda Septentrional . ISBN 9780720421033. OCLC  459805591 . Consultado el 6 de mayo de 2020 .
• Rogers, Hartley (1967). Teoría de funciones recursivas y computabilidad efectiva . Cambridge, Massachusetts : MIT Press . ISBN 9780262680523. OCLC  933975989 . Consultado el 6 de mayo de 2020 .

Notas a pie de página

1. Kleene, Stephen C. (1938). "Sobre notación de números ordinales" (PDF) . Revista de Lógica Simbólica . 3 (4): 150-155. doi :10.2307/2267778. ISSN  0022-4812. JSTOR  2267778. S2CID  34314018 . Consultado el 6 de mayo de 2020 .
2. Kleine 1952.
3. Rogers 1967.
4. Rogers 1967, §11.2.
5. Soare, Rhode Island (1987). Conjuntos y grados recursivamente enumerables: un estudio de funciones computables y conjuntos generados computablemente . Perspectivas en lógica matemática. Berlín y Nueva York: Springer-Verlag . pag. 88.ISBN _ 9780387152998. OCLC  318368332.
6. Jones 1997, págs. 229–30.
7. Kleene 1952, págs. 352-3.
8. Cutland, Nigel J. (1980). Computabilidad: una introducción a la teoría de funciones recursivas. Prensa de la Universidad de Cambridge . pag. 204.doi : 10.1017 /cbo9781139171496. ISBN 9781139935609. OCLC  488175597 . Consultado el 6 de mayo de 2020 .
9. Jones 1997.
10. Cutland, Nigel. Computabilidad: una introducción a la teoría de funciones recursivas .
11. Barendregt, Henk ; Terwijn, Sebastiaan A. (2019). «Teoremas de punto fijo para numeraciones precompletas» . Anales de lógica pura y aplicada . 170 (10): 1151-1161. doi :10.1016/j.apal.2019.04.013. hdl : 2066/205967 . ISSN  0168-0072. S2CID  52289429 . Consultado el 6 de mayo de 2020 .pag. 1151.
12. Véase Ershov 1999, §4.14 para una encuesta en inglés.

Otras lecturas

• Jockusch, CG ; Lerman, M.; Soare, Rhode Island ; Solováy, RM (1989). "Conjuntos recursivamente enumerables módulo saltos iterados y extensiones del criterio de integridad de Arslanov". La revista de lógica simbólica . 54 (4): 1288-1323. doi :10.1017/S0022481200041104. ISSN  0022-4812. JSTOR  2274816. S2CID  32203705.

enlaces externos

• Entrada "Funciones recursivas" de Piergiorgio Odifreddi en la Enciclopedia de Filosofía de Stanford , 2012.