Teoria informacji/TI Ćwiczenia 13: Różnice pomiędzy wersjami

Wersja z 18:38, 25 sie 2006

Ćwiczenie 1 [Liczby pierwsze]

{{{3}}}

Ćwiczenie 2 [Liczby losowe]

{{{3}}}

Ćwiczenie 3 [Generowanie funkcji]

Przyjmujemy, że parą słów

x, y

, jest

⟨ x, y ⟩ = x_{1} 0 x_{2} 0 \dots x_{m - 1} 0 x_{m} 1 y

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^{'} ⟩ \in R_{M} ⟹ y = y^{'}$ (tzn. $R_{M}$ jest grafem funkcji częściowej).

Dowieść, że nie jest możliwe, by dla nieskończenie wielu $⟨ x, y ⟩ \in R_{M}$ , zachodziło

(K (y) \geq | y |) \land (K (x) \leq f (| x |))

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

@@ Linia 51: / Linia 51: @@
 '''Problem'''. Spróbuj określić, jakie własności muszą mieć liczby losowe -- np. przez podanie dalszych warunków, które wykluczają losowość.
+}}
+{{cwiczenie|3 [Generowanie funkcji]|Ćwiczenie 3|Przyjmujemy, że ''parą'' słów <math> x, y </math>, jest
+<center><math> \langle x,y \rangle = x_1 0 x_2 0 \ldots x_{m-1} 0 x_m 1 y
+</math></center>
+Przypuśćmy, że zbiór wartości obliczanych przez maszynę Turinga <math> M </math>, tzn. <math> R_M = \{ M(w) : w \in \{ 0,1\}^* \} </math>, jest zbiorem par, przy czym
+(i) <math> \langle x,y \rangle \in R_M \, \Longrightarrow \, |x| = |y| </math>,
+(ii)  <math>\langle x,y \rangle , \langle x,y' \rangle\in R_M \, \Longrightarrow \,  y = y' </math>
+(tzn. <math> R_M </math> jest grafem funkcji częściowej).
+Dowieść, że nie jest możliwe, by dla nieskończenie wielu <math>  \langle x,y \rangle \in R_M </math>,
+zachodziło
+<center><math>
+( K(y) \geq |y|) \; \wedge \; ( K(x) \leq f (|x|) )
+</math></center>
+gdzie jest funkcją taką, że <math> (n - f(n)) \to \infty .</math>
 }}