En cellulär blockautomat är en klass av cellulära automater där gittret är uppdelat i block och övergångsfunktionen appliceras på varje block separat. Blockcellulära automater är användbara för att modellera fysiska fenomen, eftersom det ofta inte är svårt att välja övergångsfunktioner så att den resulterande cellulära automaten är reversibel och lyder de valda bevarandelagarna . [ett]
En cellulär automat är ett regelbundet gitter av celler, som var och en har ett tillstånd hämtat från en ändlig uppsättning tillstånd, och en övergångsfunktion som behövs för att uppdatera celltillstånden baserat på tillstånden hos dess grannar. Det kallas block om gittret är uppdelat i lika icke-korsande block och övergångsfunktionen använder sitt block som en grannskap till varje cell. I det här fallet måste automaten ha ett ändligt antal partitioner i block som används i sin tur: till exempel kan en partition flyttas i någon riktning. [1] [2]
Sålunda, under varje steg av automaten, appliceras övergångsfunktionen samtidigt på alla celler, som ändrar varje block oberoende av de andra, sedan ändras partitionen till nästa och steget upprepas. Detta gör det möjligt att utföra icke-triviala beräkningar med hjälp av ganska enkla övergångsfunktioner.
Det enklaste exemplet 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. [3] Denna stadsdel är uppkallad efter Norman Margolus ( engelska. Norman Margolus ), en av de första forskarna av blockcellulära automater. [ett]
Ett exempel på en blockcellulär automat som använder en Margolus-kvarter är "The Critters" . 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. [4] Emellertid uppvisar den komplext dynamiskt beteende liknande Conways Game of Life ; i synnerhet är det Turing komplett , se den relaterade artikeln för detaljer .