Teoria informacji/TI Wykład 14

From Studia Informatyczne

Stała Chaitina

Tak jak w poprzednim wykładzie, ustalamy jakieś bezprefiksowe kodowanie maszyn Turinga oraz bezprefiksową maszynę uniwersalną U.

Definicja [Stała Chaitina]

Stałą Chaitina określamy jako sumę szeregu
\Omega = \sum_{U(v)\downarrow } 2^{ - |v|}


Stałą Chaitina można interpretować jako prawdopodobieństwo, że losowo wybrane dane dla maszyny U spowodują jej zatrzymanie; innymi słowy, że losowo wybrany program (z danymi) się zatrzymuje.

Dokładniej, rozważmy zbiór nieskończonych ciągów zero-jedynkowych, \{ 0,1 \}^{\omega }. Dla w_1 \ldots w_n \{ 0,1 \}^{n}, określamy

p ( w_1 \ldots w_n \{ 0,1 \}^{\omega } ) = \frac{1}{2^n},

w szczególności p (\{ 0,1 \}^{\omega } ) = 1. Funkcję p można rozszerzyć na Borelowskie podzbiory \{ 0,1 \}^{\omega } tak, by stanowiła prawdopodobieństwo. Prawdopodobieśtwo to możemy też określić patrząc na ciąg x \in  \{ 0,1 \}^{\omega } jak na wynik nieskończonego procesu Bernoulliego X_1, X_2, \ldots, gdzie p (X_i  = 0) = p (X_i  = 1) = \frac{1}{2}.

W szczególności \Omega stanowi prawdopodobieństwo zdarzenia, że ciąg x \in  \{ 0,1 \}^{\omega } zawiera prefiks v, dla którego U ( v) \downarrow (z bezprefiksowości wynika, że jest co najwyżej jeden taki prefiks). Oczywiście konkretna wartość \Omega zależy od wyboru kodowania i maszyny uniwersalnej, ale jej istotne własności od tego nie zależą.

Twierdzenie [Własności \Omega]

Stała Chaitina ma następujące własności.

(1) \Omega \leq 1.

(2) Istnieje maszyna Turinga T z dodatkową taśmą nieskończoną, na której wypisane są kolejne cyfry binarnego rozwinięcia \Omega, która dla danego kodu \langle M \rangle maszyny M odpowiada na pytanie, czy M(\varepsilon ) \downarrow.

(3) Istnieje stała c taka, że

K_U (\omega_1 \ldots \omega_n ) \geq n - c,
gdzie \omega_1 \ldots \omega_n oznacza pierwszych n bitów liczby \Omega.


Punkt (2) oznacza, że "znając" stałą Chaitina potrafilibyśmy rozstrzygać problem stopu, natomiast (3) mówi nam, że z dokładnością do stałej, \Omega jest niekompresowalna.

Dowód

Ad 1. Ponieważ zbiór

L(U) = \{ w : U(w) \downarrow \}

jest bezprefiksowy, każdy skończony podzbiór {\cal S} \subseteq L(U), tworzy kod bezprefiksowy, a zatem z nierówności Krafta spełnia nierówność \sum_{x \in {\cal S}} 2^{ - | x |} \leq 1, co po przejściu do supremum daje żądaną nierówność.

Ad 2. Zanim opiszemy konstrukcję maszyny T, zróbmy pewne obserwacje na temat liczby \Omega. Znanym problemem w dowodach własności liczb rzeczywistych jest, że a priori liczba może mieć dwie różne reprezentacje (w szczególności binarne). Działoby się tak, gdyby liczba \Omega była dwójkowo wymierna, tzn.

(a) \Omega = 0. \omega_1 \omega_2 \ldots \omega_k 0 1 1 1 \ldots

(b) \Omega = 0. \omega_1 \omega_2 \ldots \omega_k 1 0 0 0 \ldots

Jakkolwiek w przyszłości wykluczymy taką możliwość, w tej chwili musimy jeszcze wziąć ją pod uwagę. Otóż bez zmniejszenia ogólności możemy założyć, że \Omega dana jest w postaci (a). Istotnie, gdybyśmy mieli maszynę T dla tego przypadku, to łatwo moglibyśmy ją zmodyfikować do maszyny T', która radziłaby sobie z przypadkiem (b). Maszyna T' działałaby tak samo jak maszyna T, z tym że począwszy od k+1-szej cyfry \Omega, "widziałaby na odwrót", tzn. 0 traktowałaby jak 1 a 1 jak 0.


Jeśli wybierzemy wariant (a), lub jeśli \Omega nie jest dwójkowo wymierna, to dla każdego n istnieje skończony podzbiór {\cal S}_n  \subseteq L(U), taki że liczba wyznaczona przez pierwszych n cyfr \Omega spełnia

0. \omega_1 \omega_2 \ldots \omega_n \leq       \sum_{x \in {\cal S}_n  } 2^{ - |x|  }

(pamiętamy, że \sum_{i = n+1}^{\infty } 2^{-i} = \frac{1}{2^n}).

