Automat komórkowy: binarne życie

Automat komórkowy (ang. cellular automaton, CA) jest systemem składającym się z pojedynczych komórek. Komórki te znajdują się obok siebie przypominając swoim wyglądem planszę lub szachownicę. Każda komórka automatu może być w jednym ze stanów, przy czym liczba takich stanów jest skończona i dowolnie duża. Stan jest najczęściej liczbą. Najczęściej liczba ta nie przekracza 256. Stan komórki zmieniany jest zgodnie z regułami mówiącymi, w jaki sposób nowy stan komórki zależy od jej obecnego stanu i stanu jej sąsiadów, czyli innych komórek znajdujących się w jej pobliżu. Sąsiedztwo może być definiowane na różne sposoby – najczęściej jest to sąsiedztwo Moore'a lub Neumanna. Stany wszyskich komórek zmieniane są synchronicznie, w jednej chwili czasowej.

Sąsiedztwa Moore'a (8) i Neumann'a (4). Stan komórki czerwonej zależy od stanu komórek zielonych.

Obydwa nazwiska wymienione powyżej są nazwiskami pionierów teorii automatów komórkowych – John von Neumann i Edward F. Moore. Oczywiście można zaproponować wiele różnych reguł działania automatu, jego stanów, rodzajów sąsiedztw i konfiguracji. Konkretny dobór automatu zależy od zastosowania – inny automat użyjemy do filtrowania i polepszania jakości obrazu, inny do symulacji rozwoju komórek rakowych, a inny do symulacji pożarów lasu.

Program

Program umożliwia symulację kilku wybranych automatów komórkowych. Użytkownik może zmienić rozmiar planszy i skrajne zachowania, rodzaj sąsiedztwa i wybrać zasady automatu komórkowego. W celach demonstracyjnych możliwa jest obserwacja jedenastu różnych przykładowych symulacji. Przy pomocy myszki możliwa jest modyfikacja planszy na której odbywa się symulacja - za pomocą kliknięcia lub przeciągnięcia lewym przyciskiem myszki można zmienić stan komórki na kolejny, natomiast prawy przycisk umożliwia powrót do stanu początkowego. Przycisk Reset przywraca planszę do stanu początkowego. Krok wykonuje pojedyncze obliczenie stanów komórek, natomiast Start rozpoczyna symulację z zadaną szybkością. Szybkość symulacji można zmieniać w trakcie używając listy Szybkość.

Każdy z parametrów symulacji tj. reguły, rodzaj sąsiedztwa, rozmiar lub typ planszy można zmieniać w trakcie symulacji. Należy jednak być ostrożnym zmieniając rozmiar planszy, gdyż zmniejszenie planszy powoduje usunięcie zewnętrznych komórek. Aktualny stan symulacji można lokalnie zapisać używając „Zapisz” - stan ten jest przechowywany dopóki nie zostaną wyczyszczone lokalne dane w przeglądarce.

Uruchom progam wybierając język:

Dostępne automaty

W programie zaimplementowano kilka automatów: Oryginalną Grę w Życie, Marsz, Inwazję, HighLife, Nasiona, Amebę i Replikator.

Automat Gra w życie został podany przez Johna Hortona Conway'a w 1970 roku. Uważany jest on za wyjątkowy przez swoją prostotę (opiera się jedynie na dwóch stanach automatu i trzech regułach) i złożoność zachowań. Gra w życie jest często porównywana z innym automatem zdefiniowanym przez von Neumann'a. Automat Johna von Neumann'a również potrafi symulować dowolną funkcję używając wyłącznie reguł logicznych, jednak opiera się na dwudziestu dziewięciu stanach komórki automatu.

Zbiór stanów każdej komórki zawiera tylko dwa elementy, a mianowicie "1" i "0". "1" oznacza, że komórka jest żywa (szara), a "0" martwa (biała).

Reguły automatu Gra w życie:

1. Jeśli w otoczeniu komórki (nie licząc jej samej) są trzy komórki żywe, to w kolejnym kroku ta komórka jest żywa,
2. Jeżeli w jej otoczeniu są dwie komórki żywe, a ona sama również jest żywa, to pozostaje żywa w kolejnym kroku,
3. W pozostałych przypadkach jest ona martwa w kolejnym kroku.

