Reverzibilis cellás automata

A reverzibilis cellás automata  olyan cellás automata , amelyben minden állapotnak egyetlen elődje van. Így ez egy szabályos cellaháló, amelyek mindegyikének állapotát egy véges állapothalmazból veszik, és egy szabály a cellák állapotának egyidejű frissítésére a szomszédok állapota alapján. A reverzibilitás feltétele, hogy bármely cella korábbi állapota meghatározható legyen a rács összes cellájának frissített állapotának ismeretében. Az idő megfordítása után egy másik reverzibilis sejtautomatát kapunk, talán jóval nagyobb szomszédságokkal, de egy olyan szabállyal is, amely meghatározza a sejt jövőbeli állapotát, a szomszédok jelenlegi állapota alapján.

Számos módszer ismert a reverzibilis cellás automaták meghatározására, köztük a blokk cellás automaták , amelyekben minden blokk a többitől függetlenül frissül, és a másodrendű cellás automaták , amelyekben a cellafrissítési szabályt az automata két korábbi állapota határozza meg. Sőt, ha az automatát egy szabálytáblázat segítségével adjuk meg, a reverzibilitásának ellenőrzése megoldható egydimenziós cellás automata esetén, de általános esetben megoldhatatlan .

A reverzibilis cellás automaták a reverzibilis számítástechnika természetes modelljét határozzák meg  , egy olyan technológiát, amely lehetővé teszi nagyon alacsony energiafogyasztású számítástechnikai eszközök létrehozását. A kvantumcelluláris automatákról , amelyek lehetővé teszik a számítások elvégzését a kvantummechanika elvei alapján , gyakran reverzibilisnek tekintik. Ezen túlmenően a fizika számos modellje, mint például az ideális gázmolekulák mozgása vagy a mágneses töltések elhelyezésének Ising-modellje , természetesen reverzibilis, és reverzibilis sejtautomaták modellezik.

A reverzibilis sejtautomatákban rejlő tulajdonságok felhasználhatók olyan automaták tanulmányozására, amelyek irreverzibilisek, de rendelkeznek attraktorral  , vagyis olyan állapotok részhalmazával, amelyekhez a véletlenszerű kezdeti állapotok konvergálnak. Ahogy Stephen Wolfram írja , „egy attraktorhoz közeledve bármely rendszer, még az irreverzibilis is, bizonyos, a visszafordíthatósághoz közeli tulajdonságokat mutat” [1] .

Példák

Elemi sejtautomaták

A legegyszerűbb cellaautomaták egydimenziós cellákból állnak, amelyek mindegyike 0-t vagy 1-et tartalmaz, míg a cella szomszédsága önmagából és mindkét oldalon egy szomszédból áll; az ilyen sejtautomatákat eleminek [ 2] nevezzük . Ha az átmeneti függvény soha nem változtatja meg a cella állapotát, mindig megfordítja, lecseréli a szomszéd állapotára (mindig ugyanaz, balra vagy jobbra), vagy az utolsó két művelet kombinációját alkalmazza, akkor egy ilyen elemi cellaautomata megfordítható. . Egyszerűsége ellenére az átmeneti függvény, amely minden cellához hozzárendeli a szomszédja értékét, fontos szerepet játszik a szimbolikus dinamikában , ahol eltolás operátorként ismert [3] .

Az elemi sejtautomaták visszafordíthatatlanok, kivéve a fent említett triviális eseteket, amelyekben minden sejtet csak az egyik szomszédjának állapota határoz meg. A 90-es szabály azonban közel áll a reverzibilishez , amelyben minden cella jövőbeli állapota a két szomszédja jelenlegi állapotának modulo 2 összege (más néven XOR ). Bár a 90-es szabály irreverzibilis, minden konfigurációjának pontosan négy elődje van, és a 90-es szabály is lokálisan visszafordítható , azaz bármely egymást követő állapotsorozatnak van legalább egy elődje [4] .  

Egyéb egydimenziós példák

Egy kicsit összetettebb példát kapunk a következőképpen: legyen az egyes cellák állapota egy rendezett pár ( l , r ), és az átmeneti függvény az új állapot bal oldalát veszi át a bal oldali szomszédtól, a jobb oldalát pedig a jobb. Ebben az esetben feltételezzük, hogy a bal és a jobb oldali részt a lehetséges értékek két különböző véges halmazából vesszük. Egy példa a cikk elején látható ábrán látható : az állapot bal oldala az alakzat alakja, a jobb oldala pedig a színe. Egy ilyen automata invertálható, mivel a jobb oldalon a cella előző állapotának bal oldalát, a bal oldalon pedig a jobb oldalát vehetjük.

Egy másik példa a reverzibilis egydimenziós cellás automatára 2-vel vagy 5-tel való szorzást decimális jelöléssel végez . Egy ilyen szorzásban minden számjegy csak az előző két számjegytől függ, ezért a következő értéket meghatározó szomszédság véges, ami egy cellás automatához szükséges. Általánosságban elmondható, hogy egy szám n természetes számmal való szorzását vagy osztását a pozíciós jelöléssel egy cellás automata akkor és csak akkor adja meg, ha n minden prímtényezője a számrendszer alapjában van. Egy ilyen automata egydimenziós és megfordítható, mivel osztható vagy szorozható ugyanazzal a számmal. És például a 3-mal való szorzást decimális jelöléssel egy cellás automata nem írja elő, mivel az átvitel tetszőlegesen sok számjegyen keresztül történhet: 333334*3=1000002 szorzásakor 5 számjegyen keresztül történik az átvitel [5] .

