Uvod Ćelijski automat je model fizikalnog sistema.
U tom modelu, diskretizirane veličine su prostor i vrijeme. Interakcije su ograničene samo na lokalnost.
Ćelijski automati imaju sastav od pravilne rešetke od n-dimenzija, koju čine polja ćelija. Pri tome svaka ta ćelija može biti u jednom od konačnog broja mogućih stanja.
Stanje svake ćelije se mijenja/osvježava u diskretiziranim vremenskim intervalima (pri čemu je pravilnost tih ažuriranja lokalna). Pritom, stanje ćelije u vremenskoj tački t+1 je zavisna veličina, na koju utiče stanje susjedstva te ćelije u trenutku k.
Susjedstvo te ćelije definišemo kao tu samu ćeliju, koja je predmetom posmatranja, i određeni broj susjednih ćelija. Ovo zavisi od protežnosti ćelijskog automata i vrsti susjedstva (postoje, naprimjer, Von Neumannovo susjedstvo, Mooreovo susjedstvo...)
Pozadina class=skin-invert-image|frame|right|Gosperov Jedrilica koja stvara "jedrilice" u ćelijskom automatu Conwayeva igra životaDaniel Dennett (1995), Darwin's Dangerous Idea, Penguin Books, London, , Ćelijski automat (mn. ćelijski automati, skr. CA) jeste diskretni model računanja koji se proučava u teoriji automata. Ćelijski automati se također nazivaju ćelijski prostori, teselacijski automati, homogene strukture, ćelijske strukture, teselacijske strukture i iterativne sekvence. Ćelijski automati pronašli su primjenu u raznim oblastima, uključujući fiziku, teorijsku biologiju i modeliranje mikrostruktura. Ćelijski automat sastoji se od regularne mreže ćelija, svaka u jednom od konačnog broja stanja, kao što su uključeno i isključeno (za razliku od spojena rešetkasta mapa spojene rešetkaste mape). Mreža može biti u bilo kojem konačnom broju dimenzija. Za svaku ćeliju, skup ćelija nazvan njeno susjedstvo je definisan u odnosu na određenu ćeliju. Početno stanje (vrijeme t = 0) bira se dodjeljivanjem stanja svakoj ćeliji. Nova generacija kreira se (unaprijed t za 1), prema nekom fiksnom pravilu (općenito, matematičkoj funkciji) što određuje novo stanje svake ćelije u smislu aktuelnog stanja ćelije i stanja ćelija u njenom susjedstvu. Tipično, pravilo za ažuriranje stanja ćelija je isto za svaku ćeliju i ne mijenja se tokom vremena, te se primjenjuje na cijelu mrežu istovremeno, iako su poznati izuzeci, kao što su stohastički ćelijski automat i asinhroni ćelijski automat.
Koncept su prvobitno osmislili Stanislaw Ulam i John von Neumann 1940-ih dok su bili savremenici u Nacionalnoj laboratoriji Los Alamos. Iako su ga neki proučavali tokom 1950-ih i 1960-ih, tek 1970-ih i Conwayeva Igra života, dvodimenzionalni ćelijski automat, interes za ovu temu proširio se izvan akademske zajednice. U 1980-ima, Stephen Wolfram bavio se sistematskim proučavanjem jednodimenzijskih ćelijskih automata, ili onoga što on naziva elementarni ćelijski automati; njegov istraživački asistent Matthew Cook pokazao je da je jedno od ovih pravila Turing-potpunosti.
Primarne klasifikacije ćelijskih automata, kako ih je opisao Wolfram, numerirane su od jedan do četiri. To su, redom, automati u kojima se obrasci uglavnom stabiliziraju u homogenost, automati u kojima se obrasci razvijaju u uglavnom stabilne ili oscilirajuće strukture, automati u kojima se obrasci razvijaju naizgled haotičan način i automati u kojima obrasci postaju izuzetno složeni i mogu trajati dugo vremena, sa stabilnim lokalnim strukturama. Smatra se da je ova posljednja klasa računarski univerzalna ili sposobna simulirati Turingovu mašinu. Posebne vrste ćelijskih automata su reverzibilni, gdje samo jedna konfiguracija vodi direktno do sljedeće, i totalistički, u kojem buduća vrijednost pojedinačnih ćelija zavisi samo od ukupne vrijednosti grupe susjednih ćelija. Ćelijski automati mogu simulirati razne sisteme iz stvarnog svijeta, uključujući biološke i hemijske.
Pregled
Jedan od načina simuliranja dvodimenzijskog ćelijskog automata je pomoću beskonačnog lista milimetarskog papira zajedno sa skupom pravila kojih se ćelije trebaju pridržavati. Svaki kvadrat se naziva "ćelija" i svaka ćelija ima dva moguća stanja, crno ili bijelo. „Susjedstvo“ ćelije su obližnje, obično susjedne, ćelije. Dva najčešća tipa susjedstava su von Neumannovo susjedstvo i Mooreovo susjedstvo. Prvi, nazvan po osnivaču teoretičara ćelijskih automata, sastoji se od četiri ortogonalno susjedne ćelije. Drugi uključuje von Neumannovo susjedstvo kao i četiri dijagonalno susjedne ćelije. Za takvu ćeliju i njegovo Mooreovo susjedstvo postoji 512 (= 29) mogućih uzoraka. Za svaki od 512 mogućih uzoraka, tabela pravila bi navela da li će središnja ćelija biti crna ili bijela u sljedećem vremenskom intervalu. Conwayeva igra života je popularna verzija ovog modela. Drugi uobičajeni tip susjedstva je prošireno von Neumannovo susjedstvo, koje uključuje dvije najbliže ćelije u svakom ortogonalnom smjeru, ukupno osam. Opća jednadžba za ukupan broj mogućih automata je kks, gdje je k broj mogućih stanja za ćeliju, a s je broj susjednih ćelija (uključujući i samu ćeliju koja se izračunava) koje se koriste za određivanje sljedećeg stanja ćelije. Dakle, u dvodimenzijskom sistemu sa Murovom okolinom, ukupan mogući broj automata bio bi 229, ili .
Obično se pretpostavlja da svaka ćelija u univerzumu počinje u istom stanju, osim konačnog broja ćelija u drugim stanjima; dodjeljivanje vrijednosti stanja naziva se konfiguracija. Općenitije, ponekad se pretpostavlja da svemir počinje prekriven periodičnim uzorkom i da samo konačan broj ćelija krši taj obrazac. Potonja pretpostavka je uobičajena kod jednodimenzikjsih ćelijskih automata. thumb|right|Toroidni oblik (torus) Ćelijski automati često se simuliraju na konačnoj mreži, a ne na beskonačnoj. U dvije dimenzije, svemir bi bio pravougaonik umjesto beskonačne ravni. Očigledan problem s konačnim mrežama je kako rukovati ćelijama na rubovima. Način na koji se s njima rukuje utjecat će na vrijednosti svih ćelija u mreži. Jedna moguća metoda je dozvoliti da vrijednosti u tim ćelijama ostanu konstantne. Druga metoda je drugačije definiranje susjedstava za ove ćelije. Moglo bi se reći da imaju manje susjeda, ali bi se onda morala definirati i nova pravila za ćelije koje se nalaze na rubovima. Ove ćelije obično se obrađuju periodičnim graničnim uvjetima, što rezultira toroidnim rasporedom: kada jedna ide s vrha, jedna dolazi na odgovarajuću poziciju na dnu, a kada jedna ide s lijeve strane, jedna dolazi s desne strane. (Ovo u suštini simulira beskonačno periodično popločavanje, a u oblasti parcijalnih diferencijalnih jednačina ponekad se naziva periodičnim graničnim uslovima.) Ovo se može vizualizovati kao spajanje lijeve i desne ivice pravougaonika trakom kako bi se formirala cijev, a zatim spajanje gornje i donje ivice cijevi trakom kako bi se formirao torus (oblik krofne). Univerzumi drugih dimenzija slično se obrađuju. Ovo rješava granične probleme sa susjedstvima, ali još jedna prednost je što se lahko programira pomoću modularnih aritmetičkih funkcija. Naprimjer, u jednodimenzijskom ćelijskom automatu, kao što su primjeri u nastavku, susjedstvo ćelije xit je {xi−1t−1, xit−1, x<sub>i+1</sup>t−1}, gdje je t vremenski korak (vertikalni), a i je indeks (horizontalni) u jednoj generaciji.
Historija Stanisław Ulam, dok je radio u Nacionalnoj laboratoriji Los Alamos 1940-ih, proučavao je rast kristala, koristeći jednostavnu mrežu rešetke kao svoj model. U isto vrijeme, John von Neumann Ulamov kolega u Los Alamosu radio je na problemu samoreplicirajućih sistema. Von Neumannov početni dizajn bio je zasnovan na ideji da jedan robot gradi drugog robota. Ovaj dizajn je poznat kao kinematički model.John von Neumann, "The general and logical theory of automata," in Lloyd A. Jeffress, ed., Cerebral Mechanisms in Behavior – The Hixon Symposium, John Wiley & Sons, New York, 1951, pp. 1–31.; Sci. Am. 1955; 192:6 (errata). Dok je razvijao ovaj dizajn, von Neumann je shvatio veliku teškoću izgradnje samoreplicirajućeg robota i veliku cijenu obezbjeđivanja "mora dijelova" za robota od kojih bi izgradio svog replikanta. Neumann je napisao rad pod naslovom "Opća i logička teorija automata", 1948. Ulam je bio taj koji je predložio korištenje diskretnog sistema za stvaranje redukcionističkog modela samoreplikacije. Nils Aall Barricelli izvršio je mnoga od najranijih istraživanja ovih modela vještačkog života. thumb|John von Neumann, Los Alamos Identifikacijska značka Ulam i von Neumann su krajem 1950-ih stvorili metodu za izračunavanje kretanja tekućine. Osnovni koncept metode bio je da se tekućina posmatra kao grupa diskretnih jedinica i izračuna kretanje svake od njih na osnovu ponašanja njenih susjeda. Tako je rođen prvi sistem ćelijskih automata. Poput Ulamove rešetkaste mreže, von Neumannovi ćelijski automati su dvodimenzijski, s njegovim samoreplikatorom implementiranim algoritamski. Rezultat je bio univerzalni kopirni uređaj i konstruktor koji radi unutar ćelijskog automata s malim susjedstvom (samo one ćelije koje se dodiruju su susjedi; za von Neumannove ćelijske automate, samo ortogonalne ćelije), i sa 29 stanja po ćeliji. Von Neumann je dao dokaz postojanja da bi određeni obrazac pravio beskonačne kopije sebe unutar datog ćelijskog univerzuma dizajnirajući konfiguraciju od 200.000 ćelija koja bi to mogla učiniti. Ovaj dizajn je poznat kao model teselacije i naziva se von Neumannov univerzalni konstruktor.<ref name=TSRA>Također, 1940-ih, Norbert Wiener i Arturo Rosenblueth razvili su model podražljivih medija s nekim karakteristikama ćelijskog automata. Njihova specifična motivacija bio je matematički opis provođenja impulsa u srčanim sistemima. Međutim, njihov model nije ćelijski automat jer je medij u kojem se signali šire kontinuiran, a talasni frontovi su krivulje. Pravi model ćelijskog automata ekscitabilnih medija razvili su i proučavali J. M. Greenberg i S. P. Hastings 1978. godine; pogledajte Greenberg-Hastingsov ćelijski automat. Originalni rad Wienera i Rosenbluetha sadrži mnoge uvide i nastavlja se citirati u modernim istraživačkim publikacijama o srčanoj aritmiji i ekscitabilnim sistemima. Tokom 1960-ih, ćelijski automati su proučavani kao poseban tip dinamičkog sistema i prvi put je uspostavljena veza sa matematičkim poljem simboličke dinamike. Godine 1969, Gustav A. Hedlund je sastavio mnoge rezultate slijedeći ovo gledište u onome što se još uvijek smatra fundamentalnim radom za matematičko proučavanje ćelijskih automata. Najfundamentalniji rezultat je karakterizacija u Curtis-Hedlund-Lyndonovu teoremu skupa globalnih pravila ćelijskih automata kao skupa kontinuiranih endomorfizama pomjerajućih prostora.
U 1969., njemački informatičarski pionir Konrad Zuse objavio je svoju knjigu Izračunavanje prostora, predlažući da su fizički zakoni svemira diskretni po prirodi i da je cijeli svemir rezultat determinističkog izračuna na jednom ćelijskom automatu; "Zuseova teorija" postala je temelj područja istraživanja pod nazivom digitalna fizika. Također 1969., informatičar Alvy Ray Smith završio je doktorsku disertaciju na Stanfordu o teoriji ćelijskih automata, prvom matematičkom tretmanu CA kao opće klase računara. Mnogi radovi su proizašli iz ove disertacije: pokazao je ekvivalentnost susjedstava različitih oblika, kako svesti Mooreovo susjedstvo na von Neumannovo susjedstvo ili kako svesti bilo koje susjedstvo na von Neumannovo susjedstvo. On je dokazao da su dvodimenzijski CA univerzalni za računanje, uveo je jednodimenzijske CA i pokazao da su i oni univerzalni za računanje, čak i sa jednostavnim susjedstvima. Pokazao je kako podvesti kompleksni von Neumannov dokaz univerzalnosti konstrukcije (i stoga samoreproducirajućih mašina) u posljedicu univerzalnosti računanja u jednodimenzijskoj CA. Namijenjen kao uvod u njemačko izdanje von Neumannove knjige o CA, napisao je pregled te oblasti s desetinama referenci na radove mnogih autora iz mnogih zemalja tokom desetak godina rada, koje moderni istraživači CA često previđaju.