Celulární automat

Celulární automat (zkratka CA) je souhrnné označení pro určitý typ fyzikálního modelu reálné situace, ať již v podobě reálného přístroje či mnohem častěji počítačového algoritmu (programu). Slouží k časové i prostorové diskrétní (nespojité) idealizaci (ideální modelaci) fyzikálních systémů, kde hodnoty veličin nabývají pouze diskrétních hodnot v průběhu času.

Využívá se v teorii systémů, matematice a teoretické biologii.

Historie

První nápady na CA se objevily již ve 40. letech dvacátého století, kdy se John von Neumann snažil navrhnout stroj, který by kontroloval i opravoval sám sebe^[1] Jeho cílem bylo najít logickou strukturu sebereprodukujícího se automatu bez nutného vztahu k biologickým procesům. Spolu s S. Ulamem rozdělili celý prostor na jednotlivé buňky (cells), přičemž každá buňka je na začátku charakterizována počátečním stavem. Tento počáteční stav se podle evolučního pravidla mění vždy po jednotlivých krocích, tzv. iteracích. Evoluční pravidlo nemusí být stejné pro všechny buňky, ale je vždy funkcí stavů buněk v okolí buňky, kterou právě zkoumáme. V padesátých letech se začaly CA používat k automatickému zpracování obrazů ^[2]. Byla vyvinuta speciální pravidla pro úpravu šumu, odhad velikosti a počtu objektů na obraze pořízeném mikroskopem.

V roce 1970 našel John Conway jednoduché pravidlo vedoucí ke komplexnímu chování. Nazval je Game of Life (více níže). V sedmdesátých letech byl vytvořen HPP model mřížového plynu trojicí Hardy, Pomeau a de Pazzis.^[3] Je to jeden z prvních CA, který zachovává kromě počtu částic také hybnost. Tímto modelem se otevřela cesta k simulování pohybu tekutin, nebo zrnitých látek pomocí CA. V osmdesátých letech se Stephen Wolfram ^[4] začal zabývat jednodimenzionálními CA, u kterých prokázal jejich vztah ke statistické fyzice.

V roce 1986 přišel na svět FHP model pánů Frische, Hasslachera a Pomeaua^[5], který nezávisle na nich objevil také Stephen Wolfram. Provedou-li se u něj příslušné limity, ukazuje se, že se jedná o obdobu Navierových–Stokesových rovnic, což je nepopiratelný důkaz schopnosti CA modelovat reálný fyzikální problém.

Přehled

Celulární automat je dynamický systém, diskrétní v hodnotách, prostoru i čase. Je tvořen pravidelnou strukturou buněk v N-rozměrném prostoru (nejčastěji je N=2, tzv. 2D CA, kde buňky tvoří čtvercovou mřížku). Každá buňka může nabývat jeden z K možných stavů. Často jde pouze o dva stavy: 0-mrtvá buňka, 1-živá buňka; v tomto případě se občas stav 1 označuje jako buňka a 0 jako prázdné políčko (mřížky).

Hodnoty stavů buněk v dalším časovém kroku (v následující generaci) se vypočtou synchronně na základě lokální přechodové funkce (stejné pro všechny buňky). Argumenty této funkce jsou aktuální hodnoty stavů vyšetřované buňky a všech sousedů (buněk v jejím okolí).

V případě 1D CA je okolí charakterizováno tzv. poloměrem, tj. počtem sousedů po obou stranách vyšetřované buňky; v případě 2D CA tvoří okolí čtyři přilehlé buňky (tzv. neumanovské okolí), a nebo se do okolí zařadí i čtyři další sousedi, dotýkajících se vyšetřované buňky jen v rozích (tzv. moorovské okolí). Zpravidla se očekává, že struktura buněk je nekonečná. V praktických realizacích se buď předpokládají okrajové buňky identicky nulové (prázdné), nebo jsou okraje „propojeny“ a tvoří v případě 1D smyčku a v případě 2D anuloid. Některé z K možných stavů jsou označovány za „klidové“; když buňka v klidovém stavu má ve svém okolí také jenom buňky v klidovém stavu, potom se hodnota jejího stavu v další generaci nemění.

Někdy je účelná širší koncepce, ve které jsou pro CA charakteristické tři klíčové vlastnosti:

paralelismus (výpočet nových hodnot všech stavů probíhá současně, na běžných sériových počítačích se musí tento postup simulovat)
lokalita (nový stav prvku závisí jen na jeho původním stavu a na původních stavech prvků z jeho okolí)
homogenita (pro všechny prvky platí stejná lokální přechodová funkce)

Nevyžaduje se při tom nutně pravidelná prostorová struktura (proto byl v uvedené charakteristice použit všeobecnější pojem „prvek“ místo „buňka“).

Význam ve fyzice

Pomocí jednoduchých pravidel lze vytvořit CA se složitým a dynamickým chováním. CA mohou představovat vymyšlený mikroskopický svět, který při pohledu z větší výšky odpovídá fyzikální realitě. Existují dva základní přístupy ke studiu fyzikálních dějů, mikroskopický a makroskopický. Z mikroskopického pohledu jsou interakce velice komplikované a mnohdy je k důkladnému popisu nezbytné užití kvantové teorie. Studujeme-li děj makroskopicky, jsou vlastnosti systému zkoumány pomocí středních hodnot příslušných veličin. Výsledné chování je spjato s charakteristickými rysy interakcí odehrávajících se na mikroskopické škále, jenomže tento vztah se při provedení středování ztrácí. CA jsou jedním z pokusů, jak tuto nepříjemnost odstranit, neboť zachování představy, co se uvnitř daného materiálu děje a jak se tyto nepatrné změny projevují vůči okolí, je pro fyziku velmi důležité. Příkladem může být studium magnetických vlastností feromagnetických látek. Makroskopickou charakteristikou je zde kritická (Curieova) teplota, která má z mikroskopického pohledu přímý vztah s rozdělením elektronů v atomech, které lze precizně studovat právě pomocí kvantové teorie.

