Teoria informacji/TI Ćwiczenia 13

Ćwiczenia

Ćwiczenie 1 [Oszacowanie]

Jak zauważyliśmy, dla złożoności bezprefiksowej nie ma tak dobrego oszacowania jak we Wniosku. Dowieść, że zachodzi słabsze oszacowanie $K_{U}(x)\leq 2\log |x|+|x|+c_{U}$

dla pewnej stałej $c_{U}$.

Ćwiczenie 2 [Liczby pierwsze]

{{{3}}}

Ćwiczenie 3 [Generowanie funkcji]

Przyjmujemy, że parą słów $x,y$, jest $\langle x,y\rangle =x_{1}0x_{2}0\ldots 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) $\langle x,y\rangle \in R_{M}\,\Longrightarrow \,|x|=|y|$,

(ii) $\langle x,y\rangle ,\langle x,y'\rangle \in R_{M}\,\Longrightarrow \,y=y'$ (tzn. $R_{M}$ jest grafem funkcji częściowej).

Dowiedź, że nie jest możliwe, by dla nieskończenie wielu $\langle x,y\rangle \in R_{M}$, zachodziło

$(K(y)\geq |y|)\;\wedge \;(K(x)\leq f(|x|))$

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