Koncepcja automatu komórkowego

Automatem komórkowym nazywamy siatkę sąsiadujących ze sobą identycznych komórek. Jest to model matematycznymodel matematycznymodel matematyczny, w którym każda w danej chwili posiada jeden ze skończonej liczby swoich stanów. Może być włączona albo wyłączona. Dodatkowo siatka może być $n$-wymiarowa.

Na samym początku działania automatu komórkowego w chwili $t = 0$, każda z komórek przyjmuje stan wylosowany z puli lub określony przez użytkownika. Potem następuje proces ewolucji każdej komórki. Na podstawie stanu swojego i swoich sąsiadów w chwili $t = 0$ przyjmuje stan zgodny z pewnymi przyjętymi przez nas zasadami. Stan ten będzie miał w chwili $t = 1$.

RgVceJhtqz0ys

Ilustracja przedstawia dwa kwadraty o boku pięciu mniejszych kwadratów.
Pierwszy kwadrat podpisany jest jak t=0.
Kwadrat ten posiada mniejsze kwadraty wypełnione niebieski kolorem: rząd drugi kwadrat drugi i czwarty, rząd trzeci kwadrat trzeci, rząd czwarty kwadrat drugi i czwarty.
Od kwadratu tego wychodzi strzałka wskazująca na drugi kwadrat podpisany jako t=1.
Kwadrat ten posiada mniejsze kwadraty wypełnione niebieskim kolorem, rząd pierwszy kwadraty pierwszy, trzeci i piątym, rząd drugi kwadrat trzeci, rząd trzeci kwadraty pierwszy, drugi, czwarty, piąty, rząd czwarty kwadrat trzeci, rząd piąty kwadrat pierwszy, trzeci, piąty.

Zazwyczaj zasady ewolucji są identyczne dla każdej komórki w siatce i nie zmieniają się w czasie. Jednak nie zawsze jest to przestrzegane. Przykładem są stochastyczne automaty komórkowe oraz asynchroniczne automaty komórkowe.

Dodatkowo automaty komórkowe są zazwyczaj symulowane w skończonej przestrzeni. W nieskończonych przestrzeniach pojawia się problem związany z komórkami skrajnymi. Ciężko jest określić, w jaki sposób się z nimi obchodzić oraz jak wpływają na pozostałe komórki.

Historia rozwoju automatów komórkowych

Historia automatów komórkowych sięga lat 40. XX wieku. Wtedy Stanisław UlamStanisław UlamStanisław Ulam, przeprowadzając badania nad rozrostem kryształów w narodowym laboratorium Los Alamos, poznał Johna von NeumannaJohn von NeumannJohna von Neumanna. Neumann w tamtym czasie pracował nad budową robota, który byłby w stanie wyprodukować własną kopię z powszechnie dostępnych materiałów. Ulam zaproponował, żeby koncepcję replikujących się obiektów przenieść do matematycznego modelu.

Był to początek znanych nam dziś automatów komórkowych. Następnie pracami Neumanna zainteresował się brytyjski informatyk Edgar Frank CoddEdgar Frank CoddEdgar Frank Codd. Zaproponował automat komórkowy, który był w stanie obliczyć wszystkie możliwe funkcje i który mógł się rozmnażać. Projekt ten ze względu na swoje skomplikowanie nigdy nie został zrealizowany. Prace Codd'a posłużyły jednak do stworzenia w 1970 roku najbardziej znanego automatu komórkowego, czyli Gry w życie, o której więcej przeczytasz w e‑materiale Gra w życiePhPMLGH2iGra w życie.

Badania nad automatami komórkowymi i ich zastosowaniem w różnych dziedzinach są prowadzone również obecnie. Przykładem jest praca Gerarda Hooft'a opublikowana w 2016 roku, która przedstawia pomysł przebudowania mechaniki kwantowej, wykorzystując automaty komórkowe.

Słownik