Komórkowy automat składa się z regularną siatką „komórek” każdy zawierający „państwo”, wybrany spośród skończonego zbioru, a które mogą się zmieniać w czasie. Stan komórki w czasie t + 1 jest funkcją stanu w czasie t skończonej liczby komórek zwanych jej „sąsiedztwem”. Z każdą nową jednostką czasu te same reguły są stosowane jednocześnie do wszystkich komórek siatki, tworząc nową „generację” komórek zależną całkowicie od poprzedniej generacji.
Studiując matematykę i informatykę teoretyczną , automaty komórkowe są zarówno dyskretnym modelem systemu dynamicznego, jak i modelem obliczeniowym . Model automatów komórkowych jest niezwykły ze względu na różnicę między prostotą jego definicji a złożonością, jaką mogą osiągnąć pewne zachowania makroskopowe : ewolucja w czasie wszystkich komórek nie jest (po prostu) zredukowana do lokalnej reguły, która definiuje system. Jako taki stanowi jeden ze standardowych modeli w badaniu złożonych systemów .
Najprostszy nietrywialny automat komórkowy, jaki możemy sobie wyobrazić, składa się z jednowymiarowej siatki komórek, która może przyjmować tylko dwa stany („0” lub „1”), z otoczeniem utworzonym dla każdej komórki. i dwie komórki przylegające do niego.
Każda z komórek może przyjąć dwa stany, są 2 3 = 8 możliwych konfiguracji (lub wzorców) takiego sąsiedztwa. Aby automat komórkowy działał, konieczne jest zdefiniowanie, jaki musi być stan komórki w następnej generacji z każdego z tych powodów. Jest na to 2 8 = 256 różnych sposobów, a więc 256 różnych automatów komórkowych tego typu.
O automatach z tej rodziny mówi się, że są „elementarne”. Często są one oznaczane liczbą całkowitą z przedziału od 0 do 255, której binarną reprezentacją jest sekwencja stanów przyjmowanych przez automat na kolejnych wzorcach 111, 110, 101 itd.
Jako przykład rozważmy automat komórkowy zdefiniowany w poniższej tabeli, który podaje regułę ewolucji:
Początkowy powód ( t ) | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
---|---|---|---|---|---|---|---|---|
Następna wartość komórki centralnej ( t +1) | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
Oznacza to, że jeśli na przykład w danym momencie t komórka jest w stanie „1”, jej lewy sąsiad w stanie „1”, a prawy sąsiad w stanie „0” (kolumna 2 tabeli), w chwili t + 1 będzie w stanie „0”.
Jeśli zaczniemy od początkowej siatki, w której wszystkie komórki są w stanie „0” z wyjątkiem jednej, otrzymamy:
gdzie każdy wiersz jest wynikiem poprzedniego wiersza.
Zgodnie z konwencją reguła ta nazywana jest „regułą 30”, ponieważ 30 w systemie dziesiętnym zapisuje się jako 00011110 w systemie dwójkowym, a 00011110 to druga linia tabeli powyżej, opisująca regułę ewolucji.
„ Gra w życie ” to dwuwymiarowy automat komórkowy, w którym każda komórka może przyjąć dwie wartości („0” lub „1”, ale mówimy raczej o „żywej” lub „martwej”) i gdzie jej przyszły stan jest określony przez jego aktualny stan i liczbę żywych komórek spośród ośmiu otaczających go:
Pozornie proste, zasady te wprowadzają wiele złożoności.
Na tej samej zasadzie możemy sobie wyobrazić dużą liczbę reguł, zmieniając progi narodzin lub przeżycia lub dodając dodatkowe stany itp. Wśród tych odmian możemy przytoczyć:
Aby określić zmiany stanu komórki, niektóre uwzględniają tylko bezpośrednich sąsiadów rozpatrywanego pudełka, ale inne uwzględniają również stan sąsiednich komórek w promieniu dwóch lub nawet więcej pól. Inni również przypisują większą wagę niektórym pudełkom w sąsiedztwie niż innym ( WeightedLife ).
Możliwych reguł definiowania automatu komórkowego jest bardzo wiele, nawet przy niewielkiej liczbie stanów i małym sąsiedztwie :
2 stany | 3 stany | 4 stany | 5 stanów | |
---|---|---|---|---|
2 sąsiadów | 16 | 19 683, | 4.294.967.296 | |
3 sąsiadów | 256 | 7 625 597 484 987 | ||
4 sąsiadów | 65,536 | |||
5 sąsiadów | 4.294.967.296 | |||
6 sąsiadów |
Model automatów komórkowych oferuje zatem ogromne pole eksploracji. To nie jest trudne do zaprogramowania komórkowy symulator automat i Web jest pełne mniej lub bardziej udanych osiągnięć. Na stronie Mirka Wojtowicza można znaleźć m.in. oprogramowanie symulacyjne oraz bardzo bogatą galerię przykładów: Mirek's Cellebration . Innym interesującym przykładem symulatora jest Golly . Dedykowany jest głównie do gry w życie i zoptymalizowany pod kątem tego automatu, wykorzystując w szczególności poczwórne drzewo połączone z hashem .
W latach czterdziestych Stanisław Ulam badał wzrost kryształów w Los Alamos National Laboratory , modelując go na siatce. W tym samym czasie John von Neumann , kolega Ulama z Los Alamos, pracował nad samoreplikującymi się systemami i miał trudności z wyjaśnieniem swojego początkowego modelu robota, który kopiowałby się z zestawu odłączonych części. Ulam zasugerował, że inspirację czerpie ze swojej pracy, co skłoniło von Neumanna do zaprojektowania abstrakcyjnego modelu matematycznego dla swojego problemu. W rezultacie powstał „kopiarka i uniwersalny konstruktor ” ( uniwersalny konstruktor i kopia w języku angielskim), pierwszy automat komórkowy: był oparty na dwuwymiarowej siatce, w której każda komórka mogła przyjmować 29 stanów. Von Neumann skonstruował tam specjalny wzór i pokazał, że może bez końca tworzyć swoje kopie.
W 1969 roku Gustav Arnold Hedlund opublikował Endomorfizmy i automorfizmy systemu dynamicznego przesunięcia , około 60-stronicową monografię, będącą syntezą 10-letnich badań społeczności zajmującej się dynamiką symboliczną (gałąź badań układów dynamicznych w matematyce, założona w szczególności przez M. Morse'a i GA Hedlunda). To właśnie ta publikacja stanowi matematyczną podstawę do badania automatów komórkowych jako poszczególnych układów dynamicznych.
Również w 1969 roku Konrad Zuse opublikował Rechnender Raum („When Space Calculates”), w którym wysunął hipotezę, że prawa fizyczne są dyskretne, a Wszechświat jest wynikiem gigantycznego automatu komórkowego.
W latach siedemdziesiątych dwuwymiarowy, dwustanowy automat komórkowy zwany „ grą w życie ”, wymyślony przez Johna Conwaya , odniósł wielki sukces, szczególnie w wyłaniającej się społeczności komputerowej. Został spopularyzowany przez Martina Gardnera w artykule w Scientific American .
W 1983 roku Stephen Wolfram opublikował pierwszą z serii publikacji, w których systematycznie analizował rodzaj bardzo prostych automatów komórkowych. Złożoność ich zachowania, wywołana przez elementarne reguły, doprowadziła go do przypuszczenia, że podobne mechanizmy mogą wyjaśniać złożone zjawiska fizyczne, idee, które rozwinął w swojej książce A New Kind of Science opublikowanej w 2002 roku.
Jeśli popularność modelu automatów komórkowych wynika w dużej mierze z podejścia eksperymentalnego, to Von Neumann od początku traktował go jako obiekt matematyczny . Większość formalnych prac nad automatami komórkowymi wykorzystuje poniższą definicję, chociaż model dopuszcza wiele interesujących uogólnień i odmian .
Automat komórkowy to -uplet, w którym:
Przypisanie stanu każdej komórce sieci nazywa się wtedy konfiguracją : konfiguracja jest elementem , to znaczy funkcją in .
Z tym skończonym i lokalnym opisem kojarzymy globalną funkcję ewolucji automatu , która oddziałuje na konfiguracje i która jest definiowana przez dla dowolnej konfiguracji (gdzie ).
Automaty komórkowe były badane jako systemy dynamiczne od lat sześćdziesiątych XX wieku w ramach pracy GA Hedlunda. Gdy rozmiar i alfabet są przyłączone, mogą być dostarczone konfiguracje przestrzeni metrycznych z Cantor przez odległości określonej przez
Zbiór automatów komórkowych alfabetu i wymiaru jest następnie scharakteryzowany przez twierdzenie Curtisa-Hedlunda-Lyondona: jest globalną funkcją takiego automatu komórkowego wtedy i tylko wtedy, gdy jest funkcją ciągłą, której komutuje z funkcjami przesunięcia (dowolna pozycja w tablica komórek odpowiada funkcji przesunięcia ).
Stamtąd automaty komórkowe można badać wszystkimi narzędziami klasycznej teorii układów dynamicznych , teorii chaosu i teorii ergodycznej , wyposażając przestrzeń konfiguracji miary .
Ta gałąź teorii automatów komórkowych pozostaje szeroko otwarta i nadal jest przedmiotem badań (zobacz tutaj przykład ważnej nierozwiązanej dotąd kwestii).
Automaty komórkowe można traktować zarówno jako dyskretne systemy dynamiczne, jak i systemy obliczeniowe . W ten sposób każdy automat jest zdolny do wykonywania pewnych obliczeń lub wykazywania pewnych dynamicznych zachowań. Czy ktoś przyjmuje jeden punkt widzenia, lub z drugiej strony, można zadać to samo pytanie: czy istnieje automat w stanie zrobić wszystko, że automaty komórkowe mogą zrobić? Mówi się więc, że taki automat jest uniwersalny .
Pojęcie uniwersalności odpowiada bardzo prostej i bardzo ogólnej idei, ale musimy uważać na to, że zgodnie ze znaczeniem, jakie stawiamy za wyrażeniem „zdolny do działania”, automaty uniwersalne nie są tym samym. Możemy wyróżnić dwa typy pojęć uniwersalności automatów komórkowych: uniwersalność Turinga, która wiąże się ze zdolnością obliczeniową, oraz uniwersalność wewnętrzna, która wiąże się ze zdolnością do wywoływania określonych zachowań dynamicznych.
Niezwykłym faktem jest to, że dla każdego z tych pojęć istnieją uniwersalne automaty. Należy również zauważyć, że pojęcie wewnętrznej uniwersalności jest silniejsze niż uniwersalność Turinga: rzeczywiście, bez wchodzenia w szczegóły, automat zdolny do symulacji wszystkich automatów może w szczególności symulować uniwersalny automat Turinga, a zatem wykonywać wszystkie obliczenia Turinga. Z drugiej strony istnieją uniwersalne automaty komórkowe Turinga, które nie są z natury uniwersalne.
Turing UniversalityUniwersalność Turinga to adaptacja automatów komórkowych o uniwersalności do obliczeń . Możemy zdefiniować to pojęcie jako zdolność automatu do symulacji uniwersalnej maszyny Turinga. Ta możliwość symulowania maszyny Turinga przez automat komórkowy jest bardzo prosta i znana była z prac Johna von Neumanna . Istnieje kilka sposobów na sformalizowanie tego, a jeden z najprostszych jest następujący. Jeśli jest to maszyna Turinga działająca z alfabetem wstążkowym i zestawem stanów , możemy zdefiniować automat komórkowy zdolny do symulacji :
Często spotykamy się z bardziej ogólnym (ale bardziej nieformalnym) znaczeniem uniwersalności Turinga: automat komórkowy jest Turinga-uniwersalny, jeśli jest w stanie symulować kompletny system obliczeniowy Turinga . Termin symulacja rzadko jest sformalizowany w ogólnych ramach. Ważną kwestią jest to, że transformacja wejść / wyjść symulowanego systemu na wejścia / wyjścia symulatora pozostaje prosta: bez tego warunku uzyskujemy pojęcie braku zainteresowania z powodu automatów, które nic nie robią ( na przykład tożsamość ) stają się uniwersalne dzięki przekształceniom wejścia / wyjścia, które wykonują za nich wszystkie obliczenia.
Wewnętrzna uniwersalnośćZ natury uniwersalny automat komórkowy jest automatem zdolnym do symulowania krok po kroku zachowania dowolnego automatu komórkowego o tym samym wymiarze. Mówiąc dokładniej, idea symulacji krok po kroku opiera się na następujących zasadach:
Na przykład gra w życie jest w stanie zasymulować krok po kroku automat z 2 stanami (czarnym i czerwonym), który wykonuje proste przesunięcie stanów w kierunku południowo-wschodnim:
Tak więc, aby zasymulować zachowanie z określonej konfiguracji początkowej, wystarczy wytworzyć konfigurację gry w życie, w której każda grupa jest wypełniona martwymi komórkami lub szybowcem, w zależności od stanu komórki, w której się znajduje .
Godne uwagi jest to, że dzięki tej bardzo prostej zasadzie symulacji niektóre automaty są w stanie zasymulować dowolny automat komórkowy z dowolnej konfiguracji: tak jest w przypadku gry w życie, jak wyjaśniono w następnej sekcji . Oczywiście, aby symulować automaty z coraz większą liczbą stanów, automat z natury uniwersalny wykorzystuje coraz większe grupy komórek. Rzeczywiście, przy ustalonym typie grupy komórek istnieje tylko skończona liczba możliwych symulacji. Tak więc, kiedy obserwujemy ewolucję gry w życie na ekranie (jakkolwiek jest ona duża), nie widzimy wszystkich zachowań, które gra w życie jest w stanie zasymulować; jednak ten automat jest zdolny do wywoływania wszystkich zachowań automatu komórkowego.
PrzykładyHistorycznie rzecz biorąc, pierwszy automat komórkowy zbudowane z właściwością uniwersalności Turing (w tym przypadku) jest uniwersalny konstruktor od Johna von Neumanna : chodzi o wymiarze 2 automat z 29 państw, które jest ponadto zdolne s „samoreplikacji.
Jeśli chodzi o pojęcie wewnętrznej uniwersalności, musieliśmy poczekać do lat 70. ubiegłego wieku z pracami banków ER, które zaproponowały automat komórkowy o wymiarze 2 z 2 stanami i 5 sąsiadami. Oferuje również z natury uniwersalny 1-wymiarowy automat z 5 stanami, ale którego sąsiedztwo jest ogromne.
Najbardziej znanym przykładem uniwersalnego automatu jest z pewnością gra w życie . Udowodniono, że Turing jest uniwersalny w książce Winning Ways for your Mathematical Plays . Dowód polega na zbudowaniu elementów konfiguracji, które można zmontować i które odpowiadają wszystkim komponentom niezbędnym do produkcji obwodów logicznych (przewody, skrzyżowania przewodów, powielanie, bramki logiczne itp.). Kompletną konstrukcję maszyny Turinga w Game of Life można znaleźć na stronie Paula Rendella . Opierając się na tych samych ideach, ostatnio udowodniono, że gra w życie jest z natury uniwersalna.
W przypadku wymiaru 1 nastąpił niedawno przełom w zakresie uniwersalności Turinga: pan Cook udowodnił, że podstawowy automat komórkowy numer 110 jest uniwersalny według Turinga. Swoje pomysły przedstawił już w 1998 roku na konferencji CA98 , ale wynik ten został (częściowo) rozpowszechniony na piśmie dopiero w 2002 roku za pośrednictwem A New Kind of Science S. Wolframa. Rzeczywiście, pan Cook był zatrudniony przez Wolfram Research do pracy nad książką A New Kind of Science, a jego praca nie została opublikowana w aktach CA98 po procesie sądowym opartym na umowie o nieujawnianiu . Pełny dowód wyniku dr Cooka został ostatecznie opublikowany w czasopiśmie naukowym w 2004 roku.
Z drugiej strony nadal nie wiemy dzisiaj, czy automat 110 jest z natury uniwersalny, czy też nie. Najmniejszy jednowymiarowy automat z otoczeniem 3 komórek, który do tej pory okazał się wewnętrznie uniwersalny, ma 4 stany.
Ogólnie rzecz biorąc, niezwykle trudno jest określić ogólne zachowanie automatu komórkowego, badając jego lokalną regułę przejścia. Powoduje to nierozstrzygalność wpływającą na najprostsze właściwości. W tej dziedzinie możemy przytoczyć prace Jarkko Kari, który sprytnie wykorzystując znane już wyniki dotyczące dachówek , wykazał, że nierozstrzygalne są następujące problemy:
Fakt, że automaty komórkowe mogą symulować dowolną maszynę Turinga, prowadzi również do nierozstrzygalnych problemów o innej naturze. Na przykład, dla niektórych automatów komórkowych, następujące problemy są także nierozstrzygalne :
Jak wyjaśniono powyżej, lokalne reguły automatów komórkowych są zbyt liczne, aby można było je szczegółowo zbadać, a przewidywanie zachowania zgodnie z lokalnymi regułami jest ogólnie bardzo trudnym problemem. Dlatego badanie automatów komórkowych często ogranicza się do określonych rodzin, albo dlatego, że łatwiej poddają się analizie, albo dlatego, że odpowiadają interesującej własności.
Automat komórkowy jest odwracalny, jeśli istnieje automat komórkowy, taki jak dwie globalne funkcje ewolucji, i są one odwrotne do siebie: jest funkcją tożsamości. Intuicyjnie „cofa się w czasie” ewolucji i odwrotnie, „cofa się w czasie” ewolucji . Zgodnie z twierdzeniem Hedlunda, możemy scharakteryzować odwracalne automaty komórkowe jako te, których funkcja globalna jest bijektywna .
Klasa ta została bardzo dobrze zbadana, w szczególności dlatego, że dostarcza modelu zbliżającego się do rzeczywistego świata fizycznego, rzekomo odwracalnego w skali mikroskopowej (patrz na ten temat artykuł o odwracalności i nieodwracalności w termodynamice ). T. Toffoli i N. Margolus są jednymi z pierwszych, którzy są szczególnie zainteresowani odwracalnymi automatami komórkowymi. Zainteresowanie leży również w poszukiwaniu odwracalnych systemów obliczeniowych, które mają zużywać mniej energii zgodnie z zasadą Landauera . Obecnie ustalono, że pewne odwracalne automaty komórkowe są uniwersalnym Turingiem (dziełem Kenichi Mority).
UznanieAlgorytmicznie niemożliwe jest odróżnienie automatów komórkowych odwracalnych od automatów, których nie ma, gdy wymiar jest większy niż 2. Z drugiej strony, w wymiarze 1 istnieje bardzo wydajny algorytm.
Inny sposób przedstawienia tej różnicy między wymiarem 1 a większymi wymiarami jest następujący: rozmiar sąsiedztwa odwrotności automatu nie może być rekurencyjnie ograniczony zgodnie z rozmiarem sąsiedztwa, gdy wymiar wynosi 2 lub więcej, podczas gdy jest wielomianowo ograniczony w wymiarze 1 (niedawny wynik pokazuje nawet, że granica jest liniowa ).
PrzykładyŁatwo jest skonstruować odwracalne automaty komórkowe. W tym celu istnieje kilka form konstrukcji.
Automaty komórkowe są na ogół dynamicznymi systemami nieliniowymi , co utrudnia ich badanie za pomocą konwencjonalnych narzędzi. Ale ta ogólna prawda nie przeszkadza niektórym automatom komórkowym posiadać mniej lub bardziej ścisłej formy liniowości.
DefinicjaFormalnie mówi się, że automat alfabetu jest liniowy, jeśli możemy podać prawo grupowe , takie jak:
W tym przypadku, jeśli rozciągniemy na operację działającą komórka po komórce w przestrzeni konfiguracyjnej, globalna funkcja związana z automatem jest rzeczywiście funkcją liniową .
Liniowość znacznie ułatwia badanie dynamiki automatów. Zatem wystarczy znać dynamikę automatu liniowego na „ podstawie ” przestrzeni jego konfiguracji, aby na podstawie liniowości wydedukować jego zachowanie w całej przestrzeni. Można wybrać dla takiej bazy przycisk (skończone) zestaw konfiguracjach wszędzie równa ( neutralny z ), z wyjątkiem być może w centralnej komórce.
Automaty addytywneJedną z najczęściej badanych rodzin automatów liniowych jest tzw. Automaty addytywne , wprowadzone przez O. Martina, A. Odlyzko i S. Wolframa w. Te kontrolery są zdefiniowane w następujący sposób:
Typowym przykładem jest taki, w którym wszystkie współczynniki są równe 1: lokalna reguła polega wówczas na wzięciu sumy modulo n wszystkich komórek w sąsiedztwie. Zatem w wymiarze 1 elementarny automat komórkowy 90 jest addytywny: jego funkcja przejściowa polega na sumowaniu stanów modulo 2 dwóch sąsiadów komórki. Wystarczy znać zachowanie tego automatu na konfiguracji wszędzie równej 0 poza centrum, gdzie warto 1, aby wydedukować z niego jego ogólne zachowanie na zasadzie superpozycji:
Automat elementarny 102 również jest addytywny. Jego działanie na konfigurację daje trójkąt Pascala modulo 2 (co również daje przybliżenie trójkąta Sierpińskiego ). A więc zaczynając od , komórka po krokach jest w stanie:
Dzięki superpozycji wnioskujemy o bezpośredniej ekspresji stanu komórki centralnej po kroku, zaczynając od dowolnej konfiguracji :
W totalistycznym automacie komórkowym następny stan komórki zależy tylko od sumy stanów jej sąsiadów; tak jest w przypadku gry w życie, w której żywa komórka pozostaje taka sama, jeśli żyje dwóch lub trzech jej sąsiadów, a martwa komórka rodzi się, gdy trzech z jej sąsiadów żyje. Dlatego automat totalistyczny nie bierze pod uwagę położenia sąsiadów komórki względem niej.
Jeśli automat komórkowy nie jest totalistyczny, to poza własnym stanem położenie sąsiadów komórki wpływa na jej późniejszy stan. Na przykład dla jednowymiarowego automatu komórkowego możemy rozróżnić sąsiednią komórkę po lewej i sąsiadującą po prawej.
Klasyfikacja ta została wprowadzona przez Stephena Wolframa w 1983 r. W jego artykule Uniwersalność i złożoność w automatach komórkowych i stanowi pierwszą próbę klasyfikacji automatów komórkowych według ich ewolucji z losowych konfiguracji początkowych. Zaproponował cztery klasy zachowań:
Jedna z krytyki klasyfikacji Wolframa polega na tym, że nie jest ona w stanie powiedzieć, czy dany automat komórkowy jest uniwersalny według Turinga ; ponadto dla każdej z klas zaproponowanych przez Wolframa znaleziono uniwersalne automaty komórkowe. Taki stan rzeczy wynika z tego, co Wolfram uważał jedynie za przypadkowe warunki początkowe, a nie konkretne struktury stworzone specjalnie na tę okazję. W szczególności nie uwzględnia się przekazywania informacji, na przykład za pośrednictwem statków .
David Eppstein zaproponował alternatywę dla tej klasyfikacji:
A priori , tylko ostatnie przypadki dopuszczają uniwersalność, nawet jeśli wszystkie automaty komórkowe, które na nie odpowiadają, nie są. Z drugiej strony nie wykazano również, że niemożliwe jest zbudowanie uniwersalnych konstrukcji dla pozostałych przypadków, inne konstrukcje niż statki również mogą przekazywać informacje.
W powyższej definicji formalnej sieć ma systematyczną formę . Możemy bez problemu uogólniać na inne regularne wykresy nieskończone.
Pierwsza klasyfikacja automatu komórkowego dotyczy sposobu stosowania reguł na siatce:
Można uogólnić pojęcie automatu komórkowego, na przykład:
Kontrolery ciągłe działają na tej samej zasadzie co automaty komórkowe, ale używają siatek lub stanów ciągłych (zwykle od 0 do 1). Takie automaty mogą na przykład symulować dyfuzję cieczy.
Probabilistyczny automat komórkowy to deterministyczny automat komórkowy, w którym lokalna reguła f jest zastępowana przez losową lokalną dynamikę, to znaczy macierz przejścia, która wskazuje zgodnie ze stanem, w którym się znajdujemy, z jakim prawdopodobieństwem możemy znaleźć się w następnym stanie.
Możliwe jest powtórzenie działania automatu komórkowego na obrazie znalezionym po zastosowaniu tego samego probabilistycznego automatu komórkowego. Możesz powtarzać iteracje w kółko. Poszukiwanie niezmiennego prawa, w którym ergodyczność (zbieżność) prawa wyjściowego jest tematem, na którym obecnie prowadzone są badania.
Przypuszcza się (ale nie udowodniono), że wszystkie probabilistyczne automaty komórkowe są ergodyczne, jeśli początkowy alfabet ma wartość 2 i zostało udowodnione, że jest to fałszywe dla wszystkich bardzo dużych alfabetów. Zostało to zademonstrowane przez Gàcsa w 2001 roku dla probabilistycznych automatów komórkowych z kardynalnym alfabetem o przybliżonej wielkości .
Pytanie pozostaje otwarte i nie jest przypuszczalne w przypadku probabilistycznych automatów komórkowych z mniejszym alfabetem kardynalnym.
W badaniach matematycznych probabilistyczne automaty komórkowe są również używane do przypuszczania pewnych praw dotyczących uogólnionych perkolacji ostatniego przejścia.
Możemy rozpatrywać model automatów komórkowych jako dyskretny odpowiednik równań różniczkowych cząstkowych . Tak więc za każdym razem, gdy zjawisko fizyczne jest opisywane za pomocą równań różniczkowych cząstkowych, można je zaproponować w postaci automatu komórkowego. Pozostaje do ustalenia, w jakim stopniu model komórkowy jest odpowiedni do wyjaśniania i / lub przewidywania badanego zjawiska. W ogólnym przypadku nic nie jest gwarantowane, a scharakteryzowanie globalnej dynamiki modelu komórki zgodnie z jego lokalną definicją może być co najmniej tak trudne, jak rozwiązanie układu równań różniczkowych cząstkowych.
Z drugiej strony automat komórkowy można łatwo zasymulować komputerowo! Tak więc, analiza numeryczna wiele metod są dyskretyzacji pewne ilości (miejsca, czasu, wartości) do wykonywania symulacji numerycznych (patrz metody elementów skończonych , na skończoną objętość lub różnic skończonych ).
Wśród modeli, które zostały dogłębnie zbadane, możemy przytoczyć sieciowe automaty gazowe ( siatki gazowe), które modelują cząstki gazu rządzone przez dyskretną wersję równań Naviera Stokesa .
Pierwszy preparat tego modelu, znany pod nazwą HPP , (to jest około komórkowej automatu wymiaru ) wynika J. Hardy, Y. Pomeau O. Pazzis w 1970 roku. Drugi preparat, FHP , zaproponowano w latach 80. U. Frischa, B. Hasslachera i Y. Pomeau: ulepsza poprzednią, zastępując sieć komórkową siecią heksagonalną.
Automaty komórkowe znajdują również zastosowanie w modelowaniu i symulacji pożarów lasów . Pierwsze użycie jest spowodowane przez Kourtza i O'Regana w 1971 roku. Modele te pozwalają łatwo obserwować rozprzestrzenianie się ognia zgodnie z kilkoma parametrami, takimi jak kierunek i siła wiatru czy wilgotność .
Wzory niektórych muszelek , takich jak szyszki i cymbiolae , są generowane przez mechanizmy przypominające model automatów komórkowych. Komórki odpowiedzialne za pigmentację znajdują się na wąskim pasku wzdłuż ujścia muszli. Każda komórka wydziela pigmenty zgodnie z wydzielaniem (lub brakiem wydzielania) jej sąsiadów, a wszystkie komórki wytwarzają wzór powłoki w miarę jej wzrostu. Na przykład gatunek tkaniny Conus wykazuje wzór przypominający regułę 30 opisaną powyżej.
K. Nagel i M. Schreckenberg zaproponowali w latach 90. model ruchu autostradowego oparty na jednowymiarowym automacie komórkowym:
Model ten odpowiada automatowi komórkowemu, jeśli nie ma zakłócenia losowego ( ). Jeśli dodatkowo (pojazd jest nieruchomy lub porusza się z maksymalną prędkością), model jest redukowany do podstawowego automatu komórkowego 184: komórki mogą przyjmować tylko dwie wartości odpowiadające pustemu lub obecności pojazdu .
Kilku naukowców, takich jak Andrew Ilachinski , wysunęło hipotezę, że wszechświat można traktować jako automat komórkowy. Ilachiński uzasadnia to następującą obserwacją: „Rozważmy ewolucję reguły 110 : gdyby była to swego rodzaju„ alternatywne prawo fizyki ”, jaki byłby racjonalny opis obserwowanych wzorców? Obserwator nieświadomy reguły zastosowanej do generowania obrazów mógłby założyć ruch pojedynczych obiektów. „ Fizyk James Crutchfield wydał rygorystyczną teorię matematyczną opartą na tej zasadzie, demonstrując pojawienie się statystycznych„ cząstek ”w automatach komórkowych. W konsekwencji wszechświat , który można opisać jako zbiór cząstek, można zatem uznać za automat komórkowy.
W październiku 2014 r. Nadal nie sformułowano jednolitej teorii opartej na tym założeniu; niemniej jednak badania w tym kierunku pomogły niektórym badaczom zdefiniować wszechświat jako dyskretny system: