Vändbar cellulär automat

En endimensionell reversibel cellulär automat med nio tillstånd. Vid varje steg kopierar varje cell formen från sin vänstra granne och färgen från sin högra granne.

En reversibel cellulär automat är en cellulär automat där varje konfiguration har en unik föregångare. Det vill säga, det är ett vanligt rutnät av celler, som var och en innehåller ett tillstånd från en ändlig uppsättning tillstånd, med en regel för uppdatering av alla celler samtidigt baserat på tillstånden för deras grannar, så att det tidigare tillståndet för en cell före en uppdatering kan bestämmas unikt från de uppdaterade tillstånden för alla celler. Den tidsomvända dynamiken hos en reversibel cellulär automat kan alltid beskrivas av en annan cellulär automatregel, möjligen i ett mycket större område.

Flera metoder är kända för att definiera cellulära automatregler som är reversibla; dessa inkluderar med blockcellulär automat , där varje uppdatering delar upp cellerna i block och tillämpar en inverterbar funktion separat på varje block, och den andra ordningens cellulära automatmetoden, där uppdateringsregeln kombinerar tillstånd från två tidigare steg i automaten . När en automat inte definieras av någon av dessa metoder, utan istället ges som en regeltabell, är problemet med att testa om det är reversibelt lösbart för cellulära blockautomater och för endimensionella cellulära automater, men är oavgörbart för andra typer av cellulära automater.

Reversibla cellulära automater bildar en naturlig modell av reversibel datoranvändning , en teknik som kan leda till datorenheter med ultralåg effekt. Kvantcellulära automater , ett sätt att utföra beräkningar med hjälp av principerna för kvantmekanik , krävs ofta för att vara reversibla. Dessutom är många problem i fysisk modellering, såsom rörelsen av partiklar i en idealgas eller Ising-modellen för inriktning av magnetiska laddningar, naturligt reversibla och kan simuleras av reversibla cellulära automater.

Egenskaper relaterade till reversibilitet kan också användas för att studera cellulära automater som inte är reversibla på hela sitt konfigurationsutrymme, men som har en delmängd av konfigurationsutrymmet som en attraktion som alla initialt slumpmässiga konfigurationer konvergerar mot. Som Stephen Wolfram skriver, "när på en attraktion måste vilket system som helst – även om det inte har reversibla underliggande regler – i någon mening visa ungefärlig reversibilitet."

Exempel

Endimensionella automater

En cellulär automat definieras av dess celler (ofta en en- eller tvådimensionell matris), en ändlig uppsättning värden eller tillstånd som kan gå in i varje cell, en stadsdel som associerar varje cell med en ändlig uppsättning närliggande celler och en uppdatering regel enligt vilken värdena för alla celler uppdateras samtidigt som en funktion av värdena för deras närliggande celler. De enklast möjliga cellulära automaterna har en endimensionell grupp av celler, som var och en kan ha ett binärt värde (antingen 0 eller 1), där varje cell har en grannskap som endast består av den och dess två närmaste celler på vardera sidan; dessa kallas de elementära cellulära automaterna . Om uppdateringsregeln för en sådan automat gör att varje cell alltid förblir i samma tillstånd, är automaten reversibel: det tidigare tillståndet för alla celler kan återställas från deras nuvarande tillstånd, eftersom för varje cell de tidigare och nuvarande tillstånden är samma. På liknande sätt, om uppdateringsregeln får varje cell att ändra sitt tillstånd från 0 till 1 och vice versa, eller om den får en cell att kopiera tillståndet från en fast angränsande cell, eller om den får den att kopiera ett tillstånd och sedan vända dess värde, är det nödvändigtvis reversibelt. Toffoli & Margolus (1990) kallar dessa typer av reversibla cellulära automater, där tillståndet för varje cell endast beror på det tidigare tillståndet för en angränsande cell, "trivial". Trots sin enkelhet är uppdateringsregeln som får varje cell att kopiera tillståndet för en angränsande cell viktig i teorin om symbolisk dynamik , där den är känd som skiftkartan .

Lite mindre trivialt, anta att cellerna återigen bildar en endimensionell array, men att varje tillstånd är ett ordnat par ( l , r ) som består av en vänster del l och en höger del r , vardera dragna från en ändlig uppsättning möjliga värden. Definiera en övergångsfunktion som ställer in den vänstra delen av en cell till att vara den vänstra delen av dess vänstra granne och den högra delen av en cell till den högra delen av dess högra granne. Det vill säga, om den vänstra grannens tillstånd är $(a, b)$ och den högra grannens tillstånd är $(c, d)$ , är det nya tillståndet för en cell resultatet av att kombinera dessa tillstånd med en parvis operation $\times$ definierad av ekvationen $(a, b) \times (c, d) = (a, d)$ . Ett exempel på denna konstruktion ges i illustrationen, där den vänstra delen representeras grafiskt som en form och den högra delen representeras som en färg; i det här exemplet uppdateras varje cell med formen på dess vänstra granne och färgen på dess högra granne. Sedan är denna automat reversibel: värdena på vänster sida av varje par migrerar åt höger och värdena på höger sida migrerar åt vänster, så det tidigare tillståndet för varje cell kan återställas genom att leta efter dessa värden i angränsande celler. Operationen $\times$ som används för att kombinera tillståndspar i denna automat bildar en algebraisk struktur som kallas ett rektangulärt band .

Multiplikation av decimaltal med två eller fem kan utföras av en endimensionell reversibel cellulär automat med tio tillstånd per cell (de tio decimalsiffrorna). Varje siffra i produkten beror endast på ett område med två siffror i det givna numret: siffran i samma position och siffran en position till höger. Mer allmänt är multiplikation eller division av dubbelt oändliga siffror i valfri radix $b$ , med en multiplikator eller divisor $x$ vars alla primfaktorer också är primtalsfaktorer av $b$ , en operation som bildar en cellulär automat eftersom den bara beror på ett begränsat tal av närliggande siffror och är reversibel på grund av förekomsten av multiplikativa inverser . Multiplikation med andra värden (till exempel multiplikation av decimaltal med tre) förblir reversibel, men definierar inte en cellulär automat, eftersom det inte finns någon fast gräns för antalet siffror i det initiala värdet som behövs för att bestämma en enstaka siffra i resultatet.

Det finns inga icke-triviala reversibla elementära cellulära automater. En nästan-miss tillhandahålls dock av regel 90 och andra elementära cellulära automater baserade på den exklusiva eller funktionen. I regel 90 är tillståndet för varje cell det exklusiva eller tidigare tillståndet för dess två grannar. Denna användning av den exklusiva eller gör övergångsregeln lokalt inverterbar, i den meningen att varje sammanhängande följd av tillstånd kan genereras av denna regel. Regel 90 är inte en reversibel cellulär automatregel, för i regel 90 har varje tilldelning av tillstånd till den fullständiga uppsättningen av celler exakt fyra möjliga föregångare, medan reversibla regler krävs för att ha exakt en föregångare per konfiguration.

Critters regel

Glider flyr från en central slumpmässig fröregion i Critters block cellulär automatregel .

