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.