Definicja Edwarda Fredkina

Podstawą jego definicji jest dwuwymiarowa, kwadratowa siatka, w której każda komórka jest opisana przez wektor pozycji: ${\displaystyle {\vec {r}}=(i,j),}$ gdzie ${\displaystyle i,j}$ są indeksami kolumn i wierszy siatki. Stan każdej komórki w iteracji ${\displaystyle t}$ jest opisywany przez ${\displaystyle \phi _{t}({\vec {r}},t)}$ i może przyjmować wartości binarne 0 i 1. Na automat komórkowy składają się:

1. regularna siatka o ${\displaystyle d}$-wymiarowej przestrzeni;
2. ustawienie początkowe:

${\displaystyle \phi ({\vec {r}},t)=\{\phi _{1}({\vec {r}},t),\phi _{2}({\vec {r}},t),\dots ,\phi _{m}({\vec {r}},t),\}}$

zmiennych boolowskich w każdym miejscu ${\displaystyle {\vec {r}}}$ siatki;

1. Reguła ${\displaystyle R=\{R_{1},R_{2},\dots ,R_{m}\},}$ która ustala stan ${\displaystyle \phi ({\vec {r}},t)}$ w czasie, w następujący sposób:

${\displaystyle \phi _{j}({\vec {r}},t+\tau )=R_{j}(\phi ({\vec {r}},t),\phi ({\vec {r}}+{\vec {\delta _{1}}},t),\phi ({\vec {r}}+{\vec {\delta _{2}}},t),\dots ,\phi ({\vec {r}}+{\vec {\delta _{q}}},t)),}$

w którym ${\displaystyle {\vec {r}}+{\vec {\delta _{q}}}}$ oznacza komórki należące do skończonego zbioru sąsiadów ${\displaystyle {\vec {r}}.}$

Siatka automatu komórkowego

Automat komórkowy na siatce heksagonalnej

Każdy automat posiada przestrzeń, w której następuje jego ewolucja. Z definicji automatu taką przestrzeń tworzą jednakowe komórki, a nazywamy ją siatką ${\displaystyle \alpha .}$ Każda komórka przechowuje swój stan – zależny od przestrzeni stanów. Komórki różnią się, są niezależne oraz każdą komórkę można jednoznacznie zidentyfikować poprzez jej położenie na siatce.

Istnieją trzy konstrukcyjne czynniki automatu komórkowego, które w zasadniczy sposób wpływają na strukturę siatki:

• wymiar przestrzeni, zależny od wielkości badanego problemu (siatka 1D, 2D, 3D, nD);
• warunek regularności, mówiący o całkowitym zapełnieniu siatki przez jednakowe komórki (komórki trójkątne, kwadratowe, sześciokątne dla 2D, sześcienne lub w kształcie dwunastościanów rombowych dla 3D etc.);
• liczba sąsiadów (zależna od obu powyższych).

Sąsiedztwo komórek

Warunki brzegowe

Przestrzeń stanów

Przestrzeń stanów określamy poprzez zdefiniowanie wartości wybranej ze skończonego zbioru ${\displaystyle Q,}$ który może być podzbiorem zbiorów podstawowych (np. liczb, liter) lub złożonych (struktury, obiekty).

Poprzez przestrzeń stanów opisane zostają wszystkie możliwe stany komórki. Stan komórki zależy od aktualnych stanów komórek z otoczenia, jak i komórka swoim stanem wpływa bezpośrednio na stany swoich sąsiadów. Od dobrego określenia przestrzeni stanów zależy szybkość automatu komórkowego, jak i jego podstawowe cechy charakterystyczne.

Reguły przejść

Reguły przejść określają ewolucję automatu komórkowego w dyskretnym czasie. Stany poszczególnych komórek aktualizuje się w każdej dyskretnej chwili ${\displaystyle t=1,2,3,\dots }$ Tym samym każdy automat komórkowy jest obiektem dynamicznym w czasie. Jak już wcześniej wspomniano, stan każdej komórki można określić na podstawie aktualnych stanów komórek sąsiednich.

