Algorytmiczna teoria informacji - Algorithmic information theory

Algorytmiczna teoria informacji (AIT) jest gałęzią informatyki teoretycznej, która zajmuje się relacjami między obliczeniami a informacją o obiektach generowanych obliczeniowo (w przeciwieństwie do generowanych stochastycznie ), takich jak ciągi znaków lub jakakolwiek inna struktura danych . Innymi słowy, w algorytmicznej teorii informacji pokazano, że nieściśliwość obliczeniowa „naśladuje” (poza stałą, która zależy tylko od wybranego uniwersalnego języka programowania) relacje lub nierówności występujące w teorii informacji . Według Gregory'ego Chaitina jest to „wynik umieszczenia teorii informacji Shannona i teorii obliczalności Turinga w shakerze i energicznego wstrząsania”.

Oprócz sformalizowania uniwersalnej miary dla nieredukowalnej zawartości informacyjnej obiektów generowanych obliczeniowo, niektóre główne osiągnięcia AIT miały pokazać, że: w rzeczywistości złożoność algorytmiczna wynika (w przypadku samookreślenia ) z tymi samymi nierównościami (z wyjątkiem stałej), co entropia robi, jak w klasycznej teorii informacji; losowość to niekompresowalność; a w sferze losowo generowanego oprogramowania prawdopodobieństwo wystąpienia dowolnej struktury danych jest rzędu najkrótszego programu, który ją generuje podczas działania na uniwersalnej maszynie.

AIT głównie bada miary nieredukowalnej zawartości informacyjnej ciągów (lub innych struktur danych ). Ponieważ większość obiektów matematycznych można opisać za pomocą ciągów lub jako granicę ciągu ciągów, można go używać do badania szerokiej gamy obiektów matematycznych, w tym liczb całkowitych . Jedną z głównych motywacji stojących za AIT jest samo badanie informacji niesionych przez obiekty matematyczne, jak w dziedzinie metamatematyki , np. jak pokazują wyniki niezupełności wymienione poniżej. Inne główne motywacje pochodziły z: przekroczenia ograniczeń klasycznej teorii informacji dla pojedynczych i stałych obiektów; sformalizowanie pojęcia losowości ; oraz znalezienie sensownego wnioskowania probabilistycznego bez uprzedniej wiedzy o rozkładzie prawdopodobieństwa (np. czy jest on niezależny i ma identyczny rozkład , markowski , czy nawet stacjonarny ). W ten sposób, AIT jest wiadomo, że w zasadzie opiera się trzech głównych pojęć matematycznych i relacji między nimi: algorytmicznych złożoności , algorytmiczne przypadkowości i algorytmiczne prawdopodobieństwa .

Przegląd

Algorytmiczna teoria informacji bada głównie miary złożoności na ciągach (lub innych strukturach danych ). Ponieważ większość obiektów matematycznych można opisać za pomocą ciągów lub jako granicę ciągu ciągów, można go używać do badania szerokiej gamy obiektów matematycznych, w tym liczb całkowitych .

Nieformalnie, z punktu widzenia algorytmicznej teorii informacji, zawartość informacyjna ciągu jest równoważna długości najbardziej skompresowanej możliwej samodzielnej reprezentacji tego ciągu. Samodzielna reprezentacja jest zasadniczo programem — w pewnym ustalonym, ale poza tym nieistotnym uniwersalnym języku programowania — który po uruchomieniu wyświetla oryginalny ciąg.

Z tego punktu widzenia 3000-stronicowa encyklopedia w rzeczywistości zawiera mniej informacji niż 3000 stron całkowicie przypadkowych liter, mimo że encyklopedia jest znacznie bardziej użyteczna. Dzieje się tak dlatego, że aby zrekonstruować cały ciąg przypadkowych liter, trzeba wiedzieć, czym jest każda pojedyncza litera. Z drugiej strony, gdyby każda samogłoska została usunięta z encyklopedii, ktoś z rozsądną znajomością języka angielskiego mógłby ją zrekonstruować, tak jak można by prawdopodobnie zrekonstruować zdanie „Ths sntnc hs lw nfrmtn cntnt” z obecnego kontekstu i spółgłosek.

