Teoria informacji/TI Ćwiczenia 14

Ćwiczenia

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

{{{3}}}

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]

{{{3}}}