Reverzibilní celulární automat

Reverzibilní celulární automat  je celulární automat , ve kterém má každý stav jednoho předchůdce. Jde tedy o pravidelnou mřížku buněk, z nichž stav každé je převzat z konečné množiny stavů, a pravidlo pro současnou aktualizaci stavů buněk na základě stavů jejích sousedů. Podmínkou vratnosti je, že předchozí stav libovolné buňky lze určit se znalostí aktualizovaných stavů všech buněk v mřížce. Po čase reverzace se získá další reverzibilní celulární automat, možná s mnohem většími sousedstvími, ale také s pravidlem pro určení budoucího stavu buňky na základě aktuálních stavů jejích sousedů.

Je známo několik metod pro definování reverzibilních celulárních automatů, včetně blokových celulárních automatů , ve kterých je každý blok aktualizován nezávisle na ostatních, a celulárních automatů druhého řádu , ve kterých je pravidlo aktualizace buňky určeno dvěma předchozími stavy automatu. Navíc, pokud je automat specifikován pomocí tabulky pravidel, problém kontroly jeho reverzibility je pro jednorozměrný celulární automat řešitelný, ale v obecném případě neřešitelný .

Reverzibilní celulární automaty definují přirozený model pro reverzibilní výpočty  , technologii, která umožňuje vytvářet výpočetní zařízení s velmi nízkou spotřebou energie. Kvantové buněčné automaty , které umožňují provádět výpočty pomocí principů kvantové mechaniky , jsou často považovány za reverzibilní. Navíc mnohé modely z fyziky, jako je pohyb molekul ideálního plynu nebo Isingův model umístění magnetických nábojů, jsou přirozeně reverzibilní a jsou modelovány reverzibilními buněčnými automaty.

Vlastnosti inherentní reverzibilním celulárním automatům lze použít ke studiu automatů, které jsou nevratné, ale mají atraktor  , podmnožinu stavů, ke kterým náhodné počáteční stavy konvergují. Jak píše Stephen Wolfram , „když se přiblíží k atraktoru, jakýkoli systém, dokonce i nevratný, vykazuje některé vlastnosti blízké reverzibilitě“ [1] .

Příklady

Elementární celulární automaty

Nejjednodušší buněčné automaty mají jednorozměrné pole buněk, z nichž každá obsahuje 0 nebo 1, zatímco okolí buňky se skládá ze sebe samé a jednoho souseda na každé straně; takovéto buněčné automaty se nazývají elementární [2] . Pokud přechodová funkce nikdy nemění stav buňky, vždy jej obrátí, nahradí stavem svého souseda (vždy stejný, vlevo nebo vpravo), nebo použije kombinaci posledních dvou operací, pak je takový elementární buněčný automat reverzibilní. . Přes svou jednoduchost hraje přechodová funkce, která přiřazuje každé buňce hodnotu jejího souseda, důležitou roli v symbolické dynamice , kde je známá jako operátor posunu [3] .

Elementární buněčné automaty jsou nevratné, kromě výše zmíněných triviálních případů, kdy je každá buňka určena stavem pouze jednoho ze svých sousedů. Pravidlo 90 se však blíží reverzibilnímu , ve kterém budoucí stav každé buňky je modulo 2 součet (také známý jako XOR ) aktuálních stavů  jejích dvou sousedů. Ačkoli je pravidlo 90 nevratné, každá z jeho konfigurací má přesně čtyři předchůdce a pravidlo 90 je také lokálně reverzibilní , to znamená, že jakákoli sekvence po sobě jdoucích stavů má alespoň jednoho předchůdce [4] .

Další jednorozměrné příklady

Trochu složitější příklad získáme takto: nechť je stav každé buňky uspořádaný pár ( l , r ) a přechodová funkce vezme levou stranu nového stavu od souseda zleva a pravou stranu právo. V tomto případě předpokládáme, že levá a pravá část jsou převzaty ze dvou různých konečných množin možných hodnot. Příklad je uveden na obrázku na začátku článku: levá strana stavu je tvar tvaru a pravá strana je jeho barva. Takový automat je invertibilní, protože můžeme vzít levou stranu předchozího stavu buňky napravo a pravou stranu nalevo.

Další příklad reverzibilního jednorozměrného buněčného automatu provádí násobení 2 nebo 5 v desítkové soustavě . Každá číslice v takovém násobení závisí pouze na dvou předchozích číslicích, a proto je okolí, které určuje další hodnotu, konečné, což je pro celulární automat nezbytné. Obecně řečeno, násobení nebo dělení čísla v pozičním zápisu přirozeným číslem n je specifikováno celulárním automatem právě tehdy, když jsou všechna prvočinitele n v základu číselné soustavy. Takový automat je jednorozměrný a reverzibilní, protože jej lze dělit nebo násobit stejným číslem. A například násobení 3 v desítkovém zápisu není určeno celulárním automatem, protože k přenosu může dojít prostřednictvím libovolně velkého počtu číslic: při násobení 333334*3=1000002 dojde k přenosu prostřednictvím 5 číslic [5] .

Zvířátka

