Teoria informacji/TI Ćwiczenia 14

From Studia Informatyczne

Ćwiczenia

Ćwiczenie 1 [Nieobliczalność \Omega]

Liczbę rzeczywistą r \in [0,1]

nazwiemy obliczalną (rekurencyjną), jeśli istnieje algorytm (maszyna Turinga), który dla danej liczby n oblicza n-tą cyfrę w rozwinięciu binarnym liczby r.

Liczbę r nazwiemy rekurencyjnie aproksymowalną, jeśli jest granicą obliczalnego ciągu liczb wymiernych, tzn. istnieje funkcja obliczalna f : N \to N \times N, taka że

r = \lim_{n \to \infty } \frac{f(n) \downarrow_1}{f(n) \downarrow_2}
Dowiedź, że każda liczba rekurencyjna jest też rekurencyjnie aproksymowalna.
Dowiedź, że istnieją liczby rzeczywiste r \in [0,1], które nie są rekurencyjnie aproksymowalne.

Oszacuj moc zbioru liczb rekurencyjnie aproksymowalnych.

Dowiedź, że liczby wymierne, algebraiczne, a także liczby \pi i e są rekurencyjne.
Dowiedź, że stała Chaitina \Omega jest rekurencyjnie aproksymowalna (niezależnie od wyboru maszyny uniwersalnej).
Dowiedź, że stała Chaitina \Omega nie jest rekurencyjna.

Wskazówka: dowód Twierdzenia


Definicja [Test]

Funkcję \delta : \{ 0,1 \}^* \to N nazwiemy testem, jeśli dla każdych m,n,
\frac{|\{ w \in \{ 0,1 \}^n : \delta (w) \geq m \} |}{2^n} \leq \frac{1}{2^m}

Zauważmy, że dla każdego w, istnieje co najwyżej skończenie wiele m, takich, że \delta (w) \geq m. Intuicyjnie, funkcja \delta (w) wskazuje, jak bardzo słowo w "odbiega od normy". Warunek stwierdza, że takich ciągów nie może być zbyt wiele (w przeciwnym razie stanowiłyby normę).

Ćwiczenie 2 [Uniwersalny test Martina-Lofa]

Niech Z = \{ \delta_0 , \delta_1 , \ldots  \} będzie przeliczalną rodziną testów.

Dowiedź, że funkcja określona wzorem
\delta^Z (w) = \max \{ \delta_n (w) - n : n \geq 0 \}

jest testem.

Interesujący jest zwłaszcza przypadek, kiedy funkcja \delta^Z sama należy do rodziny Z.

Test \delta nazwiemy efektywnym, jeśli istnieje maszyna Turinga M_{\delta }, która przyjmując na wejściu parę \langle w,m \rangle,

 jeśli \delta (w) \geq m, zatrzymuje się i daje odpowiedź TAK;
 jesli \delta (w) < m, daje odpowiedź NIE, lub się zapętla. 

Innymi słowy, zbiór \{ \langle w,m \rangle : \delta (w) \geq m \} jest rekurencyjnie przeliczalny, chociaż funkcja \delta nie musi być rekurencyjna.

Zauważmy, że rodzina E wszystkich testów efektywnych jest przeliczalnie wiele. (Dlaczego ?)

Maszyna M_{\delta } jednoznacznie wyznacza test \delta (w) = \max \{ m: \delta (w) \geq m \}, a maszyn Turinga jest oczywiście przeliczalnie wiele.


Dowiedź, że \delta^E jest testem efektywnym.

Pokaż najpierw, że istnieje rekurencyjna numeracja wszystkich testów, tzn. maszyna Turinga T, taka że zbiór jej wartości \{ T(x) : x \in \{ 0,1 \}^* \} jest dokładnie zbiorem kodów \{ \langle M_{\delta } \rangle :  \delta \mbox{   jest testem } \}.