90. szabály

A 90. szabály ( eng.  Rule 90 ) egy elemi cellás automata , vagyis egy egydimenziós , két állapotú cellás automata , amely a modulo 2 (kizárólagos "OR", angol  XOR ) függvénye alapján épül fel. A "90. szabály" nevet a Wolfram kód határozza meg .

Az automata cellák egydimenziós tömbjéből áll, amelyek mindegyike 0 ("üres", "halott") vagy 1 ("teli", "élő") értéket tartalmaz. Az automata lépése abból áll, hogy bármely cellában az értéket egyidejűleg lecseréli a két szomszédjának modulo 2 összegére [1] . A 90. szabály a legegyszerűbb, nem triviális sejtautomata [2] . Részletesen leírja Stephen Wolfram A New Kind of  Science  [ 3  ] című könyvében .

A legegyszerűbb konfigurációhoz - amelynek kezdeti pozíciója csak egy élő cellát tartalmaz - az idő-tér diagram a Sierpinski-háromszög alakú . Bármely más konfiguráció viselkedése a legegyszerűbb konfigurációk modulo 2 hozzáadásával magyarázható. Konkrétan, minden véges számú, nullától eltérő cellát tartalmazó konfiguráció replikátor, amely fokozatosan kitölti a teljes mezőt a másolataival. Ha a 90. szabály kezdeti konfigurációja véletlenszerű, akkor a későbbiek is. A megfelelő idő-tér diagramon sok különböző méretű háromszög alakú "ablak" található, amelyek több nulla sorozatának fokozatos kitöltéséből adódnak.

A 90. szabály korai feltárását a Gilbraith-sejtés motiválta, amely a szomszédos prímszámok közötti különbségekkel kapcsolatos számelméleti  megoldatlan probléma . Számelméleti szempontból is érdekes a Gould-sorozat , amely a legegyszerűbb konfigurációban tartalmazza a nem nulla cellák számát különböző lépésekben. Értékei kettő hatványai, amelyek kitevője megegyezik a nem nulla számjegyek számával a lépésszámok bináris ábrázolásában (a számozás 0-tól kezdődik).

A 90-es szabály bármely konfigurációjának pontosan négy elődje van, így sok más sejtautomatával, például az Életjátékkal ellentétben ennek az automatának nincs édenkertje , vagyis nincs elődje. Így a 90-es szabály egy cellás automata, amely szürjektív (minden konfigurációnak van elődje), de nem injektív (vannak olyan konfigurációk, amelyek a következő lépésben ugyanahhoz vezetnek), és így ellenpéldát ad a kerti tétel fordított tételére. Eden .

Jegyzetek

1. ↑ Wolfram, Stephen (1983), Statistical mechanics of cellular automata , Reviews of Modern Physics 55 (3): 601–644, doi : 10.1103/RevModPhys.55.601 , < http://www.stephenwolfram.com/publications cikkek/ca/83-statistical/ > Archivált : 2013. szeptember 21. a Wayback Machine -nál . 
2. ↑ Martin, Olivier; Odlyzko, Andrew M. & Wolfram, Stephen (1984), Algebraic properties of cellular automata , Communications in Mathematical Physics 93. kötet (2): 219–258, doi : 10.1007/BF01223745 , < http ://www.stephenwolfra /publications/articles/ca/84-properties/ > Archivált : 2012. szeptember 10. a Wayback Machine -nél . 
3. ↑ Wolfram, Stephen (2002), A New Kind of Science , Wolfram Media  . A könyv betűrendes tárgymutatója több mint 50 altémát sorol fel a Rule 90 géppel kapcsolatban.