Småkryp

"Critters" ( eng.  Critters ) - en blockcellulär automat som uppvisar beteende som liknar Conways spel "Life" ; i synnerhet är det Turing komplett [1] [2] . Den beskrevs först av Tommaso Toffoli ( italien. Tommaso Toffoli ) och Norman Margolus ( eng. Norman Margolus ) 1987, såväl som några andra reversibla cellulära automater [3] .   

Definition

"Critters" definieras på ett kvadratiskt gitter , tvådimensionellt och oändligt. Liksom i "Livet" är varje cell vid varje given tidpunkt i ett av två tillstånd: levande eller död. Samtidigt är Critters en blockcellulär automat som använder Margolus-kvarteret . Detta innebär att rutnätet vid varje steg är uppdelat i 2 × 2 block, som vart och ett uppdateras separat från de andra. Samtidigt, efter varje steg, ändras uppdelningen i block: de skiftas av en cell horisontellt och vertikalt; sålunda hamnar alla fyra cellerna i ett block i olika block i nästa steg [3] .

Övergångsfunktionen för Critters beror på antalet levande celler i blocket: om det finns två av dem ändras inte blocket; om de är noll, ett eller fyra, så är tillståndet för varje blockcell omvänt. I fallet med tre levande celler sker transformationen i två steg: varje cells tillstånd vänds och hela blocket roteras 180°. Eftersom antalet levande celler i alla fall ändras till antalet döda, och operationerna för var och en av antalet celler är reversibla separat, definierar dessa regler en reversibel cellulär automat [3] .

En alternativ version av övergångsfunktionen vänder endast tillstånden i block med två levande celler, och roterar även alla block med tre levande celler i udda steg och med en i jämna steg. Denna version skiljer sig från standardversionen genom att den inte ändrar antalet levande celler, och samtidigt har en liknande[ hur? ] dynamiskt beteende [2] .

Beteende

Som för alla reversibla cellulära apparater, om ett slumpmässigt tillstånd väljs som initialtillstånd för Critters, kommer tillståndet att förbli oordnat i evolutionsprocessen [1] [3] . Men om du börjar med ett litet antal slumpmässiga celler inom det större området av döda celler, kommer många små mönster, liknande glidflygplanet från Game of Life, att spridas från den centrala regionen och interagera på komplexa sätt [1] [2 ] [3] . Generellt sett tillåter Critters komplexa rymdskepp och oscillatorer med ett oändligt antal olika perioder [2] .

Det finns en obevisad hypotes att när man väljer periodiska randvillkor (det vill säga när man limmar kanterna på ett rektangulärt fält, vilket resulterar i en torus ), har initialpositioner med ett antal levande celler tillräckligt små jämfört med fältets storlek en hög sannolikhet att leda till ett tillstånd där ett glidflygplan vandrar slumpmässigt över ett fält av oscillerande oordnade celler [4] .

I Game of Life kan rymdskeppskollisioner resultera i ömsesidig förintelse, en stabil konfiguration eller en oscillator , vilket är omöjligt för en reversibel cellulär automat. Istället bör varje kollision resultera i minst ett rymdskepp [1] [4] , medan en symmetrisk kollision mellan två rymdskepp ger en symmetrisk uppsättning av två eller flera rymdskepp [1] . Om du beräknar det initiala tillståndet så att kollisionsplatserna är korrekta, kan du i Critters simulera en biljarddator på glidflygplan och, liksom spelet Livet, bevisa Turing fullständighet [1] .

Trots beteendets komplexitet finns det några bevarandelagar i Critters och det finns olika symmetrier . Till exempel ändras inte pariteten för antalet levande celler längs vissa diagonaler. Dessutom, om den initiala konfigurationen har ett ändligt antal levande celler, efter ett jämnt antal steg, är antalet levande celler detsamma (och efter ett udda antal steg får antalet döda celler samma värde ) [1] . Till skillnad från många av de reversibla cellulära automater som utforskats av Toffoli och Margolus, förvandlas inte "djur" till sig själva när tidens riktning vänds; emellertid förvandlas de till sig själva samtidigt som de vänder om tidens riktning och ersätter varje tillstånd med dess motsats [3] .

Anteckningar

1. ↑ 1 2 3 4 5 6 7 Margolus, Norman (1999), Crystalline Computation, i Hey, Anthony JG, Feynman and Computation , Perseus Books, sid. 267–305  .
2. ↑ 1 2 3 4 Marotta, Sebastian M. (2005), Living in Critters' world , Revista Ciências Exatas e Naturais vol 7 (1) , < http://web01.unicentro.br/revistas/index.php/RECEN /article/viewFile/385/537 > . Hämtad 29 september 2017. Arkiverad 19 mars 2012 på Wayback Machine . 
3. ↑ 1 2 3 4 5 6 Toffoli, Tommaso & Margolus, Norman (1991), 12.8.2 Critters, Cellular Automata Machines , Moscow: Mir, sid. 132–134, ISBN 5-03-001619-8  .
4. ↑ 1 2 Virgo, Nathaniel & Ikegami, Takashi (juli 2014), Det kan bara finnas en: Reversible cellular automata and the conservation of genki , Artificiellt liv 14: Proceedings of the Fourteenth International Conference on the Synthesis and Simulation of Living Systems , The MIT Press , DOI 10.7551/978-0-262-32621-6-ch084  .