Základní buněčný automat - Elementary cellular automaton

v matematika a teorie vypočítatelnosti, an základní buněčný automat je jednorozměrný buněčný automat kde existují dva možné stavy (označené 0 a 1) a pravidlo pro určení stavu buňky v příští generaci závisí pouze na aktuálním stavu buňky a jejích dvou bezprostředních sousedech. Existuje základní buněčný automat (pravidlo 110, definovaný níže), kterého je schopen univerzální výpočet, a jako takový je to jeden z nejjednodušších možných modelů výpočtu.

Systém číslování

Existuje 8 = 2³ možné konfigurace buňky a jejích dvou bezprostředních sousedů. Pravidlo definující buněčný automat musí specifikovat výsledný stav pro každou z těchto možností, takže existuje 256 = 2²³ možné základní buněčné automaty. Stephen Wolfram navrhl systém známý jako Wolframův kód, přiřadit každému pravidlu číslo od 0 do 255, které se stalo standardem. Každá možná aktuální konfigurace je zapsána v pořadí 111, 110, ..., 001 000 a výsledný stav pro každou z těchto konfigurací je zapsán ve stejném pořadí a interpretován jako binární reprezentace celého čísla. Toto číslo je považováno za číslo pravidla automatu. Například 110_d=01101110₂. Takže pravidlo 110 je definováno přechodovým pravidlem:

Úvahy a doplňky

Ačkoli existuje 256 možných pravidel, mnoho z nich je navzájem triviálně ekvivalentních až do jednoduché transformace podkladové geometrie. První taková transformace je odraz svislou osou a výsledek aplikace této transformace na dané pravidlo se nazývá zrcadlené pravidlo. Tato pravidla budou vykazovat stejné chování až do odrazu svislou osou, a proto jsou ekvivalentní ve výpočetním smyslu.

Například pokud se definice pravidla 110 odráží přes svislou čáru, získá se následující pravidlo (pravidlo 124):

Pravidla, která jsou stejná jako jejich zrcadlené pravidlo, se nazývají amfichirál. Z 256 elementárních celulárních automatů je 64 amfichirálních.

Druhou takovou transformací je výměna rolí 0 a 1 v definici. Výsledek aplikace této transformace na dané pravidlo se nazývá doplňkové pravidloNapříklad pokud se tato transformace použije na pravidlo 110, získáme následující pravidlo

a po změně pořadí zjistíme, že se jedná o pravidlo 137:

Existuje 16 pravidel, která jsou stejná jako jejich doplňková pravidla.

Nakonec lze předchozí dvě transformace aplikovat postupně na pravidlo k získání zrcadleného doplňkového pravidla. Například zrcadlené doplňkové pravidlo pravidla 110 je pravidlo 193. Existuje 16 pravidel, která jsou stejná jako jejich zrcadlená doplňková pravidla.

Z 256 elementárních celulárních automatů je 88, které jsou při těchto transformacích nerovné.

Single 1 historie

Jedna metoda používaná ke studiu těchto automatů je sledovat její historii s počátečním stavem všech 0 s výjimkou jedné buňky s 1. Když je číslo pravidla sudé (takže vstup 000 se nepočítá do 1), vytvoří smysl interpretovat stav pokaždé, t, jako celé číslo vyjádřené v binárním formátu, které vytváří sekvenci A(t) celých čísel. V mnoha případech mají tyto sekvence jednoduché uzavřené výrazy nebo mají a generující funkce s jednoduchou formou. Pozoruhodná jsou následující pravidla:

Pravidlo 28

Vygenerovaná sekvence je 1, 3, 5, 11, 21, 43, 85, 171, ... (sekvence A001045 v OEIS ). Toto je posloupnost Jacobsthal čísla a má generující funkci

${displaystyle {frac {1 + 2x} {(1 + x) (1-2x)}}}$.

Má výraz uzavřené formy

${displaystyle a (t) = {frac {4cdot 2 ^ {t} - (- 1) ^ {t}} {3}}}$

Pravidlo 156 generuje stejnou sekvenci.

Pravidlo 50

Vygenerovaná sekvence je 1, 5, 21, 85, 341, 1365, 5461, 21845, ... (sekvence A002450 v OEIS ). To má generující funkci

