Tehnologije

Celularni automati: lagana pravila, teška teorija

Oton Ribic nedjelja, 1. ožujka 2020. u 07:00

Iako površinski djeluju kao nevina zanimacija, celularni automati zapravo kriju razna zanimljiva teoretska svojstva koja zadiru u računalnu teoriju

Premda se ne radi o prvom takvom pothvatu, definitivno najpoznatiji i povijesno najzanimljiviji počeo se odvijati pod olovkom britanskog matematičara Johna Hortona Conwaya potkraj 1960-ih. Conway je bio – a i ostao – živopisan, šarolik lik kojeg interesiraju razna područja matematike, a tada su mu u središtu pozornosti bili procesi koji se samostalno odvijaju na dvodimenzionalnoj ploči, u skladu s nekoliko jednostavnih pravila. Oni su dobili i svoje službeno ime: celularni ili stanični automati (engl. cellular automaton). Celularni automati, naročito Conwayev, katkad se znaju nazivati i igrama, ali taj termin donekle zavarava jer u njima ne postoji jasan cilj, ni pobjeda, ni mogućnost izbora, a uostalom, ni igrači. No, o čemu se tu konkretno radi?

Conway je počeo s beskonačnim dvodimenzionalnim poljem, poput hipotetske šahovske ploče neograničene veličine, te pretpostavkom da svako od tih polja mora biti u jednom od dva stanja: upaljeno ili ugašeno (što se obično prevodi u “živo” i “mrtvo”). I, na tako postavljenoj osnovnoj pozornici, pokušavao je pronaći određeni sustav što jednostavnijih pravila koja bi diktirala kako bi se ta polja trebala ponašati tijekom vremena, a koja bi isto tako rezultirala vrlo kompleksnim, nepredvidljivim rezultatima.

Na prvi dojam, problem može djelovati gotovo nemoguć, nerješiv: potpuno je prirodno zapitati se je li moguće na temelju tako jednostavne premise – polja koja su živa ili mrtva, i nekoliko dodatnih jednostavnih pravila – uopće postići išta svrhovito, kamoli kompleksno. No Conway je takvu recepturu pronašao i objavio 1970. godine, i sâm nesvjestan koliku lavinu pokreće.

Život kao životno djelo

Conwayev rad dobio je ime “igra života” (engleski doslovno Game of Life), i u prvom pogledu na pravila ne djeluje posebno duboko. Conwayeva pravila su bila sljedeća: kako vrijeme teče korak po korak, ponašanje svake stanice, svakog polja, ovisi o njenih osmero susjeda. Ako stanica ima jednog ili niti jednog živog susjeda, u sljedećem će koraku biti mrtva radi usamljenosti. Ako ima četiri ili više, bit će mrtva radi repopulacije. Ako ima dva živa susjeda, ostat će u stanju u kakvom je sada, a ako ima tri, oživjet će ako već nije živa. Ove korake ponavljajmo u nedogled. I to je sve – ta četiri super jednostavna pravila definiraju sve.

Naravno, pretpostavka je da se ne počinje s praznom pločom, koja ionako ništa ne bi proizvela, već da se neka polja na početnoj poziciji ožive proizvoljno, a potom se počnu primjenjivati ova pravila i proučava se kako se situacija razvija.

Pokušate li nešto jednostavno započeti sami na tradicionalnoj matematičkoj bilježnici “na kvadratiće”, vjerojatno ćete biti razočarani time što većina najjednostavnijih oblika ne preživi više od nekoliko koraka, a u najboljem slučaju ostanu statični ili jednostavno osciliraju između dva stanja.

No ako za ovu problematiku upogonite računala, čak i iz onog vremena, i napravite mrvicu zanimljivije početne oblike sa samo desetak do dvadesetak početnih živih polja, vrlo ćete vjerojatno ostati fascinirani eksplozijom raznoraznih oblika koji će se iz njih početi razvijati.

Otkrivanje novog svijeta

U tom trenutku ime igre života postaje malo jasnije i smislenije; kako vrijeme teče, ciklus po ciklus, oblici koji nastaju i nestaju nekako djeluju kao da su živi, imaju razne kompleksne međusobne interakcije, generiraju oko sebe druge slične pseudoorganizme, i uopće ne ostavljaju dojam kao da se razvijaju prema samo četiri jednostavna pravila. Bilo koji softver za tu svrhu vrlo će vas brzo u to uvjeriti.

