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

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ść (będzie to łatwa konsekwencja własności (3)), w tej chwili musimy jeszcze wziąć ją pod uwagę.

Ad 3.