Ćelijski automat

Ćelijski automat (engl. cellular automaton; CA) je diskretni model koji se proučava unutar teorija informatike, matematike, fizike, složenog adaptivnog sistema, teorijske biologije i mikrostrukture modeliranja.

Za ćelijske automate se takođe koriste i nazivi ćelijski prostori (engl. cellular spaces), mozaični automati (engl. tessellation automata), homogene strukture (engl. homogeneous structures), ćelijske strukture (engl. cellular structure), mozaične strukture (engl. tessellation structures), učestali nizovi (engl. iterative arrays) itd.

Ćelijski automat se sastoji od pravilne mreže ćelija, od kojih je svaka u jednom od stanja čiji je broj ograničen (nije beskonačan) kao što su uključeno (1) i isključeno (0), za razliku od kombinovanih rešetki preslikavanja). Mreža može biti u bilo kojoj od dimenzija, s tim da broj tih dimenzija takođe nije beskonačan. Za svaku ćeliju, niz ćelija koji se naziva njenim susedstvom definisan je u odnosu na pomenutu ćeliju. Početno stanje (vreme $t=0$) određuje se biranjem stanja za svaku od ćelija. Nova generacija se stvara (što povećava vreme funkcijom $f=t+1$) prema nekom fiksnom tj. tačno određenom i nepromenljivom pravilu (uglavnom, matematička funkcija) koje određuje novo stanje svake od ćelija zavisno od trenutnog stanja ćelije i stanja ćelija u njenom susedstvu. Najčešće, pravilo za „ažuriranje” stanja ćelija isto je za svaku ćeliju i ne menja se vremenom, a primenjuje se na celu mrežu istovremeno (odjednom). Međutim, izuzeci postoje; na primer, stohastični ćelijski automat i asinhroni ćelijski automat.

