Obliczenia w granicy

W teorii obliczalności funkcja nazywana jest granicą obliczalną , jeśli jest granicą jednostajnie obliczalnego ciągu funkcji. Stosowane są również terminy obliczalne w limicie , limit rekurencyjnie i rekurencyjnie aproksymowalne . O funkcjach granicznych obliczalnych można myśleć jako o tych, które dopuszczają ostatecznie poprawną obliczalną procedurę zgadywania przy ich prawdziwej wartości. Zbiór jest obliczalny granicznie tylko wtedy, gdy jego funkcja charakterystyczna jest obliczalna granicznie.

Jeśli sekwencja jest jednostajnie obliczalna względem D , to funkcja jest obliczalna na granicy w D .

Definicja formalna

Całkowita funkcja jest obliczalna na granicy ${\ Displaystyle {\ kapelusz {r}} (x, s$ jeśli istnieje całkowita obliczalna funkcja $r$ że

${\ Displaystyle \ Displaystyle r (x) = \ lim _ {s \ do \ infty} {\ kapelusz {r}} (x, s)}$

Całkowita funkcja jest obliczalna w $r$${\ Displaystyle {\ hat {r}} (x$ istnieje funkcja całkowita , ) w D również zadowalające

${\ Displaystyle \ Displaystyle r (x) = \ lim _ {s \ do \ infty} {\ kapelusz {r}} (x, s)}$

Zbiór liczb naturalnych jest zdefiniowany jako obliczalny w granicy wtedy i tylko wtedy, gdy jego funkcja charakterystyczna jest obliczalna w granicy. W przeciwieństwie $i$ tego, zbiór jest obliczalny wtedy i tylko wtedy, gdy jest obliczalny w granicy przez funkcję istnieje druga obliczalna funkcja, i zwraca wartość t na $_$ że

Lemat graniczny

Lemat graniczny stwierdza $,$ że ​​zbiór liczb naturalnych jest obliczalny granicznie wtedy i tylko wtedy, gdy zbiór jest obliczalny z ( skok Turinga pustego zbioru) Zrelatywizowany lemat graniczny stwierdza, że ​​​​zbiór jest obliczalny w granicy $displaystyle$ i tylko wtedy, gdy jest obliczalny z $D'}$ . Co więcej, lemat graniczny (i jego relatywizacja) są jednakowe. $}} (x)}$$)$ funkcji do indeksu dla $\ Displaystyle {\ hat {$ w stosunku do ${\ Displaystyle 0'}$ . Można również $displaystyle {\ kapelusz {r}} (x, s)}$$od$$względnego$$dla$ do dla , który ma limit ${\ Displaystyle {\ kapelusz {r}} (x)}$ .

Dowód

Ponieważ jest zbiorem [przeliczalnym $]$ , musi być obliczalny w samej granicy, ponieważ można zdefiniować funkcję

${\ Displaystyle \ Displaystyle {\ kapelusz {r}} (x, s) = {\ rozpocząć {przypadki} 1 i {\ text{if by stage }}s,x{\text{ został wyliczony do }}0'\\0&{\text{if not}}\end{cases}}}$

$nieskończoności,$ granica , gdy dąży do funkcją $0'$$\$ }

Dlatego wystarczy pokazać, że jeśli obliczalność granic jest zachowana przez $redukcję$ , ponieważ pokaże to, że wszystkie zbiory obliczalne z są obliczalne na granicy. ${$ poprawek , które są utożsamiane z ich charakterystycznymi funkcjami i funkcją obliczalną z granicą $X_ {s$$}$ . Załóżmy, że dla pewnej redukcji Turinga i zdefiniuj funkcję obliczalną $(z) = \ phi ^ {X} ($$\ Displaystyle$$} styl wyświetlania Y_{s}}$ w następujący sposób

${\ Displaystyle \ Displaystyle Y_ {s} (z) = {\ rozpocząć {przypadki} \ phi ^ {X_ {s}} (z) & {\ tekst {jeśli}} \ phi ^ {X_ {s}}}} \text{ zbiega się w co najwyżej }}s{\text{ krokach.}}\\0&{\text{inaczej }}\end{przypadków}}}$

teraz , że obliczenie zbiega się w krokach i patrzy $}$ na pierwsze $s$$\ displaystyle$$displaystyle$ . Teraz wybierz ${\ Displaystyle s'> s}$ tak, że dla wszystkich ${\ Displaystyle z <s + 1}$${\ Displaystyle X_ {s' }(z)=X(z)}$ . Jeśli $\ Displaystyle t> s'}$$„<t}$$,$ to obliczenia zbiegają co najwyżej $}} (z)}$ kroki do ${\ Displaystyle \ phi ^ {X} (z)}$ . Stąd ${\ Displaystyle Y_ {s} (z)}$ ma granicę ${\ Displaystyle \ phi ^ {X} (z) = Y (z)}$ , więc można $obliczyć$ .

Ponieważ $zbiory są$${\ Displaystyle \ Delta _ {2} ^ {0}}$ prostu zbiorami obliczalnymi twierdzenia Posta , lemat graniczny oznacza $,$ że obliczalne zbiory graniczne to zestawy.

Ogranicz obliczalne liczby rzeczywiste

Liczba rzeczywista x jest obliczalna w granicy , jeśli istnieje obliczalna sekwencja $liczb$ ( lub, co jest równoważne, obliczalnych rzeczywistych ) , która jest zbieżna do x . W przeciwieństwie do tego, liczba rzeczywista jest obliczalna wtedy i tylko wtedy, gdy istnieje ciąg liczb wymiernych, który jest do niej zbieżny i który ma obliczalny moduł zbieżności .

Kiedy liczba rzeczywista jest postrzegana jako sekwencja bitów, obowiązuje następująca równoważna definicja. Nieskończona sekwencja $}$$displaystyle \$ gdy istnieje całkowita obliczalna funkcja przyjmująca wartości w zbiorze ${\ Displaystyle \ {0,1 \}}$ takie, że dla każdego ja granica ${\ Displaystyle \ lim _ {t \ rightarrow \ infty} \ phi (t$ istnieje i jest równe ${\ Displaystyle \ omega (i)}$ . Tak więc dla każdego ja , gdy t wzrasta $ω$ wartość ostatecznie staje się stała i równa się $i$ . Podobnie jak w przypadku obliczalnych liczb rzeczywistych, nie jest możliwe efektywne poruszanie się między dwiema reprezentacjami granicznych liczb rzeczywistych.

Przykłady

• Liczba rzeczywista, której rozwinięcie binarne koduje problem zatrzymania, jest obliczalna w granicy, ale nieobliczalna.
• Liczba rzeczywista, której rozwinięcie binarne koduje zbiór prawdy arytmetyki pierwszego rzędu, nie jest obliczalna w granicy.
• Stała Chaitina .

Zobacz też

• Sekwencja Speckera

1. J. Schmidhuber , „Hierarchie uogólnionych złożoności Kołmogorowa i niezliczone uniwersalne miary obliczalne w granicy”, International Journal of Foundations of Computer Science , 2002, doi : 10.1142/S0129054102001291 .
2. R. Soare . Rekurencyjnie przeliczalne zbiory i stopnie . Springer-Verlag 1987.
3. W. Brattka. Połączenie Galois między skokami i ograniczeniami Turinga . Dziennik. Metody Oblicz. nauka , 2018, doi : 10.23638/LMCS-14(3:13)2018 .