Teoria informacji/TI Wykład 14: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m (Zastępowanie tekstu – „<math> ” na „<math>”)
 
(Nie pokazano 9 wersji utworzonych przez 2 użytkowników)
Linia 10: Linia 10:




Stałą Chaitina można interpretować jako prawdopodobieństwo, że losowo wybrane dane dla maszyny <math>U </math>
Stałą Chaitina można interpretować jako prawdopodobieństwo, że losowo wybrane dane dla maszyny <math>U</math>
spowodują jej zatrzymanie; innymi słowy, że losowo wybrany program (z danymi) się zatrzymuje.
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,
Dokładniej, rozważmy zbiór nieskończonych ciągów zero-jedynkowych,
<math> \{ 0,1 \}^{\omega }</math>. Dla <math> w_1 \ldots w_n \{ 0,1 \}^{n}</math>, określamy
<math>\{ 0,1 \}^{\omega }</math>. Dla <math>w_1 \ldots w_n \{ 0,1 \}^{n}</math>, określamy
<center><math>
<center><math>
p ( w_1 \ldots w_n \{ 0,1 \}^{\omega } ) = \frac{1}{2^n},
p ( w_1 \ldots w_n \{ 0,1 \}^{\omega } ) = \frac{1}{2^n}</math>,</center>
</math></center>
w szczególności <math>p (\{ 0,1 \}^{\omega } ) = 1</math>. Funkcję  <math>p</math>
w szczególności <math>p (\{ 0,1 \}^{\omega } ) = 1</math>. Funkcję  <math> p</math>
można rozszerzyć na Borelowskie podzbiory <math>\{ 0,1 \}^{\omega }</math> tak, by stanowiła  
można rozszerzyć na Borelowskie podzbiory <math> \{ 0,1 \}^{\omega }</math> tak, by stanowiła  
prawdopodobieństwo. Prawdopodobieśtwo to możemy też określić patrząc na ciąg  
prawdopodobieństwo. Prawdopodobieśtwo to możemy też określić patrząc na ciąg  
<math>x \in  \{ 0,1 \}^{\omega }</math> jak na wynik nieskończonego procesu Bernoulliego  
<math>x \in  \{ 0,1 \}^{\omega }</math> jak na wynik nieskończonego procesu Bernoulliego  
<math>X_1, X_2, \ldots </math>, gdzie <math> p (X_i  = 0) = p (X_i  = 1) = \frac{1}{2}</math>.
<math>X_1, X_2, \ldots</math>, gdzie <math>p (X_i  = 0) = p (X_i  = 1) = \frac{1}{2}</math>.


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


{{twierdzenie|[Własności <math> \Omega </math>]|Chaitin_property|Stała Chaitina ma następujące własności.
{{twierdzenie|[Własności <math>\Omega</math>]|Chaitin_property|Stała Chaitina ma następujące własności.


(1) <math> \Omega \leq 1</math>.
(1) <math>\Omega \leq 1</math>.


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


(3) Istnieje stała <math> c </math> taka, że  
(3) Istnieje stała <math>c</math> taka, że  


<center><math>
<center><math>
K_U (\omega_1 \ldots \omega_n ) \geq n - c, </math></center>
K_U (\omega_1 \ldots \omega_n ) \geq n - c</math></center>
gdzie <math>\omega_1 \ldots \omega_n </math> oznacza pierwszych <math> n </math> bitów liczby <math>\Omega </math>.}}
gdzie <math>\omega_1 \ldots \omega_n</math> oznacza pierwszych <math>n</math> bitów liczby <math>\Omega</math>.}}




Punkt (2) oznacza, że "znając" stałą Chaitina potrafilibyśmy rozstrzygać problem stopu, natomiast
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, <math>\Omega </math> jest niekompresowalna.
(3) mówi nam, że z dokładnością do stałej, <math>\Omega</math> jest niekompresowalna.


