Regel 184
Regel 184 ( Eng. Rule 184 ) er en elementær cellulær automat , det vil sige en endimensionel cellulær automat med to tilstande (0 og 1).
Definition
Tilstanden af den cellulære automat er givet af et lineært array af celler, som hver indeholder en binær værdi (0 eller 1). Ved hvert udviklingstrin anvendes reglen (i dette tilfælde regel 184) samtidigt på hver af arraycellerne og bestemmer dens nye tilstand som følger:
| Cellens
nuværende nabolag |
111
|
110
|
101
|
100
|
011
|
010
|
001
|
000
|
| Ny tilstand af cellen
|
en
|
0
|
en
|
en
|
en
|
0
|
0
|
0
|
En post i denne tabel definerer den nye tilstand for hver celle afhængigt af den tidligere tilstand for den celle og dens to naboer til venstre og højre.
Navnet på reglen er en Wolfram-kode, der beskriver den givne tabel: den nederste linje i tabellen (10111000), når den oversættes fra binær til decimal giver 8 + 16 + 32 + 128 = 184.
Regel 184 kan beskrives intuitivt på flere forskellige måder:
- Ved hvert trin ændres tilstandspar af type 10 til par af type 01. Baseret på denne beskrivelse henviser Crag og Spon (1984) til regel 184 som en deterministisk version af den "kinetiske Ising-model med asymmetrisk spin-udvekslingsdynamik".
- Ved hvert trin flytter cellen i tilstand 1, til højre for hvilken er cellen i tilstand 0 ("fri plads"), til højre og frigør den optagede plads. Denne beskrivelse svarer til en applikation relateret til simulering af trafikstrømme.
- Hvis en celle er i tilstand 0, tages dens nye tilstand fra cellen til venstre for den. Ellers tages dens tilstand fra cellen til højre for den. Med andre ord kan hver celle implementeres ved hjælp af en multiplekser og i sin handling ligner en Fredkin-port [1] .
Evolution
Ud fra beskrivelsen af reglerne kan der udledes to egenskaber relateret til reglernes dynamik. For det første forbliver antallet af celler i tilstand 1 (og 0) uændret under udviklingen af et endeligt sæt celler i henhold til regel 184 i en automat med periodiske grænsebetingelser I et array af celler af uendelig længde, hvis fordelingstætheden af celler i tilstand 1 bestemmes, forbliver den også uændret under evolutionen [2] .
For det andet, selvom regel 184 ikke er symmetrisk med hensyn til vending af venstre og højre retning, har den følgende symmetri: vendingen af venstre og højre retninger med den samtidige vending af rollerne 1 og 0 fører til de samme evolutionsregler.
I en automat med regel 184 stabiliseres mønstre (sekvenser af celletilstande) normalt hurtigt, hvilket fører til en sekvens af tilstande, der bevæger sig i en af to retninger [3] .
- Hvis den oprindelige tæthed af "enere" er mindre end 50%, som et resultat af evolution, vises klynger af "enere", der bevæger sig til højre , adskilt af "nuller"; klynger er adskilt af blokke af "nuller".
- Hvis den oprindelige tæthed er større end 50 %, udvikler prøven sig til klynger af "nuller", der bevæger sig til venstre , adskilt af "enere"; klynger er adskilt af grupper af "enere".
- Hvis den oprindelige tæthed er 50%, stabiliserer prøven langsommere til en sekvens af skiftende "etler" og "nuller", som kan betragtes som at bevæge sig til venstre eller højre med lige stor succes.
Regel 184 som model
Regel 184 giver os mulighed for at løse tæthedsklassificeringsproblemet og beskrive flere tilsyneladende forskellige partikelsystemer :
- Regel 184 kan bruges som en simpel trafikstrømsmodel på en enkeltsporet motorvej og ligger til grund for mange mikroskopiske trafikstrømsmodeller . Partikler, der repræsenterer køretøjer, bevæger sig i samme retning, stopper og begynder at bevæge sig afhængigt af "tilstanden" af bilerne lige foran dem. Antallet af partikler forbliver uændret under hele simuleringen. I forbindelse med denne ansøgning kaldes regel 184 også "vejreglen" [4] .
- I aerosolfysik bruges regel 184 til at simulere aflejringen af partikler på en uregelmæssig overflade, hvor hvert lokalt minimum af overfladen ved næste simuleringstrin er fyldt med en partikel. Under simuleringen stiger antallet af partikler; den placerede partikel bevæger sig ikke.
- Regel 184-automaten kan ses i sammenhæng med ballistisk udslettelse som et system af partikler, der bevæger sig til venstre og højre i et endimensionelt miljø. Når to partikler støder sammen, udsletter de hinanden, så antallet af partikler ved hvert trin forbliver det samme eller falder.
De tilsyneladende modsætninger mellem disse beskrivelser er løst af forskellen i måderne at etablere forholdet mellem egenskaberne af den cellulære automat og elementerne i problemet.
De første undersøgelser af regel 184 synes at være udført af Lee (1987) og Krug og Spon (1988). Specielt beskrev Krug og Spon alle tre typer partikelsystemer modelleret ved hjælp af 184-reglen [5] .
Noter
- ↑ Li (1992).
- ↑ Boccara og Fukś (1998) og Moreira (2003) udforskede en mere generel klasse af cellulære automater med lignende bevarelseslove .
- ↑ Li (1987).
- ↑ Se for eksempel Fukś (1997).
- ↑ I mange senere værker, når der refereres til regel 184, henvises der til tidlige artikler af Stephen Wolfram , hvori der dog kun blev betragtet automater, der er symmetriske med hensyn til ændringen af venstre og højre retning og derfor regel 184 blev ikke overvejet.
Litteratur
- Fukś, Henryk. Løsning af tæthedsklassificeringsproblemet med to lignende cellulære automata-regler (engelsk) // Physical Review E : journal. - 1997. - Bd. 55 , nr. 3 . - P.R2081-R2084 . - doi : 10.1103/PhysRevE.55.R2081 . - .
- Fukś, Henryk; Boccara, Nino. Generaliserede deterministiske trafikregler (neopr.) // Journal of Modern Physics C. - 1998. - V. 9 , nr. 1 . - S. 1-12 . - doi : 10.1142/S0129183198000029 . — . Arkiveret fra originalen den 27. september 2007.
- Li, Wentian. Kraftspektre for almindelige sprog og cellulære automater (engelsk) // Complex Systems: journal. - 1987. - Bd. 1 . - S. 107-130 . Arkiveret fra originalen den 7. oktober 2007.
- Li, Wentian. Fænomenologi af ikke-lokale cellulære automater // Journal of Statistical Physics : journal. - 1992. - Bd. 68 , nr. 5-6 . - s. 829-882 . - doi : 10.1007/BF01048877 . - .
- Moreira, Andres. Universalitet og afgørelighed af talbevarende cellulære automater (engelsk) // Teoretisk computervidenskab: tidsskrift. - 2003. - Bd. 292 , nr. 3 . - s. 711-721 . - doi : 10.1016/S0304-3975(02)00065-8 . - arXiv : nlin.CG/0306032 .
Links