Teorema de recursividad de Kleene - Kleene's recursion theorem

En la 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 probados por primera vez por Stephen Kleene en 1938 y aparecen en su libro de 1952 Introducción a las metamatemáticas . Un teorema relacionado, que construye puntos de una función computable fijo, se conoce como el teorema de Rogers y se debe a Hartley Rogers, Jr. .

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 modo que la función correspondiente a índice es . ${\ Displaystyle \ varphi}$${\ Displaystyle e}$${\ Displaystyle \ varphi _ {e}}$

Si y son funciones parciales en los números naturales, la notación indica que, para cada n , y son ambos definidos y son iguales, o bien y ambos son 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 . Rogers describe el siguiente resultado como "una versión más simple" del (segundo) teorema de recursividad de Kleene. ${\ Displaystyle F}$${\ Displaystyle F}$${\ Displaystyle e}$${\ Displaystyle \ varphi _ {e} \ simeq \ varphi _ {F (e)}}$

Teorema del punto fijo de Rogers . Si es una función computable total, tiene un punto fijo.${\ Displaystyle F}$

Prueba del teorema del punto fijo

La demostración usa una función computable total particular , definida como sigue. 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 , primer intento de calcular . Si ese cálculo devuelve una salida , calcule y devuelva su valor, si lo hay.${\ Displaystyle y}$${\ Displaystyle \ varphi _ {x} (x)}$${\ Displaystyle e}$${\ Displaystyle \ varphi _ {e} (y)}$

Por tanto, para todos los índices de funciones computables parciales, si se define, 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 demostración, 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, debido a que 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 calculable total es libre de punto fijo, pero hay muchas funciones libres de punto fijo no calculables. El criterio de completitud de Arslanov establece que el único grado de Turing enumerable recursivamente que calcula una función libre de punto fijo es 0 ′ , el grado del problema de detención . ${\ Displaystyle F}$${\ Displaystyle \ varphi _ {e} \ not \ simeq \ varphi _ {F (e)}}$${\ Displaystyle e}$

Segundo teorema de recursividad de Kleene

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

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

El teorema se puede demostrar a partir del teorema de Rogers haciendo que sea ​​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 mapea un índice para Q en el índice p . ${\ Displaystyle F (p)}$${\ Displaystyle \ varphi _ {F (p)} (y) = Q (p, y)}$${\ Displaystyle F}$${\ Displaystyle p}$

Comparación con el teorema de Rogers

El segundo teorema de recursividad de Kleene y el teorema de Rogers pueden probarse, de manera bastante simple, el uno del otro. Sin embargo, una prueba directa del teorema de Kleene no hace uso de un programa universal, lo que significa que el teorema es válido para ciertos sistemas de programación subrecursivos 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. Cuando se expresan como programas de computadora, estos índices se conocen como quines . ${\ Displaystyle Q (x, y) = x}$${\ Displaystyle p}$

El siguiente ejemplo en Lisp ilustra cómo el corolario 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

Q se puede cambiar a cualquier función de dos argumentos.

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

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

(eval (list p nil))

Q(p, nil)

(eval (list Q p nil))

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

Suponga que y son funciones computables totales que se usan 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 recursividad puede usarse para mostrar que tales ecuaciones definen una función computable, donde la noción de computabilidad no tiene que permitir, prima facie, definiciones recursivas (por ejemplo, puede definirse por μ-recursividad , 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 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 recursividad basada en un lenguaje reflexivo. 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 muestra que el teorema de 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 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 yn es un número natural único. 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 \ existe 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 de un Φ operador enumeración fijo es un conjunto F de tal manera que Φ ( F ) = F . El primer teorema de enumeración muestra que los puntos fijos pueden obtenerse eficazmente si el operador de enumeración en sí es computable.

Primer teorema de recursividad . Las siguientes declaraciones son válidas.

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

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 recursión. Para aplicar el primer teorema de recursividad, las ecuaciones de recursividad primero deben reformularse como un operador recursivo.

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

${\ Displaystyle f (0) = 1}$

${\ Displaystyle f (n + 1) = (n + 1) \ cdot f (n)}$

El operador recursivo correspondiente Φ tendrá información que indica cómo llegar al siguiente valor de f desde el valor anterior. Sin embargo, el operador recursivo realmente definirá la gráfica 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 la gráfica de f . ${\ 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 hay un conjunto F tal que Φ ( F ) = F. El conjunto F constará enteramente de pares ordenados de números naturales, y será la gráfica de la función factorial f , como se desee.

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

${\ Displaystyle g (0) = 1}$

${\ Displaystyle g (n + 1) = 1}$

${\ Displaystyle g (2n) = 0}$

No hay una función g que satisfaga estas ecuaciones, porque implican g (2) = 1 y también implican g (2) = 0. Por tanto, no hay un punto fijo g que satisfaga estas ecuaciones de recursión. Es posible hacer un operador de enumeración correspondiente a estas ecuaciones, pero no será un operador recursivo.

Bosquejo de prueba del primer teorema de recursividad

La demostración 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 , deja F _{k + 1} sea . Finalmente, F se toma para ser . 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 usada 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})}$${\ Displaystyle \ bigcup F_ {k}}$

La segunda parte del primer teorema de recursividad se deriva de la primera parte. La suposición de que Φ es un operador recursivo se usa para mostrar 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 existe una k tal que F _k no es la gráfica de una función.

Comparación con el segundo teorema de recursividad

Comparado con el segundo teorema de recursividad, el primer teorema de recursividad produce una conclusión más sólida, pero solo cuando se satisfacen hipótesis más estrechas. Rogers usa 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.

Una diferencia entre el primer y el segundo teorema de recursividad es que se garantiza que los puntos fijos obtenidos por el primer teorema de recursividad son puntos mínimos fijos, mientras que los obtenidos a partir del segundo teorema de recursividad pueden no ser puntos mínimos fijos.

Una segunda diferencia es que el primer teorema de recursividad solo se aplica a sistemas de ecuaciones que pueden reformularse como operadores recursivos. Esta restricción es similar a la restricción a los operadores continuos en el teorema del punto fijo de Kleene de la teoría del orden . El segundo teorema de 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 recursividad de Kleene es válido para cualquier numeración precompleta . 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 recursividad de Kleene como un caso especial.

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 otro teorema de punto mínimo fijo se usa 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.

Referencias

• Ershov, Yuri L. (1999). "Parte 4: Teoría de las Matemáticas y 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. 140 . Amsterdam: 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. 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 al pie

Otras lecturas

• Jockusch, CG ; Lerman, M .; Soare, RI ; Solovay, RM (1989). "Conjuntos recursivamente enumerables modulo saltos iterados y extensiones del criterio de completitud de Arslanov". El diario de la lógica simbólica . 54 (4): 1288-1323. doi : 10.1017 / S0022481200041104 . ISSN  0022-4812 . JSTOR  2274816 .

enlaces externos

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