Vändbar cellulär automat

En reversibel cellulär automat  är en cellulär automat där varje tillstånd har en enda föregångare. Således är det ett regelbundet gitter av celler, vars tillstånd är hämtat från en ändlig uppsättning tillstånd, och en regel för att samtidigt uppdatera cellernas tillstånd baserat på tillstånden hos dess grannar. Reversibilitetsvillkoret är att det tidigare tillståndet för vilken cell som helst kan bestämmas med kännedom om de uppdaterade tillstånden för alla celler i gittret. Efter reverseringstid erhålls en annan reversibel cellulär automat, kanske med mycket större grannskap, men också med en regel för att bestämma cellens framtida tillstånd, baserat på dess grannars nuvarande tillstånd.

Flera metoder för att definiera reversibla cellulära automater är kända, inklusive blockcellulära automater , där varje block uppdateras oberoende av de andra, och andra ordningens cellulära automater , där celluppdateringsregeln bestäms av två tidigare tillstånd hos automaten. Dessutom, om automaten specificeras med hjälp av en tabell med regler, är problemet med att kontrollera dess reversibilitet lösbart för en endimensionell cellulär automat, men olösligt i det allmänna fallet.

Reversibla cellulära automater definierar en naturlig modell för reversibel datoranvändning  , en teknik som möjliggör skapandet av datorenheter med mycket låg strömförbrukning. Kvantcellulära automater , som tillåter beräkningar att göras med hjälp av kvantmekanikens principer , antas ofta vara reversibla. Dessutom är många modeller från fysiken, såsom rörelsen av ideala gasmolekyler eller Ising-modellen för placering av magnetiska laddningar, naturligt reversibla och modelleras av reversibla cellulära automater.

Egenskaperna som är inneboende i reversibla cellulära automater kan användas för att studera automater som är irreversibla men som har en attraktion  , en delmängd av tillstånd till vilka slumpmässiga initiala tillstånd konvergerar. Som Stephen Wolfram skriver , "när man närmar sig en atttraktor, uppvisar vilket system som helst, även ett irreversibelt, vissa egenskaper nära reversibilitet" [1] .

Exempel

Elementära cellulära automater

De enklaste cellulära automaterna har en endimensionell array av celler, som var och en innehåller 0 eller 1, medan cellens grannskap består av sig själv och en granne på varje sida; sådana cellulära automater kallas elementära [2] . Om övergångsfunktionen aldrig ändrar celltillståndet, alltid vänder det, ersätter det med dess grannes tillstånd (alltid samma, vänster eller höger), eller tillämpar en kombination av de två sista operationerna, då är en sådan elementär cellulär automat reversibel . Trots sin enkelhet spelar övergångsfunktionen, som tilldelar varje cell värdet av sin granne, en viktig roll i symbolisk dynamik , där den är känd som skiftoperatorn [3] .

Elementära cellulära automater är irreversibla, förutom de triviala fall som nämns ovan, där varje cell bestäms av tillståndet hos endast en av dess grannar. Emellertid är 90-regeln nära reversibel , där det framtida tillståndet för varje cell är modulo 2-summan (även känd som XOR ) av  de nuvarande tillstånden för dess två grannar. Även om regel 90 är irreversibel, har var och en av dess konfigurationer exakt fyra föregångare, och regel 90 är också lokalt reversibel , det vill säga varje sekvens av på varandra följande tillstånd har åtminstone en föregångare [4] .

Andra endimensionella exempel

Ett lite mer komplext exempel erhålls enligt följande: låt tillståndet för varje cell vara ett ordnat par ( l , r ), och övergångsfunktionen tar den vänstra sidan av det nya tillståndet från grannen till vänster och den högra sidan på den rätta. I det här fallet antar vi att de vänstra och högra delarna är hämtade från två olika ändliga uppsättningar av möjliga värden. Ett exempel visas i illustrationen i början av artikeln: den vänstra sidan av staten är formen på formen och den högra sidan är dess färg. En sådan automat är inverterbar, eftersom vi kan ta vänster sida av cellens tidigare tillstånd till höger och höger sida till vänster.

Ett annat exempel på en reversibel endimensionell cellulär automat utför multiplikation med 2 eller 5 i decimalnotation . Varje siffra i en sådan multiplikation beror bara på de två föregående siffrorna, och därför är grannskapet som bestämmer nästa värde ändligt, vilket är nödvändigt för en cellulär automat. Generellt sett specificeras multiplikationen eller divisionen av ett tal i positionsbeteckning med ett naturligt tal n av en cellulär automat om och endast om alla primtalsfaktorer för n är i talsystemets bas. En sådan automat är endimensionell och reversibel, eftersom den kan delas eller multipliceras med samma tal. Och, till exempel, multiplikation med 3 i decimalnotation specificeras inte av en cellulär automat, eftersom en överföring kan ske genom ett godtyckligt stort antal siffror: när man multiplicerar 333334*3=1000002, sker en överföring med 5 siffror [5] .

Critters