Conways Game of Life , en av de mest kända cellulära automatreglerna, är inte reversibel: till exempel har den många mönster som dör ut helt, så konfigurationen där alla celler är döda har många föregångare, och den har också Edens trädgård mönster utan föregångare. Men en annan regel som kallas "Critters" av dess uppfinnare, Tommaso Toffoli och Norman Margolus , är reversibel och har liknande dynamiskt beteende som Life.

Critters-regeln är en cellulär blockautomat där, vid varje steg, cellerna i automaten är uppdelade i 2×2 block och varje block uppdateras oberoende av de andra blocken. Dess övergångsfunktion vänder tillståndet för varje cell i ett block som inte har exakt två levande celler, och roterar dessutom med 180° block med exakt tre levande celler. Eftersom denna funktion är inverterbar är automaten som definieras av dessa regler en reversibel cellulär automat.

När man börjar med ett mindre fält av slumpmässiga celler centrerat inom ett större område av döda celler, flyr många små mönster som liknar Livets glidflygplan från det centrala slumpmässiga området och interagerar med varandra. Critters-regeln kan också stödja mer komplexa rymdskepp med varierande hastighet samt oscillatorer med oändligt många olika perioder.

Konstruktioner

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

Blockera cellulära automater

Margolus-kvarteret för blockcellulära automater. Uppdelningen av cellerna växlar mellan uppsättningen av 2 × 2 block som indikeras av de heldragna blå linjerna, och uppsättningen av block som indikeras av de streckade röda linjerna.

En cellulär blockautomat är en automat där, i varje tidssteg, automatens celler är uppdelade i kongruenta delmängder (kallade block), och samma transformation tillämpas oberoende av varje block. Vanligtvis kommer en sådan automat att använda mer än en partition i block och kommer att rotera mellan dessa partitioner vid olika tidssteg i systemet. I en ofta använd form av denna design, kallad Margolus-kvarteret, bildar automatens celler ett kvadratiskt rutnät och delas upp i större 2 × 2 kvadratiska block vid varje steg. Mitten av ett block vid ett tidssteg blir hörnet av fyra block vid nästa tidssteg, och vice versa; på detta sätt tillhör de fyra cellerna i varje 2 × 2 fyra olika 2 × 2 rutor i föregående partition. Critters-regeln som diskuterats ovan är ett exempel på denna typ av automat.

Att designa reversibla regler för blockcellulära automater och bestämma om en given regel är reversibel är lätt: för att en blockcellulär automat ska vara reversibel är det nödvändigt och tillräckligt att transformationen som tillämpas på de individuella blocken vid varje steg av automaten i sig själv är reversibel . När en blockcellulär automat är reversibel kan den tidsomvända versionen av dess dynamik också beskrivas som en blockcellulär automat med samma blockstruktur, med en tidsomvänd sekvens av partitioner av celler i block, och med övergångsfunktionen för varje block är den inversa funktionen av den ursprungliga regeln.

Simulering av irreversibla automater

Toffoli (1977) visade hur man bäddar in en irreversibel $d$ -dimensionell cellulär automatregel i en reversibel $(d + 1)$ -dimensionell regel. Varje $d$ -dimensionell del av den nya reversibla regeln simulerar ett enda tidssteg av den ursprungliga regeln. På detta sätt visade Toffoli att många funktioner hos irreversibla cellulära automater, såsom förmågan att simulera godtyckliga Turing-maskiner , också kunde utvidgas till reversibla cellulära automater.

Som Toffoli förmodade och Hertling (1998) bevisade, är ökningen i dimension som uppstår genom Toffolis metod en nödvändig betalning för dess allmänhet: under milda antaganden (som inbäddningens translations-invarians), varje inbäddning av en cellulär automat som har en Garden of Eden till en reversibel cellulär automat måste öka dimensionen.

Morita (1995) beskriver en annan typ av simulering som inte följer Hertlings antaganden och som inte ändrar dimensionen. Moritas metod kan simulera de ändliga konfigurationerna av alla irreversibla automater där det finns ett "vilande" eller "dött" tillstånd, så att om en cell och alla dess grannar är vilande så förblir cellen vilande i nästa steg. Simuleringen använder en reversibel cellulär blockautomat av samma dimension som den ursprungliga irreversibla automaten. Informationen som skulle förstöras av den simulerade automatens irreversibla steg skickas istället bort från konfigurationen till den simulerande automatens oändliga viloregion. Denna simulering uppdaterar inte alla celler i den simulerade automaten samtidigt; snarare är tiden för att simulera ett enstaka steg proportionell mot storleken på den konfiguration som simuleras. Ändå bevarar simuleringen exakt beteendet hos den simulerade automaten, som om alla dess celler uppdaterades samtidigt. Med denna metod är det möjligt att visa att även endimensionella reversibla cellulära automater är kapabla till universell beräkning.

Andra ordningens cellulära automater

De tidigare cellerna som påverkar tillståndet för en cell vid tidpunkten

t

i en andra ordningens cellulär automat

Regel 18 endimensionell cellulär automat (vänster) och andra ordningens cellulära automat härledd från den (höger). Varje rad i bilden visar en konfiguration av automaten, med tiden som går nedåt.

Den andra ordningens cellulära automattekniken är en metod för att omvandla vilken cellulär automat som helst till en reversibel cellulär automat, uppfunnen av Edward Fredkin och först publicerad av flera andra författare 1984. I denna teknik, tillståndet för varje cell i automaten vid tidpunkten $t$ är en funktion både av dess grannskap vid tidpunkten $t - 1$ och av dess eget tillstånd vid tidpunkten $t - 2$ . Specifikt mappar övergångsfunktionen för automaten varje grannskap vid tidpunkten $t - 1$ till en permutation på uppsättningen av tillstånd, och applicerar sedan den permutationen på tillståndet vid tidpunkten $t - 2$ . Den omvända dynamiken hos automaten kan beräknas genom att mappa varje grannskap till den omvända permutationen och fortsätta på samma sätt.

I fallet med automater med binärt värderade tillstånd (noll eller ett) finns det bara två möjliga permutationer på tillstånden (identitetspermutationen och permutationen som byter ut de två tillstånden), som själva kan representeras som exklusiva eller av en tillstånd med ett binärt värde. På detta sätt kan vilken konventionell tvåvärdig cellulär automat som helst konverteras till en andra ordningens cellulär automatregel genom att använda den konventionella automatens övergångsfunktion på tillstånden vid tidpunkten t − 1 , och sedan beräkna den exklusiva $eller av$ dessa tillstånd med tillstånden vid tidpunkten $t - 2$ för att bestämma tillstånden vid tidpunkten $t$ . Beteendet hos den reversibla cellulära automaten som bestäms på detta sätt kanske inte har någon likhet med beteendet hos den cellulära automaten från vilken den definierades.

Alla andra ordningens automater kan omvandlas till en konventionell cellulär automat, i vilken övergångsfunktionen endast beror på det enda föregående tidssteget, genom att kombinera par av tillstånd från på varandra följande tidssteg av andra ordningens automat till enstaka tillstånd av en konventionell cellulär automat.

Bevarat landskap

