Rakuautomaat: määratlus, toimereeglid ja Conway Game of Life

Rakuautomaat on mudel, mida kasutatakse arvutiteaduses ja matemaatikas dünaamiliste süsteemide lihtsustamiseks ja uurimiseks. Selle idee on modelleerida ruumi jagamist diskreetseteks rakkudeks (näiteks ruudustik või torustik), kus igal rakul on üks mitmest võimalikust olekust (nt "elus"/"surnud" või täisarvulised olekud). Aja sammudes (iteratsioonides) arvutatakse iga raku uus olek selle praeguse oleku ja naaberrakkude olekute põhjal, kasutades kindlat lokaalset reeglistikku.

Määratlus ja põhikomponendid

Rakuautomaati võib formaalselt kirjeldada järgmiste osadena:

• Ruudustik: tavaliselt 1D-, 2D- (nt ruudustik) või kõrgema dimensiooniga lattice; võib olla lõpmatu, piiratud või torusena pakitud (wrap-around).
• Oleku hulk: iga raku jaoks diskreetne hulk olekuid (näiteks {0,1}).
• Naabersus: määrab, milliseid lähirakke arvesse võetakse (vt allpool).
• Uuendusreegel: lokaalne funktsioon, mis määrab järgmise aja sammu oleku raku praeguse oleku ja selle naabrite põhjal.
• Sünkroonne ajauuendus: kõik rakud värskendatakse korraga järgmise iteratsiooni olekuks (selleks kasutatakse tihti nn topeltpuhvrit).

Naabersuse tüübid ja reeglid

Levinumad naabersuse definitsioonid 2D-ruudustikul:

• Moore'i naabersus: 8 naabrit (diagonaalid kaasa arvatud).
• von Neumanni naabersus: 4 naabrit (üles, alla, vasakule, paremale).

Reeglid võivad olla deterministlikud (iga kombinatsiooni korral kindel tulemus) või probabilistlikud/stohhastilised. Samuti eksisteerivad totalistlikud ja outer-totalistlikud reeglid, kus otsus sõltub vaid naabrite olekute summaarist (näiteks kui on täpselt 3 naabrit, sünnib uus); see on Game of Life tüüpi reeglite puhul tavaline.

Conway's Game of Life

Stanislaw Ulam ja John von Neumann kirjeldasid rakuautomaate juba 1940. aastatel. Kuulsaim konkreetne näide, Conway's Game of Life, sai laiemalt tuntuks 1970. aastatel. Life on kahendoleku (elus/surnud) kahe-mõõtmeline Moore'i-naaber-rakuautomaat, mille lihtsad reeglid on sageli kokku võetud notatsioonis B3/S23 (Birth-3, Survival-2 või 3):

• Kui surnud rakkil on täpselt 3 elusat naabrit, sünnib see (muutub elusaks).
• Elus rakk jääb elusaks, kui tal on 2 või 3 elusat naabrit; muul juhul see hukkub (alamtoitumus või ülerahvastatus).

Kuigi reeglid on väga lihtsad, toodab Life keerukaid nähtusi ja mustreid, näiteks:

• Still lifes (püsivad mustrid, nt "block").
• Oscillators (ajaliselt korduvad mustrid, nt "blinker").
• Gliders (liikuvad mustrid) ja glider gun (muster, mis toodab glidereid pidevalt, nt Gosperi glider gun).

Conway' elu on tõestatud Turingi-täielikuks: sobiva mustri ja algseisundi abil saab selles rakuautomaadis simuleerida suvalist arvutusmasinat.

Variatsioonid ja rakendused

Rakuautomaate kasutatakse mitmes valdkonnas:

• Füüsika ja keemia (näiteks difusioon-reaktsioonisüsteemid),
• bioloogia (mõningate organismide kasvumudelite lihtsustamine),
• komplekssüsteemide uurimine,
• krüptograafia ja juhuarvugeneraatorid (mõned CA variandid pakuvad head hajutust),
• arvuti- ja matemaatiline huvi: uuritakse universaalsust, itereeritud mustrite käitumist ja enesekorraldumist.

Tuntud variatsioonid hõlmavad näiteks mitmeolekulaarseid olekuid, probabilistlikke rakuautomaate, pideva väärtusega (kõver) automaate ja erinevaid värskenduse režiime (asünkroonne või juhuslik järjekord).

Piirangud ja praktilised märkused

• Piirid: lõpmatus ruudustikus modelleerimiseks kasutatakse tihti suuri piiratud valdkondi; piiritefektid sõltuvad sellest, kas servad on fikseeritud või ühendatud (torus).
• Simulatsioon: kõigi rakkude sünkroonne värskendamine nõuab tavaliselt topeltpuhvrit: üks massiivi praeguse oleku hoidmiseks ja teine järgmise oleku arvutamiseks.
• Visualiseerimine: värvid ja animatsioon aitavad mustreid kiiresti mõista; suured simulatsioonid vajavad tihti optimeerimist (nt sparse-representatsioonid), et salvestada ainult elusad rakud.

Lühike ajalooline märkus

Rakuautomaadid said teoreetilise aluse juba 1940. aastatel tänu töödele nagu von Neumanni ja Stanislaw Ulam uurimused enese-replikeeruvatest struktuuridest. John Conway avaldas ja populariseeris 1970ndatel mängu "Game of Life", mis tõi CA-de uurimise laiemasse teadlaste ja harrastajate ringi (Martin Gardeneri populaarteaduslikud kirjutised aitasid samuti tuntust tõsta).

Rakuautomaadid on lihtsad ideelt, kuid sageli väga rikkad käitumiselt — see tekitab huvi nii teadlastes, kunstnikes kui ka harrastajates kogu maailmas.

Bioloogia

Mõned bioloogilised protsessid toimuvad - või neid saab simuleerida - rakuautomaatide abil.

Teatavate merekarpide mustrid on loodud looduslike rakuautomaatide abil. Näiteid võib näha perekondades Conus ja Cymbiola. Pigmendirakud paiknevad kitsas ribas piki karbi huuli. Iga rakk eritab pigmente vastavalt oma naaberpigmendirakkude aktiveerivale ja pärssivale aktiivsusele, järgides matemaatilise reegli loomulikku versiooni. Rakuriba jätab aeglaselt kasvades kestale värvilise mustri. Näiteks laialt levinud liik Conus textile kannab Wolframi reegli 30 rakuautomaati meenutavat mustrit.

Taimed reguleerivad oma gaaside tarbimist ja kadumist rakuautomaadi mehhanismi abil. Iga stoom lehel toimib kui rakk.

Peajalgsete nahal liikuvaid lainemustreid saab simuleerida kahe olekuga kahemõõtmelise rakuautomaadi abil, mille iga olek vastab kas laiendatud või sissetõmmatud kromatofoorile.

Neuronite simuleerimiseks on leiutatud lävendiautomaadid, millega saab simuleerida keerukat käitumist, näiteks äratundmist ja õppimist.

Fibroblastid sarnanevad rakuautomaatidega, sest iga fibroblast suhtleb ainult oma naabritega.

Conus tekstiil näitab oma kestal rakuautomaadi mustrit.

Küsimused ja vastused

K: Mis on rakuautomaat?

K: Kes kirjeldas esimesena rakuautomaate?

K: Mis on näide rakuautomaadi kohta?

K: Kuidas rakuautomaat töötab?

K: Millal näidati esimest korda Conway's Game Of Life'i?

Otsing