Uwaga: KAŻDA komórka podlega TYM SAMYM regułom w KAŻDYM momencie!

Reguły gry w życie są (o czym można się przekonać eksperymentując z programem) tak skonstruowane, że leżą na granicy pomiędzy nieograniczonym rozrastaniem się komórek, a ich wyginięciem. Można zauważyć, że pojawiające się wzorce mogą ostatecznie zapełnić całą możliwą przestrzeń świata lub wejść w interakcję z innymi wzorcami i doprowadzić do ich wzrostu lub całkowitego zahamowania.

W programie pokazano 6 przykładowych konfiguracji świata. Proste obiekty znajdujące się w świecie mają swoje nazwy i uważane są za jedne z ciekawszych, których zachowanie zgodne z regułami automatu na pewno warto jest zobaczyć.

Blinker	Block	Clock	Glider
Gliders by the Dozen	Light-weight spaceship	Pi Heptomino	R Pentomino
Thunderbird	Toad	Tub

Automaty Inwazja i Marsz zostały umieszczone w programie ze względu na ciekawe efekty wizualne, tworzące się w trakcie działania programu.

Dla automatu Marsz komórka może znajdować się w jednym z dwóch stanów: nieaktywna (biała), aktywna (szara). Reguły automatu Marsz:

1. Jeżeli komórka jest aktywna i ma co najmniej czterech aktywnych sąsiadów, to staje się nieaktywna.
2. Jeżeli komórka jest nieaktywna i ma dwóch aktywnych sąsiadów, to staje się aktywna.
3. Jeżeli komórka ma trzech aktywnych sąsiadów, to staje się aktywna.
4. W przeciwnym przypadku komórka staje się nieaktywna.

Automat Inwazja jest automatem, dla którego inaczej niż dla Gry w życie i Marszu, definiuje się trzy stany dla komórki automatu: nieaktywna (biała), aktywna (szara), subaktywna (ciemna) – patrz rysunek poniżej. Reguły automatu Inwazja przedstawiają się następująco:

1. Jeżeli komórka jest aktywna i ma co najmniej trzech aktywnych lub subaktywnych sąsiadów, to staje się superaktywna.
2. Jeżeli komórka jest nieaktywna i ma co najmniej trzech aktywnych lub subaktywnych sąsiadów, to staje się aktywna.
3. Jeżeli komórka jest aktywna i ma od 1 do 2 aktywnych lub subaktywnych sąsiadów, to jest aktywna.
4. W innych przypadkach komórka staje się nieaktywna.

Automaty HighLife, Nasiona, Ameba i Replikator cechują się podobnymi zasadami do Gry w Życie. Komórki mogą być w jednym z dwóch stanów - aktywnym (czarny) albo martwym (biały), ale stosowane są inne zasady przetrwania i aktywacji.

W automacie HighLife komórka przeżywa (pozostaje aktywne) kiedy ma 2 lub 3 aktywnych sąsiadów, komórka ożywa (zostaje aktywna) kiedy ma 3 lub 6 aktywnych sąsiadów, w przeciwnym przypadku komórka jest martwa.

W automacie Nasiona komórka ożywa kiedy ma dokładnie dwóch aktywnych sąsiadów, w przeciwnym wypadku pozostaje martwa. Warto zauważyć, że każda aktywna komórka staje się martwa w kolejnym kroku.

W automacie Ameba komórka przeżywa kiedy ma 1, 3, 5 lub 8 aktywnych sąsiadów, a nowa komórka ożywa kiedy ma 3, 5 lub 7 aktywnych sąsiadów, w przeciwnym wypadku komórka jest martwa.

Bardzo ciekawym i efektownym automatem jest Replikator. W tym automacie komórka przeżywa albo ożywa kiedy ma 1, 3, 5 lub 7 aktywnych sąsiadów. Pomimo takich prostych reguł, każdy narysowany wzór jest replikatorem - zostanie on powielony wielokrotnie, przy założeniu jest plansza jest wystarczająco duża.

Program i tekst: Magdalena Ławrynowicz, Amadeusz Juskowiak

Prowadzący: Maciej Komosiński