Teoria informacji/TI Wykład 13

From Studia Informatyczne

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

Złożoność 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\underbrace{00\ldots 0}_{100} czy nawet

100^{\overbrace{100^{\ldots^{100}} }^{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 świadomość, ż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 zapamiętanie - 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ę, że 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 (zob. Języki, automaty i obliczenia, wykład 12), choć nie będziemy go używać bardzo intensywnie - jeśli ktoś woli, może nadal myśleć o ulubionym języku programowania. Wszystkie rozważane przez nas maszyny Turinga są deterministyczne i używają binarnego alfabetu wejściowego (\{ 0, 1 \}).

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 wykładzie 1 ze 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.

Będziemy używać następującej notacji:

  • M (w) \downarrow : maszyna M zatrzymuje się dla danych wejściowych w.
  • M (w) \uparrow : maszyna M zapętla się dla danych wejściowych w.
  • M (w) = v : M (w) \downarrow i wynikiem obliczenia jest v.


Definicja [Uniwersalna maszyna Turinga]

Uniwersalna maszyna Turinga jest to dowolna maszyna U o następujących własnościach:

(1) jeśli na wejściu jest słowo v u, 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 (u) \downarrow, to U (v u) \downarrow i M_v (u) = U (v u),

(1b) jeśli M_v (u) \uparrow, to U (v u) \uparrow.

(2) Jeśli słowo wejściowe w nie ma prefiksu będącego kodem maszyny, to U (w) \uparrow.

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

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

Innymi słowy, C_U (x) jest długością najkrótszego kodu maszyny Turinga wraz z wejściem, \langle M \rangle y, takich że M(y) = x.

Na pierwszy rzut oka definicja ta istotnie zależy od wyboru kodowania i maszyny uniwersalnej. Istotnie, przyjmując inne kodowanie, moglibyśmy otrzymać inną maszynę uniwersalną U' i w konsekwencji inną wartość C_{U'} (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', ale nie od x.

Fakt

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

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

C_U (x) \leq C_M (x) +  c_{UM}

dla każdego x.

Dowód

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

C_U (x) \leq \min \{ |\langle M \rangle | + |v| : M(v) = x \} = C_M (x) + |\langle M \rangle |.

Wystarczy więc przyjąć c_{UM} = |\langle M \rangle |.

image:End_of_proof.gif

Wniosek [niezmienniczość]

Jeśli U , U' są dwiema maszynami uniwersalnymi (być może dla różnych kodowań), to istnieje stała c_{UU'}, że
C_U (x) \leq C_{U'} (x) +  c_{UU'}

dla każdego x.

Wniosek [szacowanie]

Istnieje stała c_{U}, że
C_U (x) \leq |x| + c_{U}.

Dowód

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

image:End_of_proof.gif


Wybierając dowolną funkcję x \mapsto v, gdzie U (v) = x i |v| = C_U (x), otrzymujemy oczywiście notację. Z Faktu na temat notacji wynika, że dla każdego n istnieje słowo x długości n dla którego C_U (x) \geq |x|.

Definicja [Słowa losowe]

Słowo x spełniające C_U (x) \geq |x| nazywamy losowym (w sensie Kołmogorowa).

Intuicyjnie, w terminach języka Pascal, powiedzielibyśmy, ż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  C_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 C_U (w) \geq 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 (\mbox{bin } (n) ) = w_n. Wtedy oczywiście C_M (w_n) \leq | \mbox{bin } (n) |. Z drugiej strony, zgodnie z udowodnionym przed chwilą Faktem,

C_U (w_n) \leq C_{M} (w_n ) +  c_{UM}

a założyliśmy, że n \leq C_U (w_n), co dałoby nam

n \leq | \mbox{bin } (n) | +  c_{UM}

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

image:End_of_proof.gif

Złożoność bezprefiksowa

Wprowadzimy teraz pewne techniczne wymaganie dla maszyn Turinga, które pociągnie za sobą modyfikację pojęcia informacyjnej złożoności algorytmicznej. Ta nowa definicja jest wygodniejsza przede wszystkim przy określeniu "prawdopodobieństwa stopu" i stałej Chaitina, czym zajmiemy się na następnym wykładzie. Otóż, podobnie jak w teorii kodów, wygodnie jest wykluczyć przypadek, kiedy jedno akceptowalne słowo wejściowe jest prefiksem innego takiego słowa. Można argumentowć, że wprowadzenie odpowiedniego ograniczenia na maszyny Turinga jest zgodne z intencją złożoności Kołmogorowa, ponieważ podobna własność jest spełniona w większości języków programowania, gdzie koniec programu (również programu z danymi) jest ściśle określony.

Zbiór słów L \subseteq \{ 0,1 \}^* jest bezprefiksowy, kiedy żadne słowo w L nie jest prefiksem innego słowa w L. Maszynę Turinga M nazwiemy bezprefiksową, o ile język L (M) jest bezprefiksowy. Z samej postaci maszyny nie jest łatwo wydedukować, czy jest ona bezprefiksowa, czy nie; w istocie nietrudno jest wykazać, że w ogólności jest to problem nierozstrzygalny. Na pierwszy rzut oka jest to istotna przeszkoda dla stworzenia "bezprefiksowej maszyny uniwersalnej". Okazuje się jednak, że dowolną maszynę Turinga można w pewnym sensie efektywnie "poprawić" do maszyny bezprefiksowej i w ten sposób z listy wszystkich maszyn Turinga otrzymać listę maszyn bezprefiksowych N_0, N_1, \ldots, tak że każdy częsciowo-obliczalny język bezprefiksowy L znajdzie się na tej liście jako L = L(N_i), dla pewnego i.

W dalszym ciągu, oprócz częsciowego porządku bycia prefiksem (oznaczanego \leq) będziemy na zbiorze \{ 0,1 \}^* rozważać porządek liniowy typu \omega. Może to być na przykład tzw. porządek wojskowy, który porządkuje słowa najpierw według długości, a słowa tej samej długości leksykograficznie:

u \sqsubseteq w \Longleftrightarrow |u| < |w| \vee ( |u| = |w| \wedge (\exists x,y,y') \, u = x 0 y \wedge w = x 1 y' ) )

Fakt [Maszyny bezprefiksowe]

Istnieje algorytm, który dla danej maszyny Turinga M znajduje maszynę M' taką, że

(i) M' jest bezprefiksowa.

(ii) L(M') \subseteq L(M).

(iii) Jeśli M(x) \downarrow i dla każdego y \neq x, prefiksowo porównywalnego z x (tzn. y < x lub x < y), zachodzi M(y) \uparrow, to

M'(x) = M(x) .

W szczególności, jeśli maszyna M jest bezprefiksowa, to

L(M') = L(M).

Dowód

Mając dane M, nasz algorytm konstruuje maszynę M', której działanie opiszemy nieformalnym programem.

1. Input (dla M') = x = x_1 \ldots x_k.

2. A := \varepsilon (* A będzie przebiegać kolejne prefiksy x *).

3. Przeglądaj wszystkie słowa w \{ 0, 1 \}^* w porządku wojskowym \varepsilon = w_0, w_1, w_2, \ldots , w_i, \ldots i "ruchem zygzakowym" symuluj działanie M na wejściu A w_i.

Dokładniej, symulacja przebiega w fazach: 0,1,\ldots ,i, \ldots W i-tej fazie wykonuje się kolejny krok w obliczeniach maszyny M na słowach A w_0,  A w_1, \ldots , A w_{i-1} oraz pierwszy krok w obliczeniu M na A w_i.

Jeśli w czasie tej symulacji stwierdzisz, że M (A w_i) \downarrow, GOTO 4.

4.

if  w_i = \varepsilon  then
  if A = x  then STOP ACCEPT;
  Output =  M (A w_i ) = M(x)
  else  STOP REJECT
else
  if A = x_1 \ldots x_{\ell } , \ell < k 
  then A: = x_1 \ldots x_{\ell } x_{\ell + 1 }; GOTO 3
  else (* w_i > \varepsilon \wedge A = x *)  STOP REJECT

Bezprefiksowość maszyny M' (warunek (i)) wynika z faktu, że obliczenie dla wejścia x zawiera w sobie obliczenie dla wejścia x' < x. Gdyby więc zaszły warunki akceptacji dla wejścia x' (tzn. w_i = \varepsilon i A = x'), to w przypadku wejścia x nastąpi wyjście przez (pierwsze) STOP REJECT.

Warunek (ii) jest oczywisty, bo jeśli M' daje Output, to M'(x) = M(x).

Wreszcie, jeśli M (x) \downarrow, ale nie zachodzi to dla żadnego właściwego prefiksu ani rozszerzenia x, to ruch zygzakowy gwarantuje wykrycie M (A w_i) \downarrow, dla A = x i w_i = \varepsilon, a zatem STOP ACCEPT (warunek (iii)).

image:End_of_proof.gif


Definicja [Bezprefiksowa uniwersalna maszyna Turinga]

Bezprefiksowa uniwersalna maszyna Turinga jest to dowolna bezprefiksowa maszyna U, spełniająca warunek (2) definicji maszyny uniwersalnej oraz spełniająca waruki (1a,b), o ile v jest kodem pewnej bezprefiksowejmaszyny Turinga M_v.

(Sens: U jest uniwersalna dla maszyn bezprefiksowych.)

Maszyny takie istnieją:

Fakt

Maszyna U' otrzymana z maszyny uniwersalnej U ("zwykłej") przez konstrukcję z Faktu, jest bezprefiksową uniwersalną maszyną Turinga.

Dowód

Jedynym nieoczywistym stwierdzeniem jest, że dla bezprefiksowej maszyny, M_v (x) \downarrow pociąga za sobą U' (v x) \downarrow. Mamy U (v x) \downarrow; wystarczy więc sprawdzić, że zachodzą założenia warunku (iii) Faktu. Istotnie, dla v x < y lub v \leq y < v x, mamy U (y) \uparrow, ponieważ M_v jest z założenia bezprefiksowa i M_v (z) \uparrow \Longleftrightarrow U(vz) \uparrow. Jeśli natomiast y < v, to również U (y) \uparrow, ponieważ samo kodowanie jest bezprefiksowe (a więc y nie jest wtedy postaci \langle M \rangle  u, dla żadnej maszyny M, a w takim przypadku U się zapętla.) image:End_of_proof.gif

Definicja [Bezprefiksowa złożoność Kołmogorowa]

Bezprefiksową złożonością informacyjną Kołmogorowa słowa x jest
K_U (x) = \min \{ |v| :  U (v) = x \}

gdzie U jest bezprefiksową maszyną uniwersalną.

Kiedy wybór maszyny U nie ma znaczenia, będziemy czasem pisać po prostu K(x).

Dowód Faktu gwarantującego niezmienniczość przechodzi bez zmian.

Fakt

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

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

K_U (x) \leq K_M (x) +  c_{UM}

dla każdego x.


Natomiast nie mamy odpowiednika Wniosku, bo maszyna obliczająca identyczność nie jest bezprefiksowa.