Stała Chaitina - Chaitin's constant

W informatyce podpola z algorytmicznej teorii informacji , o Chaitin stałej ( Chaitin liczba omega ) lub zatrzymanie prawdopodobieństwo jest liczba rzeczywista , że nieformalnie rzecz ujmując, oznacza prawdopodobieństwo , że losowo skonstruowany program zatrzymał. Liczby te powstały z konstrukcji stworzonej przez Gregory'ego Chaitina .

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

Każde prawdopodobieństwo zakończenia pracy jest normalną i transcendentalną liczbą rzeczywistą, która nie jest obliczalna , co oznacza, że ​​nie ma algorytmu obliczania jego 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 zakończenia pracy opiera się na istnieniu wolnej od przedrostków uniwersalnej funkcji obliczalnej. Taka funkcja, intuicyjnie, reprezentuje język programowania z tą właściwością, że żaden ważny program nie może być uzyskany jako właściwe rozszerzenie 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 zatrzyma się z y na swojej taśmie po podaniu wejście x ).

Funkcja F jest nazywana uniwersalną, jeśli zachodzi 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 ciągów w i x . Oznacza to, że F można użyć do symulacji dowolnej obliczalnej funkcji jednej zmiennej. Nieformalnie w reprezentuje „skrypt” dla funkcji obliczalnej f , a F reprezentuje „interpreter”, który analizuje skrypt jako prefiks swojego wejścia, a następnie wykonuje go na pozostałej części wejścia.

Domeny z F jest zbiorem wszystkich wejść p na którym 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 .

Funkcja F jest nazywana 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: domena F to kod bez prefiksów (kod chwilowy) na zbiorze skończonych ciągów binarnych. Prostym sposobem na wymuszenie braku prefiksów jest użycie maszyn, których środkiem wejściowym jest strumień binarny, z którego bity mogą być odczytywane pojedynczo. Nie ma znacznika końca strumienia; koniec wejścia jest określany przez to, kiedy uniwersalna maszyna zdecyduje się przestać czytać więcej bitów, a pozostałe bity nie są uważane za część akceptowanego ciągu. Tutaj różnica między dwoma pojęciami programu, o których mowa w ostatnim akapicie, staje się jasna; jeden jest łatwo rozpoznawalny przez jakąś gramatykę, podczas gdy drugi wymaga arbitralnych obliczeń do rozpoznania.

Dziedziną dowolnej uniwersalnej funkcji obliczalnej jest zbiór przeliczalny, ale nigdy zbiór obliczalny . Domena jest zawsze Turinga równowartość do problemu stopu .

Definicja

Niech P _F być domeną prefiks wolne uniwersalnego obliczeniowego funkcji F . Stała Ω _F jest wtedy zdefiniowana jako

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

gdzie oznacza długość łańcucha p . Jest to nieskończona suma, która ma jedną sumę na każde p w domenie F . Wymóg, aby domena była wolna od prefiksów, wraz z nierównością Krafta , zapewnia, że ​​suma ta zbiega się do liczby rzeczywistej od 0 do 1. Jeśli F jest jasne z kontekstu, wówczas Ω _F może być oznaczane po prostu Ω, chociaż różne uniwersalne bezprefiksowe funkcje obliczalne prowadzą do różnych wartości Ω. ${\ Displaystyle \ lewy | p \ prawy |}$

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 być rozwiązany problem zatrzymania, będzie miał długość N bitów. W sposób zazębiający się , wszystkie programy o wszystkich długościach są uruchamiane, dopóki nie zatrzyma się wystarczająco dużo, aby wspólnie wnieść wystarczające prawdopodobieństwo dopasowania tych pierwszych N bitów. Jeśli program p nie został jeszcze zatrzymany, 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 nierozstrzygniętych problemów w teorii liczb, takich jak hipoteza Goldbacha , jest równoważnych rozwiązaniu problemu zatrzymania dla specjalnych programów (które zasadniczo szukałyby kontrprzykładów i zatrzymują się, jeśli taki zostanie znaleziony), znajomość wystarczającej liczby bitów stałej Chaitina sugerowałaby również znajomość odpowiedź na te problemy. Ale ponieważ problem zatrzymania nie jest generalnie rozwiązywalny, a zatem obliczenie dowolnej części stałej Chaitina poza pierwszymi 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 zakończenia pracy można interpretować jako miarę pewnego podzbioru przestrzeni Cantora pod zwykłą miarą prawdopodobieństwa w przestrzeni Cantora. To właśnie z tej interpretacji biorą swoją nazwę prawdopodobieństwo zatrzymania.

Miara prawdopodobieństwa w przestrzeni Cantora, czasami nazywana miarą uczciwej monety, jest zdefiniowana tak, że dla dowolnego ciągu binarnego x zbiór ciągów zaczynają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- ty element ma wartość 0, również ma miarę 1/2.

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

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

