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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
(Nie pokazano 2 pośrednich wersji utworzonych przez tego samego użytkownika)
Linia 224: Linia 224:
 
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>
  
Linia 231: Linia 231:
 
{{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>
 
}}
 
}}
Linia 237: Linia 237:
 
{{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>,
Linia 246: Linia 246:
 
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>.
Linia 266: Linia 266:
 
''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>
Linia 276: Linia 278:
 
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ń 01:21, 23 sty 2007

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

gdzie oznacza pierwszych bitów liczby .


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, jest niekompresowalna.

Dowód

Ad 1. Ponieważ zbiór

jest bezprefiksowy, każdy skończony podzbiór , tworzy kod bezprefiksowy, a zatem z nierówności Krafta spełnia nierówność , co po przejściu do supremum daje żądaną nierówność.

Ad 2. Zanim opiszemy konstrukcję maszyny , zróbmy pewne obserwacje na temat liczby . 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 była dwójkowo wymierna, tzn.

(a)

(b)

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


Jeśli wybierzemy wariant (a), lub jeśli nie jest dwójkowo wymierna, to dla każdego istnieje skończony podzbiór , taki że liczba wyznaczona przez pierwszych cyfr 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