Teoria informacji/TI Wykład 14

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}0111\ldots$

(b) $\Omega =0.\omega _{1}\omega _{2}\ldots \omega _{k}1000\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łą.

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$ .

Rozważmy punkty $L-{\frac {1}{2^{k}}},L,L+{\frac {1}{2^{k}}}+{\frac {1}{2^{k-1}}}$ i niech $A$ i $B$ będą odpowiednio początkiem i końcem przedziału $I_{y}$ .