Teorema de recursión de Kleene

Teorema de la teoría de la computabilidad

En teoría de la computabilidad , los teoremas de recursión 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 recursión se pueden aplicar para construir puntos fijos de ciertas operaciones en funciones computables , para generar quines y para 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 , tal que la función correspondiente al índice es . ${\displaystyle \varphi }$ ${\displaystyle e}$ ${\displaystyle \varphi _{e}}$

Si y son funciones parciales sobre los números naturales, la notación indica que, para cada n , o bien y están definidos y son iguales, o bien y están indefinidos. ${\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 . Nótese 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 recursión de Kleene. ^[4]

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

Esto significa, en esencia, que si aplicamos una transformación efectiva a los programas (por ejemplo, reemplazar instrucciones como sucesor, salto, eliminar líneas), siempre habrá un programa cuyo comportamiento no se vea alterado por la transformación. Por lo tanto, este teorema se puede interpretar de la siguiente manera: “dado cualquier procedimiento efectivo para transformar programas, siempre hay un programa que, cuando es modificado por el procedimiento, hace exactamente lo mismo que hacía antes”, o bien: “es imposible escribir un programa que cambie el comportamiento extensional de todos los programas”.

Demostración 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}$

Dado un valor de entrada , primero se intenta calcular . Si ese cálculo devuelve un valor de salida , entonces se calcula y se devuelve su valor, si lo hay. ${\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á definido, 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 , 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 computable total. Entonces , por la definición de . Pero, como 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 libres de punto fijo

Una función tal que para todo se llama libre de punto fijo . El teorema del punto fijo muestra que ninguna función computable total es libre de punto fijo, pero hay muchas funciones libres de punto fijo no computables. El criterio de completitud 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}$

Segundo teorema de recursión 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 recursión es que es posible construir programas autorreferenciales; consulte "Aplicación a quines" más adelante.

El segundo teorema de recursión . 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 una función tal que (una construcción descrita por el teorema de Smn ). Se puede verificar entonces que un punto fijo de esta es un índice, como se requiere. 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}$

Comparación con el teorema de Rogers

El segundo teorema de recursión de Kleene y el teorema de Rogers pueden demostrarse, de forma bastante sencilla, uno a partir 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 recursión 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 se puede producir eficazmente en el corolario 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 recursión

Supongamos que y son funciones computables totales que se utilizan en una definición recursiva para 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 recursión se puede utilizar para demostrar que dichas 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 mediante máquinas de Turing ). Esta definición recursiva se puede convertir en una función computable que supone que es un índice de sí misma, para simular la recursión: ${\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 recursión establece la existencia de una función computable tal que . Por lo 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 recursión basado 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 usar la reflexión); luego, se muestra que el teorema de recursión es casi trivial en el lenguaje reflexivo.

El primer teorema de recursión

Mientras que el segundo teorema de recursión se refiere a puntos fijos de funciones computables, el primer teorema de recursión se relaciona 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 un) conjunto finito de números y n es un único número natural. A menudo, n se considerará como un código para un par ordenado de números naturales, en particular 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 enumeración .

Cada operador de enumeración Φ determina una función a partir de conjuntos de números naturales a conjuntos de números 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 el gráfico de una función recursiva parcial, siempre devuelve el gráfico 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 recursión . Se cumplen las siguientes afirmaciones.

1. Para cualquier operador de enumeración computable Φ existe un conjunto enumerable recursivamente 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 parcial computable φ tal que Ψ(φ) = φ y φ es la función parcial computable más pequeña con esta propiedad.

El primer teorema de recursión también se denomina teorema del punto fijo (de la teoría de la recursión). ^[10] También existe una definición que se puede aplicar a los funcionales recursivos, como sigue:

Sea una función recursiva. 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) de tal manera 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 recursión, el primer teorema de recursión se puede utilizar para obtener funciones que satisfagan sistemas de ecuaciones de recursión. Para aplicar el primer teorema de recursión, las ecuaciones de recursión deben reformularse primero como un operador recursivo.

