Stała Chaitina

„Numer Omega” przekierowuje tutaj. W przypadku innych zastosowań zobacz Omega (ujednoznacznienie) § Matematyka .

W poddziedzinie informatyki algorytmicznej teorii informacji stała Chaitina ( liczba Chaitin omega ) lub prawdopodobieństwo zatrzymania jest liczbą rzeczywistą , która, mówiąc nieoficjalnie, reprezentuje prawdopodobieństwo zatrzymania losowo skonstruowanego programu. Liczby te są utworzone na podstawie konstrukcji Gregory'ego Chaitina .

Chociaż istnieje nieskończenie wiele prawdopodobieństw zatrzymania, po jednym dla każdej metody kodowania programów, często używa się litery Ω w odniesieniu do nich tak, jakby istniał tylko jeden. Ponieważ Ω zależy od użytego kodowania programu, jest czasami nazywane konstrukcją Chaitina , gdy nie odnosi się do żadnego konkretnego kodowania.

Każde prawdopodobieństwo zatrzymania jest normalną i transcendentalną liczbą rzeczywistą, której nie można obliczyć , co oznacza, że ​​nie ma algorytmu obliczania jej cyfr. Każde prawdopodobieństwo zatrzymania jest losowe Martina-Löfa , co oznacza, że ​​nie ma nawet żadnego algorytmu, który mógłby wiarygodnie odgadnąć jego cyfry.

Tło

Definicja prawdopodobieństwa zatrzymania opiera się na istnieniu uniwersalnej funkcji obliczalnej bez przedrostków. Taka funkcja, intuicyjnie, reprezentuje język programowania z tą właściwością, że nie można uzyskać prawidłowego programu jako właściwego rozszerzenia innego ważnego programu.

Załóżmy, że F jest funkcją częściową , która przyjmuje jeden argument, skończony ciąg binarny i prawdopodobnie zwraca pojedynczy ciąg binarny jako wynik. Funkcja F jest nazywana obliczalną, jeśli istnieje maszyna Turinga , która ją oblicza (w tym sensie, że dla dowolnych skończonych ciągów binarnych x i y F (x) = y wtedy i tylko wtedy, gdy maszyna Turinga zatrzymuje się z y na swojej taśmie, gdy podano wejściex ) .

   Funkcję F nazywamy uniwersalną, jeśli spełniona jest następująca właściwość: dla każdej obliczalnej funkcji f pojedynczej zmiennej istnieje łańcuch w taki, że dla wszystkich x F ( w x ) = f ( x ); tutaj w x reprezentuje konkatenację dwóch łańcuchów w i x . Oznacza to, że F można użyć do symulacji dowolnej obliczalnej funkcji jednej zmiennej. Nieformalnie w reprezentuje „skrypt” dla obliczalnej funkcji f , a F reprezentuje „interpreter”, który analizuje skrypt jako przedrostek jego danych wejściowych, a następnie wykonuje go na pozostałej części danych wejściowych.

Dziedzina F jest zbiorem wszystkich wejść p, na których jest zdefiniowana . W przypadku F , które są uniwersalne, takie p można ogólnie postrzegać zarówno jako konkatenację części programu i części danych, jak i jako pojedynczy program dla funkcji F .

Funkcję F nazywamy bezprzedrostkową, jeśli w jej dziedzinie nie ma dwóch elementów p , p′ takich, że p′ jest właściwym rozszerzeniem p . Można to przeformułować w następujący sposób: dziedzina F jest kodem bez przedrostków (kod chwilowy) na zbiorze skończonych łańcuchów binarnych. Prostym sposobem na wymuszenie braku prefiksów jest użycie maszyn, których środkiem wejściowym jest strumień binarny, z którego można odczytywać bity pojedynczo. Nie ma znacznika końca strumienia; koniec wejścia jest określany przez to, że maszyna uniwersalna zdecyduje się przestać czytać więcej bitów, a pozostałe bity nie są uważane za część akceptowanego ciągu. W tym miejscu wyraźna staje się różnica między dwoma pojęciami programu wspomnianymi w ostatnim akapicie; jeden jest łatwo rozpoznawalny przez jakąś gramatykę, podczas gdy drugi wymaga arbitralnych obliczeń do rozpoznania.

Dziedziną dowolnej uniwersalnej funkcji obliczalnej jest zbiór przeliczalny obliczeniowo , ale nigdy zbiór przeliczalny . Dziedzina jest zawsze równoważna problemowi zatrzymania w trybie Turinga .