En endimensionell cellulär automat hittad av Patt (1971) använder en stadsdel som består av fyra sammanhängande celler. I den här automaten vänder en cell sitt tillstånd när den upptar "?" position i mönstret "0?10". Inga två sådana mönster kan överlappa varandra, så samma "landskap" som omger den vända cellen fortsätter att finnas efter övergången. I nästa steg, cellen i samma "?" positionen vänds igen, tillbaka till sitt ursprungliga tillstånd. Därför är denna automat sin egen invers och är reversibel. Patt utförde en brute force sökning av alla två-tillstånd endimensionella cellulära automater med små grannskap; denna sökning ledde till upptäckten av denna automat, och visade att det var den enklaste möjliga icke-triviala endimensionella tvåtillståndsreversibla cellulära automaten. Det finns inga icke-triviala reversibla tvåtillståndsautomater med trecellskvarter, och alla tvåtillståndsreversibla automater med fyrcellskvarter är enkla varianter på Patts automat.

Patts automat kan ses i efterhand som ett exempel på tekniken "konserverat landskap" för att designa reversibla cellulära automater. I denna teknik triggas en förändring av en cells tillstånd av ett mönster bland en uppsättning grannar som inte själva ändrar tillstånd. På detta sätt kan existensen av samma mönster användas för att trigga den omvända förändringen i automatens tidsomvända dynamik. Patts automat har mycket enkel dynamik (alla cykliska sekvenser av konfigurationer har längd två), men automater som använder samma bevarade landskapsteknik med mer än ett utlösande mönster är kapabla till mer komplext beteende. I synnerhet kan de simulera vilken andra ordningens cellulär automat som helst.

SALT-modellen av Miller & Fredkin (2005) är ett specialfall av tekniken för bevarat landskap. I denna modell är cellerna i ett heltalsrutnät uppdelade i jämna och udda delmängder. I varje tidssteg byts vissa par av celler av en paritet, baserat på konfigurationen av närliggande celler av den andra pariteten. Regler som använder den här modellen kan simulera biljardbollsdatorn eller stödja långa strängar av levande celler som kan röra sig i många olika hastigheter eller vibrera vid många olika frekvenser.

Teori

En cellulär automat består av en array av celler, som var och en har ett ändligt antal möjliga tillstånd , tillsammans med en regel för uppdatering av alla celler samtidigt endast baserat på tillstånden för angränsande celler. En konfiguration av en cellulär automat är en tilldelning av ett tillstånd till varje cell i automaten; uppdateringsregeln för en cellulär automat bildar en funktion från konfigurationer till konfigurationer, med kravet att det uppdaterade värdet för en cell endast beror på någon ändlig grannskap av cellen, och att funktionen är invariant under översättningar av inmatningsmatrisen.

Med dessa definitioner är en cellulär automat reversibel när den uppfyller något av följande villkor, som alla är matematiskt likvärdiga med varandra:

Varje konfiguration av automaten har en unik föregångare som mappas till den av uppdateringsregeln.
Uppdateringsregeln för automaten är en bijektion ; det vill säga en funktion som är både en-till-en och på .
Uppdateringsregeln är en injektiv funktion , det vill säga det finns inga två konfigurationer som båda mappar till samma gemensamma konfiguration. Detta tillstånd antyds uppenbarligen av antagandet att uppdateringsregeln är en bijektion. I den andra riktningen Edens trädgårdssats för cellulära automater att varje injektiv uppdateringsregel är bijektiv.
Den tidsomvända dynamiken hos automaten kan beskrivas av en annan cellulär automat. Uppenbarligen måste uppdateringsregeln vara bijektiv för att detta ska vara möjligt. I den andra riktningen, om uppdateringsregeln är bijektiv, har den en invers funktion som också är bijektiv. Denna omvända funktion måste vara en cellulär automatregel. Beviset för detta faktum använder Curtis-Hedlund-Lyndon-satsen , en topologisk karakterisering av cellulära automatregler som de translations-invarianta funktionerna som är kontinuerliga med avseende på Cantor-topologin på konfigurationsutrymmet.
Automatens uppdateringsregel är en automorfism av det dynamiska skiftsystemet som definieras av tillståndsutrymmet och översättningarna av cellernas gitter. Det vill säga att det är en homeomorfism som pendlar med skiftkartan, som Curtis–Hedlund–Lyndon-satsen antyder.

Di Gregorio & Trautteur (1975) analyserar flera alternativa definitioner av reversibilitet för cellulära automater. De flesta av dessa visar sig vara likvärdiga antingen med injektivitet eller surjektivitet hos automatens övergångsfunktion; men det finns ytterligare ett alternativ som inte matchar någon av dessa två definitioner. Det gäller automater som Livets spel som har ett vilande eller dött tillstånd. I en sådan automat kan man definiera en konfiguration som "ändlig" om den bara har ändligt många icke-vilande celler, och man kan betrakta den klass av automater för vilka varje ändlig konfiguration har minst en ändlig föregångare. Denna klass visar sig vara skild från både surjektiva och injektiva automater, och i en del efterföljande forskning har automater med denna egenskap kallats invertible finita automata .

Testar reversibilitet

Det visades först av Amoroso & Patt (1972) att problemet med att testa reversibiliteten hos en given endimensionell cellulär automat har en algoritmisk lösning. Alternativa algoritmer baserade på automatteori och de Bruijn-grafer gavs av Culik (1987) respektive Sutner (1991) .

Culik börjar med observationen att en cellulär automat har en injektiv övergångsfunktion om och endast om övergångsfunktionen är injektiv på de delmängder av konfigurationer som är periodiska (upprepar samma delsträng oändligt ofta i båda riktningarna). Han definierar en icke-deterministisk finita-tillståndsgivare som utför övergångsregeln för automaten på periodiska strängar. Denna omvandlare fungerar genom att komma ihåg närområdet för automaten i början av strängen och gå in i ett accepterande tillstånd när det grannskapet sammanlänkade med slutet av ingången skulle göra att dess icke-deterministiskt valda övergångar blir korrekta. Culik byter sedan ingången och utgången på givaren. Givaren som resulterar från detta byte simulerar den inversa dynamiken hos den givna automaten. Slutligen använder Culik tidigare kända algoritmer för att testa om den resulterande utbytta givaren mappar varje ingång till en enda utgång.
Sutner definierar en riktad graf (en typ av de Bruijn-graf ) där varje vertex representerar ett par tilldelningar av tillstånd för cellerna i en sammanhängande sekvens av celler. Längden på denna sekvens väljs till att vara en mindre än kvartersstorleken för automaten. En kant i Sutners graf representerar ett par sekvenser av celler som överlappar i alla utom en cell, så att föreningen av sekvenserna är ett helt område i den cellulära automaten. Varje sådan kant riktas från den överlappande delsekvensen till vänster till delsekvensen till höger. Kanter inkluderas endast i grafen när de representerar kompatibla tillståndstilldelningar på de överlappande delarna av deras cellsekvenser, och när automatregeln (tillämpad på grannskapet som bestäms av den potentiella kanten) skulle ge samma resultat för båda tilldelningarna av tillstånd. Genom att utföra en linjär-tidsstark anslutningsanalys av denna graf är det möjligt att bestämma vilka av dess hörn som hör till cykler. Övergångsregeln är icke-injektiv om och endast om denna graf innehåller en riktad cykel där åtminstone en vertex har två olika tillståndstilldelningar.

