Hispanopedia Wiki
Articulo de referencia

Cálculo en el límite

En la teoría de la computabilidad , una función se denomina computable por límite si es el límite de una secuencia uniformemente computable de funciones. También se utilizan los...

Hispanopedia WikiContenido en espanolLectura gratuita

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

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

Definición formal

Una función totalr(incógnita){\displaystyle r(x)}es computable límite si hay una función computable totalr^(incógnita,s){\displaystyle {\hat {r}}(x,s)}de tal manera que

r(incógnita)=límites→∞r^(incógnita,s){\displaystyle \displaystyle r(x)=\lim _{s\to \infty }{\hat {r}}(x,s)}

La función totalr(incógnita){\displaystyle r(x)}¿Es computable el límite en D si existe una función total?r^(incógnita,s){\displaystyle {\hat {r}}(x,s)}computable en D que también satisface

r(incógnita)=límites→∞r^(incógnita,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. En cambio, el conjunto es computable si y solo si es computable en el límite mediante una función.ϕ(t,i){\displaystyle \phi (t,i)}y hay una segunda función computable que toma la entrada i y devuelve un valor de t lo suficientemente grande como para queϕ(t,i){\displaystyle \phi (t,i)}se ha estabilizado.

Lema del límite

El lema del límite establece que un conjunto de números naturales es computable por límite si y solo si el conjunto es computable por límite.0′{\displaystyle 0'}(el salto de Turing del conjunto vacío ). El lema del límite relativizado establece que un conjunto es computable en el límite enD{\displaystyle D}si y solo si es computable a partir deD′{\displaystyle D'}. Además, el lema del límite (y su relativización) se cumplen uniformemente. Por lo tanto, se puede pasar de un índice para la funciónr^(incógnita,s){\displaystyle {\hat {r}}(x,s)}a un índice parar^(incógnita){\displaystyle {\hat {r}}(x)}relativo a0′{\displaystyle 0'}. También se puede ir desde un índice parar^(incógnita){\displaystyle {\hat {r}}(x)}relativo a0′{\displaystyle 0'}a un índice para algunosr^(incógnita,s){\displaystyle {\hat {r}}(x,s)}que tiene límiter^(incógnita){\displaystyle {\hat {r}}(x)}.

Prueba

Como0′{\displaystyle 0'}es un conjunto [computablemente enumerable], debe ser computable en el límite mismo ya que la función computable puede definirse

r^(incógnita,s)={1si por etapa s,incógnita ha sido enumerado en 0′0si no{\displaystyle \displaystyle {\hat {r}}(x,s)={\begin{cases}1&{\text{si en la etapa }}s,x{\text{ se ha enumerado en }}0'\\0&{\text{si no}}\end{cases}}}

cuyo límiter(incógnita){\displaystyle r(x)}comos{\displaystyle s}va al infinito es la función característica de0′{\displaystyle 0'}.

Por lo tanto, basta con demostrar que si la computabilidad límite se conserva mediante la reducción de Turing , ya que esto demostrará que todos los conjuntos computables desde0′{\displaystyle 0'}son computables de límite. Conjuntos fijosincógnita,Y{\displaystyle X,Y}que se identifican con sus funciones características y una función computableincógnitas{\displaystyle X_{s}}con límiteincógnita{\displaystyle X}. Supongamos queY(z)=ϕincógnita(z){\displaystyle Y(z)=\phi ^{X}(z)}para alguna reducción de Turingϕ{\displaystyle \phi }y definir una función computableYs{\displaystyle Y_{s}}como sigue

Ys(z)={ϕincógnitas(z)si ϕincógnitas converge en como máximo s pasos.0de lo contrario {\displaystyle \displaystyle Y_{s}(z)={\begin{cases}\phi ^{X_{s}}(z)&{\text{si }}\phi ^{X_{s}}{\text{ converge en como máximo }}s{\text{ pasos.}}\\0&{\text{en otro caso }}\end{cases}}}

Ahora supongamos que el cálculoϕincógnita(z){\displaystyle \phi ^{X}(z)}converge ens{\displaystyle s}pasos y solo mira el primeros{\displaystyle s}trozos deincógnita{\displaystyle X}Ahora elige.s′>s{\displaystyle s'>s}de tal manera que para todosz<s+1{\displaystyle z<s+1}incógnitas′(z)=incógnita(z){\displaystyle X_{s'}(z)=X(z)}. Sit>s′{\displaystyle t>s'}luego el cálculoϕincógnitat(z){\displaystyle \phi ^{X_ {t}}(z)}converge en como máximos′<t{\displaystyle s'<t}pasos paraϕincógnita(z){\displaystyle \phi ^{X}(z)}. Por esoYs(z){\displaystyle Y_{s}(z)}tiene un límite deϕincógnita(z)=Y(z){\displaystyle \phi ^{X}(z)=Y(z)}, entoncesY{\displaystyle Y}es límite computable.

Como elΔ20{\displaystyle \Delta _{2}^{0}}Los conjuntos son simplemente los conjuntos computables a partir de0′{\displaystyle 0'}Según el teorema de Post , el lema del límite también implica que los conjuntos computables de límite son losΔ20{\displaystyle \Delta _{2}^{0}}conjuntos.

Un resultado temprano que presagia la equivalencia de la computabilidad límite conΔ20{\displaystyle \Delta _{2}^{0}}Mostowski anticipó la -idad en 1954, utilizando una jerarquía.PAG2(1){\displaystyle \mathbf {P} _{2}^{(1)}}y fórmulas∃y(límiteincógnita→∞10−incógnitaγ(incógnita,y)<1){\displaystyle \exists y(\lim _{x\to \infty }10^{-x}\gamma (x,y)<1)}, dóndeγ(incógnita,y){\displaystyle \gamma (x,y)}es una función obtenida a partir de una función recursiva primitiva arbitrariaϱ{\displaystyle \varrho }de tal manera que∃pag∀s(ϱ(pag,s,y)=0){\displaystyle \exists p\forall s(\varrho (p,s,y)=0)}es equivalente a∃incógnita0∀incógnita(incógnita>incógnita0⟹γ(incógnita,y)=0){\displaystyle \exists x_{0}\forall x(x>x_{0}\implies \gamma (x,y)=0)}. [ 1 ]

Extensión

La iteración de la computabilidad límite se puede utilizar para ascender en la jerarquía aritmética . Es decir, unmetro{\displaystyle m}función -ariaF(incógnita1,…,incógnitametro){\displaystyle f(x_{1},\ldots ,x_{m})}esΔk+10{\displaystyle \Delta _ {k+1}^{0}}si se puede escribir en la formalímitenorteklímitenortek−1…límitenorte1gramo(incógnita1,…,incógnitametro,nortek,…,norte1){\displaystyle \lim _{n_{k}}\lim _{n_{k-1}}\ldots \lim _{n_{1}}g(x_{1},\ldots ,x_{m},n_{k},\ldots ,n_{1})}para algunosmetro+k{\displaystyle m+k}función recursiva -ariagramo{\displaystyle g}, bajo el supuesto de que existen todos los límites. [ 2 ]

Limitar los números reales computables

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

Cuando un número real se considera como una secuencia de bits, se cumple la siguiente definición equivalente. Una secuencia infinitaω{\displaystyle \omega }de dígitos binarios es computable en el límite si y solo si existe una función computable totalϕ(t,i){\displaystyle \phi (t,i)}tomando valores en el conjunto{0,1}{\displaystyle \{0,1\}}de tal manera que para cada i el límitelímitet→∞ϕ(t,i){\displaystyle \lim _{t\rightarrow \infty }\phi (t,i)}existe y es igual aω(i){\displaystyle \omega (i)}. Por lo tanto, para cada i , a medida que t aumenta el valor deϕ(t,i){\displaystyle \phi (t,i)}eventualmente se vuelve constante e igualω(i){\displaystyle \omega (i)}. Al igual que en el caso de los números reales computables, no es posible pasar eficazmente entre las dos representaciones de los números reales computables límite.

Ejemplos

extensión de la teoría de conjuntos

Existe una versión modificada del lema límite para la teoría de la α-recursión a través de funciones en elα{\displaystyle \alpha }-jerarquía aritmética, que es una jerarquía definida en relación con algún ordinal admisible.α{\displaystyle \alpha }. [ 3 ]

Para un ordinal admisible dadoα{\displaystyle \alpha }, definir elα{\displaystyle \alpha }-jerarquía aritmética:

  • Una relaciónR{\displaystyle R}enα{\displaystyle \alpha }esΣ0{\displaystyle {\boldsymbol {\Sigma }}_{0}}si esα{\displaystyle \alpha }-recursivo.
  • R{\displaystyle R}esΣnorte+1{\displaystyle {\boldsymbol {\Sigma }}_{n+1}}si es la proyección de unΠnorte{\displaystyle {\boldsymbol {\Pi }}_{n}}relación.
  • R{\displaystyle R}esΠnorte{\displaystyle {\boldsymbol {\Pi }}_{n}}si su complemento esΣnorte{\displaystyle {\boldsymbol {\Sigma }}_{n}}.

DejarF{\displaystyle f}ser una función parcial deα{\displaystyle \alpha }aα{\displaystyle \alpha }Los siguientes son equivalentes:

  • (El gráfico de)F{\displaystyle f}esΣ2{\displaystyle {\boldsymbol {\Sigma }}_{2}}.
  • F{\displaystyle f}es débilmenteα{\displaystyle \alpha }-recursivo en0′{\displaystyle {\boldsymbol {0}}^{\prime }}, elα{\displaystyle \alpha }-salto de∅{\displaystyle \emptyset }utilizando índices deα{\displaystyle \alpha }-funciones computables.
  • Hay unα{\displaystyle \alpha }-función recursivaF′:α×α→α{\displaystyle f':\alpha \times \alpha \to \alpha }aproximandoF{\displaystyle f}de tal manera queF(γ)≃límiteσ→αF′(σ,γ){\displaystyle f(\gamma )\simeq \lim _{\sigma \to \alpha }f'(\sigma ,\gamma )}.

F≃gramo{\displaystyle f\simeq g}indica que o bienF(incógnita){\displaystyle f(x)}ygramo(incógnita){\displaystyle g(x)}son ambas indefinidas, o son ambas definidas e iguales.

Véase también

Referencias

  1. ↑ A. Mostowski, " Ejemplos de conjuntos definibles mediante dos y tres cuantificadores ". Fundamenta Mathematicae, vol. 42, núm. 2, págs. 259-270 (1955)
  2. ↑ G. Criscuolo, E. Minicozzi, G. Trautteur, " Limitación de 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 del grado en ordinales admisibles", págs. 170-171. Aparece 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 de Kolmogorov generalizadas y medidas universales no enumerables 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 .
Lecturas relacionadas
6 articulos
Estilo de visualización: Pi _{1}^{1}}Teoría de la computabilidadLa teoría de la computabilidad , también conocida como teoría de la recursión , es una rama de la lógica matemática , la informática y la teoría de...Función indicadoraFunción indicadoraEn matemáticas , una función indicadora o función característica de un subconjunto de un conjunto es una función que asigna los elementos del subco...Función parcialFunción parcialEn matemáticas , una función parcial f de un conjunto X a un conjunto Y es una función de un subconjunto S de X (posiblemente el propio X ) a Y. El...{\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }Función computableLas funciones computables son los objetos básicos de estudio en la teoría de la computabilidad . Las funciones computables son el análogo formaliza...{\estilo de visualización \lambda}ComputabilidadLa computabilidad es la capacidad de resolver un problema de manera eficaz. Es un tema clave en el campo de la teoría de la computabilidad dentro d...Número naturalNúmero naturalLos números naturales se pueden utilizar para contar: una manzana; dos manzanas son una manzana sumada a otra manzana, tres manzanas son una manzan...