Hra o život , jeden ze známějších celulárních automatů, není reverzibilní: mnoho konfigurací například zanikne. Obsahuje také Gardens of Eden  , konfigurace bez předchůdců. Místo toho Tommaso Toffoli a Norman Margolus vynalezli Critters,  reverzibilní buněčný automat s dynamickým chováním podobně jako Life [6] .

"Critters" je blokový celulární automat , ve kterém jsou buňky rozděleny do 2 × 2 bloků, které jsou aktualizovány odděleně od ostatních. Zároveň se po každém kroku změní rozdělení na bloky: posunou se o jednu buňku horizontálně i vertikálně. Funkce Critters transition obrátí stav každé buňky, pokud počet živých buněk v bloku nejsou dvě, a otočí celý blok o 180°, pokud je tento počet tři. Vzhledem k tomu, že počet živých buněk se mění na počet mrtvých a přechodové funkce jsou reverzibilní pro každou hodnotu počtu buněk, je takový buněčný automat reverzibilní na každém bloku, a proto je reverzibilní jako celek [6] .

Pokud začnete s malým počtem náhodných buněk uvnitř větší oblasti mrtvých buněk, pak se z centrální oblasti rozšíří mnoho malých vzorů, jako je kluzák ze Hry o život, a budou interagovat složitým způsobem. Critters zároveň umožňují složité vesmírné lodě a oscilátory s nekonečným počtem různých period [6] .

Konstrukce

Je známo několik obecných metod pro konstrukci reverzibilních celulárních automatů.

Blokovat celulární automaty

Blokový celulární automat  je celulární automat, jehož buňky jsou rozděleny do stejných bloků a přechodová funkce je aplikována na každý blok samostatně. Typicky takový automat používá postupně několik oddílů do bloků [7] . Typickým příkladem takového schématu je okolí Margolus , ve kterém jsou buňky čtvercové mřížky rozděleny na 2 × 2 bloky vertikálními a horizontálními čarami a po každém kroku je rozdělení na bloky posunuto o jednu buňku horizontálně a vertikálně. ; tak všechny čtyři buňky libovolného bloku v dalším kroku skončí v různých blocích [8] . Výše diskutovaná „zvířátka“využívají sousedství Margolus.

Aby byl blokový celulární automat reverzibilní, je nutné a postačující, aby přechodová funkce na každém bloku byla reverzibilní, což umožňuje kontrolovat reverzibilitu blokového celulárního automatu pomocí vyčerpávajícího výčtu . Inverzní celulární automat je zároveň i blokovým automatem se stejnou strukturou rozdělení do bloků, ale s funkcí inverzního přechodu [7] .

Simulace nevratných automatů

Jakýkoli -dimenzionální buněčný automat může být zabudován do -dimenzionálního reverzibilního automatu: navíc každý stav nového automatu uchovává celou historii evoluce toho starého. Pomocí tohoto vložení Toffoli ukázal, že mnoho vlastností nevratných buněčných automatů se přenáší na vratné, například mohou být Turingovy kompletní [9] .

Nárůst rozměru v takové konstrukci není náhodný: za určitých slabých omezení (jako je neměnnost vložení vzhledem k paralelním překladům ) je dokázáno, že jakékoli vložení celulárního automatu s „ rajskou zahradou “ je, konfigurace bez předchůdců, do reverzibilního celulárního automatu musí zvětšit rozměr [10] .

Avšak za přítomnosti klidových stavů ( anglicky  quiescent States ), tedy stavů, které se nemění, za předpokladu, že se nemění ani sousední státy[ jak? ] , je možné modelovat finální konfiguraci celulárního automatu v blokovém reverzibilním celulárním automatu stejné dimenze [11] . Informace, které měly být ztraceny v dalším kroku, jsou místo toho uloženy v nekonečné oblasti buněk v klidu. Čas potřebný k simulaci části konfigurace je přitom úměrný její velikosti. Přesto taková konstrukce umožňuje prokázat existenci reverzibilního jednorozměrného Turingova kompletního buněčného automatu [12] .

Poznámky

  1. ↑ Wolfram (2002 ), str. 1018 Archivováno 4. března 2016 na Wayback Machine .
  2. ↑ Schiff (2008 ), str. 44.
  3. ↑ Blanchard, Devaney & Keen (2004 ), s. 38 : "Posunová mapa je bezpochyby základním objektem v symbolické dynamice."
  4. ↑ Sutner (1991 ).
  5. ↑ Wolfram (2002 ), str. 1093 Archivováno 20. února 2016 na Wayback Machine .
  6. ↑ 1 2 3 Toffoli & Margolus (1987 ), oddíl 12.8.2, "Critters", str. 132-134; Margolus (1999 ); Marotta (2005 ).
  7. ↑ 1 2 Toffoli & Margolus (1987 ), oddíl 14.5, "Technika dělení", str. 150-153; Schiff (2008 ), oddíl 4.2.1, "Rozdělení celulárních automatů", str. 115-116.
  8. ↑ Toffoli & Margolus (1987 ), kapitola 12, "The Margolus Neighborhood", str. 119-138.
  9. ↑ Toffoli (1977 )
  10. ↑ Hertling (1998 )
  11. ↑ Morita (1995 )
  12. ↑ Kari (2005 ).

Literatura