Elementär cellulär automat

En elementär cellulär automat  är en cellulär automat med en endimensionell uppsättning celler i form av ett ändlöst band på båda sidor, som har två möjliga celltillstånd (0 och 1, "död" och "levande", "tom" och "fylld") och en regel för att bestämma tillståndet för cellen i nästa steg, genom att endast använda tillståndet för cellen och dess två grannar i det aktuella steget. I allmänhet är sådana automater bland de enklast möjliga cellulära automaterna, men under vissa regler visar de komplext beteende; att använda regel 110 leder alltså till en Turing-komplett automat.

Wolfram-kod

Totalt finns det möjliga kombinationer av cellens tillstånd och tillstånden för dess två grannar. Regeln som definierar den elementära cellulära automaten måste ange nästa tillstånd (0 eller 1) för vart och ett av dessa möjliga fall, så det totala antalet regler . Stephen Wolfram föreslog ett numreringsschema för dessa regler, känt som Wolfram - koden , som mappar varje regel till ett tal mellan 1 och 255. Detta system publicerades först av Wolfram i en tidning 1983 [1] och användes senare i hans bok A New Kind of Science " ( Eng. Science of a new type ). [2]  

För att få Wolfram-koden måste du skriva ner de möjliga konfigurationerna (111, 110, ..., 001, 000) i fallande ordning, skriva ut motsvarande tillstånd under dem och tolka den resulterande sekvensen av nollor och ettor som ett tal i det binära talsystemet . Till exempel resulterar följande schema i kod som motsvarar regel 110 :

Reflektioner och tillägg

Några av de 256 reglerna är trivialt likvärdiga med varandra på grund av närvaron av två typer av transformationer. Den första är en reflektion kring den vertikala axeln, där de vänstra och högra grannarna byts om och en spegelvänd regel erhålls .  Till exempel, regel 110 blir regel 118:

Bland de 256 reglerna finns 64 spegelsymmetriska ( eng.  amphichiral ).

Den andra typen av transformation är ersättningen av rollerna 0 och 1 i definitionen, vilket ger en extra regel ( engelsk  komplementär regel ). Till exempel blir regel 118 regel 137:

Endast 16 regler av 256 sammanfaller med deras tillägg. Upp till detta par av transformationer (inklusive de som tillämpas samtidigt - ordningen är inte viktig), finns det 88 icke-ekvivalenta elementära cellulära automater. [3]

Forskningsmetoder

Den enklaste konfigurationen

En av metoderna för att studera elementära cellulära automater är att överväga utvecklingen av den enklaste initiala konfigurationen, det vill säga bestående av endast en levande (innehållande 1) cell. Om regeln har en jämn Wolfram-kod, så finns det ingen spontan generering av liv (kombinationen 000 ger inte 1 i mitten i nästa generation), och därför har varje tillstånd av den enklaste konfigurationen ett ändligt antal icke-noll celler och kan tolkas som ett tal i binär notation.[ hur? ] Sekvensen av dessa siffror definierar en genererande funktion , som är rationell , det vill säga förhållandet mellan två polynom , och har ofta en relativt enkel form.

Slumpmässiga konfigurationer

Det är också användbart att överväga utvecklingen av slumpmässiga initiala konfigurationer. För att göra detta finns det en uppdelning i följande informella klasser av cellulära automater , uppfunna av Wolfram: [4]

• Klass 1: Konvergerar snabbt till ett tillstånd av alla nollor eller ettor. Wolfram nämner som exempel reglerna 0, 32, 160, 232.
• Klass 2: Konvergerar snabbt till ett cykliskt eller stabilt tillstånd. Till exempel regler 4, 108, 218, 250.
• Klass 3: Lagras i slumpmässigt tillstånd. Till exempel regler 22, 30 , 126, 150, 182.
• Klass 4: Båda regionerna med cykliska eller stabila tillstånd bildas, såväl som strukturer som interagerar med varandra på komplexa sätt. Ett exempel är regel 110 , som är Turing komplett .