- zbiór stanów, w których może przebywać komórka.
Program Game of Life - Reactivated służy do badania automatów komórkowych, a w szczególności bardzo powszechnej od pewnego czasu Gry w Życie, która od ponad 30 lat fascynuje wiele osób, a zwłaszcza informatyków i matematyków. Gra w Życie to automat komórkowy, wymyślony w 1970 roku przez brytyjskiego matematyka Johna Conwaya. Automaty komórkowe są dyskretnymi modelami matematycznymi, w których każda komórka znajduje się w określonym stanie i działa według lokalnej dla siebie reguły (funkcji przejścia). Wszystkie komórki pracują niezależnie od siebie i w sposób współbieżny.
Gra w Życie pokazuje przede wszystkim, jak skomplikowane wzorce mogą się wyłonić z układów rządzących się bardzo prostymi regułami. Z takimi zachowaniami mamy do czynienia w naturze. Współdziałanie wielu komórek sterowanych lokalnymi regułami potrafi stworzyć efekt, zauważalny jedynie globalnie w całym układzie.
Podstawowe właściwości automatów komórkowych to:
Formalnie rzecz biorąc, automat komórkowy stanowi trójka uporządkowana, złożona z sieci komórek {i}, dopuszczalnego zbioru stanów S oraz reguły (funkcji) przejścia λ. Dodatkowo program Game of Life Reactivated pozwala przypisać każdemu polu warunki środowiska W, które mają wpływ na wartość funkcji przejścia. Warunki środowiska na danym polu to uporządkowana trójka liczb rzeczywistych.
- zbiór stanów, w których może przebywać komórka.
Funkcja przejścia λ określa stan, w którym ma się znaleźć komórka i w t+1 kroku symulacji. Dziedziną λ jest zatem iloczyn kartezjański warunków środowiska W, otoczenia komórki i w kroku t oraz dotychczasowego stanu komórki si w kroku t
Zauważmy, że przy naszych założeniach odwzorowanie λ nie jest surjekcją. Zbiór stanów jest wspólny dla wszystkich rodzajów komórek, ale to od funkcji przejścia danego rodzaju komórki zależy, w jakim podzbiorze stanów zbioru S będzie się znajdować komórka.
Samoorganizacja automatu komórkowego polega na wyłanianiu się pewnego rodzaju wewnętrznego uporządkowania struktury kolonii komórek z upływem czasu, które to uporządkowanie nie jest wymuszone przez czynniki zewnętrzne. Podobna właściwość występuje w rzeczywistości, w fizyce i chemii. Wystarczy pomyśleć sobie chmurę i zastanowić się, co decyduje o jej kształcie.
Podstawy dla rozwoju automatów komórkowych stworzyli w latach 40 Stanisław Ulam i John von Neumann. Pomimo swej prostej budowy automaty mogą tworzyć nieskończenie skomplikowane wzory o zadziwiającej złożoności i właściwościach. Należą do nich zwłaszcza samoorganizacja, powielanie i wyłanialność wzorców zachowań. Te cechy bardzo upodobniają działanie automatów komórkowych do naturalnych organizmów i struktur (chmury, kryształy, skały), do wahań cen akcji na giełdzie lub chociażby do natężenia ruchu w komunikacji ulicznej.
Duży wkład w zbadanie dwustanowych automatów jednowymiarowych o promieniu jeden miał na początku lat 80 Stephen Wolfram. Rozważaną rodzinę automatów podzielił na cztery klasy. Automaty komórkowe mogą tworzyć struktury zadziwiająca przypominające swoją budową twory naturalne. Jednowymiarowy automat o regule 22 tworzy nieregularne, sprawiające wrażenie przypadkowości, struktury o chaotycznych zagęszczeniach. Taka struktura przypomina powierzchnie niektórych rodzai muszli morskich.
Każda komórka to automat skończony o 1-wymiarowych otoczeniu, promień 1. Numer reguły tego automatu w notacji Wolframa to 18. |
Czy pozorna losowość występowania nieregularnych zagęszczeń na powyższej, sztucznej kolonii komórek nie jest podobna do powierzchni naturalnej muszli morskiej? Czy to więc znaczy, że komórki muszli są automatami, wykonującymi proste algorytmy, dobrane przez naturę?
 Muszla morska: Olivia Porphyria |
