Teoria informacji/TI Ćwiczenia 13

Ćwiczenia

Ćwiczenie 1 [Liczby pierwsze]

{{{3}}}

Ćwiczenie 2 [Oszacowanie]

Jak zauważyliśmy, dla złożoności bezprefiksowej nie ma tak dobrego oszacowania

jak we Wniosku. Dowieść, że zachodzi przynajmniej

$K_U(x)\le 2\log |x|+|x|+c_U$

dla pewnej stałej $c_U$.

Ćwiczenie 3 [Generowanie funkcji]

Przyjmujemy, że parą słów $x,y$, jest $⟨x,y⟩=x_{1}0x_{2}0\dots x_{m-1}0x_{m}1y$

Przypuśćmy, że zbiór wartości obliczanych przez maszynę Turinga $M$, tzn. $R_M=\{M(w):w\in \{0,1{\}}^{*}\}$, jest zbiorem par, przy czym

(i) $⟨x,y⟩\in R_M⟹|x|=|y|$,

(ii) $⟨x,y⟩,⟨x,y^{\prime }⟩\in R_M⟹y=y^{\prime }$ (tzn. $R_M$ jest grafem funkcji częściowej).

Dowiedź, że nie jest możliwe, by dla nieskończenie wielu $⟨x,y⟩\in R_M$, zachodziło

$(K(y)\ge |y|)\wedge (K(x)\le f(|x|))$

gdzie jest funkcją taką, że $(n-f(n))\to \mathrm{\infty }.$