|
|
| 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ść. |
|
| |
|
Ć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
