Automat komórkowy

Automat komórkowy – system składający się z pojedynczych komórek, sąsiadujących ze sobą według pewnego ustalonego wzorca. Każda z komórek może przyjąć jeden ze stanów, przy czym liczba stanów jest skończona, ale dowolnie duża. Stan komórki zmieniany jest synchronicznie 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^[1].

Automaty komórkowe, których struktury opisane są przez siatkę komórek oraz ich stany, przejścia i reguły tych przejść, są modelami matematycznymi. Tworzą one środowisko dla większych dyskretnych klas modeli, ponieważ wszystkie opisujące je struktury przyjmują wartości dyskretne.

Każdy automat komórkowy składa się z ${\displaystyle n}$-wymiarowej regularnej, dyskretnej siatki komórek, każda komórka jest taka sama (jest kopią poprzedniej), cała przestrzeń siatki musi być zajmowana w całości przez komórki ułożone obok siebie. Każda z nich posiada jeden stan ze skończonego zbioru stanów. Ewolucja każdej komórki przebiega według tych samych ściśle określonych reguł lokalnych (jednorodność), które zależą wyłącznie od poprzedniego stanu komórki oraz od stanów skończonej liczby komórek-sąsiadów. Ewolucja następuje w dyskretnych przedziałach czasowych, jednocześnie dla każdej komórki (równoległość). W automacie komórkowym komórka jest automatem.

Definicja formalna

Jeżeli przez ${\displaystyle \alpha }$ oznaczymy regularną, uporządkowaną siatkę złożoną z jednakowych komórek ${\displaystyle c}$ o budowie zależnej od rozmiaru przestrzeni i od kształtu pojedynczej komórki,
natomiast przez ${\displaystyle S}$ – skończony zbiór stanów, jaki może przyjąć komórka ${\displaystyle c,}$
oraz przez ${\displaystyle N}$ – skończony zbiór sąsiadów, spełniający warunek:

${\displaystyle \forall c\in N,\forall r\in \alpha :r+c\in \alpha }$

a funkcję przejścia definiującą reguły ewolucji automatu w kolejnych krokach oraz dynamikę tych przejść zapiszemy jako:

${\displaystyle f\colon S^{m}\to S,}$

to automat komórkowy definiujemy jako czwórkę:

${\displaystyle A\equiv (\alpha ,S,N,f).}$

Aby opis automatu komórkowego był pełny, niezbędne jest określenie warunków brzegowych i początkowych.

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}}.}$

Historia

Twórcą automatów komórkowych jest jeden z największych myślicieli ery komputerowej, który wprowadził koncepcję samoreprodukcji – John von Neumann. Docelowo chciał stworzyć model maszyny samosterującej, tzn. takiej, iż powielałaby ona swoją budowę i przekazywała swoje cechy. Na przełomie lat 40. i 50. Neumann opracował swoją teorię, opierając się na maszynie Turinga^[2]. Opracował on pięć modeli samoreplikujących się automatów, których jednak realizacja okazała się zbyt trudna, aż do momentu, gdy zainspirowany pomysłem Stanisława Ulama, wprowadził do swego modelu dyskretny czas i przestrzeń^[3].

Konstrukcja

Każdy automat odpowiada wyżej wymienionym definicjom. Jego budowa musi się opierać na konkretnych danych. Nie mogą istnieć w jednym automacie dwie komórki, które nie mają wszystkich elementów takich samych (różnią się choćby liczbą sąsiadów). Budowa wszystkich komórek musi być identyczna (muszą mieć tyle samo sąsiadów, takie same zbiory stanów itp.). Budowa elementów automatu może również wpłynąć znacząco na jego jakość.

Siatka automatu komórkowego

(c) Akramm at pl.wikipedia, CC BY 2.5

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

Sąsiedztwo von Neumanna

Jeśli oznaczymy kierunki na zasadzie róży wiatrów: N, S, E, W oraz kierunki pośrednie NW, NE, SE, SW, to sąsiedztwem von Neumanna będzie zbiór czterech komórek: N, S, E, W

Sąsiedztwo Moore’a