Dessa metoder tar polynomtid , proportionell mot kvadraten på storleken på tillståndsövergångstabellen för inmatningsautomaten. En relaterad algoritm av Hillman (1991) bestämmer om en given regel är surjektiv när den tillämpas på ändliga längder av celler med periodiska randvillkor, och i så fall för vilka längder.

För en blockcellulär automat är det också enkelt att testa reversibilitet: automaten är reversibel om och endast om övergångsfunktionen på automatens block är inverterbar, och i det här fallet har den omvända automaten samma blockstruktur som den omvända övergångsfunktionen.

Men för cellulära automater med andra grannskap i två eller flera dimensioner är problemet med att testa reversibilitet oavgörbart , vilket innebär att det inte kan existera en algoritm som alltid stannar och alltid svarar på problemet korrekt. Beviset för detta faktum av Kari (1990) är baserat på den tidigare kända obestämbarheten av plattsättning av planet med Wang-plattor , uppsättningar av fyrkantiga plattor med markeringar på sina kanter som begränsar vilka par av plattor som kan passa kant i kant. Kari definierar en cellulär automat från en uppsättning Wang-brickor, så att automaten inte kan vara injektiv om och bara om den givna brickuppsättningen kan belägga hela planet. Hans konstruktion använder von Neumann-kvarteret och celler med ett stort antal stater. I samma artikel visade Kari också att det är obestämbart att testa om en given cellulär automatregel med två eller flera dimensioner är surjektiv (det vill säga om den har en Edens lustgård ).

Omvänd kvartersstorlek

I en endimensionell reversibel cellulär automat med $n$ tillstånd per cell, där grannskapet av en cell är ett intervall av $m$ celler, har automaten som representerar den omvända dynamiken grannskap som består av högst $n m - 1 - m + 1$ celler . Denna gräns är känd för att vara snäv för $m = 2$ : det finns reversibla cellulära automater i $n$ -tillstånd med tvåcellskvarter vars tidsomvända dynamik bildar en cellulär automat med grannskapsstorlek exakt $n - 1$ .

För varje heltal $m$ finns det bara ändligt många tvådimensionella reversibla $m$ -tillståndscellulära automater med von Neumann-kvarteret. Därför finns det en väldefinierad funktion $f (m)$ så att alla omkastningar av $m$ -tillstånd cellulära automater med von Neumann grannskapet använder en grannskap med radie som mest f ( $m) : låt$ helt enkelt $f (m)$ vara maximum, bland alla de ändligt många reversibla cellulära automaterna $i m$ -tillstånd, av den grannskapsstorlek som behövs för att representera automatens tidsomvända dynamik. Men på grund av Karis obestämbara resultat finns det ingen algoritm för att beräkna $f (m)$ och värdena för denna funktion måste växa mycket snabbt, snabbare än någon beräkningsbar funktion .

Wolframs klassificering

En välkänd klassificering av cellulära automater av Stephen Wolfram studerar deras beteende på slumpmässiga initiala förhållanden. För en reversibel cellulär automat, om den initiala konfigurationen väljs enhetligt slumpmässigt bland alla möjliga konfigurationer, fortsätter samma enhetliga slumpmässighet att gälla för alla efterföljande tillstånd. Det verkar alltså som om de flesta reversibla cellulära automater är av Wolframs klass 3: automater där nästan alla initiala konfigurationer utvecklas pseudo-slumpmässigt eller kaotiskt. Det är dock fortfarande möjligt att skilja mellan olika reversibla cellulära automater genom att analysera effekten av lokala störningar på automatens beteende. Att göra en ändring av det initiala tillståndet för en reversibel cellulär automat kan göra att ändringar i senare tillstånd bara stannar inom ett avgränsat område, sprider sig oregelbundet men obegränsat eller sprids snabbt, och Wolfram (1984) listar endimensionella reversibla cellulära automatregler uppvisar alla tre av dessa typer av beteende.

Senare arbete av Wolfram identifierar den endimensionella Rule 37R- automaten som särskilt intressant i detta avseende. När den körs på en ändlig uppsättning celler med periodiska randvillkor, med början från ett litet frö av slumpmässiga celler centrerade i ett större tomt område, tenderar det att fluktuera mellan ordnade och kaotiska tillstånd. Men med samma initiala förhållanden på en obegränsad uppsättning celler tenderar dess konfigurationer att organisera sig i flera typer av enkla rörliga partiklar.

Abstrakt algebra

Ett annat sätt att formalisera reversibla cellulära automater involverar abstrakt algebra , och denna formalisering har varit användbar för att utveckla datoriserade sökningar efter reversibla cellulära automatregler. Boykett (2004) definierar en semicentral storgrupp som en algebraisk struktur som består av en uppsättning $S$ av element och två operationer $\to$ och $\leftarrow$ på par av element, som uppfyller de två ekvationella axiomen:

för alla element $a$ , $b$ och $c$ i $S$ , $(a \to b) \leftarrow (b \to c) = b$ , och
för alla element $a$ , $b$ och $c$ i $S$ , $(a \leftarrow b) \to (b \leftarrow c) = b$ .

Detta gäller till exempel för de två operationerna där operation $\to$ returnerar sitt högra argument och operation $\leftarrow$ returnerar sitt vänstra argument.

Som Boykett hävdar, är varje endimensionell reversibel cellulär automat likvärdig med en automat i rektangulär form , där cellerna är förskjutna en halv enhet vid varje tidssteg, och där både framåt- och bakåtevolutionen av automaten har grannskap med bara två celler, cellerna en halv enhet bort i varje riktning. Om en reversibel automat har områden större än två celler, kan den simuleras av en reversibel automat med mindre grannskap och fler tillstånd per cell, där varje cell i den simulerande automaten simulerar ett sammanhängande block av celler i den simulerade automaten. De två axiomen för en semicentral storgrupp är exakt de villkor som krävs för att framåt- och bakåtövergångsfunktionerna för dessa tvåcellskvarter ska vara motsatserna till varandra. Det vill säga, varje semicentral bigroupoid definierar en reversibel cellulär automat i rektangulär form, där övergångsfunktionen för automaten använder → $-operationen$ för att kombinera de två cellerna i dess grannskap, och där ← $-operationen$ på liknande sätt definierar den omvända dynamiken hos automaten . Varje endimensionell reversibel cellulär automat är likvärdig med en i denna form.

Boykett använde denna algebraiska formulering som grund för algoritmer som uttömmande listar alla möjliga olikvärdiga reversibla cellulära automater.

Bevarandelagar

systemets bevarandelagar i designen; till exempel bör en cellulär automat som simulerar en idealisk gas bevara antalet gaspartiklar och deras totala rörelsemängd , för annars skulle den inte ge en exakt simulering. Men det har också gjorts en del forskning om de bevarandelagar som reversibla cellulära automater kan ha, oberoende av avsiktlig design. Den typiska typen av konserverad kvantitet som mäts i dessa studier tar formen av en summa, över alla sammanhängande delmängder av $k$ celler i automaten, av någon numerisk funktion av tillstånden hos cellerna i varje delmängd. En sådan kvantitet bevaras om, närhelst den tar ett ändligt värde, det värdet automatiskt förblir konstant genom varje tidssteg av automaten, och i detta fall kallas det en k:te $ordningens$ invariant av automaten.

