Wolframowe Automaty Komórkowe: Zasady, Złożoność i Gra Życia Conwa

Podstawowe automata komórkowe – 256 reguł

Podstawowy automat komórkowy (ECA) składa się z jednej, jednowymiarowej linii komórek binarnych. W każdym kroku czasowym każda komórka jest aktualizowana jednocześnie za pomocą tej samej reguły zastosowanej do komórki i jej dwóch sąsiadów. Ponieważ istnieje 2³ = 8 możliwych konfiguracji sąsiedztwa i 2 możliwe wyjścia dla każdej z nich, powstaje dokładnie 2⁸ = 256 różnych reguł. Ta skema numerowania "Wolfram code" (1983) przypisuje każdej regule unikalny, liczbowy identyfikator w zakresie od 0 do 255; reguły są generowane poprzez ewolucję z pojedynczej komórki początkowej, w której czas płynie w dół, tworząc "diagram czasoprzestrzenny" automatu.

Rule 30: 30 = 00011110₂
neighbourhood: 111 110 101 100 011 010 001 000
output:          0   0   0   1   1   1   1   0

Cztery klasy złożoności Wolfram'a

Wolfram sklasyfikował wszystkie 256 prostych reguł w cztery jakościowe klasy na podstawie długoterminowego zachowania. Klasa I – Jednorodność: wszystkie komórki ulegają upadkowi do jednego, ustalonego stanu niezależnie od początkowych warunków (Reguły 0, 8, 32). Klasa II – Okresowość/Stabilność: komórki ustalają się w prostych okresowych lub stabilnych wzorach (Reguły 4, 19, 50). Klasa III – Chaos: nieregularne, pozornie losowe wzory, wrażliwe na początkowe warunki (Reguła 30, 45, 73). Klasa IV – Złożoność: długotrwałe, niokresowe, lokalizowane struktury, które wchodzą ze sobą w skomplikowane interakcje, związane z obliczeniami i uniwersalnością (Reguły 54, 106, 110). Zachowanie Klasy IV, na granicy między porządkiem a chaosem, stanowi "brzeg chaosu", gdzie hipotetycznie działają również życie i poznanie.

Ważne zasady: 30, 90, 110

Zasada 30 generuje chaotyczny, nieregularny wzór z pojedynczej żyjącej komórki; jej centralna kolumna jest statystycznie wystarczająco losowa, aby Wolfram wykorzystał ją jako wbudowany pseudolosowy generator w Mathematica.

Zasada 90 (XOR lewej i prawej sąsiadującej komórki, pomijając środkową) generuje trójkąt Sierpińskiego — rzędy n odpowiadają trójkątowi Pascala modulo 2.

Zostało udowodnione przez Matthew Cooka w 2004 roku, że zasada 110 jest Turinga kompletna: zasada opisywana pojedynczym bajtem może symulować dowolną maszynę Turinga, co czyni ją najprostszym znanym uniwersalnym systemem obliczeniowym.

Dwa wymiary: Gra Życia Conwa

W CA w 2D komórki znajdują się na siatce z sąsiedztwem Von Neumanna (4 sąsiędzie prostopadłych, używanym w reakcjach i dyfuzji) lub sąsiedztwie Moore'a (wszystkie 8 otaczających komórek). Wprowadzona przez Johna Conwa w 1970 roku, Gra Życia jest 2D-ową, całkowitą automatyczną komórką (CA) z sąsiedztwem Moore’a, zgodnie z regułami B3/S23: martwa komórka powstaje, gdy ma dokładnie 3 żywe sąsiadów, a żywa komórka przetrwała, gdy ma 2 lub 3 sąsiadów. Z tych trzech zasad wyłania się niezwykła menażeria – statyczne formy takie jak blok, oscylatory takie jak błysk i pulsar, stateczki takie jak sterowie, oraz stateczki-pistolety emitujące stateczki w nieskończoność. Stateczka-pistolet plus bramki logiczne wystarczy do symulacji dowolnego obliczenia, co czyni Życie samo w sobie Turingiem kompletnym.

Zastosowania w nauce i sztuce

Model reakcji i dyfuzji Alberta Turinga z 1952 roku generuje wzory na sierści zwierząt – plamy lwa, prążki zebry – poprzez mechanizm podobny do CA, polegający na rozprzestrzenianiu się i reagowaniu chemikaliów-aktywatorów i hamujących. Model Nagel-Schreckenberga to 1D CA, który odtwarza korki drogowe bez centralnej kontroli, wyłaniając się wyłącznie z lokalnych zasad przyspieszania, hamowania i losowego spowalniania. Artyści i twórcy gier wykorzystują CA do generowania organicznych tekstur – zasada 30 dla losowości, wygładzanie birth-3/survival-2-3 do generowania jaskiń i korytarzy oraz agregacja ograniczona dyfuzją do wzrostu kryształów.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz the simulation i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.