Túlélésért versengenek a sejtek

Egy és kétdimenziós automaták

A sejtautomaták (cellular automaton) diszkrét modellek, elemeik szabályos (elvileg akárhány dimenziós) rácsozatban elrendezett cellák (sejtek); mindegyik sejt véges számú állapot valamelyikét veheti fel, állapota csak a saját és a szomszédjai állapotától függ. Egyforma szabályok alapján működnek, amelyek végrehajtásakor mindig egy új generáció jön létre. Az automata mind memória-, mind processzorelemekként sejteket, sejtek tömbjét használja. Stilizált világként is felfogható dinamikus rendszer.

A legegyszerűbb modell, az egydimenziós automata sejtjei két lehetséges állapotban (on vagy off, tetszetősebben: élve vagy halva) találhatók. Gyorsan változik a kezdeti beállítás: egy sejtsor véletlenszerűen kerül egyik, vagy másik állapotba. Az alatta lévő sor már a második generáció, amelyben az összes sejt állapotát szabálysor határozza meg. Minden egyes sor állapota a felette elhelyezkedő sortól függ.

A legegyszerűbb szabály három sejtre vonatkozik: a második sor tetszőleges elemét a közvetlenül felette lévőtől, az attól jobbra és balra található példányok alakítják. A három sejt nyolcféleképpen fordulhat elő: 000, 001, 010, 011, 100, 101, 110, 111. Grafikusan megjelenítve, érdekes (és látványos) diagramokat kapunk. S még ezek a rendkívül egyszerű szabályok is vezethetnek elképesztően bonyolult, önhasonló (self-similar) mintázatokhoz.

A kétdimenziós automaták bonyolultabbak, izgalmasabbak – John Horton Conway 1960-as évek végén, hetvenes évek elején kidolgozott Életjátéka (Game of Life) a legismertebb (négyzetháló) modell.

A sejtautomaták története

Stanislaw M. Ulam az 1940-es években, Los Alamosban különböző számítógépes mintajátékokat talált ki. Meghatározott szabályok alapján a számítógép állandóan átalakuló, „szinte élő” mintázatokat, geometriai formákat nyomtatott ki. A sejtekből összeálló alakzatok gyakran egymást megsemmisítve küzdöttek az élettérért. Egy-egy sejt „élete” a szomszédoktól függött.

Ulam javaslatára az akkoriban a gépi reprodukciót tanulmányozó Neumann János a mintajátékokat végtelenített sakktáblára alkalmazta. A sejtstruktúrára (s így egy – az absztrakt világot működtető – leegyszerűsített fizikára) azért volt szüksége, mert nélküle rendkívül nagy, szinte mérhetetlen mennyiségű kapcsolat jönne létre az összetevők között. Végül sikerült megvalósítania az elméleti modellt, és bebizonyította, hogy megfelelő átmeneti függvénnyel a sejtautomata univerzális és önreprodukáló.

Neumann munkáját Arthur Burks fejlesztette tovább, majd az adaptáció és az optimalizálás problémájára alkalmazva, a „genetikus algoritmusok atyjaként” emlegetett John Holland általános sejtautomata-szimuláló programot fejlesztett.

John Horton Conway a sejtautomata-tervét a minimumig igyekezett leegyszerűsíteni. Két állapotot, négy egyszerű szabályt használt, sejtenként nyolc szomszédos cellával, cellánként maximum egy sejttel: ha egy élő sejtnek kettőnél kevesebb szomszédja van, akkor meghal; ha háromnál több szomszédja van, akkor is meghal; ha egy halott sejtnek (üres cellának) pontosan három szomszédja van, akkor életre kel; máskülönben, az összes többi sejt eredeti állapotában marad.

A gyorsan (számítógéppel másodpercenkénti több generációs sebességgel) pergő játék során különös alakzatok keletkeznek, csoportok bukkannak elő, tűnnek el, aszimmetrikus formák szimmetrikusokká fejlődnek – mint az életben.
 
Sejtautomaták és emergencia

Az 1980-as években Stephen Wolfram a Neumann-automata egydimenziós változatával, egy felettébb egyszerű modellel kísérletezett. Azt a következtetést vonta le, hogy az összes egydimenziós automata négy kategória valamelyikébe tartozik: homogén, ismétlődő minták (első osztály), periodikus stabil struktúrák (második osztály), véletlenszerű, rendezetlen alakzatok, mint a televíziós fehér zaj (harmadik osztály), komplex, időtálló szerkezetek (negyedik osztály). Utóbbi a legizgalmasabb, és egyben szép példája az egyszerű összetevőkből emergens módon létrejövő, alapokból nem magyarázható bonyolult rendszereknek. (Wolfram gondolatait a cyberpunk íróként is ismert Rudy Rucker dolgozta tovább egy 2005-ös dolgozatban.)

A múlt évtized első felének legintenzívebb sejtautomata-fejlesztéseit a Santa Fe Intézetben (SFI) jegyezték. Genetikus algoritmusokkal vizsgálták, miként vezet az evolúció bonyolult információfeldolgozó-műveletekhez.

Az alkalmazások – a pirinyó organizmusoktól közlekedési dugók, egész városok életének a szimulálásáig – széles skálát ölelnek fel. Kémiai rendszereket, hangya-, vagy termeszrajokat, hópelyheket, ökoszisztémákat, a gazdaságot sejtautomatákkal is megjelenítik.