${displaystyle {frac {1} {(1-x) (1-4x)}}}$.

Má výraz uzavřené formy

${displaystyle a (t) = {frac {4cdot 4 ^ {t} -1} {3}}}$.

Všimněte si, že pravidla 58, 114, 122, 178, 186, 242 a 250 generují stejnou sekvenci.

Pravidlo 54

Vygenerovaná sekvence je 1, 7, 17, 119, 273, 1911, 4369, 30583, ... (sekvence A118108 v OEIS ). To má generující funkci

${displaystyle {frac {1 + 7x} {(1-x ^ {2}) (1-16x ^ {2})}}}$.

Má výraz uzavřené formy

${displaystyle a (t) = {frac {22cdot 4 ^ {t} -6 (-4) ^ {t} -4 + 3 (-1) ^ {t}} {15}}}$.

Pravidlo 60

Vygenerovaná sekvence je 1, 3, 5, 15, 17, 51, 85, 255, ... (sekvence A001317 v OEIS ). Toho lze dosáhnout po sobě jdoucími řádky Pascalův trojúhelník modulo 2 a interpretovat je jako celá čísla v binární podobě, která mohou být graficky znázorněna a Sierpinského trojúhelník.

Pravidlo 90

Vygenerovaná sekvence je 1, 5, 17, 85, 257, 1285, 4369, 21845, ... (sekvence A038183 v OEIS ). Toho lze dosáhnout po sobě jdoucími řádky Pascalův trojúhelník modulo 2 a interpretovat je jako celá čísla v základně 4. Pamatujte, že pravidla 18, 26, 82, 146, 154, 210 a 218 generují stejnou sekvenci.

Pravidlo 94

Vygenerovaná sekvence je 1, 7, 27, 119, 427, 1879, 6827, 30039, ... (sekvence A118101 v OEIS ). To lze vyjádřit jako

${displaystyle a (t) = {egin {cases} 1, & {mbox {if}} t = 0 [5px] 7, & {mbox {if}} t = 1 [7px] {dfrac {1 + 5cdot 4 ^ {n}} {3}}, a {mbox {if}} t {mbox {je i jinak}} [7px] {dfrac {10 + 11cdot 4 ^ {n}} {6}}, & { mbox {if}} t {mbox {je zvláštní jinak}} konec {případů}}}$.

To má generující funkci

${displaystyle {frac {(1 + 2x) (1 + 5x-16x ^ {4})} {(1-x ^ {2}) (1-16x ^ {2})}}}$.

Pravidlo 102

Vygenerovaná sekvence je 1, 6, 20, 120, 272, 1632, 5440, 32640, ... (sekvence A117998 v OEIS ). Jedná se jednoduše o sekvenci generovanou pravidlem 60 (což je jeho zrcadlové pravidlo) vynásobenou postupnými silami 2.

Pravidlo 110

Pravidlo 150

Vygenerovaná sekvence je 1, 7, 21, 107, 273, 1911, 5189, 28123, ... (sekvence A038184 v OEIS ). Toho lze dosáhnout pomocí koeficientů postupných mocnin (1+X+X²) modulo 2 a interpretovat je jako celá čísla v binární podobě.

Pravidlo 158

Vygenerovaná sekvence je 1, 7, 29, 115, 477, 1843, 7645, 29491, ... (sekvence A118171 v OEIS ). To má generující funkci

${displaystyle {frac {1 + 7x + 12x ^ {2} -4x ^ {3}} {(1-x ^ {2}) (1-16x ^ {2})}}}$.

Pravidlo 188

Vygenerovaná sekvence je 1, 3, 5, 15, 29, 55, 93, 247, ... (sekvence A118173 v OEIS ). To má generující funkci

${displaystyle {frac {1 + 3x + 4x ^ {2} + 12x ^ {3} + 8x ^ {4} -8x ^ {5}} {(1-x ^ {2}) (1-16x ^ {4 })}}}$.

Pravidlo 190

Vygenerovaná sekvence je 1, 7, 29, 119, 477, 1911, 7645, 30583, ... (sekvence A037576 v OEIS ). To má generující funkci

${displaystyle {frac {1 + 3x} {(1-x ^ {2}) (1-4x)}}}$.

