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 $\mathrm{\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\dots w_n\{0,1{\}}^n$, określamy

$p(w_1\dots 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,\dots$, gdzie $p(X_i=0)=p(X_i=1)=\frac{1}{2}$.

W szczególności $\mathrm{\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ść $\mathrm{\Omega }$ zależy od wyboru kodowania i maszyny uniwersalnej, ale jej istotne własności od tego nie zależą.

Twierdzenie [Własności $\mathrm{\Omega }$]

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

(1) $\mathrm{\Omega }\le 1$.

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

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

$K_U({\omega }_1\dots {\omega }_n)\ge n-c$ gdzie ${\omega }_1\dots {\omega }_n$ oznacza pierwszych $n$ bitów liczby $\mathrm{\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, $\mathrm{\Omega }$ jest niekompresowalna.

Dowód

Ad 1. Ponieważ zbiór

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

jest bezprefiksowy, każdy skończony podzbiór ${𝒮}\subseteq L(U)$, tworzy kod bezprefiksowy, a zatem z nierówności Krafta spełnia nierówność $\sum _{x\in {𝒮}}{2}^{-|x|}\le 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 $\mathrm{\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 $\mathrm{\Omega }$ była dwójkowo wymierna, tzn.

(a) $\mathrm{\Omega }=0.{\omega }_1{\omega }_2\dots {\omega }_{k}0111\dots$

(b) $\mathrm{\Omega }=0.{\omega }_1{\omega }_2\dots {\omega }_{k}1000\dots$

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 $\mathrm{\Omega }$ dana jest w postaci (a). Istotnie, gdybyśmy mieli maszynę $T$ dla tego przypadku, to łatwo moglibyśmy ją zmodyfikować do maszyny $T^{\prime }$, która radziłaby sobie z przypadkiem (b). Maszyna $T^{\prime }$ działałaby tak samo jak maszyna $T$, z tym że począwszy od $k+1$-szej cyfry $\mathrm{\Omega }$, "widziałaby na odwrót", tzn. 0 traktowałaby jak 1 a 1 jak 0.

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

$0.{\omega }_1{\omega }_2\dots {\omega }_n\le \sum _{x\in {{𝒮}}_n}{2}^{-|x|}$

(pamiętamy, że $\sum _{i=n+1}^{\mathrm{\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: $\epsilon =v_0,v_1,v_2,\dots$ 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 ${𝒮}\text{'}$, 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\dots {\omega }_n\le \sum _{v\in {{𝒮}}^{\prime }}{2}^{-|v|},$

ale $w\in ̸{{𝒮}}^{\prime }$; wtedy daje odpowiedź NIE.

Zauważmy, że w tej chwili możemy już wykluczyć możliwość, że $\mathrm{\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 $\mathrm{\Omega }$ była dwójkowo wymierna, to opisaną wyżej konstrukcję maszyny $T$ można przeprowadzić bez reprezentowania liczby $\mathrm{\Omega }$; zamiast pobierać bity liczby $\mathrm{\Omega }$ z dodatkowej nieskończonej taśmy, maszyna $T$ mogłaby je sobie łatwo obliczyć. Podobny argument pokazuje znacznie więcej: $\mathrm{\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\dots {\omega }_n,$

stanowi pierwsze $n$ cyfr rozwinięcia binarnego $\mathrm{\Omega }$, dla pewnego $n$. Niech

${\mathrm{\Omega }}_n={\omega }_1{\omega }_2\dots {\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)={\mathrm{\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 ${𝒮}\text{'}$ te słowa $y$, dla których obliczenie już się zakończyło. Dodatkowo, dla każdego $y\in {{𝒮}}^{\prime }$, $R$ zapamiętuje $U(y)$. Pamiętamy, że wykluczyliśmy już możliwość podwójnej reprezentacji $\mathrm{\Omega }$. Dlatego też, po pewnym skończonym czasie $R$ stwierdzi, że

$\sum _{y\in {{𝒮}}^{\prime }}{2}^{-|y|}\ge {\mathrm{\Omega }}_n$

Niech $v$ będzie pierwszym w porządku wojskowym słowem takim, że $v\ne U(y)$, dla każdego $y\in {{𝒮}}^{\prime }$. Zauważmy, że $K_U(v)\ge n$ (z definicji $\mathrm{\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)\le K_R(v)+c_{UR}$

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

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

i nierówność ta zachodzi dla każdego $x$, takiego że $U(x)={\mathrm{\Omega }}_n$. A zatem

$n\le K_U({\mathrm{\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)=\mathrm{\Omega },$

a nie 1.

Ale już

$p(y)=\frac{p_U(y)}{\mathrm{\Omega }}$

wyznacza prawdopodobieństwo na $\{0,1{\}}^{*}$.

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

$|\phi (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\le -{\log }_{2}p(y)\le K(y)+c$

Dowód

Oczywiście, wystarczy jeśli pokażemy $K(y)-c\le -{\log }_2{p}_U(y)\le K(y)+c$

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

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

skąd

$-{\log }_2{p}_U(y)\le |x|=K(y)$

Pozostaje dowieść, że

$K(y)\le -{\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|\le -{\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,\dots$

Z kolei rozważmy ciąg przedziałów domkniętych na prostej $I_{y_0},I_{y_1},I_{y_2},\dots$, 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

$[\underset{L}{\underbrace{a_1\cdot \frac{1}{2}+a_2\cdot \frac{1}{2^2}+\dots +a_k\cdot \frac{1}{2^k}}},L+\frac{1}{2^k}),$

gdzie $a_1,\dots ,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}+\dots +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\dots 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)\le \frac{8}{2^k}=\frac{1}{2^{k-3}}$

skąd otrzymujemy

$k-3\le -\log p_U(y),$

a zatem

$k=|w_y|\le -\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},\dots$ 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.