The Game of Life , en av de mer kända cellulära automaterna, är inte reversibel: till exempel dör många konfigurationer ut. Den innehåller också Edens trädgårdar  , konfigurationer utan föregångare. Istället uppfann Tommaso Toffoli och Norman Margolus Critters,  en reversibel cellulär automat med dynamiskt beteende ungefär som Life [6] .

"Critters" är en cellulär blockautomat där celler är uppdelade i 2 × 2 block som uppdateras separat från resten. Samtidigt, efter varje steg, ändras uppdelningen i block: de förskjuts av en cell horisontellt och vertikalt. Critters-övergångsfunktionen vänder tillståndet för varje cell om antalet levande celler i blocket inte är två, och roterar hela blocket med 180° om detta antal är tre. Eftersom antalet levande celler ändras till antalet döda, och övergångsfunktionerna är reversibla för varje värde av antalet celler, är en sådan cellulär automat reversibel på varje block, och är därför reversibel som helhet [6] .

Om du börjar med ett litet antal slumpmässiga celler inuti den större delen av döda celler, kommer många små mönster, som glidflygplanet från Game of Life, att spridas från den centrala regionen och interagera på komplexa sätt. Samtidigt tillåter Critters komplexa rymdskepp och oscillatorer med ett oändligt antal olika perioder [6] .

Konstruktioner

Flera allmänna metoder för att konstruera reversibla cellulära automater är kända.

Blockera cellulära automater

En cellulär blockautomat  är en cellulär automat vars celler är uppdelade i lika stora block, och övergångsfunktionen appliceras på varje block separat. Vanligtvis använder en sådan automat flera partitioner i block i sin tur [7] . Ett typiskt exempel på ett sådant schema är Margolus-kvarteret , där cellerna i ett kvadratiskt gitter är uppdelade i 2 × 2 block med vertikala och horisontella linjer, och efter varje steg skiftas uppdelningen i block med en cell horisontellt och vertikalt ; sålunda hamnar alla fyra cellerna i ett block i olika block i nästa steg [8] . "Critten" som diskuterats ovan använder grannskapet Margolus.

För att en cellulär blockautomat ska vara reversibel är det nödvändigt och tillräckligt att övergångsfunktionen på varje block är reversibel, vilket gör det möjligt att kontrollera reversibiliteten för en blockcellulär automat med hjälp av uttömmande uppräkning . Samtidigt är den omvända cellulära automaten också en blockautomat med samma struktur av partitioner i block, men den omvända övergångsfunktionen [7] .

Simulering av irreversibla automater

Vilken som helst dimensionell cellulär automat kan bäddas in i en dimensionell reversibel automat: dessutom lagrar varje tillstånd av den nya automaten hela historien om utvecklingen av den gamla. Genom att använda denna inbäddning visade Toffoli att många egenskaper hos irreversibla cellulära automater överförs till reversibla sådana, till exempel kan de vara Turing kompletta [9] .

Ökningen av dimensionen i en sådan konstruktion är inte oavsiktlig: under vissa svaga begränsningar (som invariansen av inbäddningen med avseende på parallella översättningar ), är det bevisat att varje inbäddning av en cellulär automat med " Edens trädgård ", att är, en konfiguration utan föregångare, till en reversibel cellulär automat måste öka dimensionen [10] .

Men i närvaro av vilotillstånd ( engelska  quiescent states ), det vill säga stater som inte förändras, förutsatt att grannstater inte heller förändras[ hur? ] , är det möjligt att modellera den slutliga konfigurationen av en cellulär automat i en blockreversibel cellulär automat med samma dimension [11] . Information som borde ha gått förlorad i nästa steg lagras istället i en oändlig region av celler i vila. Samtidigt är tiden som krävs för att simulera en del av konfigurationen proportionell mot dess storlek. Ändå gör en sådan konstruktion det möjligt att bevisa existensen av en reversibel endimensionell Turing-komplett cellulär automat [12] .

Anteckningar

  1. ↑ Wolfram (2002 ), sid. 1018 Arkiverad 4 mars 2016 på Wayback Machine .
  2. ↑ Schiff (2008 ), sid. 44.
  3. ↑ Blanchard, Devaney & Keen (2004 ), sid. 38 : "Skiftkartan är utan tvekan det grundläggande objektet i symbolisk dynamik."
  4. ↑ Sutner (1991 ).
  5. ↑ Wolfram (2002 ), sid. 1093 Arkiverad 20 februari 2016 på Wayback Machine .
  6. ↑ 1 2 3 Toffoli & Margolus (1987 ), avsnitt 12.8.2, "Critters", s. 132-134; Margolus (1999 ); Marotta (2005 ).
  7. ↑ 1 2 Toffoli & Margolus (1987 ), avsnitt 14.5, "Partitioneringsteknik", sid. 150-153; Schiff (2008 ), avsnitt 4.2.1, "Partitioning Cellular Automata", sid. 115-116.
  8. ↑ Toffoli & Margolus (1987 ), kapitel 12, "The Margolus Neighborhood", s. 119-138.
  9. ↑ Toffoli (1977 )
  10. ↑ Hertling (1998 )
  11. ↑ Morita (1995 )
  12. ↑ Kari (2005 ).

Litteratur