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 potrafilibyśmy się nauczyć na pamięć wybranej księgi ,,Pana Tadeusza" (a może nawet całego 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; wystarczy wtedy zapamiętać ów krótszy ,,opis". W pierwszym przybliżeniu, za złożoność liczby bylibysmy więc skłonni uznać długość jej najkrótszego opisu. Jednak widzieliśmy już na pierwszym wykładzie, że takie postawienie sprawy prowadzi do paradoksu Berry'ego, dlatego też wprowadziliśmy wtedy pojęcie notacji.

A jednak - po lepszym zrozumieniu - idea najktótszego opisu prowadzi do sensownej miary złożoności, którą przedstawimy na tym wykładzie.

Przyjmiemy, że obiekty, które chcemy opisywać, to słowa nad alfabetem $\{0,1\}$; zarówno liczby naturalne, jak też słowa nad większymi alfabetami można łatwo sprowadzić do tego przypadku.

Ideą Kołmogorowa było, by za złożoność słowa $w$ przyjąć długość najkrótszego programu generującego to słowo, przy wybranym języku programowania, np. języku Pascal. W istocie Kołmogorow nie użył języka Pascal, lecz uniwersalnej maszyny Turinga, jednak -- jak wkrótce się przekonamy -- wybór ten nie ma większego znaczenia, podobnie jak zresztą wybór innego języka programowania (np. C++ zamiast Pascala).

Zakładamy, że Czytelnik jest zaznajomiony z pojęciem maszyny Turinga, choć nie będziemy go uzywać bardzo intensywnie -- jeśli ktoś woli, może nadal myśleć o ulubionym języku programowania. Ważną własnością maszyn Turinga jest, że można je kodować za pomocą słów binarnych, jedno z wielu możliwych kodowań opisane jest w pierwszym wykładzie z Złożoności obliczeniowej. Nie jest przy tym trudno zagwarantować, by kodowanie było bezprefiksowe (tzn. żaden kod nie jest właściwym prefiksem innego).

Zakładając ustalone kodowanie, Turing podał konstrukcję maszyny uniwersalnej (zob. Języki, automaty i obliczenia, Wykład 12).

Definicja [Uniwersalna maszyna Turinga]

Uniwersalna maszyna Turinga ma następujące własności:

(1) jeśli na wejściu jest $w=vu$, gdzie $v$ jest kodem pewnej maszyny $M_v$, to $U$ symuluje działanie $M_v$ na $u$.

W szczególności

(1a) jeśli $M_v$ się zatrzymuje, to $U$ też się zatrzymuje z tym samym wynikiem, który oznaczamy $U(w)$ ($=M_v(u)$),

(1b) jeśli $M_v$ się zapętla, to $U$ też się zapętla.

(2) jeśli słowo wejściowe $w$ nie ma prefiksu będącego kodem maszyny, to $U$ się zapętla.

Zauważmy, że w powyższej definicji słowo $u$ może być puste; wtedy $U$ symuluje działanie $M_v$ startującej przy pustej taśmie. Właśnie ten przypadek będzie nas szczególnie interesował.

Definicja [Złożoność Kołmogorowa]

Złożonością informacyjną Kołmogorowa słowa x jest $K_U(x)=\min \{|v|:v\text{ jest kodem i }U(v)=x\}$

Innymi słowy, $K_U(x)$ jest najkrótszym kodem maszyny, która generuje $x$ startując z pustej taśmy.

