Celulární automat
Z Wikipedie, otevřené encyklopedie
Celulární automat (zkratka CA) je diskrétní model studovaný v teorii systémů, matematice a teoretické biologii.
Obsah |
[editovat] 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. úplné 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 stavů všech 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“).
[editovat] 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 Stanislaw 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.
[editovat] Hra LIFE
Mnohem jednodušší podoba 2D Neumanovského CA. Pracoval pouze s dvěma stavy a s úplným okolím. Pravidla pro chování buněk, zaručující nejpestřejší dynamiku obrazců:
- zrod - v okolí prázdného políčka jsou právě tři buňky („trojpohlavní“ rozmnožování)
- přežití - v okolí buňky jsou právě dvě nebo tři další buňky
- uhynutí - v okolí buňky je 0,1,4,5,6,7 nebo 8 dalších buněk
Výchozí obrazce, tvořené populacemi buněk, směřovaly obvykle po několika generacích k jedné z těchto situací:
- zánik - struktura A
- stabilní obrazec (v dalších krocích neměnný) - struktura B
- cyklicky se opakující obrazec - struktura C
- cyklicky se opakující, ale posunutý obrazec - struktura D
[editovat] 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 dvojce signálové buňky v kombinaci s prázdnou buňkou. Tato dvojce 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.
[editovat] 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:
