Blokový celulární automat je třída celulárních automatů , ve kterých je mřížka rozdělena do bloků a přechodová funkce je aplikována na každý blok samostatně. Blokové buněčné automaty jsou užitečné pro modelování fyzikálních jevů, protože často není obtížné zvolit přechodové funkce tak, aby výsledný buněčný automat byl reverzibilní a dodržoval zvolené zákony zachování . [jeden]
Buněčný automat je pravidelná mřížka buněk, z nichž každá má stav převzatý z konečné množiny stavů a přechodovou funkci potřebnou k aktualizaci stavů buněk na základě stavů svých sousedů. Nazývá se blok , pokud je mříž rozdělena na stejné neprotínající se bloky a přechodová funkce používá svůj blok jako okolí každé buňky. V tomto případě musí mít automat určitý konečný počet oddílů do bloků používaných postupně: například jeden oddíl může být posunut v určitém směru. [1] [2]
Při každém kroku automatu je tedy na všechny buňky současně aplikována přechodová funkce, která změní každý blok nezávisle na ostatních, následně se oddíl změní na další a krok se opakuje. To umožňuje provádět netriviální výpočty pomocí poměrně jednoduchých přechodových funkcí.
Nejjednodušším příkladem takového schématu je sousedství Margolus , ve kterém jsou buňky čtvercové mřížky rozděleny na 2 × 2 bloky vertikálními a horizontálními čarami a po každém kroku je rozdělení na bloky posunuto o jednu buňku horizontálně a vertikálně. ; takže všechny čtyři buňky libovolného bloku skončí v dalším kroku v různých blocích. [3] Tato čtvrť je pojmenována po Normanu Margolusovi ( anglicky Norman Margolus ), jednom z prvních výzkumníků blokových celulárních automatů. [jeden]
Příkladem blokového celulárního automatu využívajícího sousedství Margolus je „The Critters“ . Funkce Critters transition obrátí stav každé buňky, pokud počet živých buněk v bloku nejsou dvě, a otočí celý blok o 180°, pokud je tento počet tři. Vzhledem k tomu, že počet živých buněk se mění na počet mrtvých a přechodové funkce jsou reverzibilní pro každou hodnotu počtu buněk, je takový buněčný automat reverzibilní na každém bloku, a proto je reverzibilní jako celek. [4] Vykazuje však komplexní dynamické chování podobné Conwayově hře o život ; konkrétně je to Turing kompletní , podrobnosti viz související článek .