Teoria informacji/TI Ćwiczenia 14

Ćwiczenia

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

{{{3}}}

{{cwiczenie|2 [Uniwersalny test Martina-Lofa]|Ćwiczenie 2| 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ę).

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 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 testów efektywnych jest przeliczalnie wiele. (Dlaczego ?)

Maszyna $M_{\delta }$ jednoznacznie wyznacza test $\delta$ (jak ?)

$\delta (w)=\max \{m:\delta (w)\ge m\}.$

a maszyn Turinga jest oczywiście przeliczalnie wiele.

Zauważmy, że dla każdego $w,$ istnieje co najwyżej skończenie wiele $m,$ takich że $\delta (w)\ge m$.

Dowiedź, ż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 }\}$.

Dowiedź, że następujaca funkcja jest testem:

${\delta }^U(w)=\max \{$