Sejtautomaták

A sejtautomaták olyan diszkrét modellek, amiket a számításelméletben, matematikában, mikrostruktúrák modellezésében használnak fel. A modell elemei szabályos rácsozatban elrendezett cellák (sejtek), mindegyik véges számú állapot valamelyikét veheti fel. A rács akárhány dimenziós is lehet. Az idő a modellben szintén diszkrét, és a sejtek t időbeli állapota véges számú sejt (az adott sejt szomszédai) t;‒ 1 pillanatbeli állapotától függ. Ezek a szomszédok az adott sejtre jellemzőek, és időben nem változnak (a sejtet magát is tartalmazhatják). Minden sejt ugyanazon szabályok alapján működik, és minden alkalommal amikor a szabályokat végrehajtják, egy új generáció jön létre.

A megnevezés eredete

Neumann sejtautomata volt az eredeti kifejezése a sejtautomatáknak egy olyan problémafelvetés kapcsán, amit Stanislaw Ulam tett barátjának, Neumann Jánosnak. A fejlesztés eredeti célja egy önreprodukáló gép megszerkesztése volt. Fölvetették, hogy mik ennek a logikai követelményei. A sejtautomata kifejezést tehát Neumann János használta az univerzális szerkesztőgép konstruálása során.

A sejtautomaták szemléletes leírása

A ’’’sejtautomaták’’’ megnevezés olyan fogalmi gépezetet jelöl, amely hasonlít a Descartes-koordináták használatához. Ebben is, abban is, elődeink által megformált segédeszközökből áll össze egy leírási forma. A Descartes koordináták merev leírási hátteret képeznek, amely háttér előtt bizonyos változások (például helyzetváltozások) jól leírhatók. A sejtautomatáknál ez a háttér nem merev. A modellbeli eseményleírás olyan sejtháttéren történik, amely már eredendően is sok változatosságot rejt magában. Ahogyan a képi névadás is jól érzékelteti, a sejtautomaták „hátterét” sejtek képezik. A sejtsokaság belső változatossága, például a deformálhatósága, része a háttérnek, és ez a háttérmozgás rendezett. A háttér a sejtekbe épített, de egységes belső eseménysort teljesíthet: E változásokban a szomszédsági viszonyoktól való függés is fontos szerephez juthat. Mindezek a szabályok első sugallatra is gazdag cselekvőképességű rendszert és változási leírást sejtetnek.

Szereposztás a mozgásleírásnál

Ha Descartes koordináta-rendszertől indítjuk, akkor a sejtautomaták mozaikja eleven, megmozduló háttérként viselkedik a Descartes koordináták „merevségével” szemben. A hagyományos fizikai kép megnevezéseivel azt is mondhatjuk, hogy a sejtautomatákból alkotott mozaikfelülettel a deformálódó felület sejtjeihez rögzített koordináta-rendszerhez jutottunk A sejtek mozaikjához rögzített koordináta-rendszerrel nemcsak lehetővé, de szükségszerűvé válik az, hogy a felület állapotváltozásait részben belefogalmazzuk (beleolvasszuk) a vonatkoztatási rendszerbe. Ezzel azonban nyílttá is válik a kérdés: mi képez még vonatkoztatási rendszert és mi képezi már a leírásra váró állapotváltozás mozgásegyenletét?

A vonatkoztatási rendszer és leírandó jelenség szétválasztása

Kétségtelen, hogy a klasszikus mechanika is ismeri az „együtt mozgó koordináta-rendszer” fogalmát (s például az égi mechanikában kiterjedten alkalmazza). Ott azonban ez a transzformáció két merev koordináta-rendszer egymáshoz viszonyított mozgását iktatja be az eredeti merev háttér és a jelenségleírás közé. Ezzel a mozgásleírás még nem válik kétrétegűvé, hiszen a merev két koordináta-rendszer közötti átalakítás (áttérés) beépíthető a hagyományos képű mozgásegyenletbe. A sejtautomata mozgásleírási forma azzal, hogy eleven szemcsékre bontja az EGÉSZt, új mozgásleírási szintet is teremt. A sejtautomaták környező sejtállapotoktól, előző állapottól és belső programtól függő állapotváltozásai megőrzik ugyan a kezdeti feltétel+peremfeltétel+mozgásegyenlet változás-leírási szerkezetet, de az általuk nyitott új hierarchiaszint lényegében megkettőzi a mozgásleírás lehetőségét. E megkettőzéssel a változásleírás kétrétegűvé válik: a SEJTek rétegén történővé és az EGÉSZ hierarchiaszintjén történővé. E kétrétegűséggel azonban össze is keveredhetnek a korábbi egyrétegű leírásban tiszta szerepek: most már a sejtmozaik háttér, tehát a vonatkoztatási rendszer is mozog, nem csak az alakzatrendszer-EGÉSZ. A sejtháttér rendezett mozgásait így beépítve a vonatkoztatási rendszer szerepét öröklő sejtmozaik-rendszerbe új szempontok figyelembe vételére nyílik lehetőség az állapotváltozás sejtautomata rendszerű leírásában: például a visszacsatolásoknak az EGÉSZt átható rendszerére.