$0$ Till exempel, återkalla den endimensionella cellulära automaten definierad som ett exempel från ett rektangulärt band , där celltillstånden är par av värden ( l , r ) dragna från uppsättningarna $L$ och $R$ med vänstervärden och högervärden, det vänstra värdet på varje cell flyttas åt höger vid varje tidssteg, och det högra värdet för varje cell flyttas åt vänster. I det här fallet, för varje vänster eller höger värde $x$ i bandet, kan man definiera en bevarad kvantitet, det totala antalet celler som har det värdet. Om det finns $λ$ vänstervärden och $ρ$ högervärden, så finns det $λ + ρ - 2$ oberoende första ordningens invarianter, och vilken första ordningens invariant som helst kan representeras som en linjär kombination av dessa fundamentala. De bevarade kvantiteterna associerade med vänstra värden flyter jämnt åt höger med konstant hastighet: det vill säga om antalet vänstra värden lika med $x$ inom någon region $C$ på linjen tar ett visst värde vid tidpunkten , kommer det att ta samma värde för det förskjutna området $C + t /2$ vid tidpunkten $t$ . På liknande sätt flyter de bevarade kvantiteterna associerade med högra värden likformigt till vänster.

Vilken endimensionell reversibel cellulär automat som helst kan placeras i rektangulär form, varefter dess övergångsregel kan inkluderas i verkan av en idempotent semicentral bigroupoid (en reversibel regel för vilka regioner av celler med ett enda tillståndsvärde ändras endast vid sina gränser) tillsammans med en permutation på uppsättningen av tillstånd. De första ordningens invarianter för det idempotenta lyftet av automatregeln (den modifierade regeln som bildas genom att utelämna permutationen) beter sig nödvändigtvis som de för ett rektangulärt band: de har en bas av invarianter som flyter antingen åt vänster eller höger med en konstant hastighet utan samspel. Första ordningens invarianter för den totala automaten är då exakt invarianterna för det idempotenta lyftet som ger lika stor vikt åt varje par av tillstånd som tillhör samma omloppsbana av permutationen. Emellertid kan permutationen av tillstånd i regeln få dessa invarianter att bete sig annorlunda än i det idempotenta lyftet, flöda ojämnt och med interaktioner.

I fysiska system ger Noethers teorem en ekvivalens mellan bevarandelagar och symmetrier i systemet. För cellulära automater gäller dock inte detta teorem direkt, eftersom istället för att styras av energi kodas automatens beteende in i dess regler, och automaten är garanterad att lyda vissa symmetrier (översättningsinvarians i både rymden och tid) oavsett eventuella bevarandelagar som den kan följa. Icke desto mindre beter sig de bevarade kvantiteterna av vissa reversibla system på samma sätt som energi i vissa avseenden. Till exempel, om olika regioner av automaten har olika medelvärden för någon konserverad kvantitet, kan automatens regler orsaka att denna kvantitet försvinner, så att fördelningen av kvantiteten blir mer enhetlig i senare tillstånd. Genom att använda dessa bevarade kvantiteter som en stand-in för energin i systemet kan det analyseras med metoder från klassisk fysik.

Ansökningar

Gallergasautomat

En gittergasautomat är en cellulär automat utformad för att simulera rörelsen av partiklar i en vätska eller en idealisk gas . I ett sådant system rör sig gaspartiklar på raka linjer med konstant hastighet, tills de genomgår elastisk kollision med andra partiklar. Gittergasautomater förenklar dessa modeller genom att endast tillåta ett konstant antal hastigheter (vanligtvis endast en hastighet och antingen fyra eller sex rörelseriktningar) och genom att förenkla de typer av kollisioner som är möjliga.

Specifikt består HPP-gittergasmodellen av partiklar som rör sig med enhetshastighet i de fyra axelparallella riktningarna. När två partiklar möts på samma linje i motsatta riktningar kolliderar de och skickas utåt från kollisionspunkten på den vinkelräta linjen. Detta system lyder bevarandelagarna för fysiska gaser och producerar simuleringar vars utseende liknar beteendet hos fysiska gaser. Det visade sig dock följa orealistiska ytterligare bevarandelagar. Till exempel bevaras den totala rörelsemängden inom en enskild linje. Likaså är skillnaderna mellan axelparallella och icke-axelparallella riktningar i denna modell (dess anisotropi) oönskat höga. FHP -gittergasmodellen förbättrar HPP-modellen genom att ha partiklar som rör sig i sex olika riktningar, i 60 graders vinklar mot varandra, istället för bara fyra riktningar. Vid en frontalkollision avleds de två utgående partiklarna i 60 graders vinklar från de två inkommande partiklarna. Trevägskollisioner är också möjliga i FHP-modellen och hanteras på ett sätt som både bevarar total fart och undviker HPP-modellens opysiska tillagda bevarandelagar.

Eftersom rörelsen av partiklarna i dessa system är reversibel, implementeras de vanligtvis med reversibla cellulära automater. I synnerhet kan både HPP- och FHP-gittergasautomaten implementeras med en cellulär automat med två tillståndsblock med användning av Margolus-kvarteret.

Ising modell

Ising -modellen används för att modellera beteendet hos magnetiska system. Den består av en rad celler, vars tillstånd representerar ett snurr , antingen uppåt eller nedåt . Systemets energi mäts av en funktion som beror på antalet angränsande cellpar som har samma spinn som varandra. Därför, om en cell har lika många grannar i de två tillstånden, kan den vända sitt eget tillstånd utan att ändra den totala energin. En sådan vändning är emellertid energibesparande endast om inga två intilliggande celler vänder samtidigt.

Cellulära automatmodeller av detta system delar upp det kvadratiska gittret i två alternerande delmängder och utför uppdateringar på en av de två delmängderna åt gången. I varje uppdatering gör varje cell som kan vända det. Detta definierar en reversibel cellulär automat som kan användas för att undersöka Ising-modellen.

Biljardbollsberäkning och lågeffektberäkning

Fredkin & Toffoli (1982) föreslog biljardbollsdatorn som en del av deras undersökningar av reversibel datoranvändning . En biljardbollsdator består av ett system av synkroniserade partiklar (biljardbollarna) som rör sig i spår och styrs av en fast uppsättning hinder. När partiklarna kolliderar med varandra eller med hindren genomgår de en elastisk kollision ungefär som riktiga biljardbollar skulle göra. Ingången till datorn kodas med hjälp av närvaron eller frånvaron av partiklar på vissa ingångsspår, och dess utdata kodas på liknande sätt med hjälp av närvaron eller frånvaron av partiklar på utmatningsspår. Själva spåren kan ses som trådar, och partiklarna som booleska signaler transporteras på dessa trådar. När en partikel träffar ett hinder reflekteras den från det. Denna reflektion kan tolkas som en förändring i riktningen av tråden som partikeln följer. Två partiklar på olika spår kan kollidera och bilda en logisk grind vid deras kollisionspunkt.

