Automat komórkowy - Polski Serwis Naukowy

Definicja intuicyjna:
Automat komórkowy to system składający się z pojedynczych komórek, znajdujących się obok siebie. Ich układ przypomina szachownicę lub planszę do gry. 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.

John von Neumann (ur. 28 grudnia 1903 w Budapeszcie, zm. 8 lutego 1957 w Waszyngtonie) – matematyk, inżynier chemik, fizyk i informatyk. Wniósł znaczący wkład do wielu dziedzin matematyki - w szczególności był głównym twórcą teorii gier, teorii automatów komórkowych (w które pewien początkowy wkład miał także Stanisław Ulam), i stworzył formalizm matematyczny mechaniki kwantowej. Uczestniczył w projekcie Manhattan. Przyczynił się do rozwoju numerycznych prognoz pogody.
Definicja intuicyjna: Maszyna Turinga stanowi najprostszy, wyidealizowany matematyczny model komputera, zbudowany z taśmy, na której zapisuje się dane i poruszającej się wzdłuż niej "głowicy", wykonującej proste operacje na zapisanych na taśmie wartościach.

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 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 ilości 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.

Wireworld - dobrze znany automat komórkowy zaproponowany przez Briana Silvermana w roku 1987, jako część jego programu o nazwie Phantom Fish Tank. Stał on się popularny po publikacji poświęconego mu artykułu w dziale "Computer Recreations" czasopisma Scientific American.
Reguła – dające się ująć w sposób sformalizowany działanie, mające zastosowanie w określonej dziedzinie. Bardziej specjalistyczne znaczenia to m.in.:

Definicja formalna

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

Stephen Wolfram (ur. 29 sierpnia 1959 w Londynie) - naukowiec brytyjski specjalizujący się w fizyce cząsteczek, automatach komórkowych i algebrze komputerowej, znany jako twórca programu komputerowego Mathematica i założyciel Wolfram Research.
Stanisław Marcin Ulam (ur. 13 kwietnia 1909 we Lwowie, zm. 13 maja 1984 w Santa Fe) – polski i amerykański matematyk (w 1943 przyjął obywatelstwo amerykańskie), przedstawiciel lwowskiej szkoły matematycznej. Współtwórca amerykańskiej bomby termojądrowej Projekt Teller-Ulam.

$\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: $f:S^{m} \to S$

to automat komórkowy definiujemy jako czwórkę: $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 wg Edwarda Fredkina

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

Gra w życie (Life, The game of life) – jeden z pierwszych i najbardziej znanych przykładów automatu komórkowego, wymyślony w roku 1970 przez brytyjskiego matematyka Johna Conwaya.
Sześcian (właściwie sześcian foremny, inaczej heksaedr) to wielościan foremny o sześciu bokach w kształcie identycznych kwadratów. Posiada dwanaście krawędzi i osiem wierzchołków. Ścinając w pewny sposób wierzchołki sześcianu otrzymujemy wielościan półforemny o nazwie sześcian ścięty.

Regularna siatka o $d$ -wymiarowej przestrzeni;
Ustawienie początkowe: $\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 $\vec{r}$ siatki;
Reguła $R = \{R_{1}, R_{2}, \dots, R_{m} \}$ , która ustala stan $\phi(\vec{r}, t)$ w czasie, w następujący sposób: $\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 $\vec{r}+\vec{\delta_{q}}$ oznacza komórki należące do skończonego zbioru sąsiadów $\vec{r}$

czytaj dalej: [2], [3]

w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)