Teoria informacji/TI Wykład 13

Andriej Nikołajewicz Kołmogorow (1903-1987)

Złożonośc informacyjna Kołmogorowa

Odwołajmy się do codziennego doświadczenia. Chyba każdy się zgodzi, że niektóre liczby można zapamiętać łatwiej niż inne i nie zależy to tylko od wielkości liczby. Bez trudu zapamiętamy liczbę $1\underset{100}{\underbrace{00\dots 0}}$ czy nawet

$100^{\stackrel{100}{\overbrace{100^{{\dots }^{100}}}}}$

natomiast zapamietanie 20 ,,losowych" cyfr sprawi nam kłopot. No, chyba, że to będą np.

31415926535897932384

wtedy, nawet jeśli nie ,,trzymamy" tych cyfr w pamięci, możemy je w razie potrzeby odtworzyć, np. korzystając z formuły Leibniza $\frac{1}{1}-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\frac{1}{9}-\cdots =\frac{\pi }{4}$.

Nie inaczej ma się sprawa z tekstami. Mamy swiadomość, że przy odpowiednim nakładzie pracy i czasu potrafilibysmy się nauczyć na pamięć wybranej księgi ,,Pana Tadeusza" (a może nawet calego poematu), natomiast zapamietanie -- powiedzmy -- 10 stron ,,losowych" symboli wydaje się przekraczać możliwości zwykłego człowieka. No chyba, że znowu -- znaleźlibysmy jakiś ,,klucz", na przykład okazałoby się, ze jest to tekst w obcym języku, którego jednak jestesmy w stanie się nauczyć.

Jakie pojęcia matematyczne kryją się za tym zjawiskiem? W przypadku liczb odpowiedź jest stosunkowo prosta: niektóre liczby mozna opisać znacznie krócej niż podając ich rozwinięcia dziesiętne. Oczywiście, przy uściśleniu tej obserwacji trzeba pamiętać o paradoksie Berry'ego wspomnianym na pierwszym wykładzie -- w ten sposób powracamy do pojęcia notacji.