Stephen Wolfram podzielił rozważaną przez siebie grupę automatów na cztery klasy.
Komórki w grze wymyślonej przez Conwaya mogą być w jednym z dwu stanów,
a funkcja decydująca o zmianie stanu jest bardzo prosta. Komórka martwa,
mająca dokładnie trzech sąsiadów, staje się żywa. Komórka żywa
żyje nadal, jeśli ma dokładnie dwóch lub trzech żywych sąsiadów.
Sama powyższa reguła pozwoliła odnaleźć prawdziwe bogactwo form, m.in.
stałe układy komórek, oscylatory, obiekty przesuwające się,
a nawet takie które wykonują działania arytmetyczne, logiczne
czy nawet symulują komputer (w sensie Turinga)!
Proste trwałe formy życia dla gry Conwaya: ul, łódź, okręt, bochenek.
Migacz i ropucha to układy - oscylatory.
Najczęściej używanym sąsiedztwem w automatach komórkowych tej klasy jest (obok sąsiedztwa Neumanna) sąsiedztwo Moora, czyli dla komórki i o współrzędnych (x0, y0) zbiór komórek:
Komórki Conwaya używają najpowszechniejszej, ale nie jedynej reguły przejścia dla automatów klasy (2,1). Innych możliwych funkcji przejścia jest całe mnóstwo. Jeżeli przyjąć, że istnieją tylko dwa rodzaje komórek, których sąsiedztwem jest sąsiedztwo Moora o promieniu 1, to daje to nam 28=256 różnych automatów. I to przy założeniu, że argumentem funkcji jest tylko liczba sąsiadów w danym stanie. Jeśli wartość funkcji przejścia zależałaby od rozmieszczenia stanów sąsiadów, to otrzymalibyśmy liczbę 2256 automatów - ale część z nich byłaby symetryczna względem siebie.
Najbardziej znany trójstanowy automat komórkowy. Występujące tu komórki trzech rodzajów: oczekujące, płonące lub przetwarzające. Jeśli komórka oczekująca ma dokładnie dwóch (w sensie Moora) płonących sąsiadów, to również staje się płonąca - i tylko wtedy. Komórka płonąca staje sie w swoim kolejnym kroku przetwarzająca. Komórka przetwarzająca zawsze staje się oczekującą.
|
Kolonia komórek rozrastająca się dość równomiernie we wszystkich kierunkach. Utworzenie dużej ,,dziury'' wewnątrz spowoduje jej zarośnięcie.
|
Przy takiej funkcji przejścia komórki rozmnażają się we wszystkich kierunkach, tworząc bardzo dobrze (losowo) wyglądający labirynt.
|
Replikator jest określony zbiorem reguł 1357/1357. Tym czym zadziwia najbardziej, jest wierne powielanie początkowego układu komórek w ośmiu egzemplarzach, dokładnie co trzydzieści dwie generacje. Poniższa seria pokazuje niektóre z nich.
| → |
| → |
| → |
| → |
| → |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| → |
|
Oprócz tego Replicator ma inną szczególną własność. Jak widzimy powyżej, niektóre generacje komórek sprawiają wrażenie zupełnego chaosu (generacja numer 30). Jednak cała kolonia przenosi w sobie początkową informację, która wyłoni się samoistnie za kilka generacji. To jeszcze nie wszystko. Można zauważyć, że rozmnażające się komórki mają niektóre właściwości fali informacji. Gdy fala trafi na ścianę martwych komórek i takich, których funkcja przejścia jest stała, potrafi się od takiej ściany odbić! - odwracając początkowy układ. Podobnie dwie biegnące ku sobie ,,fale'' mogą się przeniknąć, nie zakłócając informacji o zbiorach, które replikują.
 Dwukrotnie odbita fala replikacji |
Wszechświat oparty na funkcji przejścia Highlife jest podobny do klasycznego świata Conwaya, ale ciekawy ze względu na występujące w nim proste replikatory, które nie zostały jeszcze odkryte w przypadku funkcji Conwaya, pomimo iż dowiedziono, że takie istnieją. Powielający się układ musi mieć w przypadku Highlife określony kształt, który składa się tylko z sześciu komórek, więc jego powstanie zachodzi dość często w losowych koloniach. Układ komórek rozszerza się ukośnie, a co 12 * 2n występują dokładnie dwie kopie początkowego żyjątka, podczas gdy w generacji o numerze 12 (2n - 1) występuje 2n pełnych żyjątek. Taki rodzaj replikacji jest symulacją w komórkach funkcji Highlife automatu jednowymiarowego, w którym funkcją przejścia jest operacja alternatywy wyłączającej na stanach dwóch sąsiadów komórki.
 Dwa pasma replikatorów w Highlife, poniżej ropucha obracająca szybowiec. |
Każdy spójny organizm w tym ekosystemie rozszerza swoje granice do momentu, gdy będzie zbiorem wypukłym. Stworzenie drogi połączenia pomiędzy organizmami prowadzi do ich syntezy. Po ustabilizowaniu obszarów można zaobserwować chaotyczne przemiany komórek w ich wnętrzach, jednak organizmy nie będą się już nigdy powiększać. Nowe komórki są tworzone tylko we wnętrzach organizmów.
 Kilka organizmów po lewej stronie zostało połączonych drogami. Organizmy po prawej stronie powstały z rozrośniętych połączeń. |