Jasno, stvar ne treba gledati mistično, niti, kako bi to mnogi senzacionalistički mediji možda predstavili, kao otkrivanje nekakvih skrivenih misli božanstava. Radi se o teoretskom matematičkom sustavu koji na temelju vrlo jednostavnih početnih pravila i stanja može proizvesti fantastično kompleksne i nepredvidljive forme. Sličan popularan primjer su fraktali.

U svakom slučaju, Conwayev rad odmah je privukao pozornost akademske zajednice te se vrlo brzo pokazalo kako postoje određena jednostavna početna stanja za koja je potrebno nekoliko stotina, ili u povremenim slučajevima, čak nekoliko tisuća koraka da se smire, tj. stabiliziraju. U tom smislu, stabilizacija znači da ostaju samo statične, nepromjenjive strukture, i oscilatori za koje je jasno kako će se dalje ponašati. No do tog trena, događale su se svakakve interakcije koje su se raširile na daleko veće područje nego što je zauzimala početna figura.

Kaos i(li) red

Upravo su te neobične interakcije i bile srž koja je privukla zajednicu, jer se pokazalo da ne postoji univerzalno pravilo prema kojem bi se ponašanje određene figure, prije stabilizacije, moglo lako predvidjeti a da se ona doista ne provede, korak po korak. Drugim riječima, Conwayeva igra bila je zanimljiva za promatranje per se, ali još zanimljivija radi tog faktora nepredvidljivosti, svojevrsnog nereda među stanicama koji se zbiva prije stabilizacije. Nije pronađena ni neka zgodna formula koja bi predvidjela barem red veličine “trajnosti” određenog početnog stanja prije stabilizacije – što je dalo dodatnu intrigu. (Jer, jednom kad se sustav može teoretski lako predvidjeti u svakom trenutku u budućnosti, načelno se drži riješenim i gubi na zanimljivosti.)

No ono što je važno za našu priču jest to da su se unutar tog Conwayevog nereda stanica koje kaotično oživljavaju i umiru, počela pronalaziti neka zanimljiva dodatna svojstva. Jedan od prvih Conwayevih problema bio je rast populacije – je li bilo moguće smisliti početno stanje u kojem veličina populacije (broj ukupno živih polja na cijeloj ploči) u prosjeku raste, i to u beskonačnost?

Britancu je intuicija govorila da je to u teoriji moguće, ali nije mogao naći konkretan primjer. U tome ga je preduhitrio Bill Gosper s MIT-a, smislivši gun, početnu poziciju koja periodički generira identične manje strukture koje izlijeću iz nje (tzv. glidere). U teoriji, koliko god veliku populaciju želite, dosegnut ćete je nakon dovoljno čekanja. Glider se pokazao samo jednom od raznih formi “svemirskih brodova” (doslovno spaceship u službenoj terminologiji) koje su u stanju beskonačno putovati – neke dijagonalno, a neke pravokutno.

Logika i računanje

Poput otvaranja novih sposobnosti lika u nekom RPG-u kad se ostvare potrebni preduvjeti, tako je i ova igra života kombiniranjem postojećih otkrivenih koncepata počela otvarati neke mogućnosti koje bi i njenom tvorcu i ostalima 1970. djelovale kao fantastika.

Ključna ideja bila je korištenje svemirskih brodova kao najjednostavnijih nositelja informacije: dolazak glidera u zadanom trenutku možemo smatrati jedinicom, a njegovo odsustvo nulom. Slijedile su osnovne logičke komponente poput invertera “i” i “ili”, a njihovo povezivanje omogućilo je logičke sklopove. Spore i nezgrapno velike, ali funkcionirajuće.

Nadalje, pojavili su se i “reflektori” svemirskih brodova, koji su ih mogli preusmjeriti i – u krajnjoj liniji, vratiti ih sustavu iz kojeg su pristigli nekoliko desetaka ili stotina vremenskih koraka kasnije. Pogađate, to je omogućilo elementarnu memoriju, kasnije rafiniranu do razine gdje se prihvaćeni glideri čuvaju, dok memoriji (opet kroz glider) stigne naredba da budu vraćeni u originalnom redoslijedu.

Kombinirajmo memoriju s logičkim komponentama i, pogađate, to je dovoljno za elementarno računalo, pod pretpostavkom da imate dovoljno strpljenja i memorije. Takva računala na Conwayevoj ploči, ne samo da su smišljena, napravljena i testirana, već se pokazalo da zadovoljavaju onaj blještavi kriterij, Turingovu kompletnost, što znači da se njima, uz dovoljno memorije, može simulirati bilo koje drugo računalo ili provesti bilo koji izračun.