Celulární automat jako jednoduchý dynamický systém

Ve fyzice jsme zvyklí popisovat časový vývoj částic pomocí diferenciálních rovnic. Pokud vůbec řešení existuje, bývá často velmi citlivé na počáteční podmínky. Studium CA nabízí jiný přístup ke studiu dynamických procesů. Jejich velká výhoda tkví v jednoduchosti, díky které jimi lze analyzovat dynamické systémy a navíc se jejich numerické řešení obejde bez zjednodušujících aproximací, což vede k přesnému výsledku. U CA se setkáváme se dvěma možnými přístupy k řešení (nejen) fyzikálních problémů. Za prvé máme CA pravidlo a chceme předpovědět jeho chování a tudíž i potenciální využití. Za druhé se jedná o obrácený problém, kdy víme, jaké požadavky na náš CA klade realita a hledáme odpovídající pravidlo. V obou případech se jedná o obtížně řešitelný problém.

Druhy celulárních automatů

Jednodimenzionální automat

Je nejjednodušší, ale nikoliv nezajímavý. Jde o jednodimenzionální automat, kde stavy buněk nabývají pouze dvou hodnot 0 nebo 1 a okolím chápeme dvě sousední buňky. Někdy se tomuto automatu výstižně říká toy model, protože je velice jednoduše programovatelný a pro mnoho lidí je první, který si sami vytvoří.

Von Neumannův CA

Von Neumann nebyl spokojen s kinematickým modelem automatu kvůli tzv. „black-box“ problému. S řešením mu pomohl jeho spolupracovník Stanisław Ulam. Navrhl prostředí tvořené pravidelnou mřížkou - jakousi šachovnicí, kde každé políčko představuje jednu buňku. Každá buňka představuje konečný automat, pracující se shodnou množinou pravidel. Množinu takových buněk můžeme pak považovat za organismus.

Neumannův CA byl sestaven asi z 200 tisíc buněk, které mohly mít 29 stavů, CA tvořilo tělo asi 80x400 buněk (bylo rozčleněno na tři složky A, B, C - továrnu, duplikátor a počítač) a dlouhý výrůstek z asi 150 tisíc buněk.

Game of life

Hra života je dvourozměrný, dvoustavový celulární automat, který svým fungováním připomíná vývoj společenství živých organismů.

Coddův automat

Pracoval s osmi stavy a s neumanovským okolím. Čtyři stavy byly strukturální:

0 - prázdná buňka
1 - jádro signálové cesty
2 - obal signálové cesty
3 - speciální použití, např. pro hradlo
4,5,6,7 - byly signálové.

Základním prvkem byla dvojice signálové buňky v kombinaci s prázdnou buňkou. Tato dvojice se v každé generaci posune o jednu pozici po signálové cestě.

Coddův automat byl teoreticky schopen emulovat Turingův stroj a též vytvořit svou vlastní kopii.

Langtonovy Q-smyčky

Langton sestrojil na bázi Coddova modelu nesrovnatelně jednodušší verzi samoreprodukujícího se 2D CA (chybí ovšem emulace Turingova stroje), tzv. Q-smyčky.

Langtonovy Q-smyčky jsou názornou ukázkou dvojí funkce informace:

neinterpretovaná informace (genotyp) se kopíruje do potomka
interpretovaná informace (fenotyp) charakterizuje tvar a chování jedince

Odkazy

Reference

↑ S. Ulam: Random processes and transformations, Proc. Int. Congr. Math. 2 (1952),264–27.
↑ K. Preston a M. Duﬀ: Modern Cellular Automata: Theory and Applications, Plenum Press, 1984
↑ . Hardy, Y. Pomeau a O. de Pazzis: Molecular Dynamics of a classical lattice gas: Transport properties and time correlation functions, Phys. Rev. A 13 (1976), 1949–60,
↑ M. Garden: The fantastic combinations of John Conway‘s new solitaire game life, Scientiﬁc American 4 (1970), 120–127, S. Wolfram: Theory and Application of Cellular Automata, World Scientiﬁc, 1986
↑ U. Frisch, B.Hasslacher a Y. Pomeau: Lattice–gas automata for the Navier– Stokes equation, Phys. Rev. Lett. 56 (1986), 1505–32

Externí odkazy

Obrázky, zvuky či videa k tématu celulární automat na Wikimedia Commons
Martina Husáková: Celulární automaty
Implementace hry Life v C#

[1] S. Ulam: Random processes and transformations, Proc. Int. Congr. Math. 2 (1952),264–27.

[2] K. Preston a M. Duﬀ: Modern Cellular Automata: Theory and Applications, Plenum Press, 1984

[3] . Hardy, Y. Pomeau a O. de Pazzis: Molecular Dynamics of a classical lattice gas: Transport properties and time correlation functions, Phys. Rev. A 13 (1976), 1949–60,

[4] M. Garden: The fantastic combinations of John Conway‘s new solitaire game life, Scientiﬁc American 4 (1970), 120–127, S. Wolfram: Theory and Application of Cellular Automata, World Scientiﬁc, 1986

[5] U. Frisch, B.Hasslacher a Y. Pomeau: Lattice–gas automata for the Navier– Stokes equation, Phys. Rev. Lett. 56 (1986), 1505–32

[1]

[2]

[3]

[4]

[5]