W roku 1987 Brian Silverman zaprojektował 4-stanowy automat komórkowy, w którym działanie komórek może w zaskakujący sposób symulować przepływ prądu elektrycznego. Funkcja przejścia takiego automatu dana jest poniższą tabelką.
| Stan | Numer | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|---|
| Brak komórki | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| Przód elektronu | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
| Tył elektronu | 2 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| Przewodnik | 3 | 3 | 1 | 1 | 3 | 3 | 3 | 3 | 3 | 3 |
Ten prosty zbiór reguł pozwala tworzyć dowolnie złożone układy działające jak obwody elektroniczne. W szczególności mogą to być dowolne bramki logiczne oraz elementy wykonujące działania arytmetyczne i logiczne.
 |
Oto trzy małe generatory prądu o różnych natężeniach w komórkach Wire World. W trzecim z układów po lewo mamy dwie diody (przewodząca i zaporowa). |
 |
Bramka NOT. Aby działała, natężenie i faza wchodzących impulsów muszą być zgodne z impulsami wytwarzanymi we wnętrzu bramki. |
 Bramki XOR, AND, OR, NAND |
Użycie kombinacji powyższych bramek logicznych pozwoliło stworzyć bardzo skomplikowane obwody elektroniczne jako układy automatów komórkowych Wire World. (O minimalizacji takich układów z bramkami można się dowiedzieć na mojej stronie o algorytmie Quine'a-McKluskey'a.)
Poniżej przedstawiony jest układ komórek, który symuluje przerzutnik RS, składający się z dwóch bramek NAND, w których wyjścia wpływają do jednego z wejść sąsiedniej bramki. Układ komórek jest niesymetryczny, ponieważ przecięcie przewodników w Wire World wymaga wprowadzenia dodatkowego elementu o rozmiarze podobnym do bramki NAND.
 Przerzutnik RS |
(1) - Wejście R‾ (Reset) (2) - Wejście S‾ (Set) (3) - Wyjście Q (4) - Wyjście Q‾ |
Automat komórkowy wymyślony przeze mnie. Występują cztery stany. Komórki w dwóch stanach (zielone i czerwone) budują chaotyczny labirynt, zgodnie z regułą amazing, a komórki w pozostałych dwóch stanach próbują znaleźć wyjście z tego labiryntu (białe i żółte), rozchodząc się we wszystkich kierunkach, rozdzielając na skrzyżowaniach.
 Cztery różne generacje |
Każdy, kto zajmował się kiedyś automatami komórkowymi lub grą w życie, zaczyna się z czasem zastanawiać nad układem komórek zgodnym z kolorami kafelek ma każdej napotkanej podłodze lub ścianie. Kafelki na podłodze parteru FTIMS tworzą następujący wzór.
|
Co powstanie z takiego układu komórek? Oto rezultaty.
| Wynik po około 170 generacjach z funkcją Conwaya | ||
 |
 |
 |
| Wynik po około 50 generacjach z funkcją Amoeba | ||
 |
 |
 |
| Wynik po około 60 generacjach z funkcją Coral | ||
 |
 |
 |
W roku 2000 Paul Rendell udowodnił Turing-zupełność Gry w Życie Conwaya,
projektując maszynę Turinga, jako układ komórek.
Automat jest rozszerzalny do Uniwersalnej Maszyny Turinga.
Oznacza to ekosystem żyjątek, który jest modelem komputera,
mogącego wykonać dowolny algorytm - także symulować inny,
dowolny automat i algorytm.
Przypuszcza się także, że Uniwersalną Maszynę Turinga da się zbudować
w świecie Highlife - tworząc głowicę na jednym z końców strumienia
replikacji oraz wykorzystując drugi, rozwijający się koniec
jako nieskończenie długą taśmę.
Duży rozmiar i złożoność poniższego ekosystemu (około 2000 x 2000)
uniemożliwiają wykorzystanie go w praktyce do czegokolwiek.
 Projekt Maszyny Turinga w Grze w Życie (Paul Rendell 2000) |
