Teoria informacji/TI Ćwiczenia 14

Ćwiczenia

Ćwiczenie 1 [Nieobliczalność $\mathrm{\Omega }$]

{{{3}}}

Definicja [Test]

Funkcję $\delta :\{0,1{\}}^{*}\to N$ nazwiemy testem, jesli 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 ?)

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