W przeciwieństwie do klasycznej teorii informacji, algorytmiczna teoria informacji podaje formalne , rygorystyczne definicje losowego ciągu i losowego ciągu nieskończonego , które nie zależą od fizycznych lub filozoficznych intuicji dotyczących niedeterminizmu lub prawdopodobieństwa . (Zbiór losowych ciągów zależy od wyboru uniwersalnej maszyny Turinga użytej do określenia złożoności Kołmogorowa , ale każdy wybór daje identyczne wyniki asymptotyczne, ponieważ złożoność Kołmogorowa ciągu jest niezmienna aż do stałej addytywnej zależnej tylko od wyboru uniwersalnej złożoności Turinga Z tego powodu zbiór losowych ciągów nieskończonych jest niezależny od wyboru maszyny uniwersalnej).

Niektóre wyniki algorytmicznej teorii informacji, takie jak twierdzenie o niezupełności Chaitina , wydają się kwestionować powszechne matematyczne i filozoficzne intuicje. Najbardziej godna uwagi jest konstrukcja stałej Chaitina Ω , liczby rzeczywistej, która wyraża prawdopodobieństwo, że samoograniczająca się uniwersalna maszyna Turinga zatrzyma się, gdy jej dane wejściowe zostaną dostarczone przez rzut uczciwej monety (czasami uważane za prawdopodobieństwo, że losowa program komputerowy w końcu się zatrzyma). Chociaż Ω jest łatwe do zdefiniowania, w każdej spójnej aksjomatyzowalnej teorii można obliczyć tylko skończoną liczbę cyfr Ω , więc jest ona w pewnym sensie niepoznawalna , zapewniając absolutną granicę wiedzy, która przypomina twierdzenia o niezupełności Gödla . Chociaż cyfr Ω nie można określić, wiele właściwości Ω jest znanych; na przykład jest to sekwencja algorytmicznie losowa, a zatem jej cyfry binarne są równomiernie rozłożone (w rzeczywistości jest to normalne ).

Historia

Algorytmiczna teoria informacji została założona przez Raya Solomonoffa , który opublikował podstawowe idee, na których opiera się ta dziedzina w ramach swojego wynalazku prawdopodobieństwa algorytmicznego — sposobu na przezwyciężenie poważnych problemów związanych ze stosowaniem reguł Bayesa w statystyce. Po raz pierwszy opisał swoje wyniki na konferencji w Caltech w 1960 r. oraz w raporcie z lutego 1960 r. „A Preliminary Report on a General Theory of Induction Inference”. Algorytmiczna teoria informacji została później rozwinięta niezależnie przez Andreya Kołmogorowa , w 1965 i Gregory Chaitina , około 1966.

Istnieje kilka wariantów złożoności Kołmogorowa lub informacji algorytmicznej; najpowszechniej stosowany opiera się na programach samookreślających się i wynika głównie z Leonida Levina (1974). Per Martin-Löf również wniósł znaczący wkład w teorię informacji o ciągach nieskończonych. Aksjomatyczne podejście do algorytmicznej teorii informacji oparte na aksjomatach Bluma (Blum 1967) przedstawił Mark Burgin w artykule przedstawionym do publikacji przez Andreya Kołmogorowa (Burgin 1982). Podejście aksjomatyczne obejmuje inne podejścia w algorytmicznej teorii informacji. Różne miary informacji algorytmicznej można traktować jako szczególne przypadki aksjomatycznie zdefiniowanych miar informacji algorytmicznej. Zamiast udowadniać podobne twierdzenia, takie jak podstawowe twierdzenie o niezmienności, dla każdej konkretnej miary, można łatwo wydedukować wszystkie takie wyniki z jednego odpowiedniego twierdzenia udowodnionego w układzie aksjomatycznym. Jest to ogólna zaleta podejścia aksjomatycznego w matematyce. Aksjomatyczne podejście do algorytmicznej teorii informacji zostało dalej rozwinięte w książce (Burgin 2005) i zastosowane do metryk oprogramowania (Burgin i Debnath, 2003; Debnath i Burgin, 2003).

Dokładne definicje

Mówi się, że ciąg binarny jest losowy, jeśli złożoność ciągu Kołmogorowa jest co najmniej równa długości ciągu. Prosty argument zliczania pokazuje, że niektóre ciągi o dowolnej długości są losowe, a prawie wszystkie ciągi są bardzo bliskie losowości. Ponieważ złożoność Kołmogorowa zależy od ustalonego wyboru uniwersalnej maszyny Turinga (nieformalnie ustalonego „języka opisu”, w którym podawane są „opisy”), zbiór losowych ciągów zależy od wyboru ustalonej uniwersalnej maszyny. Niemniej jednak zbiór ciągów losowych jako całość ma podobne właściwości niezależnie od maszyny ustalonej, więc można (i często tak mówimy) mówić o właściwościach ciągów losowych jako grupie bez konieczności uprzedniego określania maszyny uniwersalnej.

