Problem kompresji danych w najprostszej formie może odnosić się do liczb i ich zapisów. Liczby można oznaczać cyframi ("jedenaście" dla liczby 11), wyrażeń matematycznych („dwa w dwudziestym” dla 1048576), wyrażenia łańcuchowe („pięć dziewiątek” dla 99999), nazwy własne ("ilość bestii" za 666, „rok śmierci Turinga” dla 1954 r.) lub dowolne ich kombinacje. Odpowiednie jest dowolne oznaczenie, dzięki któremu rozmówca może jasno określić, o jakiej liczbie mówimy. Oczywiście powiedz o tym swojemu rozmówcy „silnia ośmiu” bardziej wydajna niż równoważna notacja „czterdzieści tysięcy trzysta dwadzieścia”. Powstaje tu logiczne pytanie: jaki jest najkrótszy zapis danej liczby?
Filozof Bertrand Russell opublikował w 1908 r , który porusza kwestię zapisu liczb od strony przeciwnej: Jaka jest najmniejsza liczba, która nie wymaga osiemdziesięciu liter?
Taka liczba musi istnieć: z osiemdziesięciu rosyjskich liter i spacji można utworzyć tylko 3480 oznaczeń, co oznacza, że za pomocą osiemdziesięciu liter można wyznaczyć nie więcej niż 3480 cyfr. Oznacza to, że nie da się w ten sposób wyznaczyć pewnej liczby nie większej niż 3480.
Oznacza to, że numer ten będzie odpowiadał oznaczeniu „najmniejsza liczba, dla której osiemdziesiąt liter nie wystarczy”, który ma tylko 78 liter! Z jednej strony ta liczba musi istnieć; z drugiej strony, jeśli ten numer istnieje, to jego oznaczenie mu nie odpowiada. Paradoks!
Najłatwiej odrzucić ten paradoks, odwołując się do nieformalności zapisów słownych. Na przykład, gdyby w notacji dozwolony był tylko specjalnie zdefiniowany zestaw wyrażeń „najmniejsza liczba, dla której osiemdziesiąt liter nie wystarczy” nie byłaby poprawną notacją, podczas gdy praktycznie przydatne są notacje, takie jak „silnia ośmiu” pozostałby do przyjęcia.
Czy istnieją formalne sposoby opisania sekwencji (algorytmu) działań na liczbach? Istnieją i jest ich mnóstwo - nazywane są językami programowania. Zamiast zapisów słownych użyjemy programów (na przykład w Pythonie), które wyświetlają wymagane liczby. Na przykład dla pięciu dziewiątek program jest odpowiedni print("9"*5). W dalszym ciągu będziemy zainteresowani najkrótszym programem dla danej liczby. Długość takiego programu nazywa się liczby; jest to teoretyczna granica, do której można skompresować daną liczbę.
Zamiast paradoksu Berry'ego możemy teraz rozważyć podobny: Jaka jest najmniejsza liczba, której wypisanie w programie kilobajtowym nie wystarczy?
Będziemy rozumować w ten sam sposób jak poprzednio: istnieje 2561024 tekstów kilobajtowych, co oznacza, że programy kilobajtowe mogą wypisać nie więcej niż 2561024 liczb. Oznacza to, że nie można w ten sposób wyprowadzić pewnej liczby nie większej niż 2561024.
Ale napiszmy program w Pythonie, który generuje wszystkie możliwe teksty kilobajtowe, uruchamia je do wykonania, a jeśli wypisuje liczbę, to dodaje ją do słownika osiągalnych. Po sprawdzeniu wszystkich 2561024 XNUMX XNUMX możliwości, niezależnie od tego, ile czasu to zajmie, program szuka najmniejszej liczby brakującej w słowniku i wypisuje tę liczbę. Wydaje się oczywiste, że taki program zmieści się w kilobajcie kodu - i wypisze tę samą liczbę, której program kilobajtowy nie może wypisać!
Jaki jest teraz haczyk? Nie można już tego przypisywać nieformalności zapisu!
Jeśli zastanawia Cię fakt, że nasz program będzie wymagał do działania astronomicznej ilości pamięci - słownika (lub tablicy bitów) składającej się z 2561024 elementów - to możesz zrobić to samo bez niego: dla każdej z 2561024 liczb po kolei , przejrzyj wszystkie 2561024 możliwych programów, aż nie będzie żadnego odpowiedniego. Nie ma znaczenia, że takie wyszukiwanie będzie trwało bardzo długo: po sprawdzeniu mniej niż (2561024)2 par z numeru i programu zakończy się i znajdzie ten bardzo ceniony numer.
A może się nie skończy? Rzeczywiście, wśród wszystkich programów, które zostaną wypróbowane, będą while True: pass (i jego funkcjonalne analogi) - a sprawa nie pójdzie dalej niż przetestowanie takiego programu!
W przeciwieństwie do paradoksu Berry’ego, w którym haczyk tkwił w nieformalności zapisu, w drugim przypadku mamy dobrze zamaskowane przeformułowanie . Faktem jest, że niemożliwe jest określenie jego wyniku z programu w skończonym czasie. W szczególności złożoność Kołmogorowa : nie ma algorytmu, który pozwoliłby dla danej liczby znaleźć długość najkrótszego programu, który tę liczbę wypisuje; co oznacza, że nie ma rozwiązania problemu Berry’ego – znalezienia długości najkrótszego oznaczenia słownego dla danej liczby.
Źródło: www.habr.com