Najkrótszego możliwego opisu danych nie da się ogólnie wyliczyć
Złożoność Kołmogorowa ciągu danych to, w uproszczeniu, długość najkrótszego programu, który potrafi ten ciąg wygenerować na ustalonej uniwersalnej maszynie. Brzmi jak idealna definicja „prawdziwej kompresowalności”: prosty napis powinien mieć krótki program, losowo wyglądający — długi. Problem polega na tym, że złożoność Kołmogorowa nie jest funkcją obliczalną. Nie ma algorytmu, który dostaje dowolny ciąg, zawsze kończy i podaje długość absolutnie najkrótszego programu generującego ten ciąg. Aby mieć pewność, że krótszy kandydat nigdy niczego nie wypisze, musielibyśmy rozwiązywać problem stopu.
Definicja najkrótszego programu
Ustalamy uniwersalny język lub maszynę U. Dla napisu x rozważamy wszystkie programy p, które uruchomione w U kończą się i wypisują x. Złożoność Kołmogorowa K_U(x) jest długością najkrótszego takiego p. Zmiana rozsądnego języka może zmienić wartości o stały narzut kompilatora, dlatego dla długich danych idea pozostaje stabilna z dokładnością do stałej zależnej od wyboru maszyny.
Dlaczego brutalne wyszukiwanie nie kończy sprawy
Możemy uruchamiać coraz więcej programów równolegle i znajdować coraz krótsze opisy, które rzeczywiście kończą się z wynikiem x. To daje coraz lepsze górne ograniczenia K(x). Kłopot pojawia się przy certyfikacie optymalności. Skąd wiemy, że jakiś jeszcze krótszy program nie będzie działał przez astronomicznie długi czas i dopiero potem wypisze x? Ogólnie nie umiemy rozstrzygnąć, czy taki program kiedyś się zatrzyma.
Nieobliczalność jest ścisłym wynikiem
Literatura teorii informacji algorytmicznej pokazuje, że funkcja złożoności Kołmogorowa nie jest obliczalna. Powiązanie z problemem stopu nie jest tylko intuicją o trudnościach implementacyjnych: można zbudować formalne dowody, że algorytm obliczający K dla wszystkich napisów prowadziłby do niemożliwych konsekwencji w teorii obliczalności.
Co w takim razie robią kompresory
ZIP, zstd, PNG czy inne algorytmy nie próbują dowodzić, że znalazły najkrótszy możliwy program opisujący dane. Wykorzystują konkretne regularności: powtórzenia, słowniki, przewidywalność symboli, transformacje i modele statystyczne. Długość skompresowanego pliku może służyć jako praktyczne przybliżenie „strukturalności”, ale nie jest dokładną złożonością Kołmogorowa.
Idealna kompresja ma granicę logiczną
Definicja K jest cenna właśnie dlatego, że oddziela pojęcie informacji od konkretnego kodeka. Jednocześnie pokazuje granicę: matematycznie możemy zdefiniować idealną długość opisu, ale nie możemy zbudować programu, który zawsze ją wyliczy. To kolejny przypadek, w którym dobrze określona wielkość znajduje się poza zasięgiem uniwersalnego algorytmu.
Dlaczego „najlepszy kompresor” nie wystarczy
Można próbować przybliżać K(x), uruchamiając wiele programów i zapamiętując najkrótszy z tych, które dotąd wygenerowały x. To daje coraz lepsze górne oszacowania: znalezienie krótszego programu od razu poprawia wynik. Problem polega na pewności, że nic krótszego już nie istnieje. Niektóre krótsze programy mogą nadal działać, a nie ma ogólnego sposobu ustalenia, czy kiedyś wypiszą x, czy nigdy się nie zatrzymają. Dlatego praktyczny kompresor może odkrywać regularności i dostarczać użytecznych przybliżeń „od góry”, ale nie może być uniwersalnym algorytmem zwracającym dokładną złożoność Kołmogorowa każdego ciągu.
Stała zależna od języka nie niszczy idei
Najkrótszy program zależy od tego, jaki uniwersalny język lub maszynę uznamy za punkt odniesienia. Twierdzenie o niezmienniczości mówi jednak, że dla dwóch rozsądnych uniwersalnych maszyn różnica złożoności tego samego ciągu jest ograniczona stałą niezależną od samego ciągu. Można bowiem dopisać stały „translator” z jednego języka na drugi. Dla długich danych pozwala to traktować K(x) jako sensowne pojęcie asymptotyczne, mimo braku absolutnie jednego języka referencyjnego.