Mówi się, że nieskończony ciąg binarny jest losowy, jeśli dla pewnej stałej c , dla wszystkich n , złożoność Kołmogorowa początkowego odcinka o długości n ciągu wynosi co najmniej n  −  c . Można wykazać, że prawie każdy ciąg (z punktu widzenia miary standardowej — „godziwej monety” lub miary Lebesgue'a — na przestrzeni nieskończonych ciągów binarnych) jest losowy. Ponadto, ponieważ można wykazać, że złożoność Kołmogorowa względem dwóch różnych maszyn uniwersalnych różni się co najwyżej stałą, zbiór losowych ciągów nieskończonych nie zależy od wyboru maszyny uniwersalnej (w przeciwieństwie do ciągów skończonych). Ta definicja losowości jest zwykle nazywana losowością Martina-Löfa , od Per Martin-Löf , aby odróżnić ją od innych podobnych pojęć losowości. Czasami nazywa się ją 1-losowością, aby odróżnić ją od innych silniejszych pojęć losowości (2-losowość, 3-losowość itp.). Oprócz koncepcji losowości Martina-Löfa istnieją również losowość rekurencyjna, losowość Schnorra, losowość Kurtza itp. Yongge Wang wykazał, że wszystkie te koncepcje losowości są różne.

(Powiązane definicje można tworzyć dla alfabetów innych niż zestaw .) ${\ Displaystyle \ {0,1 \}}$

Określona sekwencja

Algorytmiczna teoria informacji (AIT) to teoria informacji o pojedynczych obiektach, wykorzystująca informatykę i zajmująca się związkiem między obliczeniami, informacją i losowością.

Zawartość informacyjną lub złożoność obiektu można zmierzyć długością jego najkrótszego opisu. Na przykład ciąg

"0101010101010101010101010101010101010101010101010101010101010101"

ma krótki opis „32 powtórzenia '01'”, podczas gdy

"1100100001100001110111101110110011111010010000100101011110010110"

przypuszczalnie nie ma prostego opisu poza zapisaniem samego ciągu.

Bardziej formalnie, złożoność algorytmiczna (AC) ciągu znaków x jest zdefiniowana jako długość najkrótszego programu, który oblicza lub generuje x , gdzie program jest uruchamiany na jakimś uniwersalnym komputerze o stałej referencji.

Ściśle pokrewnym pojęciem jest prawdopodobieństwo, że uniwersalny komputer wypisze jakiś ciąg x, gdy zostanie zasilony programem wybranym losowo. To algorytmiczne prawdopodobieństwo „Solomonoffa” (AP) jest kluczem do rozwiązania starego filozoficznego problemu indukcji w sposób formalny.

Główną wadą AC i AP jest ich nieobliczalność. Ograniczona czasowo złożoność „Levina” karze powolny program, dodając do jego długości logarytm czasu jego działania. Prowadzi to do obliczalnych wariantów AC i AP, a uniwersalne przeszukiwanie "Levina" (US) rozwiązuje wszystkie problemy inwersji w optymalnym czasie (poza pewną nierealistycznie dużą stałą multiplikatywną).

AC i AP pozwalają również na formalną i rygorystyczną definicję losowości poszczególnych ciągów, która nie zależy od fizycznych lub filozoficznych intuicji dotyczących niedeterminizmu lub prawdopodobieństwa. Z grubsza ciąg jest algorytmiczny „Martin-Löf” losowy (AR), jeśli jest niekompresowalny w tym sensie, że jego złożoność algorytmiczna jest równa jego długości.

AC, AP i AR to podstawowe poddyscypliny AIT, ale AIT pojawia się w wielu innych obszarach. Służy jako podstawa zasady minimalnej długości opisu (MDL), może uprościć dowody w teorii złożoności obliczeniowej , została wykorzystana do zdefiniowania uniwersalnej metryki podobieństwa między obiektami, rozwiązuje problem demona Maxwella i wiele innych.

Zobacz też

Bibliografia

Zewnętrzne linki

• Algorytmiczna teoria informacji w Scholarpedia
• Relacja Chaitina z historii AIT .

Dalsza lektura