Critters

"Critters" ( eng.  Critters ) - en blokcellulær automat , der udviser adfærd svarende til Conways spil "Life" ; især er det Turing komplet [1] [2] . Det blev først beskrevet af Tommaso Toffoli ( italiensk Tommaso Toffoli ) og Norman Margolus ( eng. Norman Margolus ) i 1987, samt nogle andre reversible cellulære automater [3] .   

Definition

"Critters" er defineret på et kvadratisk gitter , todimensionelt og uendeligt. Som i "Livet" er hver celle på ethvert givet tidspunkt i en af ​​to tilstande: levende eller død. Samtidig er Critters en blokcellulær automat , der bruger Margolus-kvarteret . Det betyder, at gitteret ved hvert trin er opdelt i 2 × 2 blokke, som hver opdateres separat fra de andre. På samme tid, efter hvert trin, ændres opdelingen i blokke: de forskydes af en celle vandret og lodret; således ender alle fire celler i enhver blok i forskellige blokke i næste trin [3] .

Overgangsfunktionen for Critters afhænger af antallet af levende celler i blokken: hvis der er to af dem, ændres blokken ikke; hvis de er nul, en eller fire, så vendes tilstanden af ​​hver blokcelle. I tilfælde af tre levende celler sker transformationen i to trin: hver celles tilstand vendes om, og hele blokken roteres 180°. Da antallet af levende celler under alle omstændigheder ændres til antallet af døde, og operationerne for hvert af antallet af celler er reversible separat, definerer disse regler en reversibel cellulær automat [3] .

En alternativ version af overgangsfunktionen vender kun tilstandene i blokke med to levende celler og roterer også alle blokke med tre levende celler i ulige trin og med en i lige trin. Denne version adskiller sig fra standardversionen ved, at den ikke ændrer antallet af levende celler, og samtidig har en lignende[ hvordan? ] dynamisk adfærd [2] .

Adfærd

Som for ethvert reversibelt cellulært apparat, hvis en tilfældig tilstand vælges som den initiale tilstand for Critters, så vil tilstanden forblive uordnet i evolutionsprocessen [1] [3] . Men hvis du starter med et lille antal tilfældige celler inden for det større område af døde celler, så vil mange små mønstre, der ligner svæveflyet fra Game of Life, spredes fra den centrale region og interagere på komplekse måder [1] [2 ] [3] . Generelt tillader Critters komplekse rumskibe og oscillatorer med et uendeligt antal forskellige perioder [2] .

Der er en ubevist hypotese, at når man vælger periodiske grænsebetingelser (det vil sige, når man limer kanterne af et rektangulært felt, hvilket resulterer i en torus ), har startpositioner med et antal levende celler, der er tilstrækkeligt små sammenlignet med størrelsen af ​​feltet, en høj sandsynlighed for at føre til en tilstand, hvor et svævefly vandrer tilfældigt hen over et felt af oscillerende forstyrrede celler [4] .

I Game of Life kan rumskibskollisioner resultere i gensidig udslettelse, en stabil konfiguration eller en oscillator , hvilket er umuligt for en reversibel cellulær automat. I stedet bør enhver kollision resultere i mindst ét ​​rumskib [1] [4] , mens en symmetrisk kollision mellem to rumskibe producerer et symmetrisk sæt af to eller flere rumskibe [1] . Hvis du beregner starttilstanden, så kollisionsplaceringerne er korrekte, kan du i Critters simulere en billardcomputer på svævefly og, ligesom spillet Livet, bevise Turing-fuldstændighed [1] .

På trods af kompleksiteten af ​​adfærden er der nogle bevarelseslove i Critters , og der er forskellige symmetrier . For eksempel ændres pariteten af ​​antallet af levende celler langs nogle diagonaler ikke. Derudover, hvis den oprindelige konfiguration har et endeligt antal levende celler, er antallet af levende celler det samme efter et lige antal trin (og efter et ulige antal trin får antallet af døde celler samme værdi ) [1] . I modsætning til mange af de reversible cellulære automater, der er udforsket af Toffoli og Margolus, forvandler "dyr" sig ikke til sig selv, når tidens retning er vendt; de bliver dog til sig selv, mens de samtidig vender tidens retning og erstatter hver tilstand med dens modsætning [3] .

Noter

1. ↑ 1 2 3 4 5 6 7 Margolus, Norman (1999), Crystalline Computation, i Hey, Anthony JG, Feynman and Computation , Perseus Books, s. 267-305  .
2. ↑ 1 2 3 4 Marotta, Sebastian M. (2005), Living in Critters' world , Revista Ciências Exatas e Naturais bind 7 (1) , < http://web01.unicentro.br/revistas/index.php/RECEN /article/viewFile/385/537 > . Hentet 29. september 2017. Arkiveret 19. marts 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, s. 132-134, ISBN 5-03-001619-8  .
4. ↑ 1 2 Jomfruen, Nathaniel & Ikegami, Takashi (juli 2014), Der kan kun være én: Reversible cellular automata and the conservation of genki , Artificial Life 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  .