Computação no limite

Predefinição:Sem notas 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 $\hat{r}=\underset{s\to \mathrm{\infty }}{\lim }\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 $\hat{r}=\underset{s\to \mathrm{\infty }}{\lim }\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 $\varphi (t,i)$ e existe uma segunda função computável que recebe a entrada i e retorna um valor de t suficientemente grande a $\varphi (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^{\prime }$. Os estados limites relativizados lema de que um conjunto é limitar computável em $D$ se e somente se é computável de $D^{\prime }$.

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^{\prime }$. Pode-se também ir de um índice para $\hat{r}(x)$ relativa à $0^{\prime }$ para um índice para alguns $\hat{r}(x,s)$ que tem limite $\hat{r}(x)$.

Prova

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

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

É, 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: $Y_s(z)=\{\begin{array}{cc}{\varphi }^{X_s}(z)& \text{if }{\varphi }^{X_s}\text{ converge em no máximo }s\text{ passos.}\\ 0& \text{caso contrário}\end{array}$

Agora, suponha que o cálculo ${\varphi }^X(z)$ converge em $s$ passos e só olha para os primeiros $s$ bits de $X$. Agora escolha $s^{\prime }>s$ de tal modo que para todos $z<s+1$ $X_{s^{\prime }}(z)=X(z)$. Se $t>s^{\prime }$ em seguida o cálculo ${\varphi }^{X_t}(z)$ converge em, no máximo $s^{\prime }<t$ passos para ${\varphi }^X(z)$. Por isso $Y_s(z)$ tem um limite de ${\varphi }^X(z)=Y(z)$, então $Y$ é limite computável.

À medida que o ${\mathrm{\Delta }}_2^0$ conjuntos são apenas os conjuntos computáveis ​​a partir de $0^{\prime }$ pelo teorema Post, o lema limite também implica que os conjuntos limite computáveis ​​são os ${\mathrm{\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 $\varphi (t,i)$ tendo valores no conjunto $\{0,1\}$ de tal modo que para cada i limite do $\underset{t\to \mathrm{\infty }}{\lim }\varphi (t,i)$ existe e é igual $\omega (i)$. Assim, para cada i, tal como t aumenta o valor do $\varphi (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

1. 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.
2. R. Soare. Conjuntos recursivamente enumeráveis ​​e graus. Springer-Verlag 1987.