Pravidlo 220

Vygenerovaná sekvence je 1, 3, 7, 15, 31, 63, 127, 255, ... (sekvence A000225 v OEIS ). Toto je posloupnost Mersennova čísla a má generující funkci

${displaystyle {frac {1} {(1-x) (1-2x)}}}$.

Má výraz uzavřené formy

${displaystyle a (t) = 2cdot 2 ^ {t} -1}$.

Všimněte si, že pravidlo 252 generuje stejnou sekvenci.

Pravidlo 222

Vygenerovaná sekvence je 1, 7, 31, 127, 511, 2047, 8191, 32767, ... (sekvence A083420 v OEIS ). Toto je každý další záznam v pořadí Mersennova čísla a má generující funkci

${displaystyle {frac {1 + 2x} {(1-x) (1-4x)}}}$.

Má výraz uzavřené formy

${displaystyle a (t) = 2cdot 4 ^ {t} -1}$.

Všimněte si, že pravidlo 254 generuje stejnou sekvenci.

Náhodný počáteční stav

Druhým způsobem, jak vyšetřit chování těchto automatů, je zkoumat jejich historii počínaje náhodným stavem. Toto chování lze lépe pochopit, pokud jde o třídy Wolfram. Následující příklady uvádí Wolfram jako typická pravidla každé třídy.^[1]

• Třída 1: Mobilní automaty, které rychle konvergují do jednotného stavu. Příkladem jsou pravidla 0, 32, 160 a 232.
• Třída 2: Mobilní automaty, které rychle konvergují do opakujícího se nebo stabilního stavu. Příkladem jsou pravidla 4, 108, 218 a 250.
• Třída 3: Mobilní automaty, které zřejmě zůstávají v náhodném stavu. Příkladem jsou pravidla 22, 30, 126, 150, 182.
• Třída 4: Buněčné automaty, které vytvářejí oblasti opakujících se nebo stabilních stavů, ale také vytvářejí struktury, které navzájem komplikovaně interagují. Příkladem je pravidlo 110. Ukázalo se, že článek 110 je schopen univerzální výpočet.^[2]

Každý vypočítaný výsledek je umístěn pod zdroj těchto výsledků a vytváří tak dvourozměrné znázornění vývoje systému. 88 nerovnocenných pravidel je následující a vyvinulo se z náhodných počátečních podmínek:

• 

  Pravidlo 0

• 

  Pravidlo 1

• 

  Pravidlo 2

• 

  Pravidlo 3

• 

  Pravidlo 4

• 

  Pravidlo 5

• 

  Pravidlo 6

• 

  Pravidlo 7

• 

  Pravidlo 8

• 

  Pravidlo 9

• 

  Pravidlo 10

• 

  Pravidlo 11

• 

  Pravidlo 12

• 

  Pravidlo 13

• 

  Pravidlo 14

• 

  Pravidlo 15

• 

  Pravidlo 18

• 

  Pravidlo 19

• 

  Pravidlo 22

• 

  Pravidlo 23

• 

  Pravidlo 24

• 

  Pravidlo 25

• 

  Pravidlo 26

• 

  Pravidlo 27

• 

  Pravidlo 28

• 

  Pravidlo 29

• 

  Pravidlo 30

• 

  Pravidlo 32

• 

  Pravidlo 33

• 

  Pravidlo 34

• 

  Pravidlo 35

• 

  Pravidlo 36

• 

  Pravidlo 37

• 

  Pravidlo 38

• 

  Pravidlo 40

• 

  Pravidlo 41

• 

  Pravidlo 42

• 

  Pravidlo 43

• 

  Pravidlo 44

• 

  Pravidlo 45

• 

  Pravidlo 46

• 

  Pravidlo 50

• 

  Pravidlo 51

• 

  Pravidlo 54

• 

  Pravidlo 56

• 

  Pravidlo 57

• 

  Pravidlo 58

• 

  Pravidlo 60

• 

  Pravidlo 62

• 

  Pravidlo 72

• 

  Pravidlo 73

• 

  Pravidlo 74

• 

  Pravidlo 76

• 

  Pravidlo 77

• 

  Pravidlo 78

• 

  Pravidlo 90

• 

  Pravidlo 94

• 

  Pravidlo 104