No to je već druga priča. Ono što je bitno jest to da ploča temeljena na četiri trivijalna pravila može proizvesti toliko kompleksne i nepredvidljive rezultate, što ju je iz statusa enigmatičke zanimljivosti lansiralo u ozbiljnu matematičku temu.

Razne druge zvjerke

Iako bi se dalo argumentirati da je Conwayev celularni automat najpoznatiji takav primjer, vremenom se pojavio njih čitav zoološki vrt. Naravno, u teoriji ih možete smisliti praktički beskonačno mnogo, ali zanimljivi su samo oni koji pokazuju ovakva neobična svojstva nepredvidljivosti i kapaciteta za kompliciraniju logiku.

Većina takvih automata kompliciranija je od Conwayeve originalne ideje, ali neki od izuzetaka koji su ovaj minimalizam odveli do ekstrema su, primjerice, Pravila (Rule) 30 i 110. Ovi su celularni automati markantni po tome što se odvijaju na jednodimenzionalnoj ploči, a pravila ponašanja svakog polja ovise samo o njegovom prethodnom stanju te stanju njegovih susjeda.

Pravila su opet zavaravajuće jednostavna. Uzmimo za primjer pravilo 110: ako je stanica, tj. polje mrtvo, ali mu je živ desni susjed, u sljedećem će koraku oživjeti. Ako su živi i polje i oba susjeda, u sljedećem koraku neće biti živo. U svim ostalim situacijama “živost” polja ostaje kakva je i bila.

I opet, količina pravila koja bi se mogla napisati na poštansku marku stvara teško predvidljive, kaotične i neobične strukture, ali i omogućuje logičke sklopove, memoriju, računanje i, da, zadovoljava Turingovu potpunost. Podsjećamo, ove automate ne treba izvoditi računalo: u teoriji, a za manje forme i u praksi, mogli biste ih upogoniti popunjavajući kvadratiće bilježnice olovkom na papiru.

Primjera ima još, sežu u šesterokutna polja, u polja koja imaju više od dva moguća stanja, pa čak i u tri dimenzije, ali ona najjednostavnija ostaju i najzanimljivija.

Celularci svuda

Nakon ovog maratona, legitimno je zapitati se zašto bi ti celularni automati bili bitni čak i ako imaju takva neobična svojstva. Poput mnogih drugih teoretskih tema, njihov izravan efekt na svakodnevni život nije velik, ali pridonose istraživanju drugih područja koja su itekako primjenjiva.

Ako želimo ostati u sferi teorije, ovakvi automati pokazuju perspektivu za korištenje u teoriji prijenosa informacija, kriptografiji i autentikaciji. Mnogi među njima imaju svojstvo da je računanje koraka unaprijed trivijalno jednostavno, ali računanje prošlosti koja je do trenutačne situacije dovela, teško je i dugotrajno, a takve asimetrične funkcije u središtu su proučavanja suvremene kriptografije.

Potom, problematika je donekle srodna računalnim engineovima. Ako računate cikluse celularnog automata, nad svakim objektom provodite određene promjene ili transformacije na temelju jasnog niza pravila, potom proglasite taj rezultat novim aktualnim stanjem, i ponavljate postupak. Isto to u načelu radi i engine gotovo bilo koje aplikacije koja radi u realnom vremenu, pa time i razvoj djelotvornih algoritama jednog područja utječe na drugu, i obrnuto.

Isto tako, neki se događaji ili uzorci u znanostima mogu tumačiti, ili barem približno modelirati, celularnim automatima. Oni su upleteni od teorije naseljavanja populacije na zadanom području, preko komunikacije i ponašanja grupa prilikom donošenja odluka pa do kemijskih procesa. Štoviše, u samoj su prirodi pronađeni neki primjerci uzoraka koji su nastali celularnom automatikom, odnosno procesima koji se tako ponašaju. Klasični primjeri su školjka koja ima distinktivne šare u obliku uzorka Pravila 110 i maskirni uzorak na leđima određenih vodozemaca, koji impresivno precizno odgovaraju teoriji.

Stoga, celularni automati i dalje su aktivno područje istraživanja. Rast brzine računala i sâm neprekidno otvara nove mogućnosti koje su prethodno bile neizvedive, pa ne samo da je moguće, već i izvjesno da nas čekaju još razna zanimljiva otkrića. A i na kraju krajeva, razlog je zasigurno i to što igranje s njima brzo postane zarazno.

Golly je dobar početak bavljenja celularnim automatima, bez obzira na to zanimaju li vas samo usput, ili baš želite “zagristi” u tematiku
Golly je dobar početak bavljenja celularnim automatima, bez obzira na to zanimaju li vas samo usput, ili baš želite “zagristi” u tematiku