Elemi sejtautomata

Az elemi cellás automata  olyan sejtautomata , amelynek mindkét oldalán végtelenített szalag formájában egydimenziós cellatömb található, és két lehetséges cellaállapota van (0 és 1, "halott" és "élő", "üres" és "töltött") és egy szabály a cella állapotának meghatározására a következő lépésben, csak a cella és két szomszédjának állapotát használva az aktuális lépésben. Általában az ilyen automaták a lehető legegyszerűbb sejtautomaták közé tartoznak, azonban bizonyos szabályok szerint összetett viselkedést mutatnak; így a 110-es szabály használata egy Turing-teljes automatához vezet .

Wolfram kód

Összességében a sejt állapotának és két szomszédjának állapotának lehetséges kombinációi vannak. Az elemi cellaautomatát definiáló szabálynak minden lehetséges esetre meg kell adnia a következő állapotot (0 vagy 1), tehát a szabályok teljes számát . Stephen Wolfram egy számozási sémát javasolt ezekhez a szabályokhoz, amely Wolfram-kód néven ismert , amely minden szabályt 1 és 255 közötti számokra képez le. Ezt a rendszert először Wolfram tette közzé egy 1983-as cikkében [1] , majd később az A könyvében használták. New Kind of Science " ( Eng. Science of a new type ). [2]  

A Wolfram kód megszerzéséhez fel kell írni a lehetséges konfigurációkat (111, 110, ..., 001, 000) csökkenő sorrendben, ki kell írni a megfelelő állapotokat alájuk és a kapott nullák és egyesek sorozatát számként értelmezni. kettes számrendszerben . Például a következő séma a 110-es szabálynak megfelelő kódot eredményez :

Reflexiók és kiegészítések

A 256 szabály közül néhány triviálisan egyenértékű egymással kétféle transzformáció jelenléte miatt. Az első egy tükrözés a függőleges tengely körül, amelyben a bal és a jobb szomszédok felcserélődnek, és egy tükrözött szabályt kapunk .  Például a 110-es szabályból a 118-as szabály lesz:

A 256 szabály között 64 tükörszimmetrikus ( ang .  amphichiral ) található.

A transzformáció második típusa a definícióban a 0 és 1 szerepek cseréje, ami egy további szabályt ad ( angol  kiegészítő szabály ). Például a 118-as szabályból a 137-es szabály lesz:

A 256-ból csak 16 szabály esik egybe a kiegészítésekkel. Eddig a pár transzformációig (beleértve az egyidejűleg alkalmazottakat is - a sorrend nem fontos) 88 nem egyenértékű elemi sejtautomata van. [3]

Kutatási módszerek

A legegyszerűbb konfiguráció

Az elemi sejtautomaták tanulmányozásának egyik módszere a legegyszerűbb kezdeti konfiguráció alakulásának figyelembe vétele, vagyis az egyetlen élő (1-et tartalmazó) sejtből áll. Ha a szabálynak páros Wolfram kódja van, akkor nincs spontán életgeneráció (a következő generációban a 000 kombináció nem ad középen 1-et), ezért a legegyszerűbb konfiguráció minden állapotában véges számú nullától eltérő cellák, és bináris jelölésben számként értelmezhető.[ hogyan? ] Ezeknek a számoknak a sorozata egy generáló függvényt határoz meg , amely racionális , azaz két polinom aránya , és gyakran viszonylag egyszerű alakja van.

Véletlenszerű konfigurációk

Hasznos figyelembe venni a véletlenszerű kezdeti konfigurációk alakulását is. Ennek érdekében a Wolfram által feltalált sejtautomaták következő informális osztályaira oszthatók: [4]

• 1. osztály: Gyorsan konvergál a nullák vagy egyesek állapotába. Wolfram példaként a 0, 32, 160, 232 szabályokat említi.
• 2. osztály: Gyors konvergálás ciklikus vagy stabil állapotba. Például a 4-es, 108-as, 218-as, 250-es szabályok.
• 3. osztály: Véletlenszerű állapotban tárolva. Például a 22., 30. , 126., 150., 182. szabályok.
• 4. osztály: Mindkét régió ciklikus vagy stabil állapotú, valamint olyan struktúrák alakulnak ki, amelyek összetett módon kölcsönhatásba lépnek egymással. Példa erre a 110-es szabály , amely Turing kész .