En cellulär automat är en diskret, matematisk modell för dynamiska system som utvecklas i steg i tiden över ett rutnät av celler. Varje cell befinner sig i ett av ett ändligt antal tillstånd (oftast två: "levande" eller "död") och uppdaterar sitt tillstånd samtidigt med alla andra celler enligt en lokal regel som beror på cellens eget nuvarande tillstånd och tillstånden hos dess grannar. Syftet är att studera hur enkla lokala regler kan ge upphov till komplexa, globala mönster. Begreppet används ofta inom datavetenskap och matematik, och själva idéen är ett sätt att formaliserad en modell

Grundläggande egenskaper

  • Diskret tid och rum: Tiden går i hela steg (iterationer) och rutnätet består av diskreta celler i exempelvis en- eller tvådimensionellt rutmönster.
  • Lokala regler: Uppdateringen av en cell beror endast på cellens eget tillstånd och tillstånden hos ett begränsat antal angränsande celler (grannskap).
  • Deterministiska eller stokastiska: Regler kan vara deterministiska (samma ingång ger alltid samma utgång) eller slumpmässiga.
  • Grannskapsdefinition: Vanliga grannskap är Moore (8 grannar i 2D) och von Neumann (4 ortogonala grannar i 2D).
  • Randvillkor: Gränserna kan vara fasta, reflekterande eller periodiska (till exempel en torus).

Historia

Idén om cellulära automater utvecklades under 1940-talet av forskare som Stanislaw Ulam och John von Neumann, som studerade självorganiserande system och automater som kunde modellera biologisk tillväxt och reproduktion. På 1960–70 talen populariserades fältet ytterligare när enklare varianter och visuella exempel började användas i akademiska och populärvetenskapliga sammanhang.

Conways Game of Life (ett klassiskt exempel)

Det mest kända exemplet på en cellulär automat är Conways Game of Life, konstruerad av matematikern John Conway på 1970-talet. Life är en tvådimensionell, tvåtillstånds (levande/död) automat på ett kvadratiskt rutnät som använder Moore-grannskapet (8 grannar). Regeln kan sammanfattas med beteckningen B3/S23:

  • Födelse (B3): En död cell blir levande om den har exakt 3 levande grannar.
  • Överlevnad (S23): En levande cell överlever om den har 2 eller 3 levande grannar; annars dör den (av isolering eller överbefolkning).

Trots sina enkla regler visar Life en mängd komplexa fenomen: still lifes (stabila mönster), oscillatorer (periodiska mönster), gliders (rörliga mönster), spaceships och konstruktioner som kan utföra universell beräkning (Turing-kompletthet). Game of Life har blivit en standardreferens för hur komplexitet kan uppstå ur enkla lokala regler.

Varianter och klassificering

  • Dimensioner: Cellulära automater kan definieras i 1D, 2D, 3D eller högre dimensioner.
  • Fler tillstånd: Celler kan ha fler än två tillstånd (exempelvis färger eller energinivåer).
  • Regelvarianter: Det finns tusentals reglersystem utöver Life (t.ex. Brian's Brain, Langton's ant, Wireworld).
  • Wolframs klassificering: Stephen Wolfram föreslog en indelning (typ I–IV) av cellulära automater baserat på deras dynamiska beteende, från enkla stationära till komplexa eller kaotiska mönster.

Tillämpningar

  • Modellering: Diffusion, vågmönster, brandspridning, ekologi, spridning av sjukdomar och kemiska reaktioner.
  • Beräkning och teori: Konstruktion av logiska grindar, registermaskiner och demonstration av Turing-kompletthet.
  • Grafik och konst: Generativ konst, texturer och visuella simuleringar.
  • Fysik och materialvetenskap: Studier av kristallisation, partikelautomata och flödesfenomen.
  • Utbildning: Ett lättillgängligt sätt att introducera begrepp som emergens, kaos och komplexitet.

Exempel på vanliga mönster i Game of Life

  • Still lifes: Block, beehive — mönster som inte förändras.
  • Oscillatorer: Blinker (period 2), toad, pulsar — mönster som upprepar sig med viss period.
  • Glider: Ett litet mönster som rör sig diagonalt över brädet och är viktigt för informationsöverföring i konstruktioner.
  • Guns och breeders: Puffer trains och Gosper glider gun — mönster som kontinuerligt producerar gliders eller andra strukturer.

Praktisk implementering

En cellulär automat är lätt att implementera i programkod: representera rutnätet som en tvådimensionell matris, räkna grannar för varje cell och skapa nästa generation enligt regeln. För stora system används ofta optimeringar som hashbaserade representerade för sparsamma rutnät eller parallell körning på GPU/cluster.

Sammanfattning

Cellulära automater visar hur enkla, lokala regler kan ge upphov till rikt, oförutsägbart och ofta vackert beteende. De fungerar både som forskningsverktyg och pedagogiskt exempel och har inspirerat till studier inom matematik, datavetenskap, fysik och konst. Från de tidiga idéerna hos Stanislaw Ulam och John von Neumann till Conways uppvisning av komplexa mönster i Game of Life – fältet fortsätter att vara aktivt och fascinerande.