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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Niwinski (dyskusja | edycje)
214 edycji
Niwinski (dyskusja | edycje)
214 edycji
Linia 34: Linia 34:
</div>
</div>


Z poprzedniego ćwiczenia wiemy, że jedynymi liczbami losowymi mogą być liczby postaci <math> n = p_1 \cdot \ldots \cdot p_k,</math> gdzie <math> p_1, \ldots , p_k,</math>  są różnymi liczbami pierwszymi. Wiemy także, że <math> K_U (p_i ) \leq \log_2 p_i - \alpha (p_i), </math> gdzie <math>\alpha </math> jest funkcją rozbieżną do <math>\infty </math>. Z drugiej strony <math> \log n = \log p_1 + \ldots + \log p_k </math>. Wydaje się, że program generujący liczbę <math> n </math> (tzn. takie <math> x ,</math> że <math> U(x) = n </math>) można otrzymać jako konkatenację programów generujących liczby <math> p_1, \ldots , p_k,</math> plus informacja (o stałym rozmiarze), że wyniki należy wymnożyć.
Z poprzedniego ćwiczenia wiemy, że jedynymi liczbami losowymi mogą być liczby postaci <math> n = p_1 \cdot \ldots \cdot p_k,</math> gdzie <math> p_1, \ldots , p_k,</math>  są różnymi liczbami pierwszymi. Wiemy także, że <math> K_U (p_i ) \leq \log_2 p_i - \alpha (p_i), </math> gdzie <math>\alpha </math> jest funkcją rozbieżną do <math>\infty </math>. Z drugiej strony <math> \log n = \log p_1 + \ldots + \log p_k </math>. Wydaje się, że program generujący liczbę <math> n </math> (tzn. takie <math> x ,</math> że <math> U(x) = n </math>) można łatwo otrzymać jako konkatenację programów generujących liczby <math> p_1, \ldots , p_k,</math> plus informacja (o stałym rozmiarze), że wyniki należy wymnożyć.


Czy to znaczy, że jednak nie ma liczb losowych?
Czy to znaczy, że jednak nie ma liczb losowych?

Wersja z 18:39, 25 sie 2006

Ćwiczenia

Ćwiczenie 1 [Liczby pierwsze]

{{{3}}}


Ćwiczenie 2 [Liczby losowe]

{{{3}}}

Ćwiczenie 3 [Generowanie funkcji]

Przyjmujemy, że parą słów x,y, jest
⟨x,y⟩=x10x20…xm−10xm1y

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

(i) ⟨x,y⟩∈RM⟹|x|=|y|,

(ii) ⟨x,y⟩,⟨x,y′⟩∈RM⟹y=y′ (tzn. RM jest grafem funkcji częściowej).

Dowieść, że nie jest możliwe, by dla nieskończenie wielu ⟨x,y⟩∈RM, zachodziło

(K(y)≥|y|)∧(K(x)≤f(|x|))

gdzie jest funkcją taką, że (n−f(n))→∞.

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Teoria_informacji/TI_Ćwiczenia_13&oldid=27974”