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)\le 2\log |x|+|x|+c_U$

dla pewnej stałej $c_U$.

Ćwiczenie 2 [Liczby pierwsze]

Niech $\text{bin }(n)$ oznacza zapis binarny liczby naturalnej $n$. Powiemy, że liczba $n$ jest losowa, jeśli ciąg $\text{bin }(n)$ jest losowy.

Dowiedź, że liczby pierwsze nie są losowe (poza co najwyżej skończoną ilością).

Wykorzystaj twierdzenie, że gęstość liczb pierwszych jest $\approx \frac{\log n}{n}$. Dla naszych celów istotne jest, że ta gęstość szacuje się przez funkcję $f$, taką że $\frac{f(n)}{n}\to 0$

Dowiedź, że liczby postaci $p^k$, gdzie $p$ jest liczbą pierwszą, nie są losowe (poza co najwyżej skończoną ilością).

Dowiedź, że liczby postaci $n^k$, gdzie $k\ge 2$, nie są losowe (poza co najwyżej skończoną ilością).

Oszacuj z góry bezprefiksową złożoność liczb pierwszych tzn. $K_U(\text{bin }(p))$.

Problem. Spróbuj określić, jakie własności muszą mieć liczby losowe - np. przez podanie dalszych warunków, które wykluczają losowość.

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