Kolmogorowowa złożoność: losowość, której żaden program nie może obliczyć

Różne podejście do definicji przypadkowości

Entropia Shannon mierzy średnią zawartość informacji symboli wybranych z danego rozkładu prawdopodobieństwa. Kompleksowość Kolinowska, rozwijana niezależnie przez Raya Solomonoffa, Andreja Kolinowskiego i Grigorya Chajtina w latach 60., pyta o podobną, ale naprawdę inną sprawę dotyczące pojedynczej konkretnej lancuchu znaków: jak długie jest najkrótsy możliwy program, w pewnym ustalonej referencyjnej języku, który wydaje dokładnie ten lancuch znaków i zatrzymuje się?

K(x)  =  length of the shortest program p such that  U(p) = x

// U is a fixed universal computer (a universal Turing machine)
// K(x) is measured in bits — the length of p's encoding, not the length of x

Dlaczego niektóre nici są zmiennoprzecinkowe, podczas gdy inne nie mogą być zmiennoprzecinkowo

Załóżmy, że mamy dwie nici o 1000 znakach. Pierwsza jest tysiącem kopii cyfry „1”. Druga została wygenerowana przez rzucanie sześcienną kostką do gry tysiąc razy. Pierwsza ma niemalże zera złożoność Kolinowskiego — program tak krótki jak print("1" * 1000) dokładnie ją powtórzy, niezależnie od wybranego języka referencyjnego (z wyjątkiem małej stałej związanej z obciążeniem interpretera). Druga, jeśli jest prawdziwie losową sekwencją bez wykorzystywalnych wzorów, nie ma krótszej opisanej formuły niż podawanie samej nici — dowolny program generujący ją musi w najgorszym przypadku być co najmniej taki sam jak sama nica, ponieważ nie ma krótszej zasady, która mogłaby wygenerować dokładnie tę sekwencję rzutów kostką i nic innego.

To daje formalną definicję Kolinowskiego losowości: nica jest algorytmicznie losowa, jeśli jej złożoność Kolinowskiego jest bliska długości samej nicy — jeśli najkrótszy opis nie jest znacznie krótszy niż sam podanie nicy. To jest podstawowo inna koncepcja w stosunku do definicji Shannon'a, a obie mogą się zgodzić lub niezgodni być dla jednej konkretnej nici: tysiąc rzutów sześcienną kostką do gry ma wysoką entropię Shannon'a jako źródła (każde rzut prawdopodobnie przynosi blisko 1 bit informacji na średnim poziomie, zanim zobaczysz wynik), ale dowolna konkretne sekwencja wygenerowana przez to źródło jest prawdopodobnie losowa w sensie Kolinowskiego — obie miary zgadzają się w przypadku typowym, co nie jest przypadek, ale konceptualnie odpowiadają na różne pytania (średnia niepewność źródła, w stosunku do najkrótszej opisanej formy jednej konkretnej nici).

Dowód na to, że jest nieobliczalny, w jednym zdaniu

Oto najoczywisty i najbardziej słynny wynik w tym dziedzińcu: K(x) nie może być obliczone przez żaden algorytm dla dowolnego x, w ogólności. Klasyka dowodu to argument przeciwnego przypuszczenia podobny do paradoksu Berrya. Podejmijmy założenie, że istnieje program COMPLEXITY(x), który zawsze poprawnie oblicza K(x). Wówczas można napisać krótki program, który poszukuje po wszystkich ciągach w porządku i wydrukowuje pierwszy, dla którego skomplikowana entropia Kolmogorowa, jak zwracana jest przez COMPLEXITY, przekracza pewną dużą granicę N — nazywamy go „pierwszym ciągiem o skomplikowanej entropii większej niż N opisanym w mniej niż N znakach”. Ale ten program poszukujący i drukujący, plus stała kodowanie N, jest samym opisem tego ciągu używającym znacznie mniej niż N bitów (logika poszukiwania to mały stały element, a sama N zajmuje około log2(N) bitów do zakodowania) — co przeciwdzieli twierdzeniu, że najkrótszy opis tego ciągu wymaga więcej niż N bitów. Ta sprzeczność jest nieunikniona dla dowolnej N duża dość, aby log(N) plus stała była mniejsza od N, co zmusza do wniosku, że funkcja COMPLEXITY obliczająca K(x) dokładnie nie może istnieć wcale.

