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.
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 :
nuvarande tillstånd | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
---|---|---|---|---|---|---|---|---|
framtida tillstånd | 0 | ett | ett | 0 | ett | ett | ett | 0 |
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:
nuvarande tillstånd | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
---|---|---|---|---|---|---|---|---|
framtida tillstånd | 0 | ett | ett | ett | 0 | ett | ett | 0 |
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:
nuvarande tillstånd | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
---|---|---|---|---|---|---|---|---|
framtida tillstånd | ett | 0 | 0 | 0 | ett | 0 | 0 | ett |
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]
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.
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]
Vissa regler kan inte entydigt tilldelas en av klasserna, till exempel:
Conways Game of Life och andra cellulära automater | |||||
---|---|---|---|---|---|
Konfigurationsklasser | |||||
Konfigurationer |
| ||||
Villkor | |||||
Andra rymdskepp på ett tvådimensionellt gitter |
| ||||
Endimensionell rymdfarkost | |||||
Programvara och algoritmer |
| ||||
KA-forskare |