Cálculo en el límite

El límite de una secuencia de funciones uniformemente computable.

En teoría de la computabilidad , una función se llama límite computable si es el límite de una secuencia de funciones uniformemente computable. También se utilizan los términos computable en el límite , límite recursivo y recursivamente aproximable . Se puede pensar en las funciones computables límite como aquellas que admiten un procedimiento de estimación computable eventualmente correcto en su valor verdadero. Un conjunto es computable en límites sólo cuando su función característica es computable en límites.

Si la secuencia es uniformemente computable en relación con D , entonces la función es computable de forma limitada en D .

Definicion formal

Una función total es computable con límites si existe una función total computable tal que ${\displaystyle r(x)}$ ${\displaystyle {\hat {r}}(x,s)}$

${\displaystyle \displaystyle r(x)=\lim _{s\to \infty }{\hat {r}}(x,s)}$

La función total es computable hasta el límite en D si hay una función total computable en D que también satisface ${\displaystyle r(x)}$ ${\displaystyle {\hat {r}}(x,s)}$

${\displaystyle \displaystyle r(x)=\lim _{s\to \infty }{\hat {r}}(x,s)}$

Un conjunto de números naturales se define como computable en el límite si y sólo si su función característica es computable en el límite. Por el contrario, el conjunto es computable si y sólo si es computable en el límite mediante una función y hay una segunda función computable que toma la entrada i y devuelve un valor de t lo suficientemente grande como para que se haya estabilizado. ${\displaystyle \phi (t,i)}$ ${\displaystyle \phi (t,i)}$

Lema límite

El lema del límite establece que un conjunto de números naturales es computable en límites si y sólo si el conjunto es computable a partir de (el salto de Turing del conjunto vacío). El lema del límite relativizado establece que un conjunto es computable límite en si y sólo si es computable a partir de . Además, el lema del límite (y su relativización) se mantienen uniformemente. Por tanto, se puede pasar de un índice para la función a un índice relativo a . También se puede pasar de un índice relativo a a un índice para algunos que tienen límite . ${\displaystyle 0'}$ ${\displaystyle D}$ ${\displaystyle D'}$ ${\displaystyle {\hat {r}}(x,s)}$ ${\displaystyle {\hat {r}}(x)}$ ${\displaystyle 0'}$ ${\displaystyle {\hat {r}}(x)}$ ${\displaystyle 0'}$ ${\displaystyle {\hat {r}}(x,s)}$ ${\displaystyle {\hat {r}}(x)}$

Prueba

