Elementær cellulær automat

En elementær cellulær automat  er en cellulær automat med en endimensionel række af celler i form af et endeløst bånd på begge sider, som har to mulige celletilstande (0 og 1, "død" og "levende", "tom" og "udfyldt") og en regel for bestemmelse af cellens tilstand i det næste trin, der kun bruger cellens tilstand og dens to naboer i det aktuelle trin. Generelt er sådanne automater blandt de enklest mulige cellulære automater, men under visse regler viser de kompleks adfærd; Brug af regel 110 fører således til en Turing-komplet automat.

Wolfram-kode

I alt er der mulige kombinationer af cellens tilstand og dens to naboers tilstande. Reglen, der definerer den elementære cellulære automat, skal angive den næste tilstand (0 eller 1) for hvert af disse mulige tilfælde, så det samlede antal regler . Stephen Wolfram foreslog et nummereringsskema for disse regler, kendt som Wolfram - koden , som kortlægger hver regel til et tal mellem 1 og 255. Dette system blev først udgivet af Wolfram i et papir fra 1983 [1] og blev senere brugt i hans bog A New Kind of Science " ( Eng. Science of a new type ). [2]  

For at få Wolfram-koden skal du nedskrive de mulige konfigurationer (111, 110, ..., 001, 000) i faldende rækkefølge, skrive de tilsvarende tilstande ud under dem og fortolke den resulterende sekvens af nuller og enere som et tal i det binære talsystem . For eksempel resulterer følgende skema i kode svarende til regel 110 :

Refleksioner og tilføjelser

Nogle af de 256 regler er trivielt ækvivalente med hinanden på grund af tilstedeværelsen af ​​to slags transformationer. Den første er en refleksion om den lodrette akse, hvor venstre og højre naboer byttes om, og en spejlet regel opnås .  For eksempel bliver regel 110 til regel 118:

Blandt de 256 regler er der 64 spejlsymmetriske ( eng.  amphichiral ).

Den anden type transformation er udskiftningen af ​​rollerne 0 og 1 i definitionen, som giver en ekstra regel ( engelsk  komplementær regel ). For eksempel bliver regel 118 til regel 137:

Kun 16 regler ud af 256 falder sammen med deres tilføjelser. Op til dette par af transformationer (inklusive dem, der anvendes samtidigt - rækkefølgen er ikke vigtig), er der 88 ikke-ækvivalente elementære cellulære automater. [3]

Forskningsmetoder

Den enkleste konfiguration

En af metoderne til at studere elementære cellulære automater er at overveje udviklingen af ​​den enkleste indledende konfiguration, det vil sige kun bestående af én levende (indeholdende 1) celle. Hvis reglen har en lige Wolfram-kode, så er der ingen spontan generering af liv (kombinationen 000 giver ikke 1 i midten i næste generation), og derfor har hver tilstand af den simpleste konfiguration et endeligt tal, der ikke er nul celler og kan fortolkes som et tal i binær notation.[ hvordan? ] Rækkefølgen af ​​disse tal definerer en genererende funktion , som er rationel , det vil sige forholdet mellem to polynomier , og ofte har en relativt simpel form.

Tilfældige konfigurationer

Det er også nyttigt at overveje udviklingen af ​​tilfældige indledende konfigurationer. For at gøre dette er der en opdeling i følgende uformelle klasser af cellulære automater , opfundet af Wolfram: [4]

• Klasse 1: Konvergerer hurtigt til en tilstand af alle nuller eller ettaller. Wolfram nævner som eksempler reglerne 0, 32, 160, 232.
• Klasse 2: Konvergerer hurtigt til en cyklisk eller stabil tilstand. For eksempel regler 4, 108, 218, 250.
• Klasse 3: Opbevares i tilfældig tilstand. For eksempel regler 22, 30 , 126, 150, 182.
• Klasse 4: Der dannes både regioner med cykliske eller stabile tilstande, såvel som strukturer, der interagerer med hinanden på komplekse måder. Et eksempel er regel 110 , som er Turing komplet .