Elementární celulární automat

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.

Wolframův kód

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 :

Úvahy a doplňky

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:

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:

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]

Metody výzkumu

Nejjednodušší konfigurace

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.

Náhodné konfigurace

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]

• Třída 1: Rychle konverguje do stavu všech nul nebo jedniček. Wolfram uvádí jako příklady pravidla 0, 32, 160, 232.
• Třída 2: Rychlá konvergence do cyklického nebo stabilního stavu. Například pravidla 4, 108, 218, 250.
• Třída 3: Uloženo v náhodném stavu. Například pravidla 22, 30 , 126, 150, 182.
• Třída 4: Vytvářejí se obě oblasti s cyklickými nebo stabilními stavy a také struktury, které na sebe vzájemně působí složitým způsobem. Příkladem je pravidlo 110 , kterým je Turing kompletní .