{{dowod|||
{{dowod|||
Linia 55: Linia 54:
jest bezprefiksowy,  
jest bezprefiksowy,  
każdy skończony podzbiór  
każdy skończony podzbiór  
<math>{\cal S} \subseteq L(U) </math>,  
<math>{\cal S} \subseteq L(U)</math>,  
tworzy [[Teoria informacji/TI Wykład 1#kod|kod bezprefiksowy]], a zatem z  
tworzy [[Teoria informacji/TI Wykład 1#kod|kod bezprefiksowy]], a zatem z  
[[Teoria informacji/TI Wykład 1#kraft| nierówności Krafta]] spełnia nierówność
[[Teoria informacji/TI Wykład 1#kraft| nierówności Krafta]] spełnia nierówność
Linia 63: Linia 62:
co po przejściu do supremum daje żądaną nierówność.
co po przejściu do supremum daje żądaną nierówność.


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


(a) <math> \Omega = 0. \omega_1 \omega_2 \ldots \omega_k 0 1 1 1 \ldots </math>
(a) <math>\Omega = 0. \omega_1 \omega_2 \ldots \omega_k 0 1 1 1 \ldots</math>


(b) <math> \Omega = 0. \omega_1 \omega_2 \ldots \omega_k 1 0 0 0 \ldots </math>
(b) <math>\Omega = 0. \omega_1 \omega_2 \ldots \omega_k 1 0 0 0 \ldots</math>


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






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


<center><math>
<center><math>
Linia 90: Linia 89:
\sum_{x \in {\cal S}_n  } 2^{ - |x|  }           
\sum_{x \in {\cal S}_n  } 2^{ - |x|  }           
</math></center>
</math></center>
(pamiętamy, że <math> \sum_{i = n+1}^{\infty } 2^{-i} = \frac{1}{2^n} </math>).
(pamiętamy, że <math>\sum_{i = n+1}^{\infty } 2^{-i} = \frac{1}{2^n}</math>).


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




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


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


'''(i)''' <math> T </math> stwierdza, że <math> U (w )\downarrow </math>; wtedy daje odpowiedź
'''(i)''' <math>T</math> stwierdza, że <math>U (w )\downarrow</math>; wtedy daje odpowiedź
'''TAK'''.
'''TAK'''.


'''(ii)''' <math> T </math> stwierdza, że
'''(ii)''' <math>T</math> stwierdza, że
<center><math>
<center><math>
0. \omega_1 \omega_2 \ldots \omega_n \leq     
0. \omega_1 \omega_2 \ldots \omega_n \leq     
Linia 120: Linia 119:
'''NIE'''.
'''NIE'''.


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




Ad 3.  Opiszemy działanie pewnej maszyny <math> R </math>.  Na słowie wejściowym <math> x </math>,
Ad 3.  Opiszemy działanie pewnej maszyny <math>R</math>.  Na słowie wejściowym <math>x</math>,
<math> R </math> najpierw symuluje działanie maszyny uniwersalnej <math> U </math> na
<math>R</math> najpierw symuluje działanie maszyny uniwersalnej <math>U</math> na
słowie <math> x </math>. Dalszy opis prowadzimy przy założeniu, że obliczenie się zakończyło
słowie <math>x</math>. Dalszy opis prowadzimy przy założeniu, że obliczenie się zakończyło
z wynikiem <math> U(x) </math> i co więcej
z wynikiem <math>U(x)</math> i co więcej
<center><math>
<center><math>
U(x) =  \omega_1 \omega_2 \ldots \omega_n ,           
U(x) =  \omega_1 \omega_2 \ldots \omega_n ,           
</math></center>
</math></center>
stanowi pierwsze <math> n </math> cyfr rozwinięcia binarnego <math> \Omega </math>,  
stanowi pierwsze <math>n</math> cyfr rozwinięcia binarnego <math>\Omega</math>,  
dla pewnego <math> n </math>. Niech
dla pewnego <math>n</math>. Niech
<center> <math> \Omega_n =  \omega_1 \omega_2 \ldots \omega_n . </math></center>
<center> <math>\Omega_n =  \omega_1 \omega_2 \ldots \omega_n </math></center>


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


Z kolei, podobnie jak maszyna  <math> T </math> w dowodzie punktu (2), maszyna <math> R </math> ruchem zygzakowym
Z kolei, podobnie jak maszyna  <math>T</math> w dowodzie punktu (2), maszyna <math>R</math> ruchem zygzakowym
przegląda  kolejne  słowa  <math> y </math> i symuluje
przegląda  kolejne  słowa  <math>y</math> i symuluje
działanie na <math> U </math> na <math> y </math>, gromadząc w zmiennej <math> {\cal S}' </math>
działanie na <math>U</math> na <math>y</math>, gromadząc w zmiennej <math>{\cal S}'</math>
te słowa <math> y </math>, dla których obliczenie już się zakończyło. Dodatkowo, dla każdego
te słowa <math>y</math>, dla których obliczenie już się zakończyło. Dodatkowo, dla każdego
<math> y \in {\cal S}' </math>, <math> R </math> zapamiętuje
<math> y \in {\cal S}'</math>, <math>R</math> zapamiętuje
<math> U(y) </math>.  
<math>U(y)</math>.  
Pamiętamy, że wykluczyliśmy już możliwość podwójnej reprezentacji <math> \Omega</math>. Dlatego też,
Pamiętamy, że wykluczyliśmy już możliwość podwójnej reprezentacji <math>\Omega</math>. Dlatego też,
po pewnym skończonym czasie <math> R </math> stwierdzi, że
po pewnym skończonym czasie <math>R</math> stwierdzi, że
<center><math>
<center><math>
\sum_{y \in {\cal S}' } 2^{ - |y | } \geq \Omega_n .
\sum_{y \in {\cal S}' } 2^{ - |y | } \geq \Omega_n </math></center>
</math></center>
Niech  <math>v</math> będzie pierwszym w porządku wojskowym słowem takim, że
Niech  <math> v </math> będzie pierwszym w porządku wojskowym słowem takim, że
<math>v \neq U(y)</math>, dla każdego <math>y \in {\cal S}'</math>.
<math> v \neq U(y) </math>, dla każdego <math> y \in {\cal S}' </math>.
Zauważmy, że  <math>K_U ( v ) \geq n</math> (z definicji <math>\Omega</math>).  
Zauważmy, że  <math> K_U ( v ) \geq n </math> (z definicji <math> \Omega</math>).  
Wtedy wreszcie nasza maszyna <math>R</math> zatrzymuje się z wynikiem <math>R (x) = v</math>.
Wtedy wreszcie nasza maszyna <math> R </math> zatrzymuje się z wynikiem <math> R (x) = v</math>.


Zgodnie z [[Teoria informacji/TI Wykład 13#fakt_Kolmogorowa|Faktem]] z poprzedniego wykładu,
Zgodnie z [[Teoria informacji/TI Wykład 13#fakt_Kolmogorowa|Faktem]] z poprzedniego wykładu,
istnieje stała  
istnieje stała  
<math> c_{UR} </math>, że
<math>c_{UR}</math>, że
<center><math>
<center><math>
K_U (v) \leq K_R (v) +  c_{UR} .
K_U (v) \leq K_R (v) +  c_{UR} </math></center>
</math></center>
Ale <math>K_R (v) \leq |x|</math> (skoro <math>R</math> wygenerowała <math>v</math>
Ale <math> K_R (v) \leq |x| </math> (skoro <math> R </math> wygenerowała <math> v </math>
z wejścia <math>x</math>). To daje nam
z wejścia <math> x </math>). To daje nam
<center><math>
<center><math>
n \leq K_U (v) \leq K_R (v) +  c_{UR} \leq |x| +  c_{UR}  
n \leq K_U (v) \leq K_R (v) +  c_{UR} \leq |x| +  c_{UR}  
</math></center>
</math></center>
i nierówność ta zachodzi dla każdego <math> x </math>, takiego że  
i nierówność ta zachodzi dla każdego <math>x</math>, takiego że  
<math> U (x) = \Omega_n </math>. A zatem
<math>U (x) = \Omega_n</math>. A zatem
<center><math>
<center><math>
n \leq K_U (\Omega_n ) +  c_{UR}  
n \leq K_U (\Omega_n ) +  c_{UR}  
</math></center>
</math></center>
dla każdego <math> n </math>, tak więc <math> c = c_{UR} </math> może być żądaną stałą.
dla każdego <math>n</math>, tak więc <math>c = c_{UR}</math> może być żądaną stałą.
}}
}}


Linia 185: Linia 182:


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


<center><math>
<center><math>
Linia 191: Linia 188:
</math></center>
</math></center>


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


Zauważmy, że <math>p_U </math> nie stanowi miary prawdopodobieństwa na <math>\{ 0,1 \}^* </math>,
Zauważmy, że <math>p_U</math> nie stanowi miary prawdopodobieństwa na <math>\{ 0,1 \}^*</math>,
w szczególności
w szczególności
<center><math>
<center><math>
\sum_{y \in \{ 0,1 \}^*} p_U (y) = \Omega ,
\sum_{y \in \{ 0,1 \}^*} p_U (y) = \Omega </math>,
</math>
a nie 1.  
a nie 1.  
</center>
</center>
Linia 204: Linia 200:


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




Jak pamiętamy z wykładu [[Teoria informacji/TI Wykład 3|3]], dla skończonej przestrzeni probabilistycznej
Jak pamiętamy z wykładu [[Teoria informacji/TI Wykład 3|3]], dla skończonej przestrzeni probabilistycznej
<math>S </math>, optymalne kodowanie <math>\varphi : S \to \{ 0,1 \}^*</math> było osiągnięte wtedy, gdy
<math>S</math>, optymalne kodowanie <math>\varphi : S \to \{ 0,1 \}^*</math> było osiągnięte wtedy, gdy


<center><math>
<center><math>
Linia 217: Linia 213:


Dokładniej, [[Teoria informacji/TI Wykład 3#kod_entropia|równość]] była osiągnięta  dla prawdopodobieństw
Dokładniej, [[Teoria informacji/TI Wykład 3#kod_entropia|równość]] była osiągnięta  dla prawdopodobieństw
będących potęgami <math>\frac{1}{2} </math>, a w ogólności mamy  
będących potęgami <math>\frac{1}{2}</math>, a w ogólności mamy  
[[Teoria informacji/TI Wykład 4#pierwsze|zbieżność asymptotyczną]].
[[Teoria informacji/TI Wykład 4#pierwsze|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 <math>\{ 0,1 \}^* </math>, przy określonym wyżej prawdopodobieństwie <math>p</math>.
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 <math>\{ 0,1 \}^*</math>, przy określonym wyżej prawdopodobieństwie <math>p</math>.


Mówiąc nieformalnie, mamy
Mówiąc nieformalnie, mamy
<center><math>
<center><math>
K (y) \approx - \log_2 (p (y) ).
K (y) \approx - \log_2 p (y) </math></center>
</math></center>


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


{{fakt|[Entropia Kołmogorowa]|entro_kol|Istnieje stała <math>c</math>, że dla dowolnego <math>y \in \{ 0,1 \}^* </math>,  
{{fakt|[Entropia Kołmogorowa]|entro_kol|Istnieje stała <math>c</math>, że dla dowolnego <math>y \in \{ 0,1 \}^*</math>,  
<center><math>
<center><math>
K(y) - c \leq - \log_2 (p (y) ) \leq K(y) + c.
K(y) - c \leq - \log_2 p (y) \leq K(y) + c</math></center>
</math></center>
}}
}}


{{dowod|||Oczywiście, wystarczy jeśli pokażemy
{{dowod|||Oczywiście, wystarczy jeśli pokażemy
<center><math>
<center><math>
K(y) - c \leq - \log_2 (p_U (y) ) \leq K(y) + c.
K(y) - c \leq - \log_2 p_U (y) \leq K(y) + c</math></center>
</math></center>
Mamy <math>K(y) = |x|</math>, dla pewnego <math>x</math>,  takiego, że <math>U (x) = y</math>,
Mamy <math>K(y) = |x|</math>, dla pewnego <math>x</math>,  takiego, że <math>U (x) = y</math>,
a zatem
a zatem
<center><math>
<center><math>
\frac{1}{2^{|x|}} \leq p_U (y),
\frac{1}{2^{|x|}} \leq p_U (y)</math>,</center>
</math></center>
skąd
skąd
<center><math>
<center><math>
  - \log_2 (p_U (y) \leq |x| = K(y) .
  - \log_2 p_U (y)   \leq |x| = K(y) </math></center>
</math></center>
Pozostaje dowieść, że
Pozostaje dowieść, że
<center><math>
<center><math>
K(y) \leq - \log_2 (p_U (y) ) +c,
K(y) \leq - \log_2 p_U (y) +c</math>,</center>
</math></center>
dla pewnej stałej <math>c</math>. Wobec [[Teoria informacji/TI Wykład 13#fakt_bez_Kolmogorowa|Faktu]] o niezmienniczości, wystarczy tym celu skonstruować maszynę <math>T</math> taką, że <math>T (w_y) = y</math> oraz
dla pewnej stałej <math>c</math>. Wobec [[Teoria informacji/TI Wykład 13#fakt_bez_Kolmogorowa|Faktu]] o niezmienniczości, wystarczy tym celu skonstruować maszynę <math>T</math> taką, że <math>T (w_y) = y</math> oraz
<center><math>
<center><math>
|w_y | \leq - \log_2 (p_U (y) ) +c,
|w_y | \leq - \log_2 p_U (y) +c</math>,</center>
</math></center>
gdzie <math>T</math> i <math>c</math> nie zależą od <math>y</math>.
gdzie <math>T</math> i <math>c</math> nie zależą od <math>y</math>.


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


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


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


''Przedziałem binarnym'' jest z definicji przedział postaci
''Przedziałem binarnym'' jest z definicji przedział postaci
<center><math>
<center><math>
[\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})
\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)</math>,</center>
</math></center>
gdzie <math>a_1, \ldots , a_k \in \{ 0, 1\}</math>; <math>a_k = 1</math>.
 
Dla przedziału <math>I_y</math>, znajdźmy największy przedział binarny <math>J</math> 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 <math>L = a_1 \cdot \frac{1}{2} + a_2 \cdot \frac{1}{2^2} + \ldots + a_k \cdot \frac{1}{2^k}</math> będzie początkiem tego największego przedziału binarnego. Połóżmy
Dla przedziału <math>I_y</math>, znajdźmy największy przedział binarny <math>J</math> 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 <math>L = a_1 \cdot \frac{1}{2} + a_2 \cdot \frac{1}{2^2} + \ldots + a_k \cdot \frac{1}{2^k}</math> będzie początkiem tego największego przedziału binarnego. Połóżmy
<center><math>
<center><math>
w_y =  a_1 a_2 \ldots a_k  
w_y =  a_1 a_2 \ldots a_k  
</math></center>
</math></center>
(a zatem <math>|w_y | = k </math>).
(a zatem <math>|w_y | = k</math>).


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


Rozważmy punkty <math> L - \frac{1}{2^k}, L, L + \frac{1}{2^{k}}, L + \frac{1}{2^{k-1}}</math> i niech <math> A</math> i <math> B</math> będą odpowiednio początkiem i końcem przedziału <math>I_y</math>.
Kluczowe jest spostrzeżenie, ile kroków długości <math>\frac{1}{2^k}</math> możemy zrobić z punktu <math>L</math> w lewo lub w prawo, pozostając cały czas w przedziale <math>I_y</math>. 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 <math>I_y</math> spełnia nierówność
 
<center><math>
Nie może być <math> A \leq L - \frac{1}{2^k} </math>, bo wtedy
p_U (y) \leq \frac{8}{2^k} = \frac{1}{2^{k-3}}
</math></center>
skąd otrzymujemy
<center><math>
k-3 \leq  - \log p_U (y)</math>,</center>
a zatem
<center><math>
<center><math>
[\underbrace{a_1 \cdot \frac{1}{2} + a_2 \cdot \frac{1}{2^2} + \ldots + a_{k-1} \cdot \frac{1}{2^{k-1}}}_{L - \frac{1}{2^k}}, (L - \frac{1}{2^k}) + \frac{1}{2^{k-1}})
k = | w_y | \leq - \log p_U (y) + 3
</math></center>
</math></center>
byłby większym przedziałem binarnym zawartym w <math>I_y</math>.
Pozostaje pokazać, że znając <math>w_y</math>, potrafimy algorytmicznie odtworzyć <math>y</math>, a zatem żądana maszyna  <math>T</math>,  taka że  <math>T(w_y) = y</math>, istnieje. Konstrukcja jest żmudna, ale rutynowa. Używając ruchu zygzakowego, znajdujemy coraz lepsze przybliżenia końców przedziałów  <math>I_{y_0}, I_{y_1}, I_{y_2}, \ldots</math> tak długo, aż zdobywamy pewność, że liczba reprezentowana przez <math>w_y</math> znajduje się w przedziale <math>I_y</math>, jest to właśnie poszukiwane <math>y</math>. Zauważmy, że dla każdego <math>n</math>, od pewnego momentu krańce przedziałów mogą się przesuwać co najwyżej o <math>\frac{1}{2^n}</math>, a zatem oczekiwana chwila nastąpi.
 
Prosta analiza przypadków pokazuje, że przedział <math>I_y</math>  
  }}
  }}

Aktualna wersja na dzień 22:14, 11 wrz 2023

Stała Chaitina

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

Definicja [Stała Chaitina]

Stałą Chaitina określamy jako sumę szeregu


Stałą Chaitina można interpretować jako prawdopodobieństwo, że losowo wybrane dane dla maszyny 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, . Dla , określamy

,

w szczególności . Funkcję można rozszerzyć na Borelowskie podzbiory tak, by stanowiła prawdopodobieństwo. Prawdopodobieśtwo to możemy też określić patrząc na ciąg jak na wynik nieskończonego procesu Bernoulliego , gdzie .

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

Twierdzenie [Własności ]

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

(1) .

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

(3) Istnieje stała taka, że

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle K_U (\omega_1 \ldots \omega_n ) \geq n - c}
gdzie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \omega_1 \ldots \omega_n} oznacza pierwszych Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle n} bitów liczby Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \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, Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \Omega} jest niekompresowalna.

Dowód

Ad 1. Ponieważ zbiór

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle L(U) = \{ w : U(w) \downarrow \} }

jest bezprefiksowy, każdy skończony podzbiór Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle {\cal S} \subseteq L(U)} , tworzy kod bezprefiksowy, a zatem z nierówności Krafta spełnia nierówność Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \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 Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle T} , zróbmy pewne obserwacje na temat liczby Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \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 Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \Omega} była dwójkowo wymierna, tzn.

(a) Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \Omega = 0. \omega_1 \omega_2 \ldots \omega_k 0 1 1 1 \ldots}

(b) Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \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 Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \Omega} dana jest w postaci (a). Istotnie, gdybyśmy mieli maszynę Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle T} dla tego przypadku, to łatwo moglibyśmy ją zmodyfikować do maszyny Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle T'} , która radziłaby sobie z przypadkiem (b). Maszyna Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle T'} działałaby tak samo jak maszyna Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle T} , z tym że począwszy od Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle k+1} -szej cyfry Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \Omega} , "widziałaby na odwrót", tzn. 0 traktowałaby jak 1 a 1 jak 0.


Jeśli wybierzemy wariant (a), lub jeśli Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \Omega} nie jest dwójkowo wymierna, to dla każdego Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle n} istnieje skończony podzbiór Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle {\cal S}_n \subseteq L(U)} , taki że liczba wyznaczona przez pierwszych Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle n} cyfr Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \Omega} spełnia

(pamiętamy, że ).

Opiszemy teraz działanie maszyny . 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 , , maszyna symuluje działanie na , a równolegle przegląda kolejne słowa z , , powiedzmy w porządku wojskowym: i symuluje działanie na ruchem zygzakowym, podobnie jak w algorytmie z dowodu Faktu.


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

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

(i) stwierdza, że ; wtedy daje odpowiedź TAK.

(ii) stwierdza, że

ale ; wtedy daje odpowiedź NIE.

Zauważmy, że w tej chwili możemy już wykluczyć możliwość, że 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 była dwójkowo wymierna, to opisaną wyżej konstrukcję maszyny można przeprowadzić bez reprezentowania liczby ; zamiast pobierać bity liczby z dodatkowej nieskończonej taśmy, maszyna mogłaby je sobie łatwo obliczyć. Podobny argument pokazuje znacznie więcej: nie jest liczba wymierną ani algebraiczną, ani w ogole "obliczalną" (zobacz Ćwiczenie).


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

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

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

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

Niech będzie pierwszym w porządku wojskowym słowem takim, że , dla każdego . Zauważmy, że (z definicji ). Wtedy wreszcie nasza maszyna zatrzymuje się z wynikiem .

Zgodnie z Faktem z poprzedniego wykładu, istnieje stała , że

Ale (skoro wygenerowała z wejścia ). To daje nam

i nierówność ta zachodzi dla każdego , takiego że . A zatem

dla każdego , tak więc może być żądaną stałą.

End of proof.gif

Związek z entropią Shannona

Jeśli stałą Chaitina interpretujemy jako prawdopodobieństwo, że bezprefiksowa maszyna uniwersalna się zatrzymuje, to dla ,

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

Zauważmy, że nie stanowi miary prawdopodobieństwa na , w szczególności

,

a nie 1.

Ale już

wyznacza prawdopodobieństwo na .


Jak pamiętamy z wykładu 3, dla skończonej przestrzeni probabilistycznej , optymalne kodowanie było osiągnięte wtedy, gdy

Dokładniej, równość była osiągnięta dla prawdopodobieństw będących potęgami , 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 , przy określonym wyżej prawdopodobieństwie .

Mówiąc nieformalnie, mamy

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

Fakt [Entropia Kołmogorowa]

Istnieje stała , że dla dowolnego ,

Dowód

Oczywiście, wystarczy jeśli pokażemy

Mamy , dla pewnego , takiego, że , a zatem

,

skąd

Pozostaje dowieść, że

,

dla pewnej stałej . Wobec Faktu o niezmienniczości, wystarczy tym celu skonstruować maszynę taką, że oraz

,

gdzie i nie zależą od .

Ustawmy wszystkie słowa w porządku wojskowym:

Z kolei rozważmy ciąg przedziałów domkniętych na prostej , gdzie początkiem jest 0; koniec jest początkiem i długością przedziału jest .

Zauważmy, że suma wszystkich przedziałów zawiera się w odcinku .

Przedziałem binarnym jest z definicji przedział postaci

,

gdzie ; .

Dla przedziału , znajdźmy największy przedział binarny 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 będzie początkiem tego największego przedziału binarnego. Połóżmy

(a zatem ).

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

Kluczowe jest spostrzeżenie, ile kroków długości możemy zrobić z punktu w lewo lub w prawo, pozostając cały czas w przedziale . 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 spełnia nierówność

skąd otrzymujemy

,

a zatem

Pozostaje pokazać, że znając , potrafimy algorytmicznie odtworzyć , a zatem żądana maszyna , taka że , istnieje. Konstrukcja jest żmudna, ale rutynowa. Używając ruchu zygzakowego, znajdujemy coraz lepsze przybliżenia końców przedziałów tak długo, aż zdobywamy pewność, że liczba reprezentowana przez znajduje się w przedziale , jest to właśnie poszukiwane . Zauważmy, że dla każdego , od pewnego momentu krańce przedziałów mogą się przesuwać co najwyżej o , a zatem oczekiwana chwila nastąpi.

End of proof.gif