Elementární celulární automat je celulární automat s jednorozměrným polem buněk ve formě nekonečné pásky na obou stranách, který má dva možné stavy buňky (0 a 1, "mrtvý" a "živý", "prázdný" a "vyplněno") a pravidlo pro určení stavu buňky v dalším kroku s použitím pouze stavu buňky a jejích dvou sousedů v aktuálním kroku. Obecně takové automaty patří mezi nejjednodušší možné celulární automaty, nicméně za určitých pravidel vykazují složité chování; tak použití pravidla 110 vede k Turingově úplnému automatu.
Celkem jsou možné kombinace stavu buňky a stavů jejích dvou sousedů. Pravidlo definující elementární celulární automat musí uvádět další stav (0 nebo 1) pro každý z těchto možných případů, takže celkový počet pravidel . Stephen Wolfram navrhl schéma číslování pro tato pravidla, známé jako Wolframův kód , který mapuje každé pravidlo na číslo mezi 1 a 255. Tento systém byl poprvé publikován Wolframem v článku z roku 1983 [1] a později byl použit ve své knize A New Kind of Science “ ( angl. Science of a new type ). [2]
Pro získání Wolframova kódu je potřeba zapsat možné konfigurace (111, 110, ..., 001, 000) v sestupném pořadí, vypsat pod ně odpovídající stavy a výslednou posloupnost nul a jedniček interpretovat jako číslo. v binární číselné soustavě . Například následující schéma má za následek kód odpovídající pravidlu 110 :
současné stavy | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
---|---|---|---|---|---|---|---|---|
budoucí stav | 0 | jeden | jeden | 0 | jeden | jeden | jeden | 0 |
Některá z 256 pravidel jsou si navzájem triviálně ekvivalentní kvůli přítomnosti dvou druhů transformací. Prvním je odraz kolem svislé osy, ve kterém se zamění levý a pravý soused a získá se zrcadlené pravidlo . Například pravidlo 110 se změní na pravidlo 118:
současné stavy | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
---|---|---|---|---|---|---|---|---|
budoucí stav | 0 | jeden | jeden | jeden | 0 | jeden | jeden | 0 |
Mezi 256 pravidly je 64 zrcadlově symetrických ( angl. amphichiral ).
Druhým typem transformace je nahrazení rolí 0 a 1 v definici, což dává další pravidlo ( anglicky komplementární pravidlo ). Například pravidlo 118 se změní na pravidlo 137:
současné stavy | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
---|---|---|---|---|---|---|---|---|
budoucí stav | jeden | 0 | 0 | 0 | jeden | 0 | 0 | jeden |
Pouze 16 pravidel z 256 se shoduje s jejich dodatky. Do této dvojice transformací (včetně těch současně aplikovaných - pořadí není důležité) existuje 88 neekvivalentních elementárních celulárních automatů. [3]
Jednou z metod studia elementárních buněčných automatů je uvažovat o evoluci nejjednodušší počáteční konfigurace, která sestává pouze z jedné živé (obsahující 1) buňku. Pokud má pravidlo sudý Wolframův kód, pak nedochází k samovolnému generování života (kombinace 000 nedává 1 uprostřed v další generaci), a proto má každý stav nejjednodušší konfigurace konečný počet nenulových buňky a lze je interpretovat jako číslo v binárním zápisu.[ jak? ] Posloupnost těchto čísel definuje generující funkci , která je racionální , tedy poměr dvou polynomů , a často má relativně jednoduchý tvar.
Je také užitečné zvážit vývoj náhodných počátečních konfigurací. K tomu existuje rozdělení do následujících neformálních tříd celulárních automatů , které vynalezl Wolfram: [4]
Některá pravidla nelze jednoznačně přiřadit k jedné z tříd, například:
Conwayova hra o život a další buněčné automaty | |||||
---|---|---|---|---|---|
Konfigurační třídy |
| ||||
Konfigurace |
| ||||
Podmínky | |||||
Jiná kosmická loď na dvourozměrné mřížce |
| ||||
Jednorozměrná kosmická loď | |||||
Software a algoritmy |
| ||||
výzkumníci KA |