🟦 Automaty komórkowe 1D — Wolfram

Automat komórkowy to siatka komórek, z których każda znajduje się w jednym ze skończonej liczby stanów, ewoluująca w dyskretnych krokach czasowych. W jednowymiarowym elementarnym automacie komórkowym każda komórka jest albo żywa (1), albo martwa (0), a następny stan każdej komórki jest określany przez ustaloną regułę zastosowaną do tej komórki i jej dwóch sąsiadów. Powtarzanie tego procesu pokolenie po pokoleniu, wiersz po wierszu, buduje na ekranie wzór wizualny od góry do dołu.

Wpisz dowolny numer reguły od 0 do 255 w polu wprowadzania lub kliknij jeden z przycisków presetów (reguła 30, 90, 110, 184), aby przejść do znanych przykładów. Możesz też przełączać poszczególne bity w tabeli reguły złożonej z 8 komórek, aby dostroić regułę. Dostosuj rozmiar komórki, aby zobaczyć drobniejsze lub grubsze szczegóły, ustaw prędkość, aby kontrolować liczbę pokoleń na klatkę, i wybierz start od pojedynczej żywej komórki, losowego szumu lub symetrycznego losowego wiersza.

Reguła 90 oblicza XOR dwóch sąsiadów komórki, ignorując samą komórkę. Zaczynając od pojedynczej żywej komórki, ta operacja XOR jest matematycznie równoważna obliczaniu współczynników dwumianowych modulo 2 — dokładnie tej samej operacji, która generuje trójkąt Pascala modulo 2, będący fraktalem trójkąta Sierpińskiego. Samopodobny trójkątny wzór wynika nieuchronnie z tej arytmetyki, pokazując, jak geometria fraktalna może powstać z elementarnych operacji.

System jest zupełny w sensie Turinga, jeśli potrafi symulować dowolne obliczenie, jakie może wykonać komputer ogólnego przeznaczenia, przy wystarczającej ilości czasu i pamięci. Matthew Cook udowodnił w 2004 roku, że reguła 110 jest zupełna w sensie Turinga, pokazując, że potrafi symulować uniwersalny cykliczny system znakowania. Oznacza to, że reguła 110 — jednowymiarowa linia binarnych komórek aktualizowana tabelą zaledwie 8 bitów — jest w zasadzie zdolna do wykonania dowolnego algorytmu, co czyni ją jednym z najprostszych znanych uniwersalnych podłoży obliczeniowych.

Reguła 184 odwzorowuje bezpośrednio asymetryczny prosty proces wykluczania (ASEP), standardowy model ruchu drogowego. Każda żywa komórka reprezentuje pojazd, a reguła przesuwa pojazdy o jedną pozycję do przodu, jeśli komórka przed nimi jest pusta, w przeciwnym razie pozostają na miejscu. To naturalnie odtwarza rzeczywiste zjawiska drogowe: przy niskiej gęstości pojazdy poruszają się swobodnie; powyżej krytycznej gęstości korek propaguje się do tyłu jako fala. Reguła 184 jest wykorzystywana w fizyce i naukach o transporcie jako najprostszy dyskretny model ruchu drogowego oddający zachowanie fali korka.

Reguła 30 nie jest losowa — jest całkowicie deterministyczna — ale wzór, który generuje z pojedynczej żywej komórki, jest udowodnienie chaotyczny i przechodzi standardowe testy statystyczne na losowość. Wolfram wykorzystywał centralną kolumnę reguły 30 jako generator liczb pseudolosowych w Mathematice przez wiele lat. Wzór jest tak wrażliwy na warunki początkowe i tak wizualnie nieprzewidywalny, że przewidywanie przyszłych stanów bez uruchamiania reguły krok po kroku wydaje się obliczeniowo nieredukowalne.

Jednowymiarowe automaty komórkowe zostały po raz pierwszy zbadane na początku lat 80. XX wieku przez Stephena Wolframa, który przeprowadził systematyczny przegląd wszystkich 256 elementarnych reguł i opublikował swoje wyniki począwszy od 1983 roku. Wolfram sklasyfikował reguły w cztery klasy zachowań — punkty stałe, wzory okresowe, wzory chaotyczne i złożone zachowanie klasy IV — taksonomię, która pozostaje wpływowa w nauce o złożoności. Jego książka „A New Kind of Science” (2002) rozszerzyła te idee w szerszą teorię złożoności.

Gra w życie Conwaya to najsłynniejszy dwuwymiarowy automat komórkowy, wykorzystujący sąsiedztwo 3x3 i osiągający zupełność w sensie Turinga. Trójkąt Sierpińskiego dzieli swoją strukturę fraktalną z regułą 90. Systemy reakcji-dyfuzji, takie jak model Graya-Scotta, rozszerzają lokalne reguły na ciągłą chemię. Automaty o większym sąsiedztwie obejmują Wireworld, który potrafi emulować cyfrowe obwody logiczne.

Reguła 30 była wykorzystywana jako generator liczb pseudolosowych w systemach algebry komputerowej. Metody Lattice-Boltzmanna wykorzystują modele oparte na automatach komórkowych do symulacji dynamiki płynów w aerodynamice i mikroprzepływach. W sprzęcie rejestry przesuwne oparte na automatach komórkowych pojawiają się w szyfrach strumieniowych i kodach korekcyjnych. Naukowcy wykorzystali też automaty komórkowe do projektowania samoreplikujących się systemów robotycznych i materii programowalnej.

Obecne badania obejmują odwracalne automaty komórkowe istotne dla obliczeń kwantowych oraz ciągłe automaty komórkowe (Lenia), które tworzą przypominające żywe organizmy. Naukowcy badają automaty komórkowe jako modele czasoprzestrzeni w skali Plancka. Neuronowe automaty komórkowe, trenowane metodami głębokiego uczenia do wzrastania w docelowe obrazy i samonaprawy, otwierają nowy obszar łączący uczenie maszynowe z paradygmatem automatów komórkowych.