Som Margolus (1984) visade, kan biljardbollsdatorer simuleras med hjälp av en tvåtillstånds reversibel cellulär blockautomat med Margolus-området. I denna automats uppdateringsregel roterar block med exakt en levande cell 180°, block med två diagonalt motsatta levande celler roterar med 90°, och alla andra block förblir oförändrade. Dessa regler gör att isolerade levande celler beter sig som biljardbollar och rör sig på diagonala banor. Uppkopplade grupper med mer än en levande cell beter sig istället som biljarddatorns fasta hinder. I en appendix visade Margolus också att en tre-tillstånds andra ordningens cellulär automat som använder det tvådimensionella Moore-området kunde simulera biljardbollsdatorer.

Olöst problem i matematik :

Är varje tredimensionell reversibel cellulär automat lokalt reversibel?

(fler olösta problem i matematik)

En anledning att studera reversibla universella beräkningsmodeller som biljardbollsmodellen är att de teoretiskt kan leda till faktiska datorsystem som förbrukar mycket låga mängder energi. Enligt Landauers princip kräver irreversibla beräkningssteg en viss minimal mängd energi per steg, men reversibla steg kan utföras med en mängd energi per steg som är godtyckligt nära noll. Men för att utföra beräkningar med mindre energi än Landauers gräns är det inte tillräckligt bra för en cellulär automat att ha en övergångsfunktion som är globalt reversibel: vad som krävs är att den lokala beräkningen av övergångsfunktionen också görs i en vändbart sätt. Till exempel är reversibla blockcellulära automater alltid lokalt reversibla: beteendet hos varje enskilt block involverar tillämpningen av en inverterbar funktion med ändligt många ingångar och utgångar. Toffoli & Margolus (1990) var de första som frågade om varje reversibel cellulär automat har en lokalt reversibel uppdateringsregel. Kari (1996) visade att för en- och tvådimensionella automater är svaret positivt, och Durand-Lose (2001) visade att vilken reversibel cellulär automat som helst kunde simuleras av en (eventuellt annan) lokalt reversibel cellulär automat. Frågan om varje reversibel övergångsfunktion är lokalt reversibel förblir dock öppen för dimensioner högre än två.

Synkronisering

De rätlinjiga formerna som genereras av Tron-regeln

"Tron"-regeln för Toffoli och Margolus är en reversibel blockcellsregel med Margolus-kvarteret. När ett 2 × 2 block av celler alla har samma tillstånd, ändrar alla celler i blocket tillstånd; i alla andra fall förblir cellerna i blocket oförändrade. Som Toffoli och Margolus hävdar, kan utvecklingen av mönster som genereras av denna regel användas som en klocka för att synkronisera vilken annan regel som helst i Margolus-området. En cellulär automat synkroniserad på detta sätt lyder samma dynamik som standardregeln för Margolus-grannskap medan den körs på en asynkron cellulär automat .

Kryptering

Kari (1990) föreslog att man skulle använda multidimensionella reversibla cellulära automater som ett krypteringssystem . I Karis förslag skulle regeln för cellulär automat vara krypteringsnyckeln. Kryptering skulle utföras genom att köra regeln ett steg framåt, och dekryptering skulle utföras genom att köra den bakåt ett steg. Kari föreslår att ett system som detta kan användas som ett kryptosystem med publik nyckel . I princip kunde en angripare inte algoritmiskt bestämma dekrypteringsnyckeln (reverse-regeln) från en given krypteringsnyckel (forward-regel) på grund av obestämbarheten av att testa reversibilitet, så framåtregeln kunde offentliggöras utan att äventyra systemets säkerhet. Kari specificerade dock inte vilka typer av reversibel cellulär automat som skulle användas för ett sådant system, eller visade hur ett kryptosystem som använder detta tillvägagångssätt skulle kunna generera krypterings-/dekrypteringsnyckelpar.

Chai, Cao & Zhou (2005) har föreslagit ett alternativt krypteringssystem. I deras system bestämmer krypteringsnyckeln den lokala regeln för varje cell i en endimensionell cellulär automat. En andra ordningens automat baserad på den regeln körs i flera omgångar på en ingång för att omvandla den till en krypterad utgång. Reversibilitetsegenskapen hos automaten säkerställer att alla krypterade meddelanden kan dekrypteras genom att köra samma system i omvänd riktning. I detta system måste nycklar hållas hemliga, eftersom samma nyckel används både för kryptering och dekryptering.

Kvantberäkning

Kvantcellulära automater är arrayer av automater vars tillstånd och tillståndsövergångar lyder kvantdynamikens lagar . Kvantcellulära automater föreslogs som en beräkningsmodell av Feynman (1982) och formaliserades först av Watrous (1995) . Flera konkurrerande föreställningar om dessa automater är fortfarande under forskning, av vilka många kräver att de automater som är konstruerade på detta sätt är reversibla.

Fysisk universalitet

Janzing (2010) frågade om det var möjligt för en cellulär automat att vara fysiskt universell , vilket innebär att det för varje avgränsat område av automatens celler borde vara möjligt att omge den regionen med celler vars tillstånd bildar en lämplig stödställning som orsakar automat för att implementera godtycklig transformation på uppsättningar av stater inom regionen. En sådan automat måste vara reversibel, eller åtminstone lokalt injektiv, eftersom automater utan denna egenskap har Edens trädgårdsmönster, och det är inte möjligt att implementera en transformation som skapar en Edens trädgård.

Schaeffer (2015) konstruerade en reversibel cellulär automat som är fysiskt universell i denna mening. Schaeffers automat är en cellulär blockautomat med två tillstånd och Margolis-kvarteret, nära besläktad med automaten för biljardbollsmodellen och för HPP-gittergasen. Biljardbollsmodellen är dock inte fysiskt universell, eftersom den kan användas för att konstruera ogenomträngliga väggar som förhindrar att staten inom någon region kan läsas och transformeras. I Schaeffers modell sönderfaller varje mönster så småningom till partiklar som rör sig diagonalt i fyra riktningar. Således är hans automat inte Turing komplett . Schaeffer visade dock att det är möjligt att omge vilken ändlig konfiguration som helst genom byggnadsställningar som förfaller långsammare än den. Efter att konfigurationen sönderfaller till partiklar, fångar ställningen upp dessa partiklar och använder dem som input till ett system av booleska kretsar som är konstruerade i ställningen. Dessa kretsar kan användas för att beräkna godtyckliga funktioner för den initiala konfigurationen. Ställningen översätter sedan utsignalen från kretsarna tillbaka till ett system av rörliga partiklar, som konvergerar på den initiala regionen och kolliderar med varandra för att bygga en kopia av det transformerade tillståndet. På detta sätt kan Schaeffers system användas för att applicera vilken funktion som helst på vilken som helst avgränsad region av tillståndsrummet, vilket visar att denna automatregel är fysiskt universell.

Anteckningar

