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ó, 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 sa 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

W programie można zmienić wielkość planszy pokazującej automat na dużą lub małą. Plansze te różnią się ilością komórek automatu. Można też zmienić definicję sąsiedztwa. Użytkownik może wybrać automat z listy kilku już zdefiniowanych. Przycisk Losuj umożliwia losowe inicjowanie stanu każdej komórki automatu jedną z możliwych wartości, a przycisk Czyść przypisuje każdej komórce stan domyślny – zero. Przyciski Szybko, Średnio, Wolno sterują szybkością zmian stanów komórek, czyli ilością iteracji automatu wykonywaną w jednostce czasu. Natomiast Krok wykonuje pojedyncze obliczenie stanów komórek. Lewy przycisk myszki zmienia stan komórki na kolejny, a prawy – na zerowy.

Uruchom progam wybierając język interfejsu:

Dostępne automaty

W programie zaimplementowano trzy automaty: Życie, Inwazja i Marsz. Dla każdego z nich określono predefiniowany stan świata, jednak każdy z tych światów może zostać zmieniony przez użytkownika – np. czyszcząc go przyciskiem Czyść i wprowadzając własny wygląd.

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: nieaktywa (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: nieaktywa (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.

Program i tekst: Magdalena Ławrynowicz

Prowadzący: Maciej Komosiński