Teoria informacji/TI Ćwiczenia 14

Ćwiczenia

Ćwiczenie 1 [Nieobliczalność $\mathrm{\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=\underset{n\to \mathrm{\infty }}{\lim }\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 $\mathrm{\Omega }$ jest rekurencyjnie aproksymowalna (niezależnie od wyboru maszyny uniwersalnej).

Dowiedź, że stała Chaitina $\mathrm{\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)\ge m\}|}{2^n}\le \frac{1}{2^m}$

Zauważmy, że dla każdego $w$ istnieje co najwyżej skończenie wiele $m$ takich, że $\delta (w)\ge 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,\dots \}$ będzie przeliczalną rodziną testów.

Dowiedź, że funkcja określona wzorem

${\delta }^Z(w)=\max \{{\delta }_n(w)-n:n\ge 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ę $⟨w,m⟩$

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

Innymi słowy, zbiór $\{⟨w,m⟩:\delta (w)\ge 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)\ge 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 $\{⟨M_{\delta }⟩:\delta \text{ jest testem }\}$.