A blokk cellás automata a cellás automaták egy osztálya , amelyben a rácsot blokkokra osztják, és az átmeneti függvényt mindegyik blokkra külön alkalmazzák. A blokk cellás automaták hasznosak a fizikai jelenségek modellezésére, mivel gyakran nem nehéz olyan átmeneti függvényeket kiválasztani, hogy az eredményül kapott sejtautomaták reverzibilisek legyenek , és megfeleljenek a kiválasztott megmaradási törvényeknek . [egy]
A sejtautomata cellák szabályos rácsát jelenti, amelyek mindegyikének van egy véges állapothalmazból vett állapota, és egy átmeneti függvény szükséges a cellaállapotok frissítéséhez a szomszédok állapotai alapján. Blokknak nevezzükha a rácsot egyenlő, nem metsző blokkra osztjuk, és az átmeneti függvény a blokkot minden cella szomszédjaként használja . Ebben az esetben az automatának véges számú partícióval kell rendelkeznie felváltva használt blokkokra: például egy partíciót el lehet tolni valamilyen irányba. [1] [2]
Így az automata minden egyes lépése során az összes cellára egyszerre kerül alkalmazásra az átmeneti függvény, amely a többitől függetlenül változtat minden blokkot, majd a partíció a következőre vált és a lépés megismétlődik. Ez lehetővé teszi nem triviális számítások elvégzését meglehetősen egyszerű átmeneti függvények segítségével.
Az ilyen séma legegyszerűbb példája a Margolus szomszédság , amelyben egy négyzetrács celláit függőleges és vízszintes vonalakkal 2 × 2 blokkra osztják, és minden lépés után a blokkokra osztást egy cellával eltolja vízszintesen és függőlegesen. ; így a következő lépésben bármely blokk mind a négy cellája más-más blokkba kerül. [3] Ez a környék Norman Margolus ( angolul Norman Margolus ), a blokkos sejtautomaták egyik első kutatójáról kapta a nevét. [egy]
Példa egy Margolus környéket használó blokk cellás automatára a "The Critters" . A Critters átmeneti függvény megfordítja az egyes cellák állapotát, ha a blokkban lévő élő cellák száma nem kettő, és 180°-kal elforgatja a teljes blokkot, ha ez a szám három. Mivel az élő sejtek száma az elhaltak számára változik, és az átmeneti függvények a sejtek számának minden értékére reverzibilisek, egy ilyen sejtautomata blokkonként reverzibilis, így összességében reverzibilis. [4] Mindazonáltal összetett dinamikus viselkedést mutat, hasonlóan Conway Életjátékához ; különösen a Turing teljes , a részletekért lásd a kapcsolódó cikket .