Critters (cellulär automat)
Critters är en reversibel cellulär blockautomat med liknande dynamik som Conways Game of Life, som först beskrevs av Tommaso Toffoli och Norman Margolus 1987.
Definition
Critters definieras på ett tvådimensionellt oändligt rutnät av celler, som kan identifieras med heltalsgittret . Som i Conways Game of Life kan varje cell när som helst vara i ett av två tillstånd: levande eller död. Critters-regeln är en cellulär blockautomat som använder Margolus-kvarteret. Detta innebär att, vid varje steg, delas automatens celler upp i 2 × 2 block och varje block uppdateras oberoende av de andra blocken. 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 block fyra olika 2 × 2 block i den föregående partitionen.
Övergångsfunktionen för Critters räknar antalet levande celler i ett block, och om detta nummer är exakt två lämnar det blocket oförändrat. Om antalet levande celler är noll, en eller fyra, vänder övergångsfunktionen tillståndet för varje cell i blocket. Och slutligen, om antalet levande celler är exakt tre, vänder övergången varje tillstånd och roterar sedan hela blocket med 180°. Eftersom funktionen som kombinerar dessa operationer är inverterbar, är automaten som definieras av dessa regler en reversibel cellulär automat . Eftersom celler i kvarter bort från aktiva block kommer att pendla mellan levande och döda på varandra följande generationer, kommer hela fältet att verka "flimmer". I vissa implementeringar av Critters tas detta flimmer bort genom att invertera bilden (men inte celltillstånden) på udda generationer.
En alternativ version av övergångsfunktionen vänder tillstånden endast i block med exakt två levande celler, och i alternerande tidssteg roterar antingen blocken med tre levande celler eller blocken med en levande cell. Till skillnad från den ursprungliga övergångsfunktionen bevarar detta antalet levande celler i varje steg, men leder till likvärdigt dynamiskt beteende som den ursprungliga versionen av funktionen, utan att steget för bildinversion behövs. (Dvs de två versionerna är desamma, upp till att vända alla stater varannan generation.)
Dynamik
I Critters-regeln, som med alla reversibla cellulära automater, förblir initiala tillstånd där alla celler tar slumpmässigt valda tillstånd ostrukturerade under hela utvecklingen. Men 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. Det har förmodats, men inte bevisats, att för periodiska randvillkor (så att hela utrymmet för den cellulära automaten är ändligt) kommer initiala fält av slumpmässiga celler som är tillräckligt mindre än hela utrymmet med hög sannolikhet att leda till tillstånd där en singelflygplan följer en slumpmässig promenad genom ett fält av oscillerande skräp.
I Conways liv kan kollisioner av glidflygplan resultera i ett helt dött tillstånd, ett stabilt mönster eller en oscillator, men detta är inte möjligt i Critters. Istället, på grund av regelns reversibilitet, måste varje kollision av två eller flera segelflygplan resultera i ett mönster från vilket minst ett segelflygplan kommer ut, och när två segelflygplan kolliderar symmetriskt måste resultatet också vara en symmetrisk samling av två eller flera segelflygplan. lämnar kollisionsplatsen. Med ett initialt tillstånd som noggrant arrangerar platserna för dessa kollisioner, kan Critters-regeln fås att simulera en biljardbollsdator och därmed, liksom Life, kan den stödja universell beräkning. Critters-regeln kan också stödja mer komplexa rymdskepp med varierande hastighet samt oscillatorer med oändligt många olika perioder.
Trots komplexiteten i dess beteende, lyder Critters vissa bevarandelagar och symmetriregler . Till exempel pariteten för antalet levande celler längs vissa diagonaler i rutnätet av uppdateringsregeln och förblir oförändrad under utvecklingen av alla Critters-mönster. Dessutom, om ett mönster börjar med ett ändligt antal levande celler, kommer det efter ett jämnt antal steg att ha samma ändliga antal levande celler. (Efter udda antal steg kommer detta nummer istället att räkna de döda cellerna i mönstret.) Till skillnad från många av de andra reversibla blockcellsreglerna som studerats av Toffoli och Margolus, är Critters-regeln inte sin egen invers, så Critters-mönster lyder inte tidsomkastande symmetri; den är dock istället symmetrisk under en kombination av tidsomkastning och tillståndskomplementering.