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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 14: Linia 14:
  
 
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},
Linia 20: Linia 20:
 
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. W szczególności <math>\Omega </math> stanowi prawdopodobieństwo zdarzenia,
+
prawdopodobieństwo. Prawdopodobieśtwo to możemy też określić patrząc na ciąg
że ciąg ze zbioru <math> \{ 0,1 \}^{\omega }</math> zawiera prefiks <math> v</math>, dla którego
+
<math>x \in  \{ 0,1 \}^{\omega }</math> jak na wynik nieskończonego procesu Bernoulliego
<math>U ( v) \downarrow </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,
 +
ż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).
 
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żą.
Linia 94: Linia 96:
 
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 także przegląda kolejne słowa  
+
a równolegle przegląda kolejne słowa z <math>\{ 0,1 \}^* </math>,  
<math>v </math>, powiedzmy w porządku wojskowym, i
+
<math>v </math>, powiedzmy w porządku wojskowym: <math> \varepsilon = v_0, v_1, v_2, \ldots </math>
symuluje działanie <math> U </math> na <math> v </math>.
+
i  symuluje działanie <math> U </math> na <math> v_i </math> ruchem zygzakowym, podobnie jak
Oczywiście każda z tych maszyn może się zapętlić, dlatego <math> T </math>
+
w dowodzie Faktu.
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 słowa w porządku wojskowym tworzą
 
ciąg <math> v_0, v_1, v_2, \ldots </math>, a <math>{\cal W} (u_i) </math> oznacza:
 
wykonaj kolejny krok działania maszyny <math> U </math> na wejściu  <math> v_i</math> lub ''skip'' jeśli
 
<math> U </math> już zakończyła
 
działanie,
 
to plan działania maszyny <math> T </math> można przedstawić
 
  
<center><math>
 
{\cal W} (v_0 ) \, {\cal W} (v_1 ) \, {\cal W} (v_0 ) \, {\cal W} (v_1 ) \, {\cal W} (v_2 ) \,
 
\, {\cal W} (v_0 ) \, {\cal W} (v_1 ) \, {\cal W} (v_2 ) \,
 
{\cal W} (v_3) \, {\cal W} (v_0 ) \dots
 
</math></center>
 
  
 
W trakcie swojego obliczenia, maszyna <math> T </math> utrzymuje zmienną, powiedzmy
 
W trakcie swojego obliczenia, maszyna <math> T </math> utrzymuje zmienną, powiedzmy

Wersja z 18:55, 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 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 dowodzie 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