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}$

Ponadto zakładamy, że istnieje algorytm częsciowy, który dla każdej pary $w,m,$ takiej, że

$\delta (w)\ge m,$ zatrzymuje się i daje odpowiedź TAK, natomiast gdy $\delta (w)<m,$ algorytm daje odpowiedź NIE lub się zapętla. (Natomiast funkcja $\delta$ nie musi być obliczalna.

Zauważmy, że dla każdego

Dowiedź, że istnieje