Como es un conjunto [computable enumerable], debe ser computable en el límite mismo ya que la función computable se puede definir ${\displaystyle 0'}$

${\displaystyle \displaystyle {\hat {r}}(x,s)={\begin{cases}1&{\text{if by stage }}s,x{\text{ has been enumerated into }}0'\\0&{\text{if not}}\end{cases}}}$

cuyo límite va al infinito es la función característica de . ${\displaystyle r(x)}$ ${\displaystyle s}$ ${\displaystyle 0'}$

Por lo tanto, es suficiente demostrar que si la computabilidad límite se preserva mediante la reducción de Turing , esto demostrará que todos los conjuntos computables son computables en el límite. Conjuntos fijos que se identifican con sus funciones características y una función computable con límite . Supongamos que para alguna reducción de Turing y defina una función computable de la siguiente manera ${\displaystyle 0'}$ ${\displaystyle X,Y}$ ${\displaystyle X_{s}}$ ${\displaystyle X}$ ${\displaystyle Y(z)=\phi ^{X}(z)}$ ${\displaystyle \phi }$ ${\displaystyle Y_{s}}$

${\displaystyle \displaystyle Y_{s}(z)={\begin{cases}\phi ^{X_{s}}(z)&{\text{if }}\phi ^{X_{s}}{\text{ converges in at most }}s{\text{ steps.}}\\0&{\text{otherwise }}\end{cases}}}$

Ahora supongamos que el cálculo converge en pasos y solo mira los primeros bits de . Ahora elige tal que para todos . Si entonces el cálculo converge como máximo en pasos a . Por lo tanto , tiene un límite de , por lo que el límite es computable. ${\displaystyle \phi ^{X}(z)}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle X}$ ${\displaystyle s'>s}$ ${\displaystyle z<s+1}$ ${\displaystyle X_{s'}(z)=X(z)}$ ${\displaystyle t>s'}$ ${\displaystyle \phi ^{X_{t}}(z)}$ ${\displaystyle s'<t}$ ${\displaystyle \phi ^{X}(z)}$ ${\displaystyle Y_{s}(z)}$ ${\displaystyle \phi ^{X}(z)=Y(z)}$ ${\displaystyle Y}$

Como los conjuntos son solo los conjuntos computables según el teorema de Post , el lema límite también implica que los conjuntos límite computables son los conjuntos. ${\displaystyle \Delta _{2}^{0}}$ ${\displaystyle 0'}$ ${\displaystyle \Delta _{2}^{0}}$

Mostowski anticipó un resultado temprano que presagiaba la equivalencia de computabilidad límite con -ness en 1954, utilizando una jerarquía y fórmulas , donde es una función obtenida a partir de una función recursiva primitiva arbitraria tal que es equivalente a . ^[1] ${\displaystyle \Delta _{2}^{0}}$ ${\displaystyle \mathbf {P} _{2}^{(1)}}$ ${\displaystyle \exists y(\lim _{x\to \infty }10^{-x}\gamma (x,y)<1)}$ ${\displaystyle \gamma (x,y)}$ ${\displaystyle \varrho }$ ${\displaystyle \exists p\forall s(\varrho (p,s,y)=0)}$ ${\displaystyle \exists x_{0}\forall x(x>x_{0}\implies \gamma (x,y)=0)}$

Limitar números reales computables

Un número real x es computable en el límite si hay una secuencia computable de números racionales (o, lo que es equivalente, números reales computables ) que converge a x . Por el contrario, un número real es computable si y sólo si existe una secuencia de números racionales que converge hacia él y que tiene un módulo de convergencia computable . ${\displaystyle r_{i}}$

Cuando un número real se ve como una secuencia de bits, se cumple la siguiente definición equivalente. Una secuencia infinita de dígitos binarios es computable en el límite si y sólo si hay una función computable total que toma valores en el conjunto tales que para cada i el límite existe y es igual a . Así, para cada i , a medida que t aumenta, el valor de eventualmente se vuelve constante e igual . Como ocurre con el caso de los números reales computables, no es posible moverse efectivamente entre las dos representaciones de reales computables límite. ${\displaystyle \omega }$ ${\displaystyle \phi (t,i)}$ ${\displaystyle \{0,1\}}$ ${\displaystyle \lim _{t\rightarrow \infty }\phi (t,i)}$ ${\displaystyle \omega (i)}$ ${\displaystyle \phi (t,i)}$ ${\displaystyle \omega (i)}$

Ejemplos

• El real cuya expansión binaria codifica el problema de detención es computable en el límite pero no computable.
• El real cuya expansión binaria codifica el conjunto de verdad de la aritmética de primer orden no es computable en el límite.
• La constante de Chaitin .

Extensión de la teoría de conjuntos

Existe una versión modificada del lema de límite para la teoría de la recursividad α mediante funciones en la jerarquía aritmética, que es una jerarquía definida en relación con algún ordinal admisible . ^[2] ${\displaystyle \alpha }$ ${\displaystyle \alpha }$

Para un ordinal admisible dado , defina la jerarquía aritmética: ${\displaystyle \alpha }$ ${\displaystyle \alpha }$

• Una relación es si es recursiva. ${\displaystyle R}$ ${\displaystyle \alpha }$ ${\displaystyle {\boldsymbol {\Sigma }}_{0}}$ ${\displaystyle \alpha }$
• ${\displaystyle R}$es si es la proyección de una relación. ${\displaystyle {\boldsymbol {\Sigma }}_{n+1}}$ ${\displaystyle {\boldsymbol {\Pi }}_{n}}$
• ${\displaystyle R}$es si su complemento es . ${\displaystyle {\boldsymbol {\Pi }}_{n}}$ ${\displaystyle {\boldsymbol {\Sigma }}_{n}}$

Sea una función parcial de a . Los siguientes son equivalentes: ${\displaystyle f}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$

• (La gráfica de) es . ${\displaystyle f}$ ${\displaystyle {\boldsymbol {\Sigma }}_{2}}$
• ${\displaystyle f}$es débilmente recursivo en el salto de usar índices de funciones computables. ${\displaystyle \alpha }$ ${\displaystyle {\boldsymbol {0}}^{\prime }}$ ${\displaystyle \alpha }$ ${\displaystyle \emptyset }$ ${\displaystyle \alpha }$
• Hay una función recursiva que se aproxima a tal que . ${\displaystyle \alpha }$ ${\displaystyle f':\alpha \times \alpha \to \alpha }$ ${\displaystyle f}$ ${\displaystyle f(\gamma )\simeq \lim _{\sigma \to \alpha }f'(\sigma ,\gamma )}$

${\displaystyle f\simeq g}$denota que ambos y son indefinidos, o ambos están definidos y son iguales. ${\displaystyle f(x)}$ ${\displaystyle g(x)}$

Ver también

• secuencia de espectros

Referencias

1. A. Mostowski, "Ejemplos de conjuntos definibles mediante dos y tres cuantificadores". Fundamentos Mathematicae vol. 42, edición. 2, págs. 259-270 (1955)
2. SG Simpson, "Teoría de los grados sobre ordinales admisibles", páginas 170-171. Aparecido en J. Fenstad, P. Hinman, Teoría de la recursión generalizada: Actas del Simposio de Oslo de 1972 (1974), ISBN  0-7204-22760 .

1. J. Schmidhuber , "Jerarquías de complejidades generalizadas de Kolmogorov y medidas universales no numerables computables en el límite", Revista Internacional de Fundamentos de Ciencias de la Computación , 2002, doi :10.1142/S0129054102001291.
2. R. Soare . Conjuntos y grados recursivamente enumerables . Springer-Verlag 1987.
3. V. Brattka. Una conexión de Galois entre los saltos y los límites de Turing . Registro. Métodos Computación. Ciencia. , 2018, doi :10.23638/LMCS-14(3:13)2018.