Buněčný automat je model používaný v informatice a matematice. Jde o modelování dynamického systému pomocí řady buněk. Každá buňka má jeden z několika možných stavů. Při každém "tahu" nebo iteraci je stav aktuální buňky určen dvěma věcmi: jejím aktuálním stavem a stavy sousedních buněk.

Velmi známým příkladem celulárního automatu je Conwayova Hra o život. Stanislaw Ulam a John von Neumann poprvé popsali celulární automaty ve 40. letech 20. století. Conwayova Hra o život byla poprvé předvedena v 70. letech 20. století.

Definice a formální popis

Formálně lze buněčný automat popsat následujícími složkami:

  • mřížka buněk (např. jednorozměrná čára, dvourozměrná čtvercová síť nebo obecná grafová struktura),
  • množina možných stavů každé buňky (např. {0,1} pro "mrtvý/živý"),
  • sousedství (neighbourhood) — pravidlo, které určuje, které buňky ovlivňují danou buňku (např. von Neumannova nebo Mooreova),
  • lokální přechodová funkce (transition function) — deterministické nebo nedeterministické pravidlo, které pro daný vzor stavů v sousedství určí nový stav buňky,
  • režim aktualizace — obvykle synchronní (všechny buňky se mění současně), ale existují i asynchronní varianty.

Typy buněčných automatů a sousedství

  • Jednorozměrné automaty: buňky jsou uspořádány na řadě; příkladem jsou Wolframovy elementární automaty (2 stavy, sousedství velikosti 3), např. pravidla 30 nebo 110.
  • Dvourozměrné automaty: nejznámější je čtvercová mřížka s Mooreovým sousedstvím (8 sousedů) nebo von Neumannovým sousedstvím (4 sousedé).
  • Totalistické automaty: pravidlo závisí pouze na počtu zapnutých/aktivních sousedů, ne na jejich přesném uspořádání.
  • Deterministické vs. nedeterministické: většina klasických modelů je deterministická; některé modely obsahují náhodu nebo pravděpodobnostní pravidla.
  • Hraniční podmínky: mřížka může být neomezená, konečná s pevnými okraji, nebo periodická (torus).

Příklady pravidel a chování

  • Conwayova Hra o život (Life): dvourozměrný binární automat s pravidlem často zapisovaným jako B3/S23 — buňka se narodí (B) když má přesně 3 živé sousedy; přežije (S) když má 2 nebo 3 živé sousedy; jinak zemře nebo zůstane mrtvá. Z Life vznikají známé struktury: still lifes (stabilní vzory), oscillators (periodické vzory), gliders (pohyblivé vzory).
  • Elementární automaty (1D): jednoduché pravidlo pro trojici buněk může vést k chaotickému chování (např. Rule 30) nebo i k univerzální výpočetní schopnosti (Rule 110 je dokázaně univerzální).

Vlastnosti a teorémy

  • Komplexita z jednoduchých pravidel: i velmi jednoduchá lokální pravidla mohou generovat složité a nepředvídatelné chování.
  • Univerzálnost: některé buněčné automaty (např. Conwayova Hra o život, Rule 110) jsou Turingovsky univerzální — mohou simulovat libovolný výpočet.
  • Reverzibilita: některé automaty jsou navrženy tak, aby byly reverzibilní (každý stav má právě jeden předchůdce), což je důležité v termodynamice a informační teorii.

Aplikace

Buněčné automaty se používají v mnoha oblastech:

  • modelování biologických procesů (růst buněčných kolonií, šíření nemocí),
  • fyzikální simulace (reakčně-difuzní systémy, krystalizace),
  • dopravní modely (simulace toku vozidel),
  • generování fraktálů a proceduralní obsah v počítačové grafice,
  • teoretická informatika (studium paralelizace, výpočetní schopnosti) a kryptografie,
  • učební a popularizační nástroje při výuce dynamických systémů a emergentního chování.

Praktické poznámky

  • Při implementaci je důležité volit vhodnou reprezentaci mřížky a efektivní metody aktualizace (např. sparse reprezentace pro řídké stavy).
  • Pro experimentování existují dostupné programy a simulátory (např. specializované nástroje pro Hru o život) a velké množství komunitních knihoven.
  • Analýza chování může využívat vizualizace, spektrální analýzy časových řad nebo metody z kombinační a výpočetní teorie.

Buněčné automaty představují jednoduchý, ale velmi silný rámec pro studium, simulaci a pochopení komplexních jevů vznikajících z lokálních interakcí.