Definicja

Niech P _F będzie dziedziną uniwersalnej funkcji obliczalnej bez przedrostków F . Stała Ω _F jest wtedy zdefiniowana jako

${\ Displaystyle \ Omega _ {F} = \ suma _ {p \ w P_ {F}} 2 ^ {- | p |}}$ ,

gdzie ${\ Displaystyle \ lewo | p \ prawo |}$ oznacza długość łańcucha p . Jest to nieskończona suma , która ma jedną sumę dla każdego p w dziedzinie F . Wymóg, aby dziedzina była wolna od przedrostków, wraz z nierównością Krafta , gwarantuje, że suma ta zbiega się do liczby rzeczywistej z przedziału od 0 do 1. Jeśli F wynika jasno z kontekstu, to Ω _F można oznaczyć po prostu Ω, chociaż inny uniwersalny bez przedrostków funkcje obliczalne prowadzą do różnych wartości Ω.

Związek z problemem zatrzymania

Znając pierwsze N ​​bitów Ω, można obliczyć problem zatrzymania dla wszystkich programów o rozmiarze do N . Niech program p , dla którego ma zostać rozwiązany problem stopu, będzie miał długość N bitów. W jaskółczego ogona wszystkie programy o dowolnej długości są uruchamiane, dopóki nie zatrzyma się wystarczająco dużo, aby łącznie zapewnić wystarczające prawdopodobieństwo dopasowania tych pierwszych N bitów. Jeśli program p jeszcze się nie zatrzymał, to nigdy się nie zatrzyma, ponieważ jego udział w prawdopodobieństwie zatrzymania wpłynąłby na pierwsze N ​​bitów. W ten sposób problem zatrzymania zostałby rozwiązany dla p .

Ponieważ wiele wybitnych problemów w teorii liczb, takich jak hipoteza Goldbacha , jest równoważnych rozwiązaniu problemu stopu dla specjalnych programów (które w zasadzie szukałyby kontrprzykładów i zatrzymywałyby się, gdyby jeden został znaleziony), znajomość wystarczającej liczby bitów stałej Chaitina oznaczałaby również znajomość odpowiedź na te problemy. Ale ponieważ problem zatrzymania nie jest generalnie rozwiązywalny, a zatem obliczenie jakiejkolwiek stałej Chaitina poza kilkoma pierwszymi bitami nie jest możliwe, to po prostu redukuje trudne problemy do niemożliwych, podobnie jak próba zbudowania maszyny wyroczni dla problemu zatrzymania .

Interpretacja jako prawdopodobieństwo

Przestrzeń Cantora to zbiór wszystkich nieskończonych ciągów zer i jedynek. Prawdopodobieństwo zatrzymania można interpretować jako miarę pewnego podzbioru przestrzeni Cantora zgodnie ze zwykłą miarą prawdopodobieństwa w przestrzeni Cantora. To właśnie od tej interpretacji prawdopodobieństwa zatrzymania biorą swoją nazwę.

Miara prawdopodobieństwa w przestrzeni Cantora, czasami nazywana miarą uczciwej monety, jest zdefiniowana w taki sposób, że dla dowolnego ciągu binarnego x zbiór sekwencji rozpoczynających się od x ma miarę 2 ^{−| x |} . Oznacza to, że dla każdej liczby naturalnej n zbiór ciągów f w przestrzeni Cantora taki, że f ( n ) = 1 ma miarę 1/2, a zbiór ciągów, których n -tym elementem jest 0, również ma miarę 1/2.

Niech F będzie uniwersalną obliczalną funkcją bez przedrostków. Dziedzina P z F składa się z nieskończonego zestawu ciągów binarnych

${\ Displaystyle P = \ {p_ {1}, p_ {2}, \ ldots \}}$ .

Każdy z tych ciągów pi _określa podzbiór Si przestrzeni Cantora _; zbiór S _i zawiera wszystkie ciągi w przestrzeni kantora, które zaczynają się _na pi . Te zbiory są rozłączne, ponieważ P jest zbiorem bez przedrostków. Suma

${\ Displaystyle \ suma _ {p \ w P} 2 ^ {- | p |}}$

reprezentuje miarę zbioru

${\ Displaystyle \ bigcup _ {i \ w \ mathbb {N}} S_ {i}}$ .

W ten sposób Ω _F reprezentuje prawdopodobieństwo, że losowo wybrana nieskończona sekwencja zer i jedynek zaczyna się od ciągu bitów (o pewnej skończonej długości), który należy do domeny F . Z tego powodu Ω _F nazywa się prawdopodobieństwem zatrzymania.

