Teorema de recursión de Kleene

ImprimirCitar

En la 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 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 fijos de una función computable, se conoce como teorema de Rogers y se debe a Hartley Rogers, Jr.

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 a través de definiciones recursivas.

Notación

La declaración de los teoremas se refiere a una numeración admisible $varphi$ de las funciones recursivas parciales, tal que la función correspondiente al índice $e$ es $varphi _{e}$ .

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

Teorema del punto fijo de Rogers

Dada la función $F$ , a punto fijo de $F$ es un índice $e$ tales que $varphi _{e}simeq varphi _{F(e)}$ . Rogers describe el siguiente resultado como "una versión más simple" del teorema de recursión de Kleene (segundo).

Teorema de punto fijo de Rogers—Si $F$ es una función computable total, tiene un punto fijo.

Demostración del teorema del punto fijo

La prueba utiliza una función computable total particular $h$ , definido como sigue. Dado un número natural $x$ , la función $h$ produce el índice de la función computable parcial que realiza la siguiente computación:

Dada una aportación

y

, primer intento de computación

varphi _{x}(x)

. Si ese cálculo devuelve una salida

e

, entonces compute

varphi _{e}(y)

y devolver su valor, si lo hay.

Así, para todos los índices $x$ de funciones computables parciales, si $varphi _{x}(x)$ se define, entonces $varphi _{h(x)}simeq varphi _{varphi _{x}(x)}$ . Si $varphi _{x}(x)$ no se define, entonces ${displaystyle varphi _{h(x)}}$ es una función que no está definida. La función $h$ puede ser construido a partir de la función computable parcial $g(x,y)$ descrito arriba y el s-m-n teorema: para cada $x$ , $h(x)$ es el índice de un programa que calcula la función $ymapsto g(x,y)$ .

Para completar la prueba, deja $F$ ser cualquier función computable total, y construir $h$ como arriba. Vamos $e$ ser un índice de la composición $Fcirc h$ , que es una función computable total. Entonces... $varphi _{h(e)}simeq varphi _{varphi _{e}(e)}$ por la definición de $h$ . Pero, porque $e$ es un índice de $Fcirc h$ , $varphi _{e}(e)=(Fcirc h)(e)$ , y así $varphi _{varphi _{e}(e)}simeq varphi _{F(h(e))}$ . Por la transitividad $simeq$ , esto significa $varphi _{h(e)}simeq varphi _{F(h(e))}$ . Por lo tanto $varphi _{n}simeq varphi _{F(n)}$ para $n=h(e)$ .

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

Funciones sin puntos fijos

Una función $F$ tales que $varphi _{e}not simeq varphi _{F(e)}$ para todos $e$ se llama fija-punto libre. El teorema de punto fijo muestra que ninguna función computable total es libre de puntos fijos, pero hay muchas funciones libres de puntos fijos no compatibles. El criterio de integridad de Arslanov declara que el único título de Turing repetidamente enumerable que calcula una función sin punto fijo es 0, el grado del problema de suspensión.

El segundo teorema de recursión de Kleine

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; ver "Aplicación a quines" abajo.

El segundo teorema de recursión. Para cualquier función recursiva parcial

Q(x,y)

hay un índice

p

tales que

varphi _{p}simeq lambda y.Q(p,y)

El teorema puede probarse del teorema de Rogers dejando $F(p)$ ser una función tal que $varphi _{F(p)}(y)=Q(p,y)$ (una construcción descrita por el teorema S-m-n). Uno puede entonces verificar que un punto fijo de esto $F$ es un índice $p$ 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.

Comparación con el teorema de Rogers

El segundo teorema de recursión de Kleine y el teorema de Rogers pueden demostrarse, de manera bastante simple, el uno del otro. Sin embargo, una demostración directa del teorema de Kleene no utiliza un programa universal, lo que significa que el teorema se cumple para ciertos sistemas de programación subrecursivos que no tienen un programa universal.

Aplicación a quines

Un ejemplo clásico usando el segundo teorema de recursión es la función $Q(x,y)=x$ . El índice correspondiente $p$ en este caso produce una función computable que produce su propio índice cuando se aplica a cualquier valor. Cuando se expresa como programas informáticos, tales índices son conocidos como quines.

El siguiente ejemplo en Lisp ilustra cómo $p$ en el corolario se puede producir eficazmente a partir de la función $Q$ . La función s11 en el código es la función de ese nombre producido por el teorema S-m-n.

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

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

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

()eval ()lista p Nil)