To nie ograniczenie praktyczne czekające na szybsze komputery lub bardziej inteligentne algorytmy — to trudny wynik matematyczny, z tego samego rodziny co problem haltinga Turina i twierdzenia Gödla o niewydedukowalności (wszystkie trzy, nie przypieczętnione przypadkiem, opierają się na tej samej strukturze argumentu opartego na diagonalizacji). Nie można zweryfikować, czy kandydat na krótki program jest rzeczywiście najkrótszym, który wygeneruje dany ciąg, ponieważ sprawdzenie tego w ogólności wymaga rozwiązania problemu haltinga — sprawdzenia każdego krótszego kandydata programu, czy zatrzymuje się i wydrukowuje x, a niektóre z tych kandydatów prosto nie zatrzymują się.

Kompresja jako szczerzy i obliczalny proxy

Ogólnie rzecz biorąc, K(x) jest niewykorzystywany, zamiast tego praktycy używają długości kompresji pod kątem konkretnego, ustalonego algorytmu kompresji jako obliczalnego podstawienia — górnej granicy dla K(x), ponieważ dekompresor oraz dane skomprestzone razem tworzą prawidłową, choć niekoniecznie minimalną programę, która powtarza x. Każdy ogólnodostępny bezpieczny kompresor może pełnić tę rolę, a algorytm LZ77 — podstawowy załącznik do gzip, DEFLATE i demo na tej stronie — jest jednym z najwyraźniej widocznych w działaniu, ponieważ jego wyjście jasno oddziela kompresowalne od nienikompresowalnych części ciągu.

Podstawowa myśl za algorytmem LZ77 z oknem przesuwającym się: przejrzy string w kierunku przodu na każdym położeniu, spojrzy w tył w ograniczonym oknie na najdłuższy dopasowanie do tego, co nastąpi jeśli znaleziono dopasowanie o długości >= jakiegoś minimum: wyemituje odniesienie do tła (odległość, długość) zamiast oryginalnych znaków w przeciwnym razie: wyemituje literę(na), bez kompresji // Ciąg bardzo powtarzalny zmniejsza się do małej liczby odniesień do tła // rzeczywisty ciąg losowy nie znajdzie prawie żadnych dopasowań i pozostanie blisko // swojej długości oryginalnej — rozmiar skompresowany JEST szczerzym proxy Przeprowadź algorytm LZ77 na ciągu tysiąca jedynek, a zmniejszy się on do małej liczby bajtów — jedna litera „1” plus pojedyncze długie odniesienie do tła powtarzające się, lub zaszyfrowane w całości jako kod run-length. Przeprowadź go na tysiącu rzeczywistych rzutów monet i prawie nie zmniejszy się — ponieważ nie ma wystarczająco długich podciągów powtarzających się, które można wykorzystać; rozmiar skompresowany pozostaje bliski długości oryginalnej, co dokładnie odpowiada sygnaturze przewidzianej przez definicję Kolmogorova dla ciągu losowego algorytmicznie. Rozmiar skompresowany jest tylko górą granicą — bardziej inteligentny kompresor lub ręcznie napisany program wykorzystujący pewne mniej widoczne wzorce, których LZ77 nie zauważy, mógłby zawsze znaleźć coś krótszego — ale jako praktyczna i obliczalna szczerza estymata „jak kompresowalny jest ten konkretne ciąg”, jest odpowiednim narzędziem do wykonania, a to dokładnie jest to co demo na tej stronie wykonuje dla każdego ciągu bajtów, który podasz.

LZ77 sliding-window compression, the core idea:
  scan forward through the string
  at each position, look BACKWARD in a bounded window for the longest
  match to what comes next
  if a match of length >= some minimum is found:
    emit a (distance, length) BACK-REFERENCE instead of the raw characters
  else:
    emit the literal character(s), uncompressed

// a highly repetitive string collapses to a handful of back-references
// a genuinely random string finds almost no matches and stays close
// to its original length -- the compressed size IS the honest proxy

Gdzie niekomputowalność pojawia się jako praktyczna granica

Niekomputowalność złożoności Kolinogorowa nie jest tylko ciekawostką — podstawia za konkretne ograniczenia w innych miejscach. Daje ona formalny, bezdyskretowy fundament dla nośnika Ockamowskiego w uczeniu maszynowym i teorii induktoryjnego wnioskowania Solomonsa (faworezanie najkrótszej hipotezy zgodnej z danymi jest dowodowo prawidłowe przedziałem priorytetu, w precyzyjnym sensie prawdopodobieństwa algorytmicznego). Poza tym połącza się bezpośrednio z twierdzeniem Chaitina: dla każdego spójnego formalnego systemu axiomaticznego istnieje obliczalny próg po którym system nie może udowodnić dokładnej złożoności Kolinogorowa dowolnego ciągu, nawet jeśli każdy ciąg ma jasno określonego wartości złożoności — tu, jak Gödel pokazał dla samej arytmetyki, dojrzewa separacja między udowodnialnością a prawdą.

Często zadawane pytania