Consideremos las ecuaciones de recursión para la función factorial f : El operador recursivo correspondiente Φ tendrá información que indica cómo llegar al siguiente valor de f a partir del valor anterior. Sin embargo, el operador recursivo definirá en realidad el gráfico de f . Primero, Φ contendrá el par . Esto indica que f (0) es inequívocamente 1 y, por lo tanto, el par (0,1) está en el gráfico de f . $${\displaystyle {\begin{aligned}&f(0)=1\\&f(n+1)=(n+1)\cdot f(n)\end{aligned}}}$$ ${\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 el gráfico 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 recursión (en particular, la parte 1) establece que existe un conjunto F tal que Φ( F ) = F . El conjunto F estará formado enteramente por pares ordenados de números naturales, y será el gráfico de la función factorial f , como se desea.

La restricción a las ecuaciones de recursión que se pueden reformular como operadores recursivos garantiza que las ecuaciones de recursión realmente definan un punto mínimo fijo. Por ejemplo, considere el conjunto de ecuaciones de recursión: No existe ninguna función g que satisfaga estas ecuaciones, porque implican g (2) = 1 y también implican g (2) = 0. Por lo tanto, no existe ningún punto fijo g que satisfaga estas ecuaciones de recursión. Es posible crear un operador de enumeración correspondiente a estas ecuaciones, pero no será un operador recursivo. $${\displaystyle {\begin{aligned}&g(0)=1\\&g(n+1)=1\\&g(2n)=0\end{aligned}}}$$

Esquema de demostración del primer teorema de recursión

La demostración de la parte 1 del primer teorema de recursión 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 toma F como . El resto de la demostración consiste en una verificación de que F es recursivamente enumerable y es el punto fijo menor de Φ. La secuencia F _k utilizada en esta demostración corresponde a la cadena de Kleene en la demostración 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 recursión se desprende de la primera parte. Se utiliza el supuesto de que Φ es un operador recursivo para demostrar que el punto fijo de Φ es el gráfico de una función parcial. El punto clave es que si el punto fijo F no es el gráfico de una función, entonces existe algún k tal que F _k no es el gráfico de una función.

Comparación con el segundo teorema de recursión

En comparación con el segundo teorema de recursión, el primer teorema de recursión 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 recursión débil para el primer teorema de recursión y teorema de recursión fuerte para el segundo teorema de recursión. ^[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 sean puntos mínimos fijos, mientras que los obtenidos por el segundo teorema de recursión pueden no ser puntos mínimos fijos.

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

Teorema generalizado

En el contexto de su teoría de numeraciones, Ershov demostró que el teorema de recursión de Kleene se cumple 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).}$

Véase también

• Semántica denotacional , donde se utiliza otro teorema del punto mínimo fijo para el mismo propósito que el primer teorema de recursión.
• Combinadores de punto fijo , que se utilizan en el cálculo lambda para el mismo propósito que el primer teorema de recursión.
• Lema diagonal: 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 Griffor, 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. Bibliotheca Mathematica. North-Holland Publishing . 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 al pie

1. Kleene, Stephen C. (1938). "Sobre la notación de números ordinales" (PDF) . Journal of Symbolic Logic . 3 (4): 150–155. doi :10.2307/2267778. ISSN  0022-4812. JSTOR  2267778. S2CID  34314018 . Consultado el 6 de mayo de 2020 .
2. Kleene 1952.
3. Rogers 1967.
4. Rogers 1967, §11.2.
5. Soare, RI (1987). Conjuntos y grados recursivamente enumerables: un estudio de funciones computables y conjuntos generados computacionalmente . Perspectivas en lógica matemática. Berlín y Nueva York: Springer-Verlag . pág. 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: Introducción a la teoría de funciones recursivas. Cambridge University Press . pág. 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 .pág. 1151.
12. Véase Ershov 1999, §4.14 para una encuesta en inglés.

Lectura adicional

• Jockusch, CG ; Lerman, M.; Soare, RI ; Solovay, RM (1989). "Conjuntos enumerables recursivamente módulo saltos iterados y extensiones del criterio de completitud de Arslanov". The Journal of Symbolic Logic . 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 Stanford Encyclopedia of Philosophy , 2012.