En blokcellulær automat er en klasse af cellulære automater , hvor gitteret er opdelt i blokke, og overgangsfunktionen anvendes på hver blok separat. Blokcellulære automater er nyttige til modellering af fysiske fænomener, da det ofte ikke er svært at vælge overgangsfunktioner, således at den resulterende cellulære automat er reversibel og adlyder de valgte bevarelseslove . [en]
En cellulær automat er et regulært gitter af celler, som hver har en tilstand taget fra et endeligt sæt af tilstande og en overgangsfunktion, der er nødvendig for at opdatere celletilstandene baseret på naboernes tilstande. Det kaldes blok, hvis gitteret er opdelt i lige store ikke-skærende blokke, og overgangsfunktionen bruger sin blok som et kvarter til hver celle. I dette tilfælde skal automaten have et begrænset antal partitioner i blokke, der bruges efter tur: for eksempel kan en partition flyttes i en eller anden retning. [1] [2]
Således, under hvert trin af automaten, anvendes overgangsfunktionen samtidigt til alle celler, som ændrer hver blok uafhængigt af de andre, derefter skifter partitionen til den næste, og trinnet gentages. Dette gør det muligt at udføre ikke-trivielle beregninger ved hjælp af ret simple overgangsfunktioner.
Det enkleste eksempel på et sådant skema er Margolus-kvarteret , hvor cellerne i et kvadratisk gitter er opdelt i 2 × 2 blokke af lodrette og vandrette linjer, og efter hvert trin forskydes opdelingen i blokke med en celle vandret og lodret ; således ender alle fire celler i enhver blok i forskellige blokke i det næste trin. [3] Dette kvarter er opkaldt efter Norman Margolus ( engelsk. Norman Margolus ), en af de første forskere inden for blokcelleautomater. [en]
Et eksempel på en blokcellulær automat, der bruger et Margolus-kvarter, er "The Critters" . Critters-overgangsfunktionen vender hver cells tilstand, hvis antallet af levende celler i blokken ikke er to, og roterer hele blokken 180°, hvis dette tal er tre. Da antallet af levende celler ændres til antallet af døde, og overgangsfunktionerne er reversible for hver værdi af antallet af celler, er en sådan cellulær automatik reversibel på hver blok og er derfor reversibel som en helhed. [4] Imidlertid udviser den kompleks dynamisk adfærd, der ligner Conways Game of Life ; især er det Turing komplet , se den relaterede artikel for detaljer .