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 _{v:U(v)\downarrow }{2}^{-|v|}=\sum _{M:M(\epsilon )\downarrow }{2}^{-|⟨M⟩|}$

Stała Chaitina jest czasem przedstawiana jako prawdopodobieństwo że losowo wybrany program się zatrzymuje. Ma to istotnie 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||Chaitin_property|Stała Chaitina ma następujące własności.

(1) $\mathrm{\Omega }\le 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$