Gosperova gliderska puška (engl. Gosper's Glider Gun) koja stvara glidere u ćelijskom automatu Konvejeva „Igra života”

Koncept su prvi otkrili Stanislav Martin Ulam i Džon fon Nojman 1940-ih godina, i to dok su radili zajedno u Nacionalnoj laboratoriji u Los Alamosu (Novi Meksiko, SAD). Dok su studirali tokom 1950-ih i 1960-ih, koncepta nije bilo, a sve do 1970-ih i pojave Konvejeve „Igre života”, dvodimenzionalnog ćelijskog automata. Interesovanje za ovu temu tada se proširilo i izvan akademskih krugova. Stiven Volfram je tokom 1980-ih radio na sistematskoj studiji jednodimenzionalnog ćelijskog automata, ili kako ga on naziva — elementarni ćelijski automat. Njegov asistent Metju Kuk pokazao je da je jedno od tih pravila Tjuring-potpuno (računski univerzalno). Volfram je objavio Novu vrstu nauke (engl. A New Kind of Science) 2002. godine, tvrdeći da ćelijski automati imaju primenu u mnogim oblastima nauke. Ovo uključuje računarske procesore i kriptografiju. 

Klasifikacija ćelijskih automata

Primarna klasifikacija ćelijskih automata, prema onome što je Volfram naveo, obeležena je brojevima od 1 do 4. Čine je sledeće klase (po navedenom redu):

1. automati u kojima se obrasci generalno stabilizuju u homogenost
2. automati u kojima obrasci evoluiraju u uglavnom stabilne ili oscilirajuće strukture
3. automati u kojima obrasci evoluiraju na naizgled haotičan način
4. automati u kojima obrasci postaju izuzetno složeni i mogu da traju dugo vremena, sa stabilnim lokalnim strukturama

Ova poslednja klasa smatra se da je računski univerzalna tj. sposobna za simulaciju Tjuringove mašine.

Posebne vrste ćelijskih automata su i reverzibilni automati (gde samo jedna konfiguracija vodi direktno do one sledeće, uzastopne) te totalistički automati (u kojima buduća vrednost pojedinih ćelija zavisi od ukupne vrednosti grupe susednih ćelija).

Ćelijski automati mogu da simuliraju razne sisteme iz stvarnog života, uključujući i biološke i hemijske. 

Pregled

Crvene ćelije su Murovi susedi za plavu ćeliju

Crvene ćelije su Fon Nojmanovi susedi za plavu ćeliju (prošireno susedstvo uključuje i ružičaste ćelije, takođe)

Jedan od načina da se simulira dvodimenzionalni ćelijski automat je korišćenjem beskonačnog lista graf papira, zajedno sa setom pravila za ćelije koja treba da se prate. Svaki kvadrat se zove ćelija, a svaka ćelija ima dva moguća stanja, crno i belo. Susedstvo ćelije čine one najbliže, obično okolne ćelije koje su neposredno uz onu koja se posmatra. Dva najčešća tipa susedstva su Fon Nojmanovo susedstvo i Murovo susedstvo. Murovo susedstvo je ime dobilo po teoretičaru-osnivaču ćelijskog automata, a sastoji se od četiri ortogonalno susedne ćelije. Poslednja obuhvata Fon Nojmanovo susedstvo, kao i četiri preostale ćelije koje okružuju ćeliju čije stanje treba da se izračuna. Za takvu ćeliji i njeno Murovo susedstvo, postoji 2⁹ = 512 mogućih obrazaca. Za svaki od 512 mogućih obrazaca, tabela sa pravilima određivala bi da li će centralna ćelija biti crna ili bela na sledećem vremenskom intervalu. Konvejeva „Igra života” je popularna verzija ovog modela. Drugi uobičajen tip susedstva je prošireno Fon Nojmanovo susedstvo, koje uključuje dve najbliže ćelije u svakom od ortogonalnih smerova, što daje ukupno 8 ćelija. Opšta jednačina za takav sistem pravila je $k^{k^{s}}$, gde je $k$ broj mogućih stanja za ćeliju, a $s$ broj susednih ćelija (uključujući i ćeliju koja se posmatra) koji se koristi za određivanje sledećeg stanja posmatrane ćelije. Prema tome, u dvodimenzionalnom sistemu sa Murovim susedstvom, ukupan mogući broj automata bio bi 2²⁹ ≈ 1,34 × 10¹⁵⁴.

Obično se pretpostavlja da svaka ćelija u svemiru na početku ima isto stanje, osim za tačno određen broj ćelija u drugim stanjima; pridruživanje vrednosti stanja zove se konfiguracija. Uopšteno govoreći, ponekad se pretpostavlja da svemir započinje prekriven periodičnim obrascem, dok taj obrazac narušava samo tačno određen broj ćelija. Ova druga hipoteza uobičajena je u jednodimenzionalnim ćelijskim automatima.  

Torus, toroidalni oblik

Ćelijski automati se češće simuliraju na ograničenoj mreži nego na mreži koja je beskonačna. U dve dimenzije, svemir bi bio pravougaonik, a ne (beskonačna) ravan. Očigledan problem sa ograničenom mrežom je kako da se interpretiraju krajnje ćelije. To kako se interpretiraju ove ćelije uticaće na vrednosti svih ćelija u mreži. Jedno moguće rešenje je da se omogući da vrednost u tim ćelijama bude konstantna. Drugi metod je različito definisanje susedstava za ove ćelije. Moglo bi se reći da imaju manje suseda, ali onda bi se takođe morala definisati nova pravila za ćelije koje se nalaze na krajevima. Ove ćelije se obično interpretiraju toroidalnim principom: kada jedna ćelija s vrha nestane, druga — kao zamena — dolazi na odgovarajuću poziciju na dnu; kada nestane ćelija s leve strane, druga dolazi na desnu stranu. (Ovime se u suštini simulira beskrajno periodično „popločavanje”, a u oblasti parcijalnih diferencijalnih jednačina ponekad se naziva i periodičnim graničnim uslovima.) Ovo može da se vizualizira zamišljanjem priljubljivanja leve i desne ivice pravougaonika čime bi se formirala cev, čije bi se ivice (dva kruga na krajevima) potom spojile formirajući torus (oblik američke krofne). Sa svemirima drugih dimenzija postupa se na sličan način. Ovime se rešavaju granični problemi sa susedstvima, a još jedna prednost je u tome što se ovo da lako programirati pomoću funkcija modularne aritmetike. Na primer, kod jednodimenzionalnog ćelijskog automata prikazanog ispod, susedstvo ćelije $x_{i}^{t}$ je: $\{x_{i-1}^{t-1},x_{i}^{t-1},x_{i+1}^{t-1}\}$, gde je $t$ vremenski korak (vertikalno), a $i$ indeks (horizontalno) u jednoj generaciji.

Istorija

Džon fon Nojman, Los Alamos oznaka ID

Stanislav Ulam, dok je radio u Nacionalnoj laboratoriji Los Alamos 1940, studirao je rast kristala, koristeći jednostavnu mrežu rešetke kao njegov model.Istovremeno, Džon fon Nojman, Ulamov kolega u Los Alamosu, radi na problemu samo-repliciranih sistema. Početni dizajn, fon Nojman je osnovao na ideji jednog robota gradeći još jedan robot. Ovaj dizajn je poznat kao kinematički model. Kako je razvio ovaj dizajn, fon Nojman je došao da ostvari veliku teškoću izgradnje samo-repliciranog robota, i na velikoj ceni u pružanju robota sa „morem delova” iz kojih izgrađuje svoj replikant. Nojman čita novine pod nazivom „Generalna i logična teorija automata” na Hikson simpozijumu 1948. godine. Ulam je bio taj koji predlaže korišćenje diskretnog sistema za stvaranje redukovanog modela ponavljanja samog sebe. Nils Al Bariceli obavlja mnoge od najranijih istraživanja ovih modela veštačkog života. 

Ulam i fon Nojman su stvorili metod za izračunavanje tečnog kretanja krajem 1950-ih. Pokretački Koncept metode je bio da se razmotri tečnost kao grupa diskretnih jedinica i da se izračuna kretanje svakog od njih na osnovu ponašanja svojih suseda. Tako je rođen prvi sistem ćelijskog automata. Kao Ulamove rešetke mreže, fon Nojmanovi ćelijski automati su dvodimenzionalni, sa svojim samo-replikatorima sprovedenim algoritmički. Rezultat je bio univerzalni kopir i konstruktor koji radi u ćelijskom automatu sa malim okruženjem (samo one ćelije koje se dodiruju su susedi; za fon Nojmanov ćelijski automat, samo ortogonalne ćelije), i sa 29 stanja po ćeliji. Fon Nojman je dao dokaz postojanja, da će poseban obrazac učiniti beskrajne kopije sebe u okviru datog ćelijskog univerzuma projektovanjem konfiguracije 200.000 ćelija koje bi mogao da uradi. Ovaj projekat je poznat kao teselacioni model, i naziva se fon Nojmanov univerzalni konstruktor.

Takođe, 1940. Norbert Viner i Arturo Rosenblueth su razvili model ekscitabilnog medija sa nekim od karakteristika ćelijskog automata. Njihova specifična motivacija je matematički opis impulsa provodljivosti u srcima sistema. Međutim njihov model nije ćelijski automat, jer medij u kojem se signali prostiru je kontinuiran, a mahanje frontova su krive. Pravi ćelijski automat model ekscitabilne medije je razvijen i studiran od strane J. M. Grenberg i S. P. Hastings 1978. godine; vidi Grinberg-Hastingsov ćelijski automat. Originalni rad Viener i Rosenblueth sadrži mnoge uvide i nastavlja da bude citiran u savremenim istraživačkim publikacijama o srčanoj aritmiji i eksitablnim sistemima.

Godine 1960, ćelijski automati su proučavani kao određena vrsta dinamičkog sistema i povezivani sa matematičkim poljem simboličke dinamike po prvi put. 1969. Gustav O’Hedlund, sabrao je mnoge rezultate prateći ove tačke gledišta u ono što se i dalje smatra osnovnim papirom za matematičku studiju ćelijskog automata. Najosnovniji rezultat je karakterizacija u Kertis - Hedlund - Lindon teoremi niza globalnih pravila ćelijskog automata kao skup neprekidnih funkcija endomorfskih smena prostora. 

Godine 1969. nemački kompjuterski pionir Konrad Cuze je objavio svoju knjigu Proračunati prostor, predlažući da su fizički zakoni univerzuma diskretni po prirodi, i da je ceo univerzum izlaz determinističkim računanjima na jednom ćelijskom automatu; „Cize teorija” je postala temelj oblasti studija pod nazivom digitalna fizika.

Godine 1970, sa dva stanja, dvodimenzionalni ćelijski automat pod nazivom Igra Života postao je poznat, posebno početkom računarske zajednice. Izmislio ih je Džon Konvej i popularizovao Martin Gardner u Naučnom Američkom članku, njena pravila su sledeća: Ako ćelija ima dva crna suseda, ona ostaju ista. Ako ima tri crna suseda, postaje crna. U svim drugim situacijama postaje bela. Uprkos svojoj jednostavnosti, sistem postiže impresivnu raznovrsnost ponašanja, promenljivih između prividnih slučajnosti. Jedan od očiglednih karakteristika igre života je česta pojava jedrilica, aranžmana ćelija koje u suštini se kreću preko mreže. Moguće je dogovoriti automat tako da jedrilica interakciju obavlja proračunato, a posle mnogo truda je pokazano da Igra Života može imitirati univerzalnu Tjuringovu mašinu. To se posmatra kao uglavnom rekreativna tema, i malo praćenih radova van istražuju specifičnosti igre života i nekoliko povezanih pravila početkom 1970-ih.

Stiven Volfram  je samostalno počeo da radi na ćelijskom automatu sredinom 1981. godine, nakon razmatranja koliko je složen obrazac izgledao formiran u prirodi u suprotnosti sa drugim zakonom termodinamike. Njegove istrage su u početku podstaknute od strane interesa za modeliranje sistema, kao što su neuronske mreže. On je objavio svoj prvi rad u Pregledu moderne fizike istražujući osnovne ćelijske automate (pravilo 30 posebno) u junu 1983.  Neočekivana složenost ponašanja ovih jednostavnih pravila dovela je Volframa na sumnju da kompleksnost u prirodi može biti zbog sličnih mehanizama. Njegove istrage, međutim, dovele su ga do toga da shvati da su ćelijski automati bili siromašni u modeliranju neuronske mreže. Pored toga, tokom ovog perioda Volfram je formulisao koncepte svojstvene slučajnosti i računarskoj nesvodivosti, i predložio da pravilo 110 može biti univerzalno-činjenica dokazana kasnije uz pomoć istraživačkog saradnika Volframa, Mateja Huka 1990.

Godine 2002. Volfram je objavio tekst sa 1.280 stranica nove vrste nauke, koji intenzivno tvrdi da otkriće o ćelijskom automatu nije izolovana činjenica, ali je snažna i ima značaj za sve discipline nauke. Uprkos konfuziji u štampi, ova knjiga se ne zalaže za fundamentalnu teoriju fizike na osnovu ćelijskog automata, i iako je opisala nekoliko konkretnih fizičkih modela na osnovu ćelijskih automata, takođe dokazuje modele bazirane na kvalitativno različitim apstraktnim sistemima.

Klasifikacija

Volfram, u novoj vrsti nauke i nekoliko radova koji datiraju iz sredine 1980-ih, definiše četiri klase u kojima se ćelijski automati i nekoliko drugih jednostavnih kompjuterskih modela mogu grupisati u zavisnosti od njihovog ponašanja. Dok ranije studije o ćelijskom automatu tendenciraju da pokušaju da identifikuju tip obrazaca za određena pravila, Volframova klasifikacija je bila prvi pokušaj da se klasifikuju sama pravila, da bi složenost bila razređena: 

• Klasa 1: Skoro svi početni obrasci razvijaju brzo, stabilno i homogeno stanje. Svaka slučajnost u početnom obrascu nestaje.
• Klasa 2: Skoro svi početni obrasci razvijaju brze stabilne ili oscilovane konstrukcije. Neki od slučajnosti u početnom obrascu se mogu filtrirati. Lokalne promene u početnom obrascu teže da ostanu lokalne.
• Klasa 3: Skoro svi početni obrasci se razvijaju pseudo-slučajno ili na haotičan način. Sve stabilne strukture koje se pojavljuju se brzo uništavaju od strane okolne buke. Lokalne promene u početnom obrascu imaju tendenciju da se šire na neodređeno vreme.
• Klasa 4: Skoro svi početni obrasci se razvijaju u strukture koje reaguju na složene i interesantne načine, uz formiranje lokalnih struktura koje su u stanju da prežive duže vreme. Klasa tip 2 stabilne ili oscilovane strukture može biti eventualni ishod, ali broj koraka potrebnih da se postigne ovo stanje može biti veoma veliki, čak i kada je početni model relativno jednostavan. Lokalne promene u početnom obrascu mogu se širiti unedogled. Volfram je pretpostavio da su mnoge, ako ne i sve 4 klase ćelijskih automata u stanju da se univerzalno računaju. Ovo je dokazano za pravilo 110 i Konvejevu Igru života. 

Ove definicije su kvalitativne u prirodi i postoje neki prostori za tumačenje. Prema Volframu, „... sa skoro svim generalnim plasmanima šeme postoje neminovni slučajevi koji se pripisuju jednoj klasi jedne definicije i drugoj klasi od strane druge definicije”. Tako je i sa ćelijskim automatom: „Postoje povremena pravila... (...) ... koja pokazuju neke karakteristike jedne klase i neke druge”. "Klasifikacija Volfram-a je empirijski uparena na grupisanje u komprimovanoj dužini izlaza ćelijskog automata.

Bilo je nekoliko pokušaja da se klasifikuje ćelijski automat u formalno rigorozne klase, inspirisane klasifikacijom Volframa. Na primer, Culik i Ju, su predložili tri dobro definisane klase (i četvrtu za automate koji ne odgovaraju bilo kojem od ovih), što se ponekad zove Culik-JU nastava; Članstvo u ovome se pokazalo kao neodlučiv zadatak. Klasa Volfram 2 može biti podeljena u dve podgrupe stabilnih (fiksnih tačaka) i oscilovanih (periodičnih) pravila.

Reverzibilno

Glavni članak: Reversible cellular automaton

Ćelijski automat je sa dva lica ako za svaku trenutnu konfiguraciju za ćelijski automat, postoji tačno jedna protekla konfiguracija. Ako neko misli na ćelijski automat kao mapiranje funkcija konfiguracije do konfiguracije, ponavljanje znači da je ova funkcija bijekcija. Ako je ćelijski automat reverzibilan, njegovo vreme preokreta ponašanja može se opisati kao ćelijski automat; Ova činjenica je posledica Kertis- Hedlund-Lindonove teoreme, a topološka karakterizacija ćelijskog automata. Za ćelijske automate u kojima svaka konfiguracija nema sliku, konfiguracije bez slike nazivaju se Obrascem rajskog vrta.

Za jednodimenzionalni ćelijski automat poznati su algoritmi za odlučivanje da li je pravilo reverzibilno ili nepovratno. Međutim, za ćelijski automat sa dve ili više dimenzija reverzibilnost je neodlučiva; ne postoji algoritam koji uzima kao ulaz pravilo automata i garantuje precizno da odredi da li je automat reverzibilan. Dokaz Jarkova Karija je u vezi sa problemom pločice Vang pločica.

Reverzibilan ćelijski automat se često koristi da simulira takve fizičke fenomene kao što su gas i dinamika fluida, jer poštuju zakone termodinamike. Kako ćelijski automat sadrži pravila specijalno konstruisana da budu reverzibilna. Takve sisteme su proučavali Tomaso Tofoli, Norman Margolus i drugi. Nekoliko tehnika se mogu koristiti za eksplicitno konstruisanje reverzibilnog ćelijskog automata sa poznatim inverzijama. Dva česta su drugi red ćelijskog automata i blok ćelijskog automata, od kojih oba uključuju modifikovanu definiciju ćelijskog automata na neki način. Iako takvi automati ne striktno zadovoljavaju definiciju datu gore, može se pokazati da mogu biti emulirano konvencionalni ćelijski automati sa dovoljno velikim susedima i brojevima stanja, i da se stoga mogu smatrati podskupom konvencionalnih ćelijskih automata. S druge strane, ona je pokazala da svaki reverzibilni ćelijski automat oponaša blok ćelijskog automata.

Totalitarno

Posebna klasa ćelijskih automata su totalitarni ćelijski automati. Stanje svake ćelije u totalitarnom ćelijskom automatu je predstavljeno brojem (obično celobrojna vrednost proistekla iz konačnog skupa), a vrednost ćelije u vremenu t zavisi samo od zbira vrednosti ćelija u njenom susedstvu (eventualno i sama ćelija) u vremenu t-1. Ako stanje ćelije u vremenu t zavisi i od sopstvenog stanja i o ukupnih svojih suseda u vremenu t-1 potom ćelijski automat se pravilno zove spoljašnji totalitarni. Konvejeva Igra života je primer spoljnog totalitarnog ćelijskog automata sa vrednostima ćelija 0 i 1; Spoljni totalitarni ćelijski automati sa istom strukturom Morevog susedstva kao život se ponekad nazivaju život nalik Ćelijskom Automatu.

Automati koji dovode u vezu

Postoji mnogo mogućih generalizacija koncepta Ćelijskog Automata. 

Ćelijski automat na osnovu heksagonalnih ćelija umesto kvadrata (pravilo 34/2)

Jedan od načina je korišćenjem nečeg drugog osim pravougaonog oblika (kubnih, itd ) rešetka. Na primer, ako je ravan popločana sa redovnim heksagonima, ti heksagoni mogu se koristiti kao ćelije. U mnogim slučajevima nastali ćelijski automat je ekvivalentan onom sa pravougaone mreže sa posebno dizajniranim naseljima i pravilima. Još jedna varijacija bi bila da se napravi sama mreža neregularno, kao što je sa Penrouz pločicama.

Takođe, pravila mogu biti verovatnija više nego deterministička. Zato se ćelijski automati nazivaju verovatnoće ćelijskog automata. Probabilističko pravilo daje, za svaki uzorak u vremenu t, verovatnoću da će centralna ćelija tranzistirati na svako moguće stanje u vremenu t+1. Ponekad jednostavnije pravilo se koristi; Na primer: „Pravilo je Igra života, ali na svaki vremenski interval postoji 0,001% verovatnoća da će svaka ćelija preći na suprotnu boju.”

Susedi ili pravila mogu se menjati tokom vremena ili prostora. Na primer, u početku novo stanje ćelije može biti određeno horizontalnim susednim ćelijama, ali za naredne generacije će se koristiti vertikalne ćelije.

U celularnom automatu, na nova stanja ćelije ne utiču nova stanja druge ćelije. To se može promeniti tako da, na primer, 2 po 2 bloka ćelija mogu biti određeni samim sobom i ćelijama susednih sebi. 

Postoje kontinuirani automati. Ovo je kao totalistički ćelijski automat, ali umesto pravila i stanja su diskretna (npr tabela, koristeći stanja {0,1,2 } ), kontinuirane funkcije se koriste, a stanja postaju kontinuirana (obično u vrednosti 0,1). Stanje lokacije je konačan broj realnih brojeva. Određeni ćelijski automat može da dovede do širenja u tečnom obrascu na ovaj način. 

Kontinuirani prostorni automati imaju kontinuiranu lokaciju. Stanje lokacije je konačan broj realnih brojeva. Vreme je takođe kontinuirano, a stanje se razvija u skladu sa diferencijalnim jednačinama. Jedan važan primer je reakcija-difuzija teksture, diferencijalna jednačina koju je predložio Alan Tjuring da objasni kako hemijske reakcije mogu da stvore pruge na zebri i tačke na leopardu. Kada se oni aproksimiraju od strane ćelijskog automata, oni često daju slične modele. MekLenan smatra kontinuirano prostorni automat kao model obračuna. 

Postoje poznati primeri kontinuiranog prostornog automata, koji pokazuju propagiranje fenomena analogno jedrilici u Igri života.

Elementarni ćelijski automat

Glavni članak: Elementary cellular automaton

Najjednostavniji netrivijalni ćelijski automat će biti jednodimenzionalni, sa dva moguća stanja po ćeliji, i susedne ćelije su definisane kao susedne ćelije sa obe strane zida. Ćelija i njena dva suseda formiraju naselje od 3 ćelije, tako da postoje 2³ = 8 mogućih obrazaca za susede. Pravilo se sastoji od odlučivanja, za svaki uzorak, da li će ćelija biti 1 ili 0 u sledećoj generaciji. Onda Postoje 2⁸ = 256 mogućih pravila. Ovih 256 ćelijskih Automata se uglavnom odnose na njihov Volframov kod, standardno nazvana konvencija koju je izumeo Volfram koja daje svakom pravilu broj od 0 do 255. Pravilo 30 i pravilo 110 ćelijskih automata su posebno interesantni. Na slici ispod je pokazana istorija svakog kada započinje konfiguraciju koja se sastoji od 1 (na vrhu svake slike) okružen sa 0. Svaki red piksela predstavlja generaciju u istoriji automata, sa t=0 vrhom reda. Svaki piksel je bele boje za 0 i crne za 1. 

Pravilo 30

Pravilo 30 ćelijski automat

trenutni obrazac	111	110	101	100	011	010	001	000
novo stanje za centralnu ćeliju	0	0	0	1	1	1	1	0

Pravilo 110

Pravilo 110 ćelijski automat

trenutni obrazac	111	110	101	100	011	010	001	000
novo stanje za centralnu ćeliju	0	1	1	0	1	1	1	0

Pravilo 30 pokazuje klasu 3 ponašanja, što znači čak i jednostavni ulazni modeli, kao što je to prikazano dovode do haotične, naizgled slučajne istorije. 

Pravilo 110, kao Igra života, prikazuje šta Volfram naziva klasa 4 ponašanja, koja nije ni potpuno slučajna, niti se u potpunosti ponavlja. Lokalizovane strukture se pojavljuju i interaguju u različitim komplikovanim načinima. U toku razvoja nove vrste nauke, kao asistent Volframu 1994. godine, Metju Kuk pokazuje da su neke od ovih struktura dovoljno bogate da podrže univerzalnost. Ovaj rezultat je zanimljiv jer pravilo 110 je veoma jednostavan 1-dimenzionalni sistem, i težak za inženjera za obavljanje specifičnog ponašanja. Ovaj rezultat pruža značajnu podršku za Volframovo mišljenje da je klasa 4 sistema inherentna kao i da je univerzalna. Kuk je predstavio svoj dokaz na konferenciji Santa Fe Instituta za Celularni automat 1998. godine, ali je Volfram blokirao da dokaz bude uključen u zbornik konferencije, zato što Volfram nije želeo dokaz najavljen pre objavljivanja Nove vrste nauke. 2004. godini, Kukov dokaz je konačno objavljen u Volframovom časopisu složenih sistema (vol. 15, br 1 ), preko deset godina nakon toga Kuk je došao sa njom. Pravilo 110 je bilo osnova za neke od najmanjih univerzalnih tjuringovih mašina.

Pravilo prostora

Pravilo elementarnog ćelijskog automata je određeno sa 8 bita, a sva osnovna pravila ćelijskog automata mogu se smatrati da sede na temenima 8-dimenzionalnih jedinica hiperkuba. Ova jedinica Hiperkuba je pravilo prostora ćelijskog automata. Za sledeći najbliži sused ćelijskog automata, pravilo je određeno sa 2⁵ = 32 bita. Udaljenost između dva pravila može se definisati po broju koraka potrebnih za prelazak sa jednog temena, što predstavlja prvo pravilo, na drugo teme, predstavljajući još jedno pravilo, duž ivice hiperkuba. Ovo pravilo-ka-pravilu udaljenosti se naziva i Hamingova udaljenost. 

Pravilo prostora ćelijskog automata dozvoljava nam da postavimo pitanje o tome da li pravila sa sličnim dinamičkim ponašanjima su „blizu” svakog od njih. Grafičko crtanje visoko dimenzionalnih hiperkubova na 2-dimenzionalnom području ostaje težak zadatak, a jedan sirov lokator pravila u hiperkubu je broj bita-1 u 8-bitnom stringu za elementarna pravila (ili 32-bitni za sledeći najbliži sused pravila). Crtanje pravila u različitim klasama Volframa u ovim kriškama prostora pravila pokazuju da klasa 1 pravila teže da imaju manji broj bit-1, čime se nalaze u jednoj regiji prostora, dok klasa 3 pravila imaju tendenciju da imaju veći procenat (50%) od bita-1.

Za veće pravilo prostora ćelijskog automata, ona je pokazala da je klasa 4 pravila se nalazi između klasa 1 i klasa 3 pravila. Ovo zapažanje je osnova za frazu ivice haosa, i podseća na faze tranzicije u termodinamici. 

Biologija

Konus tekstil pokazuje ćelijski automat obrazac na svojoj ljusci.

Za više informacija pogledajte: Patterns in nature

Neki biološki procesi se odvijaju ili mogu biti simulirani uz pomoć ćelijkog automata.

Obrasci nekih školjki, poput onih u Konusu i rodu Simbolija, nastaju prirodnim ćelijskim automatom. Pigmentne ćelije borave u uskom delu duž usne. Svaka ćelija luči pigmente u skladu sa aktiviranjem i inhibiranjem aktivnosti svojih suseda pigmentnih ćelija, poštovanjem prirodne verzije matematičkih pravila. Ćelija ostavlja obojen obrazac na ljusci dok ona polako raste. Na primer, raširena vrsta Konus tekstila nosi obrazac koji podseća na Volframovo Pravilo 30 ćelijskog automata.

Biljke regulišu njihov unos i gubitak gasova putem mehanizma ćelijskog automata. Svaka stoma na listu deluje kao ćelija.

Šare talasa pomeranja na koži glavonožaca mogu se simulirati sa dva stanja, dvodimenzionalni ćelijski automat, svakom stanju odgovara ili proširen ili povučen Hromatofor.

Granični automati su  bili izmišljeni da simuliraju neurone, i složena ponašanja kao što je prepoznavanje i učenje koje može biti simulirano.

Fibroblasti rađaju sličnosti sa ćelijskim automatom, kako svaki fibroblast samo reaguju sa svojim susedima.

Hemijski tipovi

Belousov - Zabotinska reakcija je prostorno-vremenski hemijski oscilator koji se može simulirati pomoću ćelijskog automata. Tokom 1950-ih A. M. Zabotinski (produžuje rad B. P. Belousova) otkriva da kada tanak, homogen sloj mešavine malonske kiseline, zakiseljene bromatno, i cerijusove soli je pomešan zajedno i ostavljen netaknut, fascinantne geometrijske šare, kao što su koncentrični krugovi i spirale propagiraju po sredini. U „Kompjuterskoj rekreaciji”, sekciji Augustovog problema iz 1988. Naučne amerike, A. K. Devdnej diskutuje o ćelijskom automatu, napravljenom od strane Martina Gerhardata i Hajke Šustera, Univerziteta u Bilefeldu (Zapadna Nemačka). Ovaj automat stvara talas obrasca koji liče onima u Belousov-Zabotinskoj reakciji. 

Aplikacije

Kompjuterski procesor

Procesori ćelijskih automata su fizičke implementacije koncepata CA, koji mogu da obrade informacije računski. Obrađeni elementi su raspoređeni u redovnoj mreži identičnih ćelija. Mreža je obično kvadrat pločica, ili teselacija, dve ili tri dimenzije; druge stvari su moguće, ali još uvek se ne koriste. Ćelije stanja određuju samo interakcijom sa susednim ćelijama. Ne postoji način da direktno komuniciraju sa ćelijama dalje. Jedan takav procesor ćelijskog automata niza konfiguracija je sistolni niz. Mobilna interakcija može biti preko električnog naboja, magnetizma, vibracija (fonon i u kvantnim skalama), ili bilo kojeg drugog fizički korisnog sredstva. Ovo se može uraditi na više načina tako da nisu potrebne žice između bilo kojih elemenata. Ovo je veoma različito od procesora koji se koriste u većini računara danas, fon Njumanov dizajn, koji je podeljen u sekcije sa elementima koji mogu da komuniciraju sa udaljenim elementima preko žice. 

Kriptografija

Pravilo 30 je prvobitno predloženo kao moguća Blok šifra za upotrebu u kriptografiji. Dvodimenzionalni ćelijski automat se koristio za slučajne brojeve generacije.

Ćelijski automati su bili predlagani za kriptografiju javnog ključa. Jednosmerna funkcija je evolucija konačnog CA, za koji se smatra da je teško naći. S obzirom na pravilo, svako može lako izračunati buduća stanja, ali čini se da je veoma teško izračunati prethodna stanja. 

Kodiranje korekcije greške

CA je primenio dizajn ispravljanja greške kodova u novinama „Dizajn ĆAZNIGK — Ćelijski automat zasnovan na ispravljanju greške koda”, D. Roj Čoudari, S. Basu, I. Sen Gupta, P. Pal Čaudari. U radu definiše novu šemu izgradnje SEC-DED kodova koristeći CA, a takođe izveštava brz hardverski dekoder za kod.

Modeling fizičke realnosti

Glavni članci: Digital physics i digital philosophy

Kao što Endru Ilačinski ističe u svom ćelijskom automatu, mnogi naučnici su postavili pitanje da li je univerzum ćelijski automat. Ilačinski tvrdi da značaj ovog pitanja može biti bolje vrednovan sa jednostavnim posmatranjem, koja se može početi kao sledeće. Razmislite evoluciju pravila 110: ako je to neka vrsta „strane fizike”, šta bi bio razuman opis posmatranih obrazaca? Ako posmatrač nije znao kako su generisane slike, koje posmatrač može završiti pretpostavljanjem o kretanju nekih čestica nalik objektima. Zaista, fizičar Džejms Kračfild je izgradio rigoroznu matematičku teoriju od te ideje, što dokazuje statističkom pojavom " čestica " iz ćelijskog automata. Zatim, kao argument ide, moglo bi se zapitati da li naš svet, koji je trenutno dobro opisan fizikom elementarnih čestica, može biti ЋA kao u svom najosnovnijem nivou. 

Iako nije razvijena kompletna teorija duž ove linije, razvijanje ove hipoteze dovelo je naučnike do zanimljivih špekulacija i plodnih intuicija o tome kako možemo smisliti naš svet u diskretnim okvirima. Marvin Minski, pionir AI, istraživao je kako da razume interakcije čestica sa četvorodimenzionalnim ЋA rešetkama; Konrad Cuse — pronalazač prvog radnog računara, Z3—razvijen nepravilnim organizovanjem rešetke se pozabavio pitanjem sadržaja informacija čestica. U skorije vreme, Edvard Fredkin izložio je ono što je on izrazio na „konačnoj prirodi hipoteze”, odnosno, ideja da „na kraju svakog kvanta fizike, uključujući i prostora i vremena će se ispostaviti da bude diskretan i konačan”. Fredkin i Volfram su jaki zagovornici CA-baziranog na fizici.

U poslednjih nekoliko godina, ostali predlozi u pogledu ovih linija su se pojavili iz literature u nestandardnom računanju. Volframova Nova vrsta nauke smatra CA ključnim za razumevanje različitih subjekata, uključujući i fiziku. Matematika modela referenci, stvorena od strane iLABA osnivača Gabrijela Rosija i razvijena uz pomoć Franceska Berta i Jakopo Tagliuba, poseduje originalan2D/3D univerzum na osnovu novog „rombičnog dodeksadrona zasnovan na” rešetki i jedinstvenom pravilu. Ovaj model zadovoljava univerzalnost (ekvivalentan je Tjuringovoj mašini) i savršenu reverzibilnost (želja ako neko želi da lako očuva različite količine i nikada ne izgubi sve informacije ), i to dolazi ugrađeno u teoriji prvog reda, dozvoljavajući mogućnost računanja, kvalitetnih izjava univerzalne evolucije.

Specifična pravila

Specifični tipovi ćelijskog automata uključuju:

• Brajanov mozak
• Langtonov mrav
• Provodni svet
• Pravilo 90
• Pravilo 184
• Fon Nojmanov ćelijski automat
• Nobilov ćelijski automat
• Kodov ćelijski automat
• Langtonove petlje
• KoDi

Rešeni problemi

Problemi koji mogu biti rešeni sa ćelisjkim automatom uključuju:

• Problem firingove sinhronizacije tima
• Većinski problem

Vidi još

• Teorija automata
• Dvosmerni saobraćaj
• Ćelijski automat u popularnoj kulturi
• Ciklični ćelijski automat
• Nadraživa sredina
• Mirekovo slavlje
• Pokretni ćelijski automat
• Kvantni ćelijski automat
• Sistem podrške prostorne odluke
• Turmiti

Literatura

• Dennett, Daniel (1995). Darwin's Dangerous Idea. London: Penguin Books. ISBN 978-0-14-016734-4. 
• Adamatzky, Andrew, ur. (2010). Game of Life Cellular Automata. Springer. ISBN 978-1-84996-216-2. 
• Bialynicki-Birula, Iwo; Bialynicka-Birula, Iwona (2004). Modeling Reality: How Computers Mirror Life. Oxford University Press. ISBN 978-0-19-853100-5. 
• Chopard, Bastien; Droz, Michel (2005). Cellular Automata Modeling of Physical Systems. Cambridge University Press. ISBN 978-0-521-46168-9. 
• Gutowitz, Howard, ur. (1991). Cellular Automata: Theory and Experiment. MIT Press. ISBN 9780262570862. 
• Ilachinski, Andrew (2001). Cellular Automata: A Discrete Universe. World Scientific. ISBN 9789812381835. 
• Kier, Lemont B.; Seybold, Paul G.; Cheng, Chao-Kun (2005). Modeling Chemical Systems using Cellular Automata. Springer. ISBN 9781402036576. 
• Schiff, Joel L. (2011). Cellular Automata: A Discrete View of the World. Wiley & Sons, Inc. ISBN 9781118030639. 
• Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media. ISBN 978-1579550080. 
• Cellular automaton FAQ from the newsgroup comp.theory.cell-automata
• "Neighbourhood Survey" (includes discussion on triangular grids, and larger neighborhood CAs)
• von Neumann, John, 1966, The Theory of Self-reproducing Automata, A. Burks, ed., University of Illinois Press, Urbana, IL.
• Cosma Shalizi's Cellular Automata Notebook contains an extensive list of academic and professional reference material.
• Wolfram's papers on CAs Arhivirano na sajtu Wayback Machine (27. septembar 2013)
• A.M. Turing. 1952. The Chemical Basis of Morphogenesis. Phil. Trans. Royal Society, vol. B237. str. 37–72. (proposes reaction-diffusion, a type of continuous automaton).
• Evolving Cellular Automata with Genetic Algorithms: A Review of Recent Work, Melanie Mitchell, James P. Crutchfeld, Rajarshi Das (In Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA'96). Moscow, Russia: Russian Academy of Sciences, 1996)
• The Evolutionary Design of Collective Computation in Cellular Automata, James P. Crutchfeld, Melanie Mitchell, Rajarshi Das (In J. P. Crutch¯eld and P. K. Schuster (editors), Evolutionary Dynamics|Exploring the Interplay of Selection, Neutrality, Accident, and Function. New York: Oxford University Press, 2002)
• The Evolution of Emergent Computation, James P. Crutchfield and Melanie Mitchell (SFI Technical Report 94-03-012)
• Ganguly, Sikdar, Deutsch and Chaudhuri "A Survey on Cellular Automata"

Spoljašnje veze

• (jezik: engleski) Ćelijski automati — unosi od strane Frančeska Bertoa i Jakopa Tagliabua u delu Stanford Encyclopedia of Philosophy
• (jezik: engleski) Mirekovo slavlje — osnova za besplatne pretraživačke softvere i biblioteke pravila za MCell i MJCell ćelijske automate; softver podržava veliki broj 1D i 2D pravila, a veb-sajt omogućava i detaljni leksikon pravila i mnoge galerije slika koje se učitavaju sa primerima za pravila; MCell je aplikacija za Vindous, dok je MJCell Java aplet; izvorni kod je dostupan
• (jezik: engleski) Moderni ćelijski automat — lak za korišćenje i interaktivan, sa živim bojama 2D ćelijskih automata; pokreće ga Java aplet, a uključuje i tradicionalna, reverzibilna, heksagonalna, višekoračna, frakcijska i druga pravila za generisanje obrazaca; hiljade pravila je već pripremljeno za upotrebu, a besplatan softver je trenutno dostupan
• (jezik: engleski) Petlje samoreplikacije u ćelijskom svemiru — Javin aplet koji omogućava pravljenje petlji samoreplikacije
• (jezik: engleski) Kolekcija preko 10 različitih apleta za ćelijski automat — u virtuelnom labu Monaš univerziteta
• (jezik: engleski) Golly — podržava Nojmanov princip, Nobili, GOL i mnoge druge sisteme ćelijskih automata (razvijen od strane Tomasa Rokickog i Endrua Trevoroua; ovo je jedini simulator koji je trenutno dostupan i može da demonstrira Fon Nojmanov tip samoreplikacije)
• (jezik: engleski) Wolfram Atlas — Atlas raznih vrsta jednodimenzionalnih ćelijskih automata
• (jezik: engleski) „Konvejev život” — Konvejeva „Igra života”
• (jezik: engleski) „Prvo replicirajuće stvorenje nastalo u simulatoru života”
• (jezik: engleski) Matematika modela referenci — opšti vodič za CA, interaktivni apleti, besplatan kod i izvori za CA kao model fundamentalne fizike
• (jezik: engleski) Fourmilab laboratorija za ćelijske automate
• (jezik: engleski) Busy Boxes — 3D reverz. („SALT” arhitektura za CA)
• (jezik: engleski) Repozitorijum ćelijskih automata — CA istraživači, istorijske veze, besplatan softver, knjige i još mnogo toga