Teoria informacji/TI Wykład 14

Stała Chaitina

Tak jak w poprzednim wykładzie, ustalamy jakieś bezprefiksowe kodowanie maszyn Turinga (przypominamy, że przykład takiego kodowania można znaleźć w 1 wykładzie z Teorii złożoności) oraz maszynę uniwersalną $U$. Będziemy pisać $M(v)\downarrow$ na oznaczenie własności maszyna M zatrzymuje się startując ze słowa wejściowego v.

Definicja [Stała Chaitina]

Stałą Chaitina określamy jako sumę szeregu $\mathrm{\Omega }=\sum _{U(v)\downarrow }{2}^{-|v|}=\sum _{M(\epsilon )\downarrow }{2}^{-|⟨M⟩|}$

Stała Chaitina jest czasem przedstawiana jako prawdopodobieństwo, że losowo wybrany program się zatrzymuje (ma to miejsce przy pewnym wyborze kodowania i miary prawdopodobieństwa). 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 }<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. Wykażemy, że (*)

$\sum _M{2}^{-|⟨M⟩|}\le 1$

(tu sumowanie rozciąga się na wszystkie maszyny Turinga, a nie tylko te, dla których $M(\epsilon )\downarrow$). Istotnie, przy bezprefikowsym kodowaniu, dla każdego skończonego zbioru maszyn ${ℳ}$, odpowiedni zbiór kodów tworzy kod bezprefiksowy, a zatem z nierówności Krafta spełnia nierówność $\sum _{M\in {ℳ}}{2}^{-|⟨M⟩|}\le 1$, co po przejściu do supremum daje nierówność (*). Ponieważ niewątpliwie istnieje maszyna, która nie zatrzymuje się na pustej taśmie, $\mathrm{\Omega }$ jest ostro mniejsza od lewej strony (*).

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.

Niech ${𝒮}=\{M:M(\epsilon )\downarrow \}.$

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$ zbioru ${𝒮}$, taki że liczba wyznaczona przez pierwszych $n$ cyfr $\mathrm{\Omega }$ przedstawia się

$0.{\omega }_1{\omega }_2\dots {\omega }_n=\sum _{M\in {{𝒮}}_n}{2}^{-⟨M⟩}$

(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 nie będące kodem żadnej maszyny, $T$ je odrzuca. Przypuśćmy, że na wejściu jest $⟨M⟩$; niech $n=|⟨M⟩|$. Maszyna $T$ symuluje działanie $M$ na $\epsilon$ (tzn. na pustej taśmie), a także przegląda kolejne kody maszyn Turinga $⟨M^{\prime }⟩$, powiedzmy w porządku wojskowym, i symuluje działanie $M^{\prime }$ na $\epsilon$. Oczywiście każda z tych maszyn może się zapętlić, dlatego $T$ nie symuluje ich "po kolei"; zamiast tego wykonuje na przemian po jednej (kolejnej) instrukcji kolejnych symulowanych maszyn.

Można to sobie wyobrazić jako "ruch zygzakowy". Jeśli przyjąć, że maszyny w porządku wojskowym tworzą ciąg $M_0,M_1,M_2,\dots$, a ${𝒲}(M_i)$ oznacza: wykonaj kolejną instrukcję maszyny $M_i$ lub skip jeśli $M_i$ już zakończyła działanie, to plan działania maszyny $T$ można przedstawić

${𝒲}(M_0){𝒲}(M_1){𝒲}(M_0){𝒲}(M_1){𝒲}(M_2){𝒲}(M_0){𝒲}(M_1){𝒲}(M_2){𝒲}(M_3){𝒲}(M_0)\dots$

W trakcie swojego obliczenia, maszyna $T$ utrzymuje zmienną, powiedzmy ${𝒮}\text{'}$, której aktualną wartością jest (skończony) zbiór kodów tych maszyn $M^{\prime },$ dla których już udało się stwierdzić, że $M^{\prime }(\epsilon )\downarrow$.

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

(i) $T$ stwierdza, że $M(\epsilon )\downarrow$; wtedy daje odpowiedź TAK.

(ii) $T$ stwierdza, że

$0.{\omega }_1{\omega }_2\dots {\omega }_n=\sum _{⟨M^{\prime }⟩\in {{𝒮}}^{\prime }}{2}^{-|⟨M^{\prime }⟩|},$

ale $M\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)={\mathrm{\Omega }}_n=0.{\omega }_1{\omega }_2\dots {\omega }_n,$

dla pewnego $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 maszyny $M^{\prime }$ i symuluje ich działanie na $\epsilon$, gromadząc w zmiennej ${𝒮}\text{'}$ kody tych maszyn, dla których obliczenie już się zakończyło. Dodatkowo, dla każdego $⟨M^{\prime }⟩\in {{𝒮}}^{\prime }$, $R$ zapamiętuje $M^{\prime }(\epsilon )$. Pamiętamy, że wykluczyliśmy już możliwość podwójnej reprezentacji $\mathrm{\Omega }$. Dlatego też, po pewnym skończonym czasie $R$ stwierdzi, że

$\sum _{⟨M^{\prime }⟩\in {{𝒮}}^{\prime }}{2}^{-|⟨M^{\prime }⟩|}={\mathrm{\Omega }}_n.$

Niech $v$ będzie pierwszym w porządku wojskowym słowem takim, że $v\ne M^{\prime }(\epsilon )$, dla każdego $⟨M^{\prime }⟩\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łą.