Computação no limite

Na teoria da computabilidade, uma função é chamada limite computável se é o limite de uma seqüência uniforme de funções computáveis. Os termos computáveis no limite e limite recursiva são também utilizados. Pode-se pensar que as funções computáveis como limite aqueles admitindo-se um processo de adivinhação, eventualmente, correto computável no seu verdadeiro valor. Um conjunto é limite computável apenas quando a sua função característica é o limite computável.

Se a seqüência é relativo uniforme computável para D, então a função é computável limite em D.

Definição formal

A função total função $r(x)$ é o limite computável se existe uma função total computável ${\hat {r}}(x,s)$ de tal modo que $\displaystyle {\hat {r}}=\lim _{s\to \infty }{\hat {r}}(x,s)$ .

A função de função total $r(x)$ é limite computável em D se existe uma função função total ${\hat {r}}(x,s)$ computável em D também satisfaz $\displaystyle {\hat {r}}=\lim _{s\to \infty }{\hat {r}}(x,s)$ .

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

Lema

Os estados limites lema de que um conjunto de números naturais é limite computável se e somente se o conjunto é computável de $0'$ . Os estados limites relativizados lema de que um conjunto é limitar computável em $D$ se e somente se é computável de $D'$ .

Note-se que o lema limite (e sua relativização) manter uniformemente. Assim, pode-se ir de um índice para a função ${\hat {r}}(x,s)$ de um índice para ${\hat {r}}(x)$ relativa à $0'$ . Pode-se também ir de um índice para ${\hat {r}}(x)$ relativa à $0'$ para um índice para alguns ${\hat {r}}(x,s)$ que tem limite ${\hat {r}}(x)$ .

Prova

Como $0'$ é um conjunto computavelmente enumerável, ele deve ser computável no próprio limite como a função computável pode ser definida $\displaystyle {\hat {r}}(x,s)={\begin{cases}1&{\text{se sequencialmente }}s,x{\text{ tem sido enumerável}}0'\\0&{\text{se não}}\end{cases}}$

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

É, portanto, suficiente para mostrar que se a computabilidade limite é preservada pela redução de Turing. Conjuntos Fix $X,Y$ que são identificados com as suas funções característicos e uma função computável $X_{s}$ com limite $X$ . Suponha-se que para alguma redução Turing e definir uma função computável como segue: $\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 $\phi ^{X}(z)$ converge em $s$ passos e só olha para os primeiros $s$ bits de $X$ . Agora escolha $s'>s$ de tal modo que para todos $z<s+1$ $X_{s'}(z)=X(z)$ . Se $t>s'$ em seguida o cálculo $\phi ^{X_{t}}(z)$ converge em, no máximo $s'<t$ passos para $\phi ^{X}(z)$ . Por isso $Y_{s}(z)$ tem um limite de $\phi ^{X}(z)=Y(z)$ , então $Y$ é limite computável.

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

Limite computável números reais

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

Quando um número real é visto como uma sequência de bits, a seguinte definição equivalente porões. Uma seqüência infinita $\omega$ de dígitos binários é computável no limite se e somente se existe uma função total computável $\phi (t,i)$ tendo valores no conjunto $\{0,1\}$ de tal modo que para cada i limite do $\lim _{t\rightarrow \infty }\phi (t,i)$ existe e é igual $\omega (i)$ . Assim, para cada i, tal como t aumenta o valor do $\phi (t,i)$ eventualmente torna-se constante e igual a $\omega (i)$ . Tal como acontece com o caso de computáveis números reais, não é possível de forma eficaz mover-se entre as duas representações de reais limite computáveis.

Exemplos

real cujo binário expansão codifica o problema da parada é computável no limite, mas não computável.
real cujo binário expansão codifica o conjunto verdade de primeira ordem aritmética não é computável no limite.

Referências

J. Schmidhuber, "Hierarquias de complexidades generalizadas Kolmogorov e nonenumerable medidas universais computáveis no limite", Revista Internacional de Fundamentos da Ciência da Computação, 2002.
R. Soare. Conjuntos recursivamente enumeráveis e graus. Springer-Verlag 1987.