Q(p, cero)

()eval ()lista Q p Nil)

Aplicación a la eliminación de la recursividad

Supongamos que $g$ y $h$ son funciones computables totales que se utilizan en una definición recursiva para una función $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 tales ecuaciones definen una función computable, donde la noción de computabilidad no tiene que permitir, prima facie, para definiciones recursivas (por ejemplo, puede ser definida por μ-recursion, o por máquinas Turing). Esta definición recursiva puede convertirse en una función computable $varphi _{F}(e,x,y)$ que asume $e$ es un índice a sí mismo, para simular la recursión:

{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 $varphi _{f}$ tales que $varphi _{f}(x,y)simeq varphi _{F}(f,x,y)$ . Así $f$ satisface la definición recursiva dada.

Programación reflexiva

La programación reflexiva se refiere al uso de autorreferencias en los programas. Jones presenta una vista del segundo teorema de recursión basado 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 recursión es casi trivial en el lenguaje reflexivo.

El primer teorema de recursión

Mientras que el segundo teorema de recursión trata sobre puntos fijos de funciones computables, el primer teorema de recursión 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 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, especialmente cuando las funciones se definen mediante operadores de enumeración. Los operadores de enumeración tienen una importancia central en el estudio de la reducibilidad de la enumeración.

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

Phi (X)={nmid exists Asubseteq 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 los puntos fijos se pueden obtener de manera efectiva si el propio operador de enumeración es computable.

Primer teorema de recursión. Se mantienen las siguientes declaraciones.

Para cualquier operador de enumeración computable ⋅ there is a recursively enumerable set F tal que Ё(F) F y F es el conjunto más pequeño con esta propiedad.
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 recursión, el primer teorema de recursión se puede utilizar para obtener funciones que satisfagan sistemas de ecuaciones de recurrencia. Para aplicar el primer teorema de recursión, las ecuaciones de recurrencia primero deben reformularse como un operador recursivo.

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

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

El operador recursivo correspondiente ⋅ will have information that tell how to get to the next value of f del valor anterior. Sin embargo, el operador recursivo en realidad definirá el gráfico de f. Primero, ⋅ contendrá el par $(varnothing(0,1))$ . Esto indica que f(0) es inequívocamente 1, y por lo tanto el par (0,1) está en el gráfico de f.

Siguiente, para cada n y m, ⋅ contendrá el par $({(n,m)},(n+1,(n+1)cdot m))$ . Esto indica que, si f()n) es m, entonces f()n + 1) es ()n + 1)mAsí que el par ()n + 1,n + 1)m) está en el gráfico 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).

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á la gráfica de la función factorial f, como se desee.

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

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

No hay función g que satisfaga estas ecuaciones, porque implican g(2) = 1 y también implican g(2) = 0. Por lo tanto, no hay un punto fijo g que satisfaga estas ecuaciones de recurrencia. 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 recursión

La prueba de la parte 1 del primer teorema de recursión se obtiene mediante la iteración del operador de enumeración Ё comenzando con el conjunto vacío. Primero, una secuencia F_k es construido, para $k=0,1,ldots$ . Vamos F₀ Sé el set vacío. Proceder inductivamente, para cada uno k, vamos F_{k + 1} Ser $F_{k}cup Phi (F_{k})$ . Finalmente, F se ha tomado ${textstyle bigcup F_{k}}$ . El resto de la prueba consiste en una verificación que F es recurrentemente enumerable y es el punto menos fijo de Ё. La secuencia F_k utilizado en esta prueba corresponde a la cadena Kleene en la prueba del teorema de punto fijo Kleene.

La segunda parte del primer teorema de recursión 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 hay alguna k tal que F_k no es la gráfica 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 solo cuando se satisfacen hipótesis más limitadas. 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 recurrencia es que se garantiza que los puntos fijos obtenidos por el primer teorema de recurrencia son puntos fijos mínimos, mientras que los obtenidos del segundo teorema de recurrencia pueden no ser puntos fijos mínimos.

Una segunda diferencia es que el primer teorema de recursión solo se aplica a los 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 orden del punto fijo de Kleene. 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 la numeración, Ershov demostró que el teorema de recursión de Kleene se cumple 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 recursión de Kleene como un caso especial.

Dado un número precompleto $nu$ , entonces para cualquier función computable parcial $f$ con dos parámetros existe una función computable total $t$ con un parámetro tal que

forall nin mathbb {N}:nu circ f(n,t(n))=nu circ t(n).

Contenido relacionado

Más resultados...