Nieruchomości

Każda stała Chaitina Ω ma następujące właściwości:

• Jest algorytmicznie losowy (znany również jako losowy Martin-Löf lub 1-losowy). Oznacza to, że najkrótszy program wysyłający pierwsze n bitów Ω musi mieć rozmiar co najmniej n − O(1). Dzieje się tak, ponieważ, podobnie jak w przykładzie Goldbacha, te n bitów pozwala nam dowiedzieć się dokładnie, które programy zatrzymują się spośród wszystkich programów o długości co najwyżej n .
• W konsekwencji jest to liczba normalna , co oznacza, że ​​jej cyfry są równo rozłożone, jakby powstały w wyniku rzutu uczciwą monetą.
• To nie jest liczba obliczalna ; nie ma obliczalnej funkcji, która wyliczałaby jej rozwinięcie binarne, jak omówiono poniżej.
• Zbiór liczb wymiernych q takich, że q < Ω jest przeliczalny ; liczba rzeczywista z taką właściwością nazywana jest w teorii rekurencji liczbą rzeczywistą lewostronną .
• Zbiór liczb wymiernych q takich, że q > Ω nie jest przeliczalny. (Powód: każda liczba rzeczywista lewostronna o tej właściwości jest obliczalna, a Ω nie.)
• Ω jest liczbą arytmetyczną .
• Jest to odpowiednik Turinga problemu zatrzymania $,$ a zatem na arytmetycznej .

Nie każdy zbiór, który jest równoważny Turingowi z problemem zatrzymania, jest prawdopodobieństwem zatrzymania. Dokładniejsza relacja równoważności, równoważność Solovaya , może być użyta do scharakteryzowania prawdopodobieństw zatrzymania wśród lewych liczb rzeczywistych. Można pokazać, że liczba rzeczywista w [0,1] jest stałą Chaitina (tj. prawdopodobieństwem zatrzymania pewnej uniwersalnej funkcji obliczalnej bez przedrostków) wtedy i tylko wtedy, gdy jest lewostronna i algorytmicznie losowa. Ω należy do nielicznych definiowalnych algorytmicznie liczb losowych i jest najbardziej znaną algorytmicznie losową liczbą, ale wcale nie jest typowa dla wszystkich algorytmicznie losowych liczb.

Nieobliczalność

Liczbę rzeczywistą nazywamy obliczalną, jeśli istnieje algorytm, który przy danym n zwraca pierwszych n cyfr liczby. Jest to równoważne z istnieniem programu, który wylicza cyfry liczby rzeczywistej.

Żadne prawdopodobieństwo zatrzymania nie jest obliczalne. Dowód tego faktu opiera się na algorytmie, który mając dane n pierwszych cyfr Ω, rozwiązuje problem zatrzymania Turinga dla programów o długości do n . Ponieważ problem zatrzymania jest nierozstrzygalny , nie można obliczyć Ω.

Algorytm przebiega w następujący sposób. Biorąc pod uwagę pierwsze n cyfr Ω i a k ​​≤ n , algorytm wylicza dziedzinę F do momentu znalezienia wystarczającej liczby elementów dziedziny, tak aby prawdopodobieństwo, które reprezentują, mieściło się w granicach 2 ^{− ( k +1)} Ω. Po tym punkcie żaden dodatkowy program o długości k nie może znajdować się w dziedzinie, ponieważ każdy z nich dodałby 2 ^{− k} do miary, co jest niemożliwe. Zatem zbiór ciągów o długości k w dziedzinie jest dokładnie zbiorem takich ciągów już wyliczonych.

Losowość algorytmiczna

Liczba rzeczywista jest losowa, jeśli ciąg binarny reprezentujący liczbę rzeczywistą jest ciągiem losowym algorytmicznie . Calude, Hertling, Khoussainov i Wang wykazali, że rekurencyjnie przeliczalna liczba rzeczywista jest algorytmicznie losową sekwencją wtedy i tylko wtedy, gdy jest liczbą Ω Chaitina.

Twierdzenie o niezupełności dla prawdopodobieństw zatrzymania

Główny artykuł: Twierdzenie Chaitina o niezupełności