Na pierwszy rzut oka definicja ta istotnie zależy od wyboru kodowania. Istotnie, przyjmując inne kodowanie, moglibyśmy otrzymać inną maszynę uniwersalną $U^{\prime }$ i w konsekwencji inną wartość $K_{U^{\prime }}(x)$. Okazuje się jednak, że nie polepszymy w ten sposób złożoności Kołmogorowa więcej niż o stałą (zależną od $U$ i $U^{\prime }$, ale nie od $x$.

Fakt

Niech $M$ będzie dowolną maszyną Turinga i niech $K_M(x)=\min \{|v|:M(v)=x\}.$

Wtedy istnieje taka stała $c_{UM}$, że

$K_U(x)\le K_M(x)+c_{UM}$

dla każdego $x$.

Dowód

Niech $⟨M⟩$ oznacza kod maszyny $M$. Wtedy, zgodnie z definicją $U$, $M(v)=U(⟨M⟩v)$, dla każdego $v$, dla którego którakolwiek ze stron jest określona. Mamy więc

$K_U(x)\le \min \{|⟨M⟩|+|v|:M(v)=x\}=K_M(x)+|⟨M⟩|.$

Wystarczy więc przyjąć $c_{UM}=|⟨M⟩|$.

Wniosek 1

Jeśli $U,U^{\prime }$ są dwiema maszynami uniwersalnymi (być może dla różnych kodowań), to istnieje stała $c_{U{U}^{\prime }}$, że $K_U(x)\le K_{U^{\prime }}(x)+c_{U{U}^{\prime }}$

dla każdego $x$.

Dowód

W powyższym fakcie wystarczy przyjąć za $M$ modyfikację maszyny $U^{\prime }$, która zatrzymuje się tylko wtedy, gdy wejście jest dokładnie kodem pewnej maszyny Turinga (w sensie kodowania dla $U^{\prime }$).

Wniosek 2

Istnieje stała $c_U$, że $K_U(x)\le |x|+c_U.$

Dowód

W powyższym fakcie wystarczy przyjąć za $M$ maszynę obliczajacą funkcję identycznościową.

Wybierając dowolną funkcję $x\mapsto v$, gdzie $v$ jest kodem maszyny takiej, że $|v|=K_U(x)$, otrzymujemy oczywiście notację. Z Faktu na temat notacji wynika, że dla każdego $n$ istnieje słowo $x$, dla którego $K_U(x)\ge |x|$.

Definicja [Słowa losowe]

Słowo x spełniające $K_U(x)\ge |x|$ nazywamy losowym (w sensie Kołmogorowa).

Intuicyjnie, w terminach języka Pascal, powiedzielibysmy, że są to słowa, dla których nie ma istotnie lepszego programu niż write ('$x$').

Wspomniana powyżej notacja $x\mapsto v$ wydaje się być bardzo sensowną propozycją, ma jednak poważną wadę: przy żadnym wyborze tej funkcji nie jest obliczalna. W równoważnym sformułowaniu, mamy następujące

Twierdzenie

Funkcja $x\mapsto K_U(x)$ nie jest obliczalna.

Dowód

Dowód oparty jest na pomyśle paradoksu Berry'ego: dla każdego $n$ znajdujemy słowo $w_n$, którego ,,opis wymaga $n$ symboli" i w ten sposób dochodzimy do sprzeczności.

Przypuśćmy, że powyższa funkcja jest obliczalna. Wówczas obliczalna byłaby również funkcja, która binarną reprezentację liczby $n$ (oznaczmy ją bin ($n$)) przekształca na pierwsze w porządku wojskowym słowo $w$, takie że $K_U(w)\ge n$ (oznaczmy je $w_n$; porządek wojskowy porządkuje wszystkie słowa najpierw według długości a potem leksykograficznie). Niech $M$ będzie maszyną realizującą tę funkcję, tzn. $M(\text{bin }(n))=w_n$. Wtedy oczywiście $K_M(w_n)\le |\text{bin }(n)|$. Z drugiej strony, zgodnie z udowodnionym przed chwilą Faktem,

$K_U(w_n)\le K_M(w_n)+c_{UM}$

a założyliśmy, że $n\le K_U(w_n)$, co dałoby nam

$n\le |\text{bin }(n)|+c_{UM}$

dla wszystkich $n$, co jest oczywiście niemożliwe.