Elementarne automaty komórkowe

Niedawno odkryłem dostępną darmowo w sieci książkę Stephena Wolframa (tego od programu Mathematica i wyszukiwarki Wolfram|Alpha) - "A New Kind of Science". Czytelnikom, którzy widzieli jego ostatnie wystąpienie na TED nie trzeba mówić o jego ciekawych poglądach na przyszłość współczesnej nauki oraz o tym, jak duże znaczenie przywiązuje do szukania złożonych zachowań w rzeczach prostych. Przed lekturą drugiego rozdziału wspomnianej książki postanowiłem napisać sobie prosty, dwustanowy, jednowymiarowy automat komórkowy i wygenerować opisywane przez Wolframa obrazy. Implementacja zajęła piątkowe popołudnie i wieczór, a w rezultacie powstał program symulujący automat komórkowy z dowolną trójelementową regułą oraz renderujący obrazy. (Galeria automatów komórkowych) Poniżej chciałbym zaprezentować kilka najciekawszych przykładów tego, co potrafi stworzyć tak prosty automat komórkowy. Nieco dalej wyjaśnię, na czym polega numeracja reguł. Na samym końcu chciałbym też opowiedzieć o programie, który napisałem. Reguła 30

Ulubiona reguła S. Wolframa, szeroko omówiona w jego książce. Z prawej strony tworzy się wzór nie mający żadnej widocznej struktury. Sekwencja kolorów bezpośrednio pod punktem startowym jest podobno losowa według wielu testów sprawdzających generatory liczb losowych - sam Wolfram użył reguły 30 jako generatora liczb losowych w programie Mathematica. Reguła 18

Pierwsze pojawienie się trójkąta Sierpińskiego. Wiele reguł produkuje różnej postaci trójkąty Sierpińskiego. W całej galerii naliczyłem 24 wystąpienia tego wzoru: 18, 22, 26, 60, 82, 90, 102, 105, 126, 129, 146, 150, 151, 153, 154, 161, 165, 167, 181, 182, 183, 195, 210, 218. Reguła 151

Reguła ta jest bardzo ciekawą wariacją wokół trójkąta Sierpińskiego. Powstaje z samych brzegów automatu - to krawędzie są źródłem wzoru, który przy górnej granicy przypomina wspomniany fraktal. Bardzo interesujący jest też wynik "interferencji" zbiegających się wzorców. Reguła 124

Prawa krawędź tego wzoru pokazuje powtarzającą się sekwencję trójkątów. Na środku jednak pojawia się bardzo ciekawa struktura, która sprawia wrażenie zupełnie chaotycznej. Reguła 225

Ciekawy, chaotyczny wzór powstaje z punktu początkowego. Tutaj jednak, podobnie jak przy regule 151, najciekawsze rzeczy tworzy sama krawędź. Numeracja Wolframa Numeracja reguł, zaproponowana przez Wolframa w A New Kind of Science, jest bardzo prosta. Automat, na którym pracujemy oblicza stan nowej komórki z trzech innych - z tej bezpośrednio nad sobą, oraz z lewego i prawego sąsiada komórki nad sobą. Wystarczy zaobserwować, że mając do dyspozycji trzy komórki, z których każda może przyjąć dwa stany (zapalona albo zgaszona), uzyskujemy 8 możliwych układów. Dla każdego takiego układu definiujemy zasadę - czy nowa komórka ma zostać zgaszona, czy zapalona. Łącząc takie zasady dla wszystkich ośmiu stanów uzyskujemy jedną regułę opisującą wszystkie możliwe sytuacje spotkane w omawianym automacie komórkowym. Łączenie zasad w numer reguły jest oparte o operacje bitowe. Jeżeli potraktujemy trójki komórek jako liczby binarne, gdzie stan 'zapalona' oznacza 1, a stan 'zgaszona' oznacza 0, uzyskujemy naturalną numerację od 0 do 7. I teraz jeżeli zasada oparta o daną trójkę mówi, ze nowa komórka ma być zapalona, to ustawiamy bit odpowiadający 'numerowi' trójki komórek na 1, a jeżeli nowa komórka ma być zgaszona - to na 0. Uzyskany numer zasady jest liczbą ośmiobitową, a więc z zakresu od 0 do 255.

Jeżeli sam opis był zbyt zagmatwany, to mam nadzieję, że powyższe zdjęcie wyjaśniło sprawę ;). Symulator automatu komórkowego (Pobierz symulator) Sam symulator to prosty program w Common Lispie, który pisałem przez piątkowy wieczór. Trzon designu stanowiły schematy narysowane kredą na betonie przed pizzerią oraz kod rozpisany na pudełku od pizzy :). Program ten umie przeprowadzać symulacje dla jednowymiarowego, dwustanowego automatu komórkowego o dowolnej szerokości na podstawie reguł sprawdzających trzy sąsiadujące ze sobą komórki.

Screen z symulatora automatów komórkowych.

Główny program wypisuje swoje wyniki w postaci tekstowej, jednak dopisałem też nakładkę, która umie generować obrazy i zapisywać je do plików. Korzysta ona ze znanej programistom gier biblioteki SDL za pośrednictwem bindingów lispbuilder-sdl. Krawędzie i warunki początkowe Jest jedna ważna rzecz, o której na tym etapie trzeba wspomnieć. Jak w każdym automacie komórkowym, tak i w tym pojawia się problem krawędzi, czyli tego, jaką wartość ma przyjąć lewy sąsiad pierwszej komórki oraz prawy sąsiad ostatniej. W przypadku mojej implementacji, komórki 'z poza planszy' przyjmują domyślnie stan 'zgaszony', pusty. Uważny czytelnik zauważy, że wygenerowane przeze mnie obrazki różnią się miejscami od przykładów z książki Wolframa - wynika to z tego, że symulacja odbywała się na automacie o szerokości 800, gdzie bardzo szybko dochodziła do głosu obecność krawędzi. Zdjęcia zamieszczone w A New Kind of Science są wolne od wpływu krawędzi - najprawdopodobniej 'krawędź' jest gdzieś bardzo daleko :). Wszystkie obrazki zostały wygenerowane przy tych samych warunkach początkowych, jakie stosował Stephen Wolfram w A New Kind of Science - startujemy ze wszystkimi komórkami zgaszonymi, i zapalamy jedną dokładnie na środku. Symulator - pobieranie i użycie Pobierz symulator (źródła). Przykład użycia (za pomocą specjalnych funkcji do prostego testowania):

(load (compile-file "ca1d.lisp"))

;; wyswietlenie w konsoli 17 iteracji (16 + stan poczatkowy)
;; automatu dlugosci 16 zgodnie z regula 30
(test-wolfram-rule 16 30 16)

;; zakladam, ze lispbuilder-sdl jest juz zaladowany
(load (compile-file "ca1d-gfx.lisp"))

;; wyswietlenie graficznie 600 iteracji (ze stanem poczatkowym wlacznie)
;; automatu dlugosci 800 zgodnie z regula 30
(test-rule-800x600 30)

;; j.w., ale celem wygenerowania samego obrazka:
(test-rule-800x600 30 t)