Dla każdego konkretnego spójnego skutecznie reprezentowanego systemu aksjomatycznego dla liczb naturalnych , takiego jak arytmetyka Peano , istnieje stała N taka, że ​​żaden bit Ω po N -tym nie może być udowodniony jako 1 lub 0 w tym systemie. Stała N zależy od tego, jak system formalny jest skutecznie reprezentowany, a zatem nie odzwierciedla bezpośrednio złożoności systemu aksjomatycznego. Ten wynik niezupełności jest podobny do twierdzenia Gödla o niezupełności , ponieważ pokazuje, że żadna spójna formalna teoria arytmetyki nie może być kompletna.

Super Omegi

Jak wspomniano powyżej, pierwsze n bitów stałej Ω Gregory'ego Chaitina jest losowych lub nieskompresowalnych w tym sensie, że nie możemy ich obliczyć za pomocą algorytmu zatrzymującego zawierającego mniej niż nO(1) bitów. Rozważmy jednak krótki, ale nigdy nie zatrzymujący się algorytm, który systematycznie wyświetla listę i uruchamia wszystkie możliwe programy; za każdym razem, gdy jeden z nich zatrzymuje się, jego prawdopodobieństwo jest dodawane do wyjścia (inicjowane przez zero). Po skończonym czasie pierwsze n bitów wyjścia już nigdy się nie zmieni (nie ma znaczenia, że ​​sam ten czas nie jest obliczany przez program zatrzymujący). Istnieje więc krótki, nieprzerwany algorytm, którego wyjście jest zbieżne (po skończonym czasie) na pierwszych n bitach Ω. Innymi słowy, wyliczalne pierwsze n bitów Ω jest wysoce ściśliwe w tym sensie, że można je obliczyć za pomocą bardzo krótkiego algorytmu; nie są losowe w odniesieniu do zbioru algorytmów wyliczających. Jürgen Schmidhuber (2000) skonstruował „Super Ω” z obliczeniem granicznym, który w pewnym sensie jest znacznie bardziej losowy niż oryginalny Ω z obliczeniem granicznym, ponieważ nie można znacząco skompresować Super Ω żadnym algorytmem wyliczającym, który nie zatrzymuje się.

Dla alternatywnego „Super Ω”, prawdopodobieństwo uniwersalności uniwersalnej maszyny Turinga (UTM) bez przedrostków - mianowicie prawdopodobieństwo, że pozostanie ona uniwersalna, nawet jeśli każde jej wejście (jako ciąg binarny ) jest poprzedzone losowym ciągiem binarnym - może być postrzegane jako $.$ braku zatrzymania maszyny z wyrocznią trzeciej iteracji problemu ( tj przy użyciu Turinga Jump .

Zobacz też

• Twierdzenie o niezupełności
• Złożoność Kołmogorowa

Prace cytowane

•   Calude, Cristian S. (2002). Informacje i losowość: perspektywa algorytmiczna (wyd. Drugie). Skoczek. ISBN 3-540-43466-6 .
• Calude, Cristian S.; Dinneen, Michael J.; Shu, Chi-Kou (2001). Obliczanie przebłysku losowości (PDF) . arXiv : nlin/0112022 . Bibcode : 2001nlin.....12022C . Zarchiwizowane (PDF) od oryginału w dniu 5 grudnia 2004 r.
• Downey, R.; Hirschfeldt, D. (2010). Losowość i złożoność algorytmiczna . Springer-Verlag.
• Li, Ming; Vitanyi, Paul (1997). Wprowadzenie do złożoności Kołmogorowa i jej zastosowań . Skoczek. Rozdział wprowadzający pełny tekst .
• Schmidhuber, Jürgen (2002). „Hierarchie uogólnionych złożoności Kołmogorowa i niezliczone uniwersalne miary obliczalne w granicy”. Międzynarodowy Dziennik Podstaw Informatyki . 13 (4): 587–612. doi : 10.1142/S0129054102001291 . Preprint: Algorytmiczne teorie wszystkiego (arXiv: quant-ph/ 0011122)

Linki zewnętrzne

• Aspects of Chaitin's Omega Survey artykuł omawiający ostatnie postępy w badaniach Omega Chaitina.
• Omega i dlaczego matematyka nie ma artykułu TOEs opartego na artykule Gregory'ego Chaitina , który ukazał się w sierpniowym wydaniu Mathematics Today z 2004 roku, z okazji 50. rocznicy śmierci Alana Turinga.
• Granice rozumu , Gregory Chaitin, pierwotnie ukazała się w Scientific American, marzec 2006.
• Obliczalna granica Super Omega bardziej losowa niż Omega i uogólnienia informacji algorytmicznych autorstwa Jürgena Schmidhubera