Sejtautomata

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 sejtautomata leggyakoribb formája: egy négyzetrácsban (a sejttérben) helyezkedik el, a négyzetrácsok által közrefogott cellákat sejteknek nevezzük. A sejteknek különféle állapotaik lehetnek (véges sokféle), ezeket célszerű színekkel jelölni. Ahogy az idő telik (az időt természetes számok mérik), a cellák változtatják állapotukat, általában saját és más sejtek, például néhány szomszédjuk előző időpillanatbeli állapotától függően. Így különféle mintázatok alakulnak ki, amelyek tudományos vizsgálat tárgyát képezik. A leggyakrabban vizsgált tulajdonságok a stabilitás (a mintázat bizonyos határok között állandó marad, pl. periodikusan változik az időben), vagy az önreprodukció (egy mintázat szabályos időközönként „megalkotja” saját másolatát a sejttérben). A sejtautomatákat Neumann János vezette be 1940 körül, aki a gépek önreprodukciójához akart matematikai modellt alkotni (néhány sikertelenebb próbálkozás után, a sejtautomaták bizonyultak tanulmányozásra érdemes modellnek). Az egyik legismertebb sejtautomata-rendszer John Conway Életjátéka, amelynek számítógépes megvalósítása népszerű szórakoztató matematikai eszközzé vált a matematikában laikusnak számítók körében is.

A modell elemei tehát 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 Stanisław 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 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.

Kapcsolódó szócikkek

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

Informatikai portál • összefoglaló, színes tartalomajánló lap