Opiszemy teraz działanie maszyny T. Jak zwykle w takich przypadkach, opiszemy algorytm, pozostawiając Czytelnikowi jego formalizację w języku maszyn Turinga. Jeśli na wejściu jest słowo w, |w| = n, maszyna T symuluje działanie U na w, a równolegle przegląda kolejne słowa z \{ 0,1 \}^*, v, powiedzmy w porządku wojskowym: \varepsilon = v_0, v_1, v_2, \ldots i symuluje działanie U na v_i ruchem zygzakowym, podobnie jak w algorytmie z dowodu Faktu.


W trakcie swojego obliczenia, maszyna T utrzymuje zmienną, powiedzmy {\cal S}', której aktualną wartością jest (skończony) zbiór tych słów v, dla których już udało się stwierdzić, że U(v )\downarrow.

Zgodnie z powyższą oberwacją, w skończonym czasie jeden z dwóch przypadków ma miejsce.

(i) T stwierdza, że U (w )\downarrow; wtedy daje odpowiedź TAK.

(ii) T stwierdza, że

0. \omega_1 \omega_2 \ldots \omega_n \leq     \sum_{v \in {\cal S}' } 2^{ - |v | },

ale w \not\in  {\cal S}'; wtedy daje odpowiedź NIE.

Zauważmy, że w tej chwili możemy już wykluczyć możliwość, że \Omega jest liczbą dwójkowo wymierną. Istotnie, Czytelnik pamięta zapewne doskonale, że problem stopu jest nierozstrzygalny, tzn. nie istnieje maszyna bez dodatkowej taśmy, realizująca postulat z warunku (2). Gdyby jednak \Omega była dwójkowo wymierna, to opisaną wyżej konstrukcję maszyny T można przeprowadzić bez reprezentowania liczby \Omega; zamiast pobierać bity liczby \Omega z dodatkowej nieskończonej taśmy, maszyna T mogłaby je sobie łatwo obliczyć. Podobny argument pokazuje znacznie więcej: \Omega nie jest liczba wymierną ani algebraiczną, ani w ogole "obliczalną" (zobacz Ćwiczenie).


Ad 3. Opiszemy działanie pewnej maszyny R. Na słowie wejściowym x, R najpierw symuluje działanie maszyny uniwersalnej U na słowie x. Dalszy opis prowadzimy przy założeniu, że obliczenie się zakończyło z wynikiem U(x) i co więcej

U(x) =  \omega_1 \omega_2 \ldots \omega_n ,

stanowi pierwsze n cyfr rozwinięcia binarnego \Omega, dla pewnego n. Niech

\Omega_n =  \omega_1 \omega_2 \ldots \omega_n .

Oczywiście, dla wielu x nie będzie to prawdą; wtedy maszyna R zgodnie z naszym opisem będzie wykonywać jakieś działania, których wynik nas nie interesuje. Ważne jest jednak, że dla pewnego x istotnie zajdzie U(x) = \Omega_n (z własności maszyny uniwersalnej).

Z kolei, podobnie jak maszyna T w dowodzie punktu (2), maszyna R ruchem zygzakowym przegląda kolejne słowa y i symuluje działanie na U na y, gromadząc w zmiennej {\cal S}' te słowa y, dla których obliczenie już się zakończyło. Dodatkowo, dla każdego y \in {\cal S}', R zapamiętuje U(y). Pamiętamy, że wykluczyliśmy już możliwość podwójnej reprezentacji \Omega. Dlatego też, po pewnym skończonym czasie R stwierdzi, że

\sum_{y \in {\cal S}' } 2^{ - |y | } \geq \Omega_n .

Niech v będzie pierwszym w porządku wojskowym słowem takim, że v \neq U(y), dla każdego y \in {\cal S}'. Zauważmy, że K_U ( v ) \geq n (z definicji \Omega). Wtedy wreszcie nasza maszyna R zatrzymuje się z wynikiem R (x) = v.

Zgodnie z Faktem z poprzedniego wykładu, istnieje stała c_{UR}, że

K_U (v) \leq K_R (v) +  c_{UR} .

Ale K_R (v) \leq |x| (skoro R wygenerowała v z wejścia x). To daje nam

n \leq K_U (v) \leq K_R (v) +  c_{UR} \leq |x| +  c_{UR}

i nierówność ta zachodzi dla każdego x, takiego że U (x) = \Omega_n. A zatem

n \leq K_U (\Omega_n ) +  c_{UR}

dla każdego n, tak więc c = c_{UR} może być żądaną stałą.

image:End_of_proof.gif

Związek z entropią Shannona

Jeśli stałą Chaitina interpretujemy jako prawdopodobieństwo, że bezprefiksowa maszyna uniwersalna U się zatrzymuje, to dla y \in \{ 0,1 \}^*,

p_U (y) = \sum_{v: U(v) = y } 2^{ - |v|}

stanowi prawdopodobieństwo zdarzenia, że maszyna U zatrzymuje się z wynikiem y.

Zauważmy, że p_U nie stanowi miary prawdopodobieństwa na \{ 0,1 \}^*, w szczególności

\sum_{y \in \{ 0,1 \}^*} p_U (y) = \Omega , a nie 1.

Ale już

p(y) = \frac{p_U (y)}{\Omega }
wyznacza prawdopodobieństwo na \{ 0,1 \}^*.


Jak pamiętamy z wykładu 3, dla skończonej przestrzeni probabilistycznej S, optymalne kodowanie \varphi : S \to \{ 0,1 \}^* było osiągnięte wtedy, gdy

|\varphi (y) | \approx - \log_2 (p (y) )

Dokładniej, równość była osiągnięta dla prawdopodobieństw będących potęgami \frac{1}{2}, a w ogólności mamy zbieżność asymptotyczną.

Otóż podobny związek możemy wskazać dla bezprefiksowej złożoności Kołmogorowa, która w pewnym sensie wyznacza optymalne kodowanie słów w \{ 0,1 \}^*, przy określonym wyżej prawdopodobieństwie p.

Mówiąc nieformalnie, mamy

K (y) \approx - \log_2 p (y) .

Dokładniej, pokażemy następujący

Fakt [Entropia Kołmogorowa]

Istnieje stała c, że dla dowolnego y \in \{ 0,1 \}^*,
K(y) - c \leq - \log_2 p (y)  \leq K(y) + c.

Dowód

Oczywiście, wystarczy jeśli pokażemy
K(y) - c \leq - \log_2 p_U (y)  \leq K(y) + c.

Mamy K(y) = |x|, dla pewnego x, takiego, że U (x) = y, a zatem

\frac{1}{2^{|x|}} \leq p_U (y),

skąd

- \log_2 p_U (y)   \leq |x| = K(y) .

Pozostaje dowieść, że

K(y) \leq - \log_2 p_U (y)  +c,

dla pewnej stałej c. Wobec Faktu o niezmienniczości, wystarczy tym celu skonstruować maszynę T taką, że T (w_y) = y oraz

|w_y | \leq - \log_2 p_U (y)  +c,

gdzie T i c nie zależą od y.

Ustawmy wszystkie słowa y \in \{ 0,1 \}^* w porządku wojskowym: y_0, y_1, y_2, \ldots

Z kolei rozważmy ciąg przedziałów domkniętych na prostej I_{y_0}, I_{y_1}, I_{y_2}, \ldots, gdzie początkiem I_{y_0} jest 0; koniec I_{y_m} jest początkiem I_{y_{m+1}} i długością przedziału I_{y_m} jest p_U (y_m).

Zauważmy, że suma wszystkich przedziałów I_{y_m} zawiera się w odcinku [0,1].

Przedziałem binarnym jest z definicji przedział postaci

\left[ \underbrace{a_1 \cdot \frac{1}{2} + a_2 \cdot \frac{1}{2^2} + \ldots + a_k \cdot \frac{1}{2^k}}_L, L + \frac{1}{2^k} \right),

gdzie a_1, \ldots , a_k \in \{ 0, 1\}; a_k = 1.

Dla przedziału I_y, znajdźmy największy przedział binarny J w nim zawarty, a gdyby było więcej przedziałów o tej samej długości, to ten, którego początek jest położony najbardziej na lewo. Niech L = a_1 \cdot \frac{1}{2} + a_2 \cdot \frac{1}{2^2} + \ldots + a_k \cdot \frac{1}{2^k} będzie początkiem tego największego przedziału binarnego. Połóżmy

w_y =  a_1 a_2 \ldots a_k

(a zatem |w_y | = k).

Oszacujemy teraz długość przedziału I_y (równą p_U (y)) w zależności od k.

Kluczowe jest spostrzeżenie, ile kroków długości \frac{1}{2^k} możemy zrobić z punktu L w lewo lub w prawo, pozostając cały czas w przedziale I_y. Analiza przypadków pokazuje, że możemy zrobić co najwyżej 2 kroki w lewo i 5 kroków w prawo. W każdym razie długość przedziału I_y spełnia nierówność

p_U (y) \leq \frac{8}{2^k} = \frac{1}{2^{k-3}}

skąd otrzymujemy

k-3 \leq   - \log p_U (y),

a zatem

k = | w_y | \leq - \log p_U (y) + 3

Pozostaje pokazać, że znając w_y, potrafimy algorytmicznie odtworzyć y, a zatem żądana maszyna T, taka że T(w_y) = y, istnieje. Konstrukcja jest żmudna, ale rutynowa. Używając ruchu zygzakowego, znajdujemy coraz lepsze przybliżenia końców przedziałów I_{y_0}, I_{y_1}, I_{y_2}, \ldots tak długo, aż zdobywamy pewność, że liczba reprezentowana przez w_y znajduje się w przedziale I_y, jest to właśnie poszukiwane y. Zauważmy, że dla każdego n, od pewnego momentu krańce przedziałów mogą się przesuwać co najwyżej o \frac{1}{2^n}, a zatem oczekiwana chwila nastąpi.

image:End_of_proof.gif