Czym jest automat komórkowy?
Automat komórkowy (CA) to siatka komórek, z których każda znajduje się w jednym z niewielu możliwych stanów (często tylko dwóch: żywa/martwa, włączona/wyłączona, płonąca/niepłonąca). Przy każdym takcie zegara każda komórka stosuje tę samą regułę do swojego sąsiedztwa i aktualizuje swój stan. Żadna komórka nie ma specjalnego statusu. Żadna komórka nie „wie" nic o globalnej siatce.
Mimo tej radykalnej prostoty automaty komórkowe potrafią symulować niemal każdy złożony system — co skłoniło Stephena Wolframa do postawienia w 2002 roku tezy, że sam wszechświat może być automatem komórkowym.
Gra w Życie Conwaya
Najsłynniejszy automat komórkowy, wymyślony przez matematyka Johna Hortona Conwaya w 1970 roku. Siatka jest nieskończona. Każda komórka jest albo żywa, albo martwa. Reguła zależy od tego, ile spośród ośmiu sąsiadów jest żywych:
| Obecny stan | Żywi sąsiedzi | Następny stan |
|---|---|---|
| Martwa | Dokładnie 3 | Narodziny (żywa) |
| Żywa | 2 lub 3 | Przeżywa |
| Żywa | < 2 | Umiera (niedostatek populacji) |
| Żywa | > 3 | Umiera (przegęszczenie) |
Z tych czterech reguł wyłaniają się wzory, które potrafią poruszać się (szybowce), oscylować (mruganki), tworzyć inne wzory (działa) — a nawet tworzyć w pełni działającą maszynę Turinga, czyli wzór zdolny symulować dowolny program komputerowy. Gra w Życie jest zupełna w sensie Turinga.
Wypróbuj: W naszym symulatorze automatów komórkowych wybierz „Grę w Życie" i narysuj losowy fragment. Kliknij krok raz, dwa razy, pięć razy — obserwuj, jak różne kształty początkowe mają zupełnie inne losy.
Elementarne automaty Wolframa
Stephen Wolfram badał najprostsze możliwe automaty komórkowe: jednowymiarowe (pojedynczy rząd komórek), dwa stany, sąsiedztwo złożone z 3 komórek. Istnieje dokładnie 256 możliwych reguł (numerowanych 0–255 w zapisie binarnym). Wolfram podzielił je wszystkie na cztery klasy:
Automaty komórkowe w świecie rzeczywistym
Wzrost kryształów
Płatki śniegu rosną jako dwuwymiarowy automat komórkowy na sieci heksagonalnej. Para wodna osadza się na istniejącym lodzie — ale tylko na komórkach z odpowiednią liczbą sąsiadów. Efekt: rozgałęziona symetria sześciokrotna. W naszej symulacji wzrostu kryształów możesz zmieniać temperaturę i obserwować, jak pojawia się i wyostrza rozgałęzienie dendrytyczne.
Model pożaru lasu
Trzy stany: puste, drzewo, płonące. Każda płonąca komórka podpala swoich sąsiadów. Przy każdym takcie drzewa odrastają losowo. Iskry uderzają losowo. System samoorganizuje się do krytycznej gęstości — zawsze na granicy katastrofalnego pożaru. Ten wzorzec, samoorganizująca się krytyczność, został odkryty podczas badania rzeczywistych danych o pożarach w Kalifornii.
Reakcja-dyfuzja (Gray-Scott)
Dwa gatunki chemiczne reagują ze sobą i dyfundują po siatce. Różne proporcje parametrów dają plamy (skóra leoparda), pasy (zebra), spirale (koral) i labiryntopodobne wzory — spotykane wszędzie w biologii. Natura wykorzystuje reakcję-dyfuzję jako zegar rozwojowy do rozmieszczania mieszków włosowych, linii papilarnych i plam pigmentowych. Wypróbuj symulator reakcji-dyfuzji i dostosuj szybkości podawania i zabijania.
Przepływ ruchu drogowego
Model Nagela-Schreckenberga to jednowymiarowy automat komórkowy samochodów na autostradzie. Każdy samochód przyspiesza lub hamuje w zależności od swoich sąsiadów. Z tego wyłaniają się zjawiskowe korki — falujące fale ruchu typu stop-and-go bez widocznej przyczyny.
Dlaczego to ma znaczenie
Automaty komórkowe zacierają granicę między fizyką a obliczeniami. Sugerują, że bogactwo świata naturalnego może nie wymagać skomplikowanych praw — a jedynie prostych reguł, stosowanych jednolicie, iterowanych w nieskończoność. Za każdym razem, gdy patrzysz na wzór na muszli, wydmę piasku czy chmurę, patrzysz na wynik działania własnego automatu komórkowego natury.