Gra w życie Conwaya i automaty komórkowe prowokują do zadania mnóstwa dziwnych pytań. Jak bardzo wszechświat jest podobny do ogromnego automatu komórkowego? Czy różnicą jest tylko gigantyczna złożoność tego pierwszego? Jeśli tak, to wszechświat byłby tylko wielkim komputerem, wykonującym jakiś algorytm. Czy o jakimkolwiek zdarzeniu można byłoby powiedzieć, że jest tak naprawdę losowe, jeśli pełna informacja o aktualnym stanie wszystkich komórek (czyli cząstek elementarnych, nie ważne jakich) pozwoliłaby obliczyć stan wszechświata w dowolnej późniejszej chwili czasu? Czy może wszystko jest czysto deterministyczne, tak jak w grze Conwaya, i istniałby ,,wzór na wszystko'', pozwalający przy znajomości pełnej informacji o stanie bieżącym obliczyć wszystko, co nastąpi później? A gdyby móc zapisać i później wiernie odtworzyć stan całej materii, na jej najgłębszym poziomie, w ciele człowieka, to czy odtworzone zostałyby też jego myśli i wspomnienia? Czy pamięć, uczucie, marzenie i wizja w ludzkim umyśle są jedynie konsekwencją aktualnego stanu materii w jego mózgu? Pesymistyczna wizja. Gdyby taka funkcja przejścia istniała, to czy byłaby złożona? Wydaje się, że tak. Z drugiej strony gra Conwaya pokazała, że bardzo proste reguły tworzą bardzo złożone systemy.
 |
 |
 |
 |
 |
 |
 |
 |
 |
Program Game of Life Reactivated jest oparty na systemie wtyczek, co ułatwia jego rozszerzanie i modyfikowanie. Funkcje przejścia są z założenia bardzo krótkie i proste. Bardzo łatwo można napisać definicję własnej funkcji przejścia, skompilować ją do postaci modułu i przypisać go rodzajowi komórki. Takie podejście umożliwia bardzo elastyczne tworzenie dowolnie wyszukanych automatów komórkowych.
Kod takiego dynamicznie ładowanego modułu może wyglądać następująco.
#include "common.h" #include "komorka.h" #include "sasiedztwo.h" #include "srodowisko.h" /* * Przykładowa funkcja przejścia */ extern "C" int funkcja (const Warunki_Srodowiska *W, const Sasiedztwo_Moora *S, int stan) { int Zywi_Sasiedzi = Zlicz_Niemartwych_Sasiadow(S); const Komorka *k; // Komórka umiera przy ujemnej temperaturze if (W->temperatura() < 0) return 0; // Komórka przyjmuje stan 1 przy dużym nasłonecznieniu i wilgotności if (W->oswietlenie() > 50 && W->wilgotnosc() > 50) return 1; // Komórka przyjmuje stan 2, jeśli jej północy sąsiad też jest w takim stanie if ((k = S->Sasiad_Polnocny()) && k->podaj_stan() == 2) return 2; // Komórka przyjmuje stan 4, jeśli ma // ponad pięciu niemartwych sąsiadów w stanie 3 if (Zlicz_Sasiadow_W_Stanie(S, 3) > 5) return 4; // W pozostałych przypadkach komórka obumiera return 0; }Kompilacja nowego modułu z funkcją przejścia:
$ cd Funkcje_Przejscia
$ g++ -I.. -I../fltk -march=i686 -mcpu=i686 -O3 -ffast-math \
-fexpensive-optimizations -shared -fPIC przyklad.cpp -o przyklad.so
$ strip przyklad.so
> cd Funkcje_Przejscia
> g++ -DWIN32 -I.. -I../fltk -march=i686 -mcpu=i686 -O3 -ffast-math \
-fexpensive-optimizations -shared -fPIC przyklad.cpp -o przyklad.dll
> strip przyklad.dll
| Kod funkcji | Biblioteka .dll (MS Windows ©) | Biblioteka .so (GNU/Linux) |
|---|---|---|
| 1d-150.cpp | 1d-150.dll | 1d-150.so |
| 3stany.cpp | 3stany.dll | 3stany.so |
| amazing.cpp | amazing.dll | amazing.so |
| amoeba.cpp | amoeba.dll | amoeba.so |
| artist.cpp | artist.dll | artist.so |
| brians_brain.cpp | brians_brain.dll | brians_brain.so |
| conway.cpp | conway.dll | conway.so |
| coral.cpp | coral.dll | coral.so |
| highlife.cpp | highlife.dll | highlife.so |
| maze_race.cpp | maze_race.dll | maze_race.so |
| replicator.cpp | replicator.dll | replicator.so |
| ring.cpp | ring.dll | ring.so |
| seeds.cpp | seeds.dll | seeds.so |
| sierpinski.cpp | sierpinski.dll | sierpinski.so |
| walled_cities.cpp | walled_cities.dll | walled_cities.so |
| wire_world.cpp | wire_world.dll | wire_world.so |
Niniejszy program jest wolnym oprogramowaniem; możesz go rozprowadzać dalej i/lub modyfikować na warunkach Powszechnej Licencji Publicznej GNU, wydanej przez Fundację Wolnego Oprogramowania - według wersji 2-giej tej Licencji lub którejś z późniejszych wersji. Również tam znajdziesz dalsze informacje (w szczególności o braku jakiejkolwiek gwarancji).