Computación en el límite

Límite de una secuencia de funciones computable uniformemente

En teoría de computabilidad , una función se denomina 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 , recursivo en el límite y recursivamente aproximable . Se puede pensar en las funciones límite computables como aquellas que admiten un procedimiento de conjetura computable eventualmente correcto en su valor verdadero. Un conjunto es límite computable solo cuando su función característica es límite computable.

Si la secuencia es uniformemente computable en relación con D , entonces la función es límite computable en D.

Definición formal

Una función total es computable al límite 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 límite computable 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 solo si su función característica es computable en el límite. Por el contrario, el conjunto es computable si y solo si es computable en el límite por 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 el límite si y solo 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 en el límite si y solo si es computable a partir de . Además, el lema del límite (y su relativización) se cumplen de manera uniforme. Por lo tanto, se puede pasar de un índice para la función a un índice para relativo a . También se puede pasar de un índice para relativo a a un índice para algún que tenga 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 [computablemente enumerable], debe ser computable en el límite mismo ya que la función computable puede definirse ${\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 a medida que tiende al infinito es la función característica de . ${\displaystyle r(x)}$ ${\displaystyle s}$ ${\displaystyle 0'}$

Por lo tanto, basta con mostrar que si la computabilidad límite se conserva mediante la reducción de Turing , ya que esto mostrará que todos los conjuntos computables a partir de son computables límite. Fije conjuntos que se identifican con sus funciones características y una función computable con límite . Suponga que para alguna reducción de Turing y defina una función computable como sigue ${\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 considera los primeros bits de . Ahora elijamos tal que para todos los . Si entonces el cálculo converge en como máximo pasos a . Por lo tanto tiene un límite de , por lo que es límite 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 simplemente los conjuntos computables a partir del teorema de Post , el lema del 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ó en 1954 un resultado temprano que prefiguraba la equivalencia de la computabilidad límite con la -idad , 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)}$

Extensión

La iteración de la computabilidad de límites se puede utilizar para ascender en la jerarquía aritmética. Es decir, una función -aria es si y solo si se puede escribir en la forma de alguna función recursiva -aria \(g\), bajo el supuesto de que existen todos los límites. ^[2] ${\displaystyle m}$ ${\displaystyle f(x_{1},\ldots ,x_{m})}$ ${\displaystyle \Delta _{k+1}^{0}}$ ${\displaystyle \lim _{n_{k}}\lim _{n_{k-1}}\ldots \lim _{n_{1}}g(x_{1},\ldots ,x_{m},n_{k},\ldots ,n_{1})}$ ${\displaystyle m+k}$

Limitar los números reales computables

Un número real x es computable en el límite si existe 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 solo si existe una secuencia de números racionales que converge a él y que tiene un módulo de convergencia computable . ${\displaystyle r_{i}}$

Cuando un número real se considera 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 solo si hay una función computable total que toma valores en el conjunto tales que para cada i existe el límite y es igual a . Por lo tanto, para cada i , a medida que t aumenta, el valor de finalmente se vuelve constante y es igual a . Al igual que con el caso de los números reales computables, no es posible moverse efectivamente entre las dos representaciones de los 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

• Lo real cuya expansión binaria codifica el problema de detención es computable en el límite pero no computable.
• Lo 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 del límite para la teoría de la α-recursión a través de funciones en la jerarquía -aritmética, que es una jerarquía definida en relación con algún ordinal admisible . ^[3] ${\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 . Las 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 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 y ambos no están definidos, o ambos están definidos y son iguales. ${\displaystyle f(x)}$ ${\displaystyle g(x)}$

Véase también

• Secuencia de Specker

Referencias

1. A. Mostowski, "Ejemplos de conjuntos definibles mediante dos y tres cuantificadores". Fundamenta Mathematicae vol. 42, núm. 2, pp.259--270 (1955)
2. G. Criscuolo, E. Minicozzi, G. Trautteur, "Limitar la recursividad y la jerarquía aritmética". Revue française d'automatique informatique recherche opérationnelle, Informatique théorique, libro 9, núm. R3 (1975), págs.5-12. Editorial Dunod-Gauthier-Villars.
3. SG Simpson, "Teoría de grados sobre ordinales admisibles", pp.170--171. Publicado en J. Fenstad, P. Hinman, Generalized Recursion Theory: Proceedings of the 1972 Oslo Symposium (1974), ISBN  0-7204-22760 .

1. J. Schmidhuber , "Jerarquías de complejidades de Kolmogorov generalizadas y medidas universales no numerables computables en el límite", International Journal of Foundations of Computer Science , 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 saltos de Turing y límites . Log. Methods Comput. Sci. , 2018, doi :10.23638/LMCS-14(3:13)2018.