Cálculo no limite - Computation in the limit

Na teoria da computabilidade , uma função é chamada de limite computável se for o limite de uma sequência de funções uniformemente computável. Os termos computáveis ​​no limite , limite recursivo e recursivamente aproximado também são usados. Pode-se pensar em funções computáveis ​​limitadas como aquelas que admitem um procedimento de adivinhação computável eventualmente correto em seu valor verdadeiro. Um conjunto é limite computável apenas quando sua função característica é limite computável.

Se a sequência é uniformemente calculável em relação ao D , então a função é calculável no limite D .

Definição formal

Uma função total é um limite computável se houver uma função total computável tal que ${\ displaystyle r (x)}$ ${\ displaystyle {\ hat {r}} (x, s)}$

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

A função total é o limite computável em D se houver uma função total computável em D que também satisfaça ${\ displaystyle r (x)}$${\ displaystyle {\ hat {r}} (x, s)}$

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

Um conjunto de números naturais é definido para ser computável no limite se e somente se sua função característica for computável no limite. Em contraste, o conjunto é computável se e somente se ele é computável no limite por uma função e há uma segunda função computável que recebe a entrada i e retorna um valor de t grande o suficiente para que tenha estabilizado. ${\ displaystyle \ phi (t, i)}$${\ displaystyle \ phi (t, i)}$

Lema do limite

O lema do limite afirma que um conjunto de números naturais é limite computável se e somente se o conjunto é computável (o salto de Turing do conjunto vazio). O lema do limite relativizado afirma que um conjunto é limite computável em se e somente se ele é computável a partir de . Além disso, o lema do limite (e sua relativização) se mantém uniformemente. Assim, pode-se ir de um índice para a função a um índice para relativo a . Também se pode ir de um índice para relativo a um índice para alguns que tem limite . ${\ 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)}$

Prova

Como é um conjunto [computavelmente enumerável], ele deve ser computável no próprio limite, pois a função computável pode ser definida ${\ displaystyle 0 '}$

${\ displaystyle \ displaystyle {\ hat {r}} (x, s) = {\ begin {cases} 1 & {\ text {if by stage}} s, x {\ text {foi enumerado em}} 0 '\ \ 0 & {\ text {if not}} \ end {cases}}}$

cujo limite quanto vai para o infinito é a função característica de . ${\ displaystyle r (x)}$${\ displaystyle s}$${\ displaystyle 0 '}$

Portanto, é suficiente mostrar que se a computabilidade de limite é preservada pela redução de Turing , pois isso mostrará que todos os conjuntos computáveis ​​de são computáveis ​​de limite. Conjuntos fixos que são identificados com suas funções características e uma função computável com limite . Suponha que para alguma redução de Turing e defina uma função computável como segue ${\ 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 {converge em no máximo}} s {\ text {passos.}} \\ 0 & {\ text {caso contrário}} \ end {cases}}}$

Agora, suponha que o cálculo converta em etapas e olhe apenas para os primeiros bits de . Agora escolha isso para todos . Se, então, o cálculo converge em no máximo etapas para . Portanto, tem um limite de , então o limite é computável. ${\ 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}$

À medida que os conjuntos são apenas os conjuntos computável de pelo teorema de pós , o lema limite também implica que o limite conjuntos computáveis são os conjuntos. ${\ displaystyle \ Delta _ {2} ^ {0}}$${\ displaystyle 0 '}$${\ displaystyle \ Delta _ {2} ^ {0}}$

Limitar números reais computáveis

Um número real x é computável no limite se houver uma sequência computável de números racionais (ou, o que é equivalente, números reais computáveis ) que converge para x . Em contraste, um número real é computável se e somente se houver uma seqüência de números racionais que converge para ele e que tem um módulo de convergência computável . ${\ displaystyle r_ {i}}$

Quando um número real é visto como uma sequência de bits, a seguinte definição equivalente é válida. Uma seqüência infinita de dígitos binários é computável no limite se e somente se houver uma função computável total tomando valores no conjunto tais que para cada i o limite existe e é igual . Assim, para cada i , à medida que t aumenta, o valor de eventualmente torna-se constante e igual . Tal como acontece com os números reais computáveis, não é possível mover-se efetivamente entre as duas representações de reais computáveis ​​limite. ${\ 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)}$

Exemplos

• O real cuja expansão binária codifica o problema da parada é computável no limite, mas não computável.
• O real cuja expansão binária codifica o conjunto verdade da aritmética de primeira ordem não é computável no limite.
• Constante de Chaitin .

Veja também

• Sequência Specker

Referências

1. J. Schmidhuber, "Hierarquias de complexidades de Kolmogorov generalizadas e medidas universais inumeráveis ​​computáveis ​​no limite", International Journal of Foundations of Computer Science , 2002.
2. R. Soare. Conjuntos e graus recursivamente enumeráveis . Springer-Verlag 1987.