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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 21: Linia 21:
  
  
 
{{cwiczenie|2 [Liczby losowe]|Ćwiczenie 2|Wyjaśnij następujący pozorny paradoks.
 
 
Z uwagi poprzedzającej  [[Teoria informacji/TI Wykład 13#random|definicję losowości]] wiemy, że przy pewnym wyborze maszyny uniwersalnej, istnieje nieskończenie wiele liczb losowych. (Dlaczego?)
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible-content" style="display:none">
 
Wiemy, że dla każdej maszyny uniwersalnej <math> U,</math> istnieje nieskończenie wiele słów losowych. Gdyby prawie wszystkie te słowa zaczynały się od 0, możemy wziąć maszynę <math> U',</math> która działa tak jak <math> U,</math>
 
tylko zamienia 0 i 1.
 
 
Zastrzeżenie o wyborze maszyny jest jednak istotne, bo z drugiej strony moglibyśmy wziąć modyfikację <math> U,</math> która „przez ''default''˝ poprzedza wynik jedynką (o ile nie otrzymuje informacji, że ma tego nie robić), co automatycznie zmniejsza złożoność liczb o 1.
 
</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 ł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?
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible-content" style="display:none">
 
Oczywiście jest problem z konkatenacją. Jeśli po prostu napiszemy <math> x y </math>, to zgubimy informację o tym, gdzie kończy się <math> x  </math>, a zaczyna <math>  y </math>. Przypuśćmy, że <math> x = x_1 \ldots x_m. </math> <math>y = y_1 \ldots y_n </math>. Odwracalną konkatenacją może być np.
 
<center><math> x_1 0 x_2 0 \ldots x_{m-1} 0 x_m 1 y
 
</math></center>
 
co jednak wydłuża wynik o <math> |x|  </math>. Bardziej ekonomiczną realizacją jest
 
<center><math> a_1 0 a_2 0 \ldots a_{\ell -1} 0 a_{\ell } 1 x y
 
</math></center>
 
gdzie <math> a_1 \ldots a_{\ell } </math> jest binarnym przedstawieniem liczby <math> |x|  </math>,
 
co jednak wydłuża wynik o <math> 2 \cdot \log |x|  </math>.
 
</div>
 
</div>
 
 
'''Problem'''. Spróbuj określić, jakie własności muszą mieć liczby losowe - np. przez podanie dalszych warunków, które wykluczają losowość.
 
'''Problem'''. Spróbuj określić, jakie własności muszą mieć liczby losowe - np. przez podanie dalszych warunków, które wykluczają losowość.
  

Wersja z 20:09, 16 gru 2009

Ćwiczenia

Ćwiczenie 1 [Liczby pierwsze]

{{{3}}}


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 , jest

Przypuśćmy, że zbiór wartości obliczanych przez maszynę Turinga , tzn. , jest zbiorem par, przy czym

(i) ,

(ii) (tzn. jest grafem funkcji częściowej).

Dowiedź, że nie jest możliwe, by dla nieskończenie wielu , zachodziło

gdzie jest funkcją taką, że