Posługując się powyższymi oznaczeniami, sąsiedztwem Moore’a będzie zbiór wszystkich ośmiu komórek dookoła komórki centralnej

Sąsiedztwo Moore’a-von Neumanna

Jest to połączenie dwóch poprzednich sąsiedztw w jedno.

Sąsiedztwo Margolusa

Stosuje się je w automatach do symulacji spadającego piasku, czy też interakcji cząsteczek gazu. Reguły przejścia opierają się na kwadratowych blokach tworzonych przez cztery sąsiadujące komórki. Stany tych sąsiednich komórek zmieniają się jednocześnie, przy czym komórki przyjmują wartości binarne 1 i 0. Tak dzieje się na całej siatce automatu. W następnym kroku reguły są obliczane podobnie, tylko że zmieniają się grupy komórek. Bloki tworzące owe grupy przesuwają się o jeden w prawo i w dół.

Warunki brzegowe

Periodyczne (przenikające)

Definiują one zamkniętą siatkę w taki sposób, że np. symulując poruszającą się cząstkę po dojściu do krawędzi, pojawi się ona z drugiej strony. Komórka znajdująca się na brzegu siatki ma za sąsiada komórkę leżącą po drugiej stronie siatki. Ten typ przejść bardzo dobrze opisuje nasze otoczenie – środowisko, w którym wszystko również odbywa się na periodycznej przestrzeni, jaką jest torus.

Zamknięte pochłaniające (o stałej wartości).

Siatka jest zdefiniowana w taki sposób, że brzegi siatki wypełnione są z góry ustaloną wartością, która poprzez funkcję przejścia ustala wpływ na zachowanie automatu. W praktyce, symulując np. cząstkę gazu, po przekroczeniu krawędzi siatki przestaje ona istnieć. Najczęściej stosuje się je w automatach, w których generuje się automatycznie komórki i niezbędna jest ich redukcja, aby nie zagęścić liczby komórek w automacie.

Zamknięte odbijające (o stałej wartości).

Warunki brzegowe na krawędzi siatki tworzą barierę, od której symulowane cząstki się odbijają. Stosowane do symulacji zamkniętych przestrzeni doświadczalnych.

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.

Podział Wolframa

Klasa I

Automaty niezmienne – ewoluują do czasu, kiedy wszystkie komórki osiągną identyczny stan niezależnie od stanu początkowego (zbieżne).

Klasa II

Automaty ewoluujące do stanu stabilnego lub okresowych wzorców (okresowe).

Klasa III

Automaty wykazujące nieporządek zarówno lokalnie, jak i globalnie, nie wykazujące żadnego wzorca (chaotyczne).

Klasa IV

Automaty wykazujące bardziej złożone, długotrwałe zachowanie („żywe”).

Zastosowanie

Technika automatów komórkowych jest używana do symulacji komputerowych w wielu problemach nauki i techniki. Automaty te dostarczają również wielu zagadnień teorii dynamiki nieliniowej.

Popularne automaty komórkowe

• gra w życie
• mrówka Langtona
• turmity
• wireworld

Przypisy

Linki zewnętrzne

• Automaty komórkowe – Krzysztof Kułakowski (Wydział Fizyki i Informatyki Stosowanej AGH)
• Automaty komórkowe – Paweł Konieczny. mimuw.edu.pl. [zarchiwizowane z tego adresu (2007-07-09)]. (Instytut Matematyki Stosowanej i Mechaniki Uniwersytetu Warszawskiego)
• Automaty komórkowe, notatki do wykładu – Krzysztof Malarz (Wydział Fizyki i Informatyki Stosowanej AGH)
• Eric W.E.W. Weisstein Eric W.E.W., Cellular Automaton, [w:] MathWorld [online], Wolfram Research [dostęp 2020-12-12]  (ang.).
• FrancescoF. Berto FrancescoF., JacopoJ. Tagliabue JacopoJ., Cellular Automata, [w:] Stanford Encyclopedia of Philosophy [online], CSLI, Stanford University, 22 sierpnia 2017, ISSN 1095-5054 [dostęp 2017-12-31]  (ang.). (Automaty komórkowe)