Teoria informacji/TI Wykład 14: Różnice pomiędzy wersjami
Linia 266: | Linia 266: | ||
''Przedziałem binarnym'' jest z definicji przedział postaci | ''Przedziałem binarnym'' jest z definicji przedział postaci | ||
<center><math> | <center><math> | ||
− | \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) | + | \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}} | + | Rozważmy punkty <math> L - \frac{1}{2^k}, L, L + \frac{1}{2^{k}} + \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>. |
Nie może być <math> A \leq L - \frac{1}{2^k} </math>, bo wtedy | Nie może być <math> A \leq L - \frac{1}{2^k} </math>, bo wtedy | ||
Linia 284: | Linia 286: | ||
byłby większym przedziałem binarnym zawartym w <math>I_y</math>. | byłby większym przedziałem binarnym zawartym w <math>I_y</math>. | ||
− | + | Podobnie nie może być <math> L + \frac{1}{2^{k}} + \frac{1}{2^{k-1}} \leq B</math>, bo wtedy | |
+ | <center><math> | ||
+ | \left[ L + \frac{1}{2^{k}}, L + \frac{1}{2^{k}} + \frac{1}{2^{k-1}} \right) | ||
+ | </math></center> | ||
+ | byłby takim przedziałem. | ||
}} | }} |
Wersja z 23:32, 22 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 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ślamyw 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 ]
(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
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 kod bezprefiksowy, a zatem z nierówności Krafta spełnia nierówność , co po przejściu do supremum daje żądaną nierówność.
, tworzyAd 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 porządku wojskowym: i symuluje działanie na ruchem zygzakowym, podobnie jak w algorytmie z dowodu Faktu.
. 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
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, żeale
; 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 . NiechOczywiś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, żeNiech
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 nami nierówność ta zachodzi dla każdego
, takiego że . A zatemdla każdego
, tak więc może być żądaną stałą.
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ścia 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]
Dowód
Mamy
, dla pewnego , takiego, że , a zatemskąd
Pozostaje dowieść, że
dla pewnej stałej Faktu o niezmienniczości, wystarczy tym celu skonstruować maszynę taką, że oraz
. Wobecgdzie
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 .Rozważmy punkty
i niech i będą odpowiednio początkiem i końcem przedziału .Nie może być
, bo wtedybyłby większym przedziałem binarnym zawartym w
.Podobnie nie może być
, bo wtedybyłby takim przedziałem.