• 

  Pravidlo 105

• 

  Pravidlo 106

• 

  Pravidlo 108

• 

  Pravidlo 110

• 

  Pravidlo 122

• 

  Pravidlo 126

• 

  Pravidlo 128

• 

  Pravidlo 130

• 

  Pravidlo 132

• 

  Pravidlo 134

• 

  Pravidlo 136

• 

  Článek 138

• 

  Pravidlo 140

• 

  Pravidlo 142

• 

  Pravidlo 146

• 

  Pravidlo 150

• 

  Pravidlo 152

• 

  Pravidlo 154

• 

  Pravidlo 156

• 

  Pravidlo 160

• 

  Pravidlo 162

• 

  Pravidlo 164

• 

  Pravidlo 168

• 

  Pravidlo 170

• 

  Pravidlo 172

• 

  Pravidlo 178

• 

  Pravidlo 184

• 

  Pravidlo 200

• 

  Pravidlo 204

• 

  Pravidlo 232

Neobvyklé případy

V některých případech není chování buněčného automatu okamžitě zřejmé. Například pro pravidlo 62 se interagující struktury vyvíjejí jako ve třídě 4. Ale v těchto interakcích je alespoň jedna ze struktur zničena, takže automat nakonec vstoupí do opakovaného stavu a buněčný automat je třída 2.^[3]

Pravidlo 73 je třída 2^[4] protože kdykoli existují dvě po sobě jdoucí 1 s obklopené 0 s, je tato funkce zachována v následujících generacích. To efektivně vytváří stěny, které blokují tok informací mezi různými částmi pole. Existuje omezený počet možných konfigurací v sekci mezi dvěma stěnami, takže automat se musí nakonec začít opakovat uvnitř každé sekce, i když období může být velmi dlouhé, pokud je sekce dostatečně široká. Tyto stěny se vytvoří s pravděpodobností 1 pro zcela náhodné počáteční podmínky. Pokud je však přidána podmínka, že délky běhů po sobě jdoucích 0 s nebo 1 s musí být vždy liché, pak automat zobrazí chování třídy 3, protože stěny se nikdy nemohou vytvořit.

Pravidlo 54 je třída 4^[5] a také se jeví jako schopný univerzálního výpočtu, ale nebyl studován tak důkladně jako pravidlo 110. Bylo katalogizováno mnoho interagujících struktur, u nichž se souhrnně očekává, že budou dostatečné pro univerzálnost.^[6]

Reference

• Weisstein, Eric W. "Elementární mobilní automat". MathWorld.
• Weisstein, Eric W. „Pravidlo 30“. MathWorld.
• Weisstein, Eric W. „Pravidlo 50“. MathWorld.
• Weisstein, Eric W. „Pravidlo 54“. MathWorld.
• Weisstein, Eric W. „Pravidlo 60“. MathWorld.
• Weisstein, Eric W. „Pravidlo 62“. MathWorld.
• Weisstein, Eric W. „Pravidlo 90“. MathWorld.
• Weisstein, Eric W. „Pravidlo 94“. MathWorld.
• Weisstein, Eric W. „Pravidlo 102“. MathWorld.
• Weisstein, Eric W. „Pravidlo 110“. MathWorld.
• Weisstein, Eric W. „Pravidlo 126“. MathWorld.
• Weisstein, Eric W. „Pravidlo 150“. MathWorld.
• Weisstein, Eric W. „Pravidlo 158“. MathWorld.
• Weisstein, Eric W. „Pravidlo 182“. MathWorld.
• Weisstein, Eric W. „Pravidlo 188“. MathWorld.
• Weisstein, Eric W. „Pravidlo 190“. MathWorld.
• Weisstein, Eric W. „Pravidlo 220“. MathWorld.
• Weisstein, Eric W. „Pravidlo 222“. MathWorld.

externí odkazy

• "Elementární celulární automaty" na Wolfram Atlas jednoduchých programů
• 32 bajtů dlouhý spustitelný výkres systému MS-DOS celulárním automatem (Pravidlo 110 ve výchozím stavu)
• Přehlídka všech náhodně vybraných pravidel
• Minimální emulace CA s analyzátorem pravidel Wolfram online ve vanilkovém Javascriptu