A cellás automata (gyakran használják a "celluláris automata" kifejezést is) a számítástechnikában és a matematikában alkalmazott absztrakt modell, amely egy egyszerű, diszkrét dinamikus rendszert ír le cellákból álló rácson. A modell alapelve, hogy a tért felosztjuk kis, egymással kapcsolatban álló cellákra; minden cellának egy előre definiált, véges számú lehetséges állapota van. Az idő diszkrét lépésekre (iterációkra, "fordulókra") van bontva, és minden lépésben minden cella új állapota az aktuális állapota és a környező cellák állapota alapján, egy lokális átmeneti szabály (update rule) szerint kerül meghatározásra.

Formális felépítés — mi alkot egy celluláris automatát?

  • Rács (L): a cellák elrendezése; lehet 1D (sor), 2D (négyzetrács), vagy magasabb dimenziós; gyakori a végtelen sík vagy a véges periódikus (toroidális) rács.
  • Állapothalmaz (S): minden cella felvehető állapotainak halmaza (pl. bináris: élő/halott).
  • Szomszédság (N): az a cellakészlet, amely befolyásolja az adott cella következő állapotát (pl. Moore- vagy von Neumann-szomszédság).
  • Átmeneti függvény (f): a lokális szabály, amely a cella és szomszédai aktuális állapotából kiszámítja a következő állapotot. A frissítés általában szinkron — minden cellát egyszerre frissítenek.

Szomszédságok és peremfeltételek

Gyakori szomszédságok a 2D négyzetrácson:

  • Moore-szomszédság: a 8 közvetlen szomszéd (átlós irányokkal együtt).
  • von Neumann-szomszédság: a 4 ortogonális szomszéd (fel, le, bal, jobb).

Peremfeltételek lehetnek: véges rács széleinek külön kezelése, tükrözés, vagy periodikus (toroidális) perem, illetve modellezhetjük a rácsot gyakorlatilag végtelennek.

Viselkedés és osztályozás

A celluláris automaták nagyon eltérő dinamikát mutathatnak: egyesek egyszerű, gyorsan stabilizálódó állapotokat eredményeznek; mások komplex, kaotikus viselkedést vagy strukturált, ismétlődő mintákat hoznak létre. Stephen Wolfram és mások különböző osztályozásokat javasoltak a viselkedések leírására (pl. rendezett, kaotikus, komplex/térben terjedő minták).

Gyakori típusok és változatok

  • Determinista vs. sztochasztikus: a szabály lehet determinisztikus vagy valamilyen véletlenszerű elemet tartalmazó (pl. valószínűségi átmenetek).
  • Diszkrét vs. folyamatos: a hagyományos CA diszkrét állapotú és időben diszkrét; vannak azonban folytonos állapotú és/vagy folyamatos időben definiált változatok is.
  • Egyszerű 1D automaták: például Wolfram 1D szabályai (Rule 30, Rule 110 stb.).

Alkalmazások

Celluláris automatákat használnak modellezésre és számításra számos területen:

  • fizikai rendszerek (diffúzió, fázisátalakulások),
  • biológiai modellek (sejtautomaták, morfológia, populációdinamika),
  • kémiai reakciók (pl. reakció–diffúziós rendszerek szimulációja),
  • forgalom- és tömegközlekedés-modellezés,
  • kriptográfiai és párhuzamos számítási módszerek,
  • művészet és procedurális tartalomgenerálás (pl. textúra- vagy tájgenerálás).

A celluláris automaták története röviden

A celluláris automaták korai elképzelését a Stanislaw Ulam és John von Neumann dolgozta ki az 1940-es és 1950-es években, elsősorban az önszerveződő rendszerek és az önreprodukció elméleti vizsgálatára. A legismertebb példa a népszerű kultúrában azonban a következő részben ismertetett játék, amelyet John Conway dolgozott ki és amelyet az 1970-es években széles körben megismertek és népszerűsítettek.

Conway's Game of Life — a legismertebb példa

A celluláris automaták egyik leghíresebb példája a Conway's Game of Life. John Conway 1970 körül alkotta meg ezt a 2D bináris celluláris automatát, amely a Moore-szomszédságot használja. A Life szabályai egyszerűek, de a rendszer nemtriviális, gazdag és váratlan viselkedést produkál.

Alapvető szabályok (négyzetrács, élő/halott állapot):

  • Számoljuk meg egy cella 8 szomszédjának élő celláinak számát.
  • Ha a cella élő és a szomszédok száma 2 vagy 3, akkor a cella megmarad élőnek (survival).
  • Ha a cella halott és pontosan 3 élő szomszédja van, akkor újraéled (birth).
  • Egyébként a cella halott lesz vagy marad halott (death by loneliness or overcrowding).

Példák és jellegzetes minták a Life-ban

  • Still lifes (pl. block): statikus konfigurációk, amelyek változatlanul maradnak.
  • Oscillators (pl. blinker): időnként periodikusan visszatérő minták (periodus >1).
  • Spaceships (pl. glider, lightweight spaceship): a rácson haladva mozgó minták.
  • Guns (pl. Gosper glider gun): ismétlődően generál glidereket, tehát végtelen növekedést eredményez.

Turing-teljesitás és komplexitás

Bár a szabályok egyszerűek, a Game of Life a gyakorlati konstrukciók révén képes univerzális számításra — elvileg Turing-teljessé tehető. Ez azt jelenti, hogy kellő erőforrás mellett képes bármilyen algoritmust szimulálni. A Life és más celluláris automaták ezért fontos szerepet játszanak a komplex rendszerelmélet, a mesterséges élet és az elméleti számítástudomány kutatásában.

Összefoglalás

A celluláris automaták egyszerű, lokális szabályokra épülő modellek, melyekből gyakran váratlan, komplex viselkedés és gazdag mintázatok jelennek meg. A modell fontos eszköz a tudományban és a műszaki gyakorlatban: segít megérteni, hogyan állhat elő bonyolult viselkedés egyszerű helyi kölcsönhatásokból. A Conway's Game of Life ikonikus példája annak, hogyan vezethetnek nagyon egyszerű szabályok rendkívül gazdag, kutatható dinamikához.