Celični avtomat

Célični avtomát (okrajšava CA) je diskretni model, ki ga raziskujejo teorija izračunljivosti, matematika in teoretična biologija. Vsebuje pravilno mrežo celic, ki je vsaka v končnem številu stanj. Mreža ima lahko končno število razsežnosti. Tudi čas je diskreten in stanje celice v času t je funkcija stanj končnega števila celic (okolic) v času t - 1. Te okolice so izbira celic relativno glede na izbrano celico in se ne spreminjajo, čeprav je celica sama lahko v okolici in po navadi ne spada vanjo. Vsaka celica ima svoje pravilo za naslednje stanje, ki temelji na vrednosti njene okolice. Ko se uveljavijo ta pravila za vse celice v mreži, nastane nova generacija celic.

Enorazsežni ciklični celični avtomat

Pregled

En način simulacije dvorazsežnega celičnega avtomata je s pomočjo neskončnega lista milimetrskega papirja in z množico pravil za naslednjo generacijo celic. Vsak kvadratek je »celica« in vsaka celica ima lahko dve stanji, črno in belo. Okolica celice je 8 kvadratov, ki se jo dotikajo. Za takšno celico in njene sosede je število možnih vzorcev enako 512 (2⁹). Za vsak od 512 možnih vzorcev tabela pravil navaja ali je osrednja celica v naslednjem časovnem intervalu črna ali bela. Conwayjeva igra življenja je priljubljena različica tega modela.

Po navadi se privzame da vsaka celica v vesolju zaživi v istem stanju, razen za končno število celic v drugih stanjih, kar se velikokrat imenuje konfiguracija. Še bolj v splošnem se dopušča da se vesolje prične pokrito s periodičnim vzorcem in le končno število celic krši ta vzorec. Zadnja podmena je običajna v enorazsežnih celičnih avtomatih.

Celični avtomati se pogosto simulirajo na končni in manj na neskončni mreži. V dveh razsežnostih je vesolje pravokotnik in ne neskončna ravnina. Očitni problem na končnih mrežah predstavljajo robne celice. Njihovo obravnavanje bo vplivalo na vrednosti vseh celic v mreži. Ena možna rešitev je, da se tem točkam dopustijo konstantne vrednosti. Drugi način je drugačna opredelitev okolice zanje. Lahko se jim dodeli manj sosedov, vendar je treba zato za robne celice določiti nova pravila. Robne celice se obravnava kot da so urejene po svitku: kadar ena izgine na vrhu, se pojavi na odgovarjajoči legi na dnu, in kadar izgine na levi, se pojavi na desni. To je podobno neskončnemu periodičnemu tlakovanju in se pri parcialnih diferencialnih enačbah včasih obravnava kot periodični robni pogoji. To se lahko predstavlja tako, da se sklopi levi in desni rob pravokotnika, in se dobi cev, nato se sklopi zgornji in spodnji rob cevi, da se dobi svitek. Vesolja drugih razsežnosti se obravnavajo podobno. Tudi tukaj gre za reševanje robnih problemov z okolicami. V enorazsežnem celičnem avtomatu je okolica celice x_i^t, kjer je t časovni korak (navpično) in i indeks (vodoravno) v eni generaciji, enaka {x_i−1^t−1, x_i^t−1, x_i+1^t−1}. Problemi nastopijo ko se okolica na levem robu nanaša na zgornjo levo celico, ki kot njena okolica ni v celičnem prostoru.

Zgodovina

