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źlibyśmy jakiś ,,klucz", na przykład okazałoby się, ze jest to tekst w obcym języku, którego jednak jesteśmy w stanie się nauczyć.

Jakie pojęcia matematyczne kryją się za tym zjawiskiem? W przypadku liczb odpowiedź jest stosunkowo prosta: niektóre liczby całkowite można opisać znacznie krócej niż podając ich rozwinięcia dziesiętne. Oczywiście, pojęcie opisania liczby (czy czegokolwiek innego) wymaga ścisłego określenia, co zrobiliśmy na pierwszym wykładzie pod pojęciem notacji (w przeciwnym razie narażamy się na paradoks Berry'ego).