Każdy z tych ciągów p _i określa podzbiór S _i przestrzeni Cantora; Zestaw S _i zawiera wszystkie sekwencje w przestrzeni cantor które zaczynają p _I . Zbiory te 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) znajdującego się w domenie 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 do wyprowadzenia pierwszych n bitów Ω musi mieć rozmiar co najmniej n -O(1). Dzieje się tak, ponieważ, tak jak w przykładzie Goldbacha, te n bitów pozwalają nam dokładnie określić, które programy zatrzymują się wśród wszystkich tych o długości co najwyżej n .
• W konsekwencji jest to normalna liczba , co oznacza, że ​​jej cyfry są rozmieszczone równomiernie, tak jakby zostały wygenerowane przez rzucenie uczciwą monetą.
• Nie jest to liczba obliczalna ; nie ma żadnej obliczalnej funkcji, która wylicza jej rozwinięcie binarne, jak omówiono poniżej.
• Zbiór liczb wymiernych q taki, że q < Ω jest przeliczalny ; liczba rzeczywista o takiej własności nazywana jest lewostronną liczbą rzeczywistą w teorii rekurencji .
• Zbiór liczb wymiernych q taki, że q > Ω nie jest przeliczalny. (Powód: każda lewa liczba rzeczywista z tą własnością jest obliczalna, a Ω nie.)
• Ω to liczba arytmetyczna .
• Jest równym Turingowi do problemu stopu i w ten sposób na poziomie w hierarchii arytmetycznej .${\ Displaystyle \ Delta _ {2} ^ {0}}$

Nie każdy zestaw, który jest odpowiednikiem Turinga z problemem zatrzymania, jest prawdopodobieństwem zatrzymania. Drobniejsze relacja równoważności, Solovay równoważność , mogą być używane do scharakteryzowania wstrzymaniem prawdopodobieństw wśród liczb rzeczywistych lewej CE. Można pokazać, że liczba rzeczywista w [0,1] jest stałą Chaitina (tj. prawdopodobieństwem zakończenia jakiejś uniwersalnej funkcji obliczalnej bez przedrostków) wtedy i tylko wtedy, gdy jest ona lewostronna i algorytmicznie losowa. Ω jest jedną z niewielu możliwych do zdefiniowania liczb algorytmicznie losowych i jest najlepiej znaną liczbą algorytmicznie losową, ale wcale nie jest typowa dla wszystkich liczb algorytmicznie losowych.

Nieobliczalność

Liczba rzeczywista nazywana jest obliczalną, jeśli istnieje algorytm, który przy danym n zwraca pierwszych n cyfr liczby. Jest to równoznaczne z istnieniem programu, który wylicza cyfry liczby rzeczywistej.

Nie można obliczyć żadnego prawdopodobieństwa zatrzymania. Dowód tego faktu opiera się na algorytmie, który, mając pierwsze n cyfr Ω, rozwiązuje problem zatrzymania Turinga dla programów o długości do n . Ponieważ problem zatrzymania jest nierozstrzygnięty , Ω 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, aż zostanie znaleziona wystarczająca liczba elementów tej dziedziny, tak aby prawdopodobieństwo, które reprezentują, mieściło się w granicach 2 ^{−( k +1)} od Ω. Po tym punkcie żaden dodatkowy program o długości k nie może być w dziedzinie, ponieważ każdy z nich ^dodałby do miary 2 ^{− k} , co jest niemożliwe. Zatem zbiór ciągów o długości k w domenie jest dokładnie zbiorem takich ciągów, które zostały już wyliczone.

Losowość algorytmiczna

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

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

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 skutecznie reprezentowany jest system formalny , a zatem nie odzwierciedla bezpośrednio złożoności systemu aksjomatycznego. Ten wynik niezupełności jest podobny do twierdzenia o niezupełności Gödla , ponieważ pokazuje, że żadna spójna formalna teoria arytmetyki nie może być kompletna.

Super Omega

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

Alternatywnego „Super Ohm”, z prawdopodobieństwem uniwersalności z przedrostkiem wolne Uniwersalna Maszyna Turinga (UTM) - mianowicie, prawdopodobieństwo, że pozostaje uniwersalny nawet kiedy każde wejście z nim (jako ciąg binarny ) jest poprzedzona przez losowy ciąg binarny – może być postrzegane jako prawdopodobieństwo braku zatrzymania maszyny z wyrocznią w trzeciej iteracji problemu zatrzymania (tj. przy użyciu notacji skoku Turinga ). ${\ Displaystyle O ^ {(3)}}$

Zobacz też

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

Bibliografia

Prace cytowane

• Cristian S. Calude (2002). Informacja i losowość: perspektywa algorytmiczna , wydanie drugie. Skoczek. ISBN  3-540-43466-6
• Cristian S. Calude, Michael J. Dinneen i Chi-Kou Shu. Obliczanie przebłysku losowości .
• R. Downey i D. Hirschfeldt (2010), Algorytmiczna losowość i złożoność , Springer-Verlag.
• Ming Li i Paul Vitányi (1997). Wprowadzenie do złożoności Kołmogorowa i jej zastosowań . Skoczek. Pełny tekst rozdziału wprowadzającego .
• Jürgena Schmidhubera (2000). Algorytmiczne teorie wszystkiego (arXiv: quant-ph/ 0011122). Odniesienie do czasopisma: J. Schmidhuber (2002). Hierarchie uogólnionych złożoności Kołmogorowa i niewyliczalne miary uniwersalne obliczalne w granicy. International Journal of Foundations of Computer Science 13(4):587-612.

Linki zewnętrzne

• Aspekty artykułu Chaitin's Omega Survey omawiające ostatnie postępy w badaniach nad Omega Chaitin.
• Artykuł Omega i dlaczego matematyka nie ma TOE na podstawie artykułu autorstwa Gregory'ego Chaitina, który ukazał się w sierpniowym wydaniu Mathematics Today, z okazji 50. rocznicy śmierci Alana Turinga.
• Granice rozumu , Gregory Chaitin, pierwotnie ukazał się w Scientific American, marzec 2006.
• Limit-obliczalna Super Omega bardziej losowa niż Omega i uogólnienia informacji algorytmicznych, Jürgen Schmidhuber