A sejtautomata modell mint leírási forma

Amikor egy jelenséget sejtautomata modellel írunk le, egy újszerű leírási formát használunk föl a jelenség bizonyos jellemző vonásainak kiemelésére. A sejtautomata modell, mint leírási forma, jobban kidolgozza azt a hátteret, amelyen az átalakulási események zajlanak, és két rétegre bontja magának az állapotváltozásnak a leírását is. Valójában az esemény-hátteret is kétszintűnek tekinti. Az egyik háttér-szint lokális: az állapotváltozási eseményekben főszereplő sejteket (alak, környezet, kezdeti értékek) adja meg. A másik háttér-szint globális: a sejtek mozaikot (hálózatot) alkotó együttesét (vagy teret kitöltő terét) adja meg, vagyis magát az egészében vizsgált felületet.

A sejtfelület állapotváltozásainak leírása is két rétegben történik. Az egyes sejtek szintjén: helyi (lokális) átmeneti függvénnyel, amely időben egyenletesen következő lépésenként, diszkrét függvényként adja meg a sejt állapotát korábbi állapota, a szomszéd sejtek állapota és a belső program függvényében. A második esemény-leírási szint a sejtmozaik rendszer állapotváltozásaié, amely az egyes sejtek lépéseiből összegződik, s időlépésenként létrejövő sejtmozaik-képernyő állapotváltozások sorozataként kerül megadásra (vagy kiszámításra).

A sejtautomata modellben tehát az eseményháttérnek és az állapotváltozások átmeneteinek a megadása is két-két részben történik. Mindkettőben szerepel egy lokális és egy globális rész. Betűpárokkal fölcímkézve e megadási formát, a ’’’háttér statikus megadását az Aa és az Ab pontokkal’’’, az ’’’átalakulást átmeneti függvényekkel’’’ leíró (dinamikus, mozgásegyenleteknek megfelelő) megadását ’’’a Ba és Bb pontokkal’’’ végezzük.

A sejtautomata modell formai megadása

A sejtautomata modell megadása tehát formailag a következőket jelenti:

• A. A háttér
• Aa a sejtek alakja, lokális kapcsolatai a mozaikhálózatban, kezdeti állapotai
• Ab a sejtekből fölépülő sejtmozaik-rendszemek egész felületet megadó (sejtekből megépítve) együttese: a globális felületrács, kezdeti paramétereivel

• B. Az átmenetek (átmeneti függvények)
• Ba az egyes sejtek lokális átmeneti függvényei, időlépésenként: ez a belső programtól (a sejtek automaták) és a szomszédságtól függ
• Bb az egész felület (sejtmozaik hálózat) globális átmeneti függvénye, amely az egyes sejtek lokális átmeneti függvényeiből összegződik időlépésenkénti állapotsorozat formájában

Bár az egyes a és b pontok nem teljesen függetlenek egymástól, a sejtautomata modell keretei között történő állapotváltozás leírásnak az ereje a lokális és a globális szerkezet és dinamika együttes figyelembe vételéből, kapcsoltságából fakad. Mondhatjuk azt is, hogy a sejtautomata leírásban éppen az eseményeknek ezen a kétrétegűségén van a hangsúly.

Ismert sejtautomaták

A legismertebb sejtautomaták egyike a John Conway által kifejlesztett életjáték. Ennek a sejtmozaik háttere olyan, mint a kockás füzet: ebben a szerkezetben minden sejtnek nyolc sejtszomszédja van. Az egyes sejtek kétféle állapotban lehetnek: élő vagy halott állapotban. Az idő, ahogy minden egyszerűbb sejtautomatában, diszkrét időegységekben múlik. Időlépésenként változtathatják állapotukat a sejtek a következő szabályok szerint:

