Alicja w krainie fraktali

- Drogi panie Kiciu-Dziwaku - zaczęła raczej nieśmiało, ponieważ nie wiedziała, czy forma ta przypadnie Kotu do gustu.(Kot uśmiechnął się jeszcze szerzej. Widzę, że mu się spodobało” - pomyślała Alicja). - Czy nie mógłby pan mnie poinformować, którędy powinnam pójść? - mówiła dalej.

- To zależy w dużej mierze od tego, dokąd pragnęłabyś zajść - odparł Kot-Dziwak.

- Właściwie wszystko mi jedno.

- W takim razie również wszystko jedno, którędy pójdziesz.

- Chciałabym tylko dostać się dokądś - dodała Alicja w formie wyjaśnienia

Ach, na pewno tam się dostaniesz, jeśli tylko będziesz szła dość długo.

Lewis Caroll, „Alicja w krainie czarów”, Przełożył Antoni Marianowicz

Alicja ma w ten sposób szansę dostania się do Krainy Fraktali. O ile zechce tę szansę wykorzystać.

Drogi Panie Kiciu-Dziwaku – a jak się z danych szans skorzysta? - spytała Alicja.
Do tego potrzebny jest szans-generator, a także alfabet – odparł Kot Dziwak.

Zacznijmy od alfabetu. Bo o alfabetach już rozmawialiśmy przy okazji grup. Alfabet jednoliterowy jest nieciekawy. Alfabet, by mógł być ciekawy, musi mieć przynajmniej dwie litery. Takie jak np. 0 i 1, lub a i b. Z liter możemy tworzyć słowa. Takie jak 011001 lub 0010110111011 lub babaabaababaaababbba. Słowa mogą być krótkie lub długie. Każde słowo krótkie można wydłużyć – dodając dalsze litery alfabetu na końcu słowa. Teoretycznie długościom słów nie ma granic. W praktyce jednak kartka na której słowo piszemy się kiedyś skończy. Możemy wtedy kontynuować na następnej kartce. Teoretycznie nic nie stoi na przeszkodzie by rozważać nieskończone ciągi liter. Taki ciąg nieskończony zapisujemy jako:

babaabaababaaababbba...

Trzy kropki na końcu oznaczają, że tu urwaliśmy zapis, ale samo słowo ciągnie się dalej, bez końca.

Do maszyny do pisania, takie z dwiema tylko literami, a i b, siada małpa. Stuka w klawisze. Powstaje słowo. Małpa może mieć predylekcję – chętniej uderza w a niż w b. Lub na odwrót. Mamy więc prawdopodobieństwa pa i pb. Są to liczby pomiędzy 0 i 1, takie, że pa + pb = 1. Na przykład pa = 1/4, pb = 3/4. Chyba, że małpa podlega dyssypacji – wtedy pa + pb może być mniejsze od jedynki. Przyjmijmy jednak, że małpa jest konserwatywna, zatem pa + pb = 1. Przyjmijmy, na początek, że predylekcje małpy są stałe w czasie. Bo przecież takie być nie muszą. Ale od prostych przypadków dobrze zaczynać. Niestety czasem ludzie do prostych przypadków się ograniczają.. A szkoda.

Chcemy zasymulować działania małpy na komputerze. Komputer ma zazwyczaj wbudowany „szans-generator” - generator liczb pseudo-losowych. Komputer ma swoje granice, zazwyczaj nałożone przez rodzaj procesora, system operacyjny, stosowane algorytmy. Ma w szczególności największą liczbę (pseudo-) losową, którą jest w stanie wygenerować. Nazwijmy ją RAND_MAX. Na przykład RAND_MAX = 2³¹= 2147483648. Nie jest to zatrważająco wielka liczba, ale do wielu celów praktycznych wystarcza. Generujemy więc liczbę losową, nazwijmy jąrand, dzielimy przez RAND_MAX i mamy liczbę losową z przedziału (0,1):

0 < r = rand/RAND_MAX < 1.

Gdy r < pa piszemy a, w przeciwnym razie piszemy b. W ten sposób możemy małpę odesłać do małpiarni, komputer jej działania zasymuluje. Robimy pętlę, powiedzmy:

pa = 1/4;

pb = 3/4;

Od 1 do 1000000 rób:

generuj r;

Gdy r < pa, pisz a, w przeciwnym razie pisz b;

Dałem tu komputerowi granicę długości słowa, w tym przypadku 1000000. Inaczej nic z napisanymi słowami nie moglibyśmy zrobić, bo pisaniu nie byłoby końca. Znaczy koniec byłby, bo chcemy by komputer słowo pamiętał, a pojemność pamięci ma przecież swoje granice.

No dobrze, wygenerowaliśmy słowo złożone z miliona liter, i co z tego? Alicja dokonała milion losowych wyborów, i co z tego? Co w tym ciekawego?

Otóż z samych generowanych losowo liter nic ciekawego jeszcze nie wynika. Ciekawe zaczyna się dopiero wtedy, gdy każda wygenerowana litera coś znaczy. Gdy podłożymy jakiś kod. Na przykład tak jak to było, gdy bawiliśmy się w teorię grup i macierzy – jak to było w poprzednich notkach.

Nie znam żadnego kodu – powiedziała Alicja. Panie Kocie Dziwaku, czy nie pogniewasz się na mnie gdy Cię o jakiś, choćby jeden, ciekawy kod poproszę? Bo nawet jeśli będę błądzić, to chciałabym by moje błądzenie było interesujące.
„I owszem”, odpowiedział Kot Dziwak, „mogę Ci dać pseudo-ciekawy kod, na początek. Ale co z tym kodem zrobić – do tego będziesz musiała dojść już sama. Oto ten kod:

Za a weź macierz [[1,0],[0,3]]. Za b weź macierz [[1,2],[0,3]]. Za pa i pb weź 1/2. Bye—bye, muszę lecieć”, powiedział Kot Dziwak, i zniknął. Alicja została sama w lesie. No, nie całkiem sama, bo z kodem.

Kot dał jej Kod.