Amoroso, S.; Patt, YN (1972), "Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures", Journal of Computer and System Sciences , 6 (5): 448–464, doi : 10.1016/S0022-0000(72)80013- 8 , MR 0317852 .
Béal, Marie-Pierre; kartong, Olivier; Prieur, Christophe; Sakarovitch, Jacques (2003), "Squaring transducers: an efficient procedure for deciding functionality and sequentiality", Theoretical Computer Science , 292 (1): 45–63, doi : 10.1016/S0304-3975(01)00214-519 , 6462 519 , 6462 .
Blanchard, Paul; Devaney, Robert L .; Keen, Linda (2004), "Complex dynamics and symbolic dynamics", i Williams, Susan G. (red.), Symbolic Dynamics and its Applications , Proceedings of Symposia in Applied Mathematics, vol. 60, Providence, RI: American Mathematical Society, s. 37–60, doi : 10.1090/psapm/060/2078845 , MR 2078845 .
Boykett, Tim (2004), "Effektiva uttömmande listor över reversibla endimensionella cellulära automater", Theoretical Computer Science , 325 (2): 215–247, doi : 10.1016/j.tcs.2004.06.007 , MR 2086738 .
Boykett, Tim; Kari, Jarkko ; Taati, Siamak (2008), "Bevarandelagar i rektangulär CA" (PDF) , Journal of Cellular Automata , 3 (2): 115–122, MR 2394641 , arkiverad från originalet (PDF) 2015-09-30 .
Capobianco, Silvio; Toffoli, Tommaso (2011), "Kan något från Noethers teorem räddas för diskreta dynamiska system?", Proceedings of the 10th International Conference on Unconventional Computation (UC 2011), Lecture Notes in Computer Science , vol. 6714, Springer-Verlag, s. 77–88, arXiv : 1103.4785 , doi : 10.1007/978-3-642-21341-0_13 , S2CID 42541816 .
Chai, Zhenchuan; Cao, Zhenfu; Zhou, Yuan (2005), "Encryption based on reversible second-order cellular automata", Parallell and Distributed Processing and Applications (ISPA 2005 Workshops) , Lecture Notes in Computer Science , vol. 3759, Springer-Verlag, s. 350–358, doi : 10.1007/11576259_39 .
Culik, Karel, II (1987), "On invertible cellular automata" (PDF) , Complex Systems , 1 (6): 1035-1044, MR 0931401 .
Czeizler, Eugen (2004), "Om storleken på de omvända kvarteren för endimensionella reversibla cellulära automater", Theoretical Computer Science , 325 (2): 273–284, doi : 10.1016/j.tcs.2004.06.009 , MR 2086740 .
Czeizler, Eugen; Kari, Jarkko (2007), "A tight linear bound on the synchronization delay of bijective automata", Theoretical Computer Science , 380 (1–2): 23–36, doi : 10.1016/j.tcs.2007.02.052 , MR 2330639 .
Di Gregorio, S.; Trautteur, G. (1975), "On reversibility in cellular automata", Journal of Computer and System Sciences , 11 (3): 382-391, doi : 10.1016/S0022-0000(75)80059-6 , MR 0392201 .
Durand-Lose, Jérôme (2001), "Representing reversible cellular automata with reversible block cellular automata", Diskreta modeller: kombinatorik, beräkning och geometri (Paris, 2001) , Diskret matematik. Theor. Comput. Sci. Proc., AA, Maison Inform. Matematik. Diskret. (MIMD), Paris, s. 145–154, MR 1888769 .
Durand-Lose, Jérôme (2002), "Computing inside the billiard ball model", i Adamatzky, Andrew (red.), Collision-Based Computing , Springer-Verlag, s. 135–160 .
Feynman, Richard P. (1982), "Simulating physics with computers", International Journal of Theoretical Physics , 21 (6–7): 467–488, Bibcode : 1982IJTP...21..467F , doi : 10.1007/BF0265017 MR 0658311 , S2CID 124545445 .
Fredkin, Edward ; Toffoli, Tommaso (1982), "Conservative logic", International Journal of Theoretical Physics , 21 (3–4): 219–253, Bibcode : 1982IJTP ...21..219F , doi : 10.1007/BF01857727 , 52CID 627 , 52CID 37305161 . Omtryckt i Adamatzky, Andrew , ed. (2002), Collision-Based Computing , Springer-Verlag, s. 47–82 .
Fukś, Henryk (2007), "Remarks on the critical behavior of second order additive invariants in elementary cellular automata", Fundamenta Informaticae , 78 (3): 329–341, arXiv : nlin/0502037 , Bibcode : 2005nlin..... .2037F , MR 2346870 .
Hattori, Tetsuya; Takesue, Shinji (1991), "Additive conserved quantities in discrete-time lattice dynamical systems", Physica D: Nolinear Phenomena , 49 (3): 295–322, Bibcode : 1991PhyD...49..295H , doi : .101/10 0167-2789(91)90150-8 , MR 1115865 .
Hedlund, GA (1969), "Endomorphisms and automorphisms of the shift dynamical systems", Mathematical Systems Theory , 3 (4): 320–375, doi : 10.1007/BF01691062 , MR 0259881 , S2CID 7 .
Hertling, Peter (1998), "Embedding cellular automata into reversible ones", Unconventional models of computation (Auckland, 1998), Springer Series in Discrete Mathematics and Theoretical Computer Science, Springer-Verlag, s. 243–256, MR 1653663 .
Hillman, David (1991), "The structure of reversible one-dimensional cellular automata", Physica D: Nolinear Phenomena , 52 (2–3): 277–292, Bibcode : 1991PhyD...52..277H , doi : 10.1016 /0167-2789(91)90128-V , MR 1128996 .
Janzing, Dominik (2010), Finns det en fysiskt universell cellulär automat eller Hamiltonian? , arXiv : 1009.1720 , Bibcode : 2010arXiv1009.1720J .
Kari, Jarkko (1990), "Reversibility of 2D cellular automata is unecidable", Cellular automata: theory and experiment (Los Alamos, NM, 1989), Physica D: Nolinear Phenomena , 45 (1–3): 379–385, Bibcode : 1990PhyD...45..379K , doi : 10.1016/0167-2789(90)90195-U , MR 1094882 .
Kari, Jarkko (1992), "On the inverse neighborhoods of reversible cellular automata", Lindenmayer Systems: Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology , Springer-Verlag, s. 477–495, doi : 10.1007/978- 3-642-58117-5_29 , MR 1226709 .
Kari, Jarkko (1996), "Representation of reversible cellular automata with block permutations", Mathematical Systems Theory , 29 (1): 47–61, doi : 10.1007/BF01201813 , MR 1360196 , S2CID 0 319 .
Kari, Jarkko (2005), "Reversible cellular automata" (PDF) , Developments in Language Theory: 9th International Conference, DLT 2005, Palermo, Italien, 4–8 juli 2005, Proceedings , Lecture Notes in Computer Science , vol. 3572, Springer-Verlag, s. 2–23, doi : 10.1007/11505877_5 , MR 2187250 .
Kari, Jarkko (2009), "Structure of reversible cellular automata", Unconventional Computation: 8th International Conference, UC 2009, Ponta Delgada, Portugal, 7–11 september 2009, Proceedings , Lecture Notes in Computer Science , vol. 5715, Springer-Verlag, sid. 6, Bibcode : 2009LNCS.5715....6K , doi : 10.1007/978-3-642-03745-0_5 , MR 2539690 .
Margolus, Norman (1984), "Physics-like models of computation", Physica D: Nolinear Phenomena , 10 (1–2): 81–95, Bibcode : 1984PhyD...10...81M , doi : 10.1016/0167 -2789(84)90252-5 , MR 0762656 . Återtryckt i Wolfram, Stephen (1986), Theory and Applications of Cellular Automata , Advanced series on complex systems, vol. 1, World Scientific, s. 232–246 , och i Adamatzky, Andrew , ed. (2002), Collision-Based Computing , Springer-Verlag, s. 83–104 .
Margolus, Norman (1999), "Crystalline computation", i Hey, Anthony JG (red.), Feynman and Computation , Perseus Books, s. 267–305, arXiv : comp-gas/9811002 , Bibcode : 1998comp.gas.11002M .
Marotta, Sebastian M. (2005), "Living in Critters' world" , Revista Ciências Exatas e Naturais , 7 (1), arkiverad från originalet 2012-03-19 .
McIntosh, Harold V. (2009), "12. Reversible cellular automata", One Dimensional Cellular Automata , Luniver Press, s. 205–246 .
Meyer, David A. (1996), "From quantum cellular automata to quantum lattice gases", Journal of Statistical Physics , 85 (5–6): 551–574, arXiv : quant-ph/9604003 , Bibcode : 1996JSP... .85..551M , doi : 10.1007/BF02199356 , MR 1418805 , S2CID 661940 .
Miller, Daniel B.; Fredkin, Edward (2005), "Two-state, reversible, universal cellular automata in three dimensions", Proceedings of the 2nd Conference on Computing Frontiers (CF '05) , New York, NY, USA: ACM, s. 45–51 , arXiv : nlin/0501022 , doi : 10.1145/1062261.1062271 , ISBN 1-59593-019-1 , S2CID 14082792 .
Miller, Daniel B.; Fredkin, Edward (2012), Cirkulär rörelse av strängar i cellulära automater och andra överraskningar , arXiv : 1206.2060 , Bibcode : 2012arXiv1206.2060M .
Moraal, Hendrik (2000), "Graph-theoretical characterization of invertible cellular automata", Physica D: Nolinear Phenomena , 141 (1–2): 1–18, Bibcode : 2000PhyD..141....1M , doi : 10.1016 /S0167-2789(00)00020-8 , MR 1764165 .
Morita, Kenichi (1995), "Reversible simulation of one-dimensional irreversible cellular automata", Theoretical Computer Science , 148 (1): 157–163, doi : 10.1016/0304-3975(95)00038-X , MR 4347 .
Myhill, John (1963), "The converse of Moore's Garden-of-Eden theorem", Proceedings of the American Mathematical Society , 14 ( 4): 685–686, doi : 10.2307/2034301 , JSTOR 2034301 , MR 41577 . Omtryckt i Burks, Arthur W. (1970), Essays on Cellular Automata , University of Illinois Press, s. 204–205 .
Nagaj, Daniel; Wocjan, Pawel (2008), "Hamiltonian quantum cellular automata in one dimension", Physical Review A , 78 (3): 032311, arXiv : 0802.0886 , Bibcode : 2008PhRvA..78c2311N , 37.311N , 32311 , 302.0886 11 , S2CID 18879990 .
Patt, YN (1971), Injektioner av grannskapsstorlek tre och fyra på uppsättningen av konfigurationer från den oändliga endimensionella tessellationsautomaten för tvåtillståndsceller, teknisk rapport ECON-N1-P-1, Ft. Monmouth, NJ 07703 . Som citeras av Amoroso & Patt (1972) och Toffoli & Margolus (1990) .
Pomeau, Y. (1984), "Invariants in cellular automata", Journal of Physics A: Mathematical and General , 17 (8): L415–L418, Bibcode : 1984JPhA...17L.415P , doi : 10.1088/0305-447 /17/8/004 , MR 0750565 .
Richardson, D. (1972), "Tessellations with local transformations", Journal of Computer and System Sciences , 6 (5): 373–388, doi : 10.1016/S0022-0000(72)80009-6 , MR 0319678 .
Schaeffer, Luke (2015), "A physically universal cellular automaton", Proceedings of the 6th Innovations in Theoretical Computer Science Conference (ITCS 2015) , Association for Computing Machinery , s. 237–246, doi : 10.1145/2688073 . 41888073 , S4145 /2688073 . ECCC TR14-084 .
Schiff, Joel L. (2008), Cellular Automata: A Discrete View of the World , Wiley, ISBN 978-0-470-16879-0 .
Schumacher, B .; Werner, RF (2004), Reversible quantum cellular automata , arXiv : quant-ph/0405174 , Bibcode : 2004quant.ph..5174S .
Seck Tuoh Mora, Juan Carlos; Chapa Vergara, Sergio V.; Juárez Martínez, Genaro; McIntosh, Harold V. (2005), "Procedurer för att beräkna reversibla endimensionella cellulära automater" (PDF) , Physica D: Nolinear Phenomena , 202 (1–2): 134–141, Bibcode : 2005PhyD..202..134S , doi : 10.1016/j.physd.2005.01.018 , MR 2131890 .
Shepherd, DJ; Franz, T.; Werner, RF (2006), "A universally programmeable quantum cellular automaton", Physical Review Letters , 97 (2): 020502, arXiv : quant -ph/0512058 , Bibcode : 2006PhRvL..97b0502S ,0102S ,102S ,102S ,102S , 102S ,1002S ,L. 20502 , PMID 16907423 , S2CID 40900768 .
Sutner, Klaus (1991), "De Bruijn-grafer och linjära cellulära automater" (PDF) , Complex Systems , 5 : 19–30, MR 1116419 .
Takesue, Shinji (1990), "Relaxation properties of elementary reversible cellular automata", Cellular automata: theory and experiment (Los Alamos, NM, 1989), Physica D: Nolinear Phenomena , 45 (1–3): 278–284, Bibcode : 1990PhyD...45..379K , doi : 10.1016/0167-2789(90)90195-U , MR 1094882 .
Toffoli, Tommaso (1977), "Computation and construction universality of reversible cellular automata", Journal of Computer and System Sciences , 15 (2): 213–231, doi : 10.1016/S0022-0000(77)80007-X , MR 64640 .
Toffoli, Tommaso ; Margolus, Norman (1987), Cellular Automata Machines: A New Environment for Modeling , MIT Press, ISBN 9780262200608 .
Toffoli, Tommaso ; Margolus, Norman (1990), "Invertible cellular automata: a review", Physica D: Nolinear Phenomena , 45 (1–3): 229–253, Bibcode : 1990PhyD...45..229T , doi : 10.1016/0167- 2789(90)90185-R , MR 1094877 .
Vichniac, Gérard Y. (1984), "Simulating physics with cellular automata", Physica D: Nolinear Phenomena , 10 (1–2): 96–115, Bibcode : 1984PhyD...10...96V , doi : 10.1016/ 0167-2789(84)90253-7 , MR 0762657 .
Watrous, John (1995), "On one-dimensional quantum cellular automata", Proceedings of the 36th Annual Symposium on Foundations of Computer Science (Milwaukee, WI, 1995) , Los Alamitos, CA: IEEE Computer Society Press, s. 528– 537, doi : 10.1109/SFCS.1995.492583 , MR 1619103 , S2CID 7441203 .
Wolfram, Stephen (1984), "Cellular automata as models of complexity" (PDF) , Nature , 311 (5985): 419–424, Bibcode : 1984Natur.311..419W , doi : 10.1038 /31142CID3 414279a 2 .
Wolfram, Stephen (2002), A New Kind of Science , Wolfram Media, ISBN 1-57955-008-8 , MR 1920418