• Egy olyan sejt helyére, amely halott, de három élő sejtszomszédja van, élő sejt „születik”.
• Egy olyan sejt, amely élő volt, és két vagy három szomszédja is élő volt, az ilyen sejt életben marad.
• Az összes többi, másmilyen környezetű sejt halott lesz a következő lépésben.

Az életjáték sok érdekes szerkezet mozgását, gyarapodását, vagy elmúlását és sajátos alakzatok tartós fönnmaradását tudja szimulálni.

Neumann János és Codd sejtautomatái

Az 1940-es években Neumann János fölvetette a következő problémát.

• Miféle logikai szerkezet elegendő egy olyan automatikus géphez, amely önmagát reprodukálni képes?

Maga Neumann János megalkotta az Univerzális Konstruktor nevű modellt egy négyzetrácson, 29 féle állapotot fölvenni képes sejtekkel. E. F. Codd angol matematikus egy egyszerűbb gépet tudott konstruálni, amelyben csak 8 féle állapotra volt szükség. Ennek alapján Neumann eredeti fölvetését módosították a következőre:

• Miféle logikai szerkezet szükséges egy olyan automatikus géphez, amely önmagát reprodukálni képes?

Codd sejtautomatáját C. G. Langton tovább tudta egyszerűsíteni 1984-ben.

Lásd még (egyszerű sejtautomata leírások)

• Arkhimédeszi testek
• Levélállás
• életjáték
• szimmetria
• Wolfram Research
• Stephen Wolfram

Irodalom

• Edgar F. Codd (1968): Cellular Automata. Academic Press, New York
• Claude Shannon (1965): Számológépek és automaták. (In: A kibernetika klasszikusai, Studium-30.) Gondolat, Budapest
• Von Neumann, J. and A. W. Burks (1966). Theory of self-reproducing automata. Urbana, University of Illinois Press.
• Langton, C. G. (1984): Self-Reproduction in Cellular Automata. Physica 10D
• Eigen, M., Winkler R. (1981): A játék. Természeti törvények irányítják a véletlent. (Ford. Koch Sándor). Gondolat Könyvkiadó, Budapest (ISBN 963-281-019-8)
• Bérczi Sz. (1993): Symmetry and Topology in Cellular Automatic Transformations, The Solution of the Indirect Von Neumann Problem for the Transfiguratuions of Cylindrical Cell-Mosaic systems of Fibonacci Plants. Abstracta Botanica. 17.(12.).Budapest (ISSN 0133 6215)
• Bérczi Sz. (1993): Symmetry Changes by Cellular Automata in Transformations of Closed Double-Threads and Cellular Tubes with Möbius-Band, Torus, Tube-Knot and Klein-Bottle Topologies. Symmetry: Culture and Science, 4. No. 1. p. 49-68. (ISSN 0865 4824)
• Vollmar, R. (1982): Sejtautomata algoritmusok. Műszaki könyvkiadó, Budapest
• Bérczi Sz. (1992): Sejtautomaták: platoni és archimedészi testeken át. Iskolakultúra. II. 22.sz. 30-43. (HU ISSN 1215 5233)
• Peák I. (1980): Bevezetés az automaták elméletébe, I. egyetemi jegyzet, J3-1115. Tankönyvkiadó, Budapest
• Bérczi Sz. (1990): Szimmetria és struktúraépítés. egyetemi jegyzet, J3-1441. Tankönyvkiadó, Budapest
• Bérczi Sz. (1994): Sejtautomaták: Fibonacci növényeken át. Iskolakultúra. IV. No. 7. 16-32. o. (HU ISSN 1215 5233)
• Takács V.D. (szerk.): (1978): Sejtautomaták. Gondolat, Budapest
• Bérczi Sz. (1991): Platonic-Archimedean Spherical Cellular Automata in the Solution of the Indirect Von-Neumann Problem on Sphere for Transformations of Regular Tessellations. (In: Symmetry and Topology in Evolution, B. Lukács, Sz. Bérczi, I. Molnár, Gy. Paál, Eds.) p. 111-116. MTA-KFKI-1991-32/C. Budapest

Külső hivatkozások

• Előadás a sejtautomatákról
• Celluláris automata a mediawikin
• Neumann János: A számológép és az agy. MEK
• Conway: Életjáték
• Conway életjátékának részletesebb leírása a HUPWIKIn
• Von Neumann, J. and A. W. Burks (1966). Theory of self-reproducing automata
• Langton munkássága
• Sejtautomaták egy fajra