Zadanie kompresji danych w swojej najprostszej formie może odnosić się do liczb i ich oznaczeń. Liczby mogą być oznaczane liczebnikami ("jedenaście" dla liczby 11), wyrażeniami matematycznymi ("dwa do dwudziestej" dla 1048576), wyrażeniami tekstowymi ("pięć dziewiątek" dla 99999), nazwami własnymi ("liczba bestii" dla 666, "rok śmierci Turinga" dla 1954), lub dowolnymi ich kombinacjami. Odpowiednie jest każde oznaczenie, za pomocą którego rozmówca będzie w stanie jednoznacznie określić, o której liczbie mowa. Oczywiste jest, że poinformowanie rozmówcy "silnia ośmiu" jest skuteczniejsze niż równoważne oznaczenie "czterdzieści tysięcy trzysta dwadzieścia". Tutaj pojawia się logiczne pytanie: jakie oznaczenie dla danego liczby jest najkrótsze?
Filozof Bertrand Russell w 1908 roku opublikował , który porusza kwestię oznaczeń liczb z przeciwnej strony: jaką jest najmniejsza liczba, dla oznaczenia której nie wystarczy osiemdziesięciu liter?
Taka liczba musi istnieć: z osiemdziesięciu rosyjskich liter i spacji można stworzyć tylko 3480 oznaczeń, więc przy użyciu osiemdziesięciu liter można oznaczyć nie więcej niż 3480 liczb. Oznacza to, że pewna liczba, nie większa niż 3480, nie może być w ten sposób oznaczona.
Oznacza to, że tej liczbie będzie odpowiadać oznaczenie "najmniejsza liczba, dla oznaczenia której nie wystarczy osiemdziesięciu liter", które składa się tylko z 78 liter! Z jednej strony, ta liczba musi istnieć; z drugiej, jeśli ta liczba istnieje, to jej oznaczenie nie odpowiada jej. Paradoks!
Najprostszy sposób, aby zbagatelizować ten paradoks, to odwołać się do nieformalności słownych oznaczeń. Mówiąc, że gdyby w oznaczeniach dopuszczany był jedynie określony zestaw wyrażeń, to "najmniejsza liczba, dla oznaczenia której nie wystarczy osiemdziesięciu liter" nie byłoby dozwolonym oznaczeniem, podczas gdy praktycznie użyteczne oznaczenia takie jak "silnia ośmiu" pozostałyby dozwolone.
Czy istnieją formalne sposoby opisu sekwencji (algorytmu) działań na liczbach? Tak, i jest ich wiele — nazywa się je językami programowania. Zamiast słownych oznaczeń użyjemy programów (na przykład w Pythonie), które wyświetlają odpowiednie liczby. Na przykład, dla pięciu dziewiątek, odpowiedni będzie program print("9"*5). Nadal będziemy się interesować najkrótszym programem dla danego liczby. Długość takiego programu nazywa się liczby; to teoretyczna granica, do której daną liczbę można skompresować.
Zamiast paradoksu Berry'ego możemy teraz rozważyć analogiczny: jaką najmniejszą liczbę można uzyskać z programu o wielkości mniejszej niż jeden kilobajt?
Rozważania prowadzić będziemy tak samo, jak poprzednio: istnieje 2561024 kilobajtowych tekstów, co oznacza, że za pomocą programów o wielkości jednego kilobajta można uzyskać najwyżej 2561024 liczb. Zatem istnieje pewna liczba, która nie jest większa niż 2561024, której nie można uzyskać w ten sposób.
Ale napiszemy program w Pythonie, który generuje wszystkie możliwe teksty o wielkości jednego kilobajta, uruchamia je, a jeśli któreś z nich generuje jakąś liczbę - dodaje tę liczbę do słownika osiągalnych. Po sprawdzeniu wszystkich 2561024 możliwości, nieważne ile to zajmie - program wyszukuje, która najmniejsza liczba brakuje w słowniku i zwraca tę liczbę. Wydaje się oczywiste, że taki program zmieści się w jednym kilobajcie kodu - i zwróci tę liczbę, której nie można uzyskać programem o wielkości jednego kilobajta!
Gdzie więc tkwi haczyk teraz? Nie można już go zrzucić na nieformalność oznaczeń!
Jeśli martwi Was to, że nasz program wymagałby astronomicznej ilości pamięci do działania - słownik (lub tablica bitowa) z 2561024 elementami - można to wszystko zrealizować bez niego: dla każdego z 2561024 liczb po kolei przeszukiwać wszystkie 2561024 możliwe programy, aż znajdzie się odpowiedni. Nie ważne, że takie przeszukiwanie zajmie bardzo dużo czasu: po sprawdzeniu mniej niż (2561024)2 par liczby i programu musi się zakończyć i znaleźć tę wymarzoną liczbę.
Czy jednak się zakończy? Wszak wśród wszystkich programów, które będą sprawdzane, znajdzie się while True: pass (i jej funkcjonalne odpowiedniki) - i dalej sprawdzenie takiego programu nie pójdzie już naprzód!
W przeciwieństwie do paradoksu Berry'ego, gdzie haczyk tkwił w nieformalności oznaczeń, w drugim przypadku mamy do czynienia z dobrze zamaskowaną przekształceniem . Istotą sprawy jest to, że z programu nie można w końcu określić jego wyniku w skończonym czasie. W szczególności, złożoność Kolmogorowa Nie ma takiego algorytmu, który pozwalałby dla podanej liczby znaleźć długość najkrótszego programu, który tę liczbę wyświetla; a zatem nie ma też rozwiązania dla problemu Berry'ego — znaleźć dla podanej liczby długość najkrótszego słownego oznaczenia.
Źródło: habr.com