Critters

A Game of Life , az egyik ismertebb sejtautomata, nem visszafordítható: például sok konfiguráció kihal. Tartalmazza a Gardens of Eden  -t is, elődök nélküli konfigurációkat. Ehelyett Tommaso Toffoli és Norman Margolus feltalálta a Critters-t,  egy reverzibilis sejtautomatát, amelynek dinamikus viselkedése az élethez hasonló [6] .

A "Critters" egy blokk cellás automata , amelyben a cellák 2 × 2 blokkra vannak osztva, amelyeket a többitől külön frissítenek. Ugyanakkor minden lépés után megváltozik a blokkokra osztás: egy cellával eltolódnak vízszintesen és függőlegesen. 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 visszafordíthatók, egy ilyen sejtautomata blokkonként reverzibilis, így összességében reverzibilis [6] .

Ha kis számú véletlenszerű sejttel kezdi az elhalt sejtek nagyobb régiójában, akkor sok kis minta, mint például az Életjáték siklója, a központi régióból fog terjedni, és összetett módon kölcsönhatásba lépnek egymással . Ugyanakkor a Critterek végtelen számú különböző periódusú összetett űrhajókat és oszcillátorokat tesznek lehetővé [6] .

Konstrukciók

Számos általános módszer ismert reverzibilis sejtautomaták létrehozására.

Celluláris automaták blokkolása

A blokk cellás automata  olyan cellás automata, amelynek a celláit egyenlő blokkokra osztják, és az átmeneti függvényt mindegyik blokkra külön alkalmazzák. Általában egy ilyen automata több partíciót használ fel egymás után blokkokra [7] . Egy ilyen séma tipikus 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 bármely blokk mind a négy cellája más-más blokkba kerül a következő lépésben [8] . A fentebb tárgyalt "lények"Margolus környékét használják.

Ahhoz, hogy egy blokkos cellás automata reverzibilis legyen, szükséges és elegendő, hogy az egyes blokkon lévő átmeneti függvények reverzibilisek legyenek, ami lehetővé teszi egy blokk cellás automata reverzibilitásának ellenőrzését kimerítő felsorolással . Ugyanakkor az inverz cellás automata egy blokkautomata is, amelynek blokkokra való felosztása azonos, de inverz átmeneti függvénye [7] .

Irreverzibilis automaták szimulációja

Bármely -dimenziós sejtautomata beágyazható egy -dimenziós reverzibilisbe: ráadásul az új automata minden állapota eltárolja a régi evolúciójának teljes történetét. Ezzel a beágyazással Toffoli megmutatta, hogy az irreverzibilis sejtautomaták számos tulajdonsága átkerül a reverzibilisekre, például Turing-teljesek lehetnek [9] .

A dimenziónövekedés egy ilyen konstrukcióban nem véletlen: bizonyos gyenge megkötések mellett (mint például a beágyazás invarianciája a párhuzamos fordításokhoz képest ) bebizonyosodott, hogy a sejtautomaták bármilyen beágyazása az „ Édenkertbe ” az elődök nélküli konfigurációnak egy reverzibilis cellás automatává kell növelnie a dimenziót [10] .

Azonban nyugalmi állapotok ( angolul quiescent states ), vagyis olyan állapotok jelenlétében , amelyek nem változnak, feltéve, hogy a szomszédos állapotok sem változnak [ hogyan? ] , lehetőség van egy cellás automata végső konfigurációjának modellezésére egy azonos dimenziójú blokk -reverzibilis cellás automatában [11] . Az információkat, amelyeket a következő lépésben el kellett volna veszíteni, ehelyett a nyugalmi sejtek végtelen régiójában tárolják. Ugyanakkor a konfiguráció egy részének szimulálásához szükséges idő arányos annak méretével. Ennek ellenére egy ilyen konstrukció lehetővé teszi egy reverzibilis egydimenziós Turing-teljes cellás automata létezésének bizonyítását [12] .

Jegyzetek

  1. ↑ Wolfram (2002 ), p. 1018 Archiválva : 2016. március 4. a Wayback Machine -nél .
  2. ↑ Schiff (2008 ), p. 44.
  3. ↑ Blanchard, Devaney és Keen (2004 ), p. 38 : "Az eltolási térkép kétségtelenül a szimbolikus dinamika alapvető tárgya."
  4. ↑ Sutner (1991 ).
  5. ↑ Wolfram (2002 ), p. 1093 Archivált : 2016. február 20. a Wayback Machine -nál .
  6. ↑ 1 2 3 Toffoli & Margolus (1987 ), 12.8.2. szakasz, "Critters", pp. 132-134; Margolus (1999 ); Marotta (2005 ).
  7. ↑ 1 2 Toffoli & Margolus (1987 ), 14.5. szakasz, "Particionálási technika", pp. 150-153; Schiff (2008 ), 4.2.1. szakasz, "Cellular Automata particionálása", pp. 115-116.
  8. ↑ Toffoli & Margolus (1987 ), 12. fejezet, "The Margolus Neighborhood", pp. 119-138.
  9. ↑ Toffoli (1977 )
  10. ↑ Hertling (1998 )
  11. ↑ Morita (1995 )
  12. ↑ Kari (2005 ).

Irodalom