Ulam je v 1940-ih letih v Los Alamosu raziskoval rast kristalov s pomočjo preprostega mrežnega modela. Istočasno je njegov sodelavec von Neumann reševal problem avtoreproduktivnih sistemov. Von Neumannov prvotni namen je temeljil na predstavi kako en robot zgradi drugega. Ta se imenuje kinematični model. Pri razvoju tega modela je von Neumann spoznal, da je zelo težko zgraditi samoponovljivi robot in da je izgradnja zelo draga. Ulam je predlagal naj razvije svoj model v okviru matematične abstrakcije, podobno kot je to naredil sam pri raziskovanju rasti kristalov. Tako se je rodil prvi sistem celičnih avtomatov. Podobno kot Ulamov mrežni model, so tudi von Neumannovi celični avtomati dvorazsežni in njihova samoponovljivost je določena algoritemsko. Nastal je univerzalni kopirni stroj in konstruktor v okviru celičnih avtomatov z majhno okolico (vsebovala je le tiste celice, ki so se dotikale okolice, pri von Neumannovem celičnem avtomatu pa le ortogonalne celice) in z 29. stanji za posamezno celico. Von Neumann je podal eksistenčni dokaz da bo določeni vzorec dal neskončno enakih kopij za dano celično vesolje. Ta model je znan kot model pokritja in se imenuje von Neumannov univerzalni konstuktor.

V 1970-ih je postal na široko znan dvorazsežni celični avtomat z dvema stanjema z imenom igra življenja, še posebej med zgodnjo računalniško srenjo. Izumil ga je Conway, populariziral pa Gardner s člankom v Scientific American. Pravila zanj so preprosta: če ima črna celica 2 ali 3 sosede, ostane črna. Če ima bela celica 3 sosede, postane črna. V vseh drugih primerih ostane ali postane bela. Navkljub svoji preprostosti, sistem doseže izrazito raznolikost obnašanja, ki niha med navidezno naključnostjo in redom. Ena od najbolj očitnih značilnosti igre življenja je pogosto pojavljanje skupin celic, ki se premikajo po mreži. Takšne skupine celic lahko trčijo ali vplivajo druga na drugo. Z veliko truda so pokazali, da lahko igra življenja oponaša univerzalni Turingov stroj. Ker so na igro življenja večinoma gledali kot na razvedrilno stvar, niso veliko raziskovali njene posebnosti in značilnosti nekaj z njo povezanih pravil.

Enorazsežni celični avtomat s pravilom 110 in dvema stanjema

Leta 1969 je Zuse objavil svojo knjigo Računski prostor (Rechnender Raum), kjer je predlagal da so fizikalni zakoni po svoji naravi diskretni, in da je celotno Vesolje le izhod determinističnega izračuna velikanskega celičnega avtomata. To je bilo prvo delo s področja, ki se danes imenuje digitalna fizika.

Wolfram je leta 1983 objavil prvega od nizov člankov, kjer je sistematično raziskoval zelo osnovni, vendar neznani razred celičnih avtomatov, ki jih je imenoval osnovni celični avtomati. Nepričakovana zapletenost v obnašanju teh preprostih pravil je vodila Wolframa v domnevo, da je zapletenost v naravi posledica podobnih mehanizmov. Poleg tega je Wolfram v tem času opredelil pojem notranje naključnosti in računske nepoenostavljivosti in predlagal da je pravilo 110 univerzalno, kar je v 1990-ih dokazal Cook, dokaz pa je po zapletu objavil leta 2004 v Wolframovi reviji Complex Systems. Wolfram je nato razvil računalniški program Mathematica in z njim raziskoval druge abstraktne sisteme. Leta 2002 je objavil svoje rezultate v delu Nova vrsta znanosti (A New Kind of Science) z orisom Cookovega dokaza. Wolfram je v delu poudaril, da odkritja o celičnih avtomatih niso osamljena dejstva, ampak so surova in so pomembna za vse znanstvene vede. Čeprav so v akademskih krogih knjigo kritizirali, ni pobijala osnovne fizikalne teorije na podlagi celičnih avtomatov in, čeprav je opisala več določenih fizikalnih modelov na podlagi celičnih avtomatov, je podala modele, ki so temeljili na po vrednosti različnih abstraktnih sistemih.

Rucker je v svoji knjigi Življenjska škatla, školjka in duša (The Lifebox, The Seashell and The Soul) iz leta 2005 razširil Wolframove teorije v smeri teorije splošnega avtomatizma. Ta za razlago kako lahko preprosta pravila porodijo zapletene rezultate kot model uporablja celične avtomate.