Stan komórki ${\displaystyle x}$ w chwili ${\displaystyle t}$ oznaczmy jako ${\displaystyle x_{t},}$ a stan sąsiedztwa jako ${\displaystyle u(x_{t}).}$ Dla takich kryteriów stan komórki ${\displaystyle x}$ w kolejnym kroku iteracji można opisać wzorem:

${\displaystyle x_{t+1}=f(u(x_{t}),x_{t}),}$

gdzie ${\displaystyle f}$ określa funkcję przejścia, która może być opisana różnego rodzaju zależnościami, np. jako tabela przejść, w postaci algorytmicznej lub jako zbiór reguł. Reguły przejść muszą być zdefiniowane obok przestrzeni stanów oraz zdefiniowanego sąsiedztwa, ponieważ w innym przypadku automat nie mógłby ewoluować.

Warunki początkowe

Ważnym elementem konstrukcyjnym automatów komórkowych są warunki początkowe, czyli stany poszczególnych komórek w zerowej iteracji, czyli na samym początku. To od ustawienia początkowego komórek zależy dalsza ewolucja automatu, jego zachowanie, stan końcowy, tym samym powodzenie całej symulacji.

Niektóre automaty komórkowe z założenia muszą mieć w odpowiedni sposób ustalone warunki początkowe. Weźmy pod uwagę Heavy triangles, układ ten zaczyna się od jednej komórki uaktywnionej umieszczonej w środku siatki 1D. Przykładowo w Game of Life, to od warunków początkowych zależy czy w efekcie końcowym otrzymamy wszystkie komórki martwe, czy też komórki, które będą żyły w cyklicznych formach, czy też będą do samego końca powstawały chaotycznie. Od ustawienia warunków początkowych może również zmienić się przynależność automatu komórkowego do różnych klas Stephena Wolframa – opisanych poniżej. Jednym słowem warunki początkowe danego automatu komórkowego zależą od jego charakteru i problemu – zadania przez niego symulowanego.

Ewolucja automatu komórkowego

Po ustaleniu i zdefiniowaniu wszystkich elementów składowych automatu komórkowego można przejść do nakładania reguł na siatkę, czyli aktualizowania jej.

Cały proces ewolucji automatu można podzielić na kilka części:

1. Stan początkowy – jest to, wspomniane już, ustalenie warunków początkowych. Zwykle są to stany neutralne nie powodujące konfliktów w automacie.
2. Aktualizacja siatki automatu – w każdej iteracji każda z komórek automatu przechodzi przez poniższą sekwencję instrukcji:
   1. Sprawdzenie reguł przejść – w tym kroku sprawdzany jest aktualny stan komórki, stany komórek sąsiednich, jak i inne parametry automatu;
   2. Sprawdzanie sąsiedztwa – bada się, czy któraś z komórek sąsiednich nie wchodzi w stan konfliktu. Jeżeli takie konflikty zaczynają występować, to należy wyeliminować wszystkie istniejące konflikty, według ustalonych wcześniej reguł dla takich przypadków;
   3. Sprawdzanie warunków brzegowych – sprawdzane tu są komórki które są na krawędziach siatki. Usuwa się je gdy są zbędne (sąsiedztwo zamknięte pochłaniające) lub tworzy nowe (sąsiedztwo periodyczne);
   4. Sprawdzenie liczby iteracji – jeśli jest to automat o skończonym, z góry określonym cyklu życiowym, to w tym kroku sprawdzamy czy może nastąpić koniec ewolucji. Czasami sprawdza się również w tym miejscu czy automat zmienił swój stan i czy przeszedł do stanu stabilnego i nic w nim się już nie zmieni w kolejnych krokach iteracji.
   5. Zwiększenie licznika iteracji i przejście do kroku 2.1.