PL 
EnglishDomyślny
Українська🧮 Złożoność Kołmogorowa: najkrótszy opis
Kompresuj ciąg bitów na żywo prawdziwym algorytmem typu LZ77 i używaj długości skompresowanej jako uczciwego, obliczalnego przybliżenia z góry dla (dowodliwie nieobliczalnej) złożoności Kołmogorowa.
O tej symulacji
Złożoność Kołmogorowa K(x) ciągu x definiuje się jako długość najkrótszego programu, który generuje x na uniwersalnej maszynie Turinga. Intuicyjnie mierzy ona, ile prawdziwej informacji zawiera ciąg — ciąg ściśliwy do krótkiego opisu (jak milion zer) ma niską złożoność, podczas gdy prawdziwie losowy ciąg nie ma opisu krótszego niż on sam. Koncepcję rozwinęli niezależnie Solomonoff, Kołmogorow i Chaitin na przełomie lat 60. Niestety K(x) jest dowodliwie nieobliczalne — żaden program nie może obliczyć K(x) dla dowolnego x, co wynika bezpośrednio z problemu stopu i paradoksu Berry'ego. Ta symulacja obchodzi ten problem, używając rzeczywistego algorytmu kompresji LZ77 jako obliczalnego przybliżenia z góry: długość skompresowanego ciągu nigdy nie jest mniejsza niż prawdziwe K(x), ale daje praktyczny, obserwowalny wgląd w to samo zjawisko.
🔬 Co pokazuje
Rzeczywistą kompresję LZ77 działającą na żywo na różnych ciągach bitów, z długością wyjścia jako przybliżeniem z góry złożoności Kołmogorowa.
🎮 Jak korzystać
Wybierz preset ciągu (zera, wzorzec Thue-Morse'a, losowy) lub wpisz własny, uruchom kompresję i porównaj długość oryginalną z długością skompresowaną.
💡 Czy wiesz, że?
Prawdziwa złożoność Kołmogorowa jest nieobliczalna dla dowolnego ciągu — żaden algorytm, niezależnie od mocy obliczeniowej, nigdy nie może jej dokładnie wyznaczyć dla wszystkich możliwych danych wejściowych.
Często zadawane pytania
Czym jest K(x)?
K(x) to długość najkrótszego programu komputerowego (w ustalonym uniwersalnym języku), który po uruchomieniu bez danych wejściowych generuje dokładnie ciąg x i się zatrzymuje. Formalizuje ideę, że im więcej wzorca lub struktury ma ciąg, tym krócej można go opisać.
Dlaczego K(x) jest nieobliczalne?
Dowód wynika z paradoksu Berry'ego: gdyby istniał program obliczający K(x) dla dowolnego x, można by skonstruować program, który przeszukuje wszystkie ciągi i zwraca pierwszy o złożoności większej niż jego własna długość — sprzeczność, ponieważ ten program sam jest krótkim opisem tego ciągu. Głębiej wiąże się to z nierozstrzygalnością problemu stopu, ponieważ obliczenie K(x) wymagałoby wiedzy, czy krótsze programy się zatrzymują.
Co właściwie pokazuje ta symulacja jako przybliżenie?
Symulacja uruchamia rzeczywisty algorytm kompresji LZ77 na wprowadzonym ciągu bitów i zwraca długość wynikowego skompresowanego kodu. Ponieważ każdy dekompresor LZ77 jest krótkim, ustalonym programem, długość skompresowanych danych plus stała długość dekompresora stanowi prawidłowe (choć niedoskonałe) obliczalne ograniczenie górne na K(x).
Dlaczego preset Thue-Morse'a nie kompresuje się zbytnio?
Ciąg Thue-Morse'a jest zbudowany rekurencyjnie i unika prostych powtórzeń bloków, więc mimo posiadania niskiej rzeczywistej złożoności Kołmogorowa (istnieje krótka reguła generująca), prosty kompresor oparty na słowniku, taki jak LZ77, nie wykrywa tej głębszej struktury i daje słabsze przybliżenie niż w przypadku ciągów z oczywistą powtarzalnością.
Dlaczego preset losowy prawie się nie kompresuje?
Prawdziwie losowy ciąg bitów z definicji nie zawiera powtarzających się wzorców, które LZ77 mogłoby wykorzystać, więc skompresowana długość jest bliska długości oryginalnej — dokładnie tego oczekujemy, ponieważ losowe ciągi mają K(x) bliskie ich własnej długości.
Czy Math.random() w tej symulacji generuje prawdziwą losowość?
Nie — Math.random() to generator liczb pseudolosowych, deterministyczny algorytm, który technicznie ma bardzo niską złożoność Kołmogorowa (krótki opis: „uruchom ten konkretny algorytm z tym ziarnem”), mimo że statystycznie wygląda losowo dla większości praktycznych testów.
Jak obliczana jest długość bitów w symulacji?
Symulacja liczy bity potrzebne do zakodowania sekwencji tokenów LZ77 — par (odległość, długość) dla dopasowanych powtórzeń oraz literałów dla niedopasowanych bitów — dając realistyczne oszacowanie rzeczywistego rozmiaru skompresowanego pliku.
Czy lepszy kompresor dałby wynik bliższy prawdziwemu K(x)?
Tak, do pewnego stopnia — bardziej zaawansowane kompresory (np. oparte na kontekstowym modelowaniu lub sieciach neuronowych) mogą wykrywać głębsze wzorce niż LZ77 i dawać ciaśniejsze ograniczenia górne, ale żaden skończony algorytm nigdy nie osiągnie dokładnego K(x) dla wszystkich możliwych ciągów wejściowych, ponieważ pozostaje ono nieobliczalne.
Jak K(x) wiąże się z entropią Shannona?
Entropia Shannona mierzy średnią niepewność źródła losowego względem rozkładu prawdopodobieństwa, podczas gdy złożoność Kołmogorowa mierzy nieściśliwość pojedynczego konkretnego ciągu niezależnie od jakiegokolwiek rozkładu. Dla ciągów generowanych przez źródło ergodyczne oczekiwana wartość K(x) na symbol zbiega asymptotycznie do entropii Shannona źródła.