Regula 184

Regula 184 ( Eng.  Rule 184 ) este un automat celular elementar , adică un automat celular unidimensional cu două stări (0 și 1).

Definiție

Starea automatului celular este dată de o matrice liniară de celule, fiecare dintre ele conţinând o valoare binară (0 sau 1). La fiecare pas de evoluție, regula (în acest caz, regula 184) este aplicată simultan fiecărei celule ale matricei și determină noua sa stare după cum urmează:

O intrare din acest tabel definește noua stare a fiecărei celule în funcție de starea anterioară a acelei celule și de cei doi vecini ai săi din stânga și din dreapta.

Numele regulii este un cod Wolfram care descrie tabelul dat: linia de jos a tabelului (10111000) atunci când este tradusă din binar în zecimal, dă 8 + 16 + 32 + 128 = 184.

Regula 184 poate fi descrisă intuitiv în mai multe moduri diferite:

• La fiecare pas, perechile de stări de tip 10 sunt schimbate în perechi de tip 01. Pe baza acestei descrieri, Crag și Spon (1984) se referă la regula 184 ca o versiune deterministă a „ modelului cinetic Ising cu dinamică asimetrică a schimbului de spin”.

• La fiecare pas, celula din starea 1, la dreapta căreia se află celula din starea 0 ("spațiu liber"), se deplasează spre dreapta, eliberând spațiul ocupat. Această descriere corespunde unei aplicații legate de simularea fluxurilor de trafic.

• Dacă o celulă este în starea 0, atunci noua ei stare este luată din celula din stânga ei. În caz contrar, starea sa este preluată din celula din dreapta acesteia. Cu alte cuvinte, fiecare celulă poate fi implementată folosind un multiplexor și în acțiunea sa seamănă cu o poartă Fredkin [1] .

Evoluție

Din descrierea regulilor se pot deduce două proprietăți legate de dinamica regulilor. În primul rând, în timpul evoluției unui set finit de celule conform regulii 184 într-un automat cu condiții la limită periodice , numărul de celule în starea 1 (și 0) rămâne neschimbat. Într-o matrice de celule de lungime infinită, dacă se determină densitatea de distribuție a celulelor în starea 1, aceasta rămâne, de asemenea, neschimbată în timpul evoluției [2] .

În al doilea rând, deși regula 184 nu este simetrică în raport cu inversarea direcțiilor stânga și dreapta, ea are următoarea simetrie: inversarea direcțiilor stânga și dreapta cu inversarea simultană a rolurilor 1 și 0 duce la aceleași reguli de evoluție.

Într-un automat cu regula 184, modelele (secvențele stărilor celulelor) se stabilizează de obicei rapid, ducând la o secvență de stări care se mișcă într-una din cele două direcții [3] .

• Dacă densitatea inițială a „unilor” este mai mică de 50%, ca urmare a evoluției, apar grupuri de „uni” care se deplasează spre dreapta , separate prin „zerouri”; clusterele sunt separate prin blocuri de „zerouri”.
• Dacă densitatea inițială este mai mare de 50%, eșantionul evoluează în grupuri de „zerouri” care se deplasează spre stânga , separate prin „uni”; clusterele sunt separate prin grupuri de „unii”.
• Dacă densitatea inițială este de 50%, eșantionul se stabilizează mai lent într-o secvență de „unuri” și „zerouri” alternante, care pot fi considerate ca deplasări la stânga sau la dreapta cu succes egal.

Regula 184 ca model

Regula 184 ne permite să rezolvăm problema de clasificare a densității și să descriem mai multe sisteme de particule aparent diferite :

• Regula 184 poate fi folosită ca un model simplu de flux de trafic pe o autostradă cu o singură bandă și stă la baza multor modele microscopice de flux de trafic . Particulele reprezentând vehicule se deplasează în aceeași direcție, se opresc și încep să se miște în funcție de „starea” mașinilor aflate direct în fața lor. Numărul de particule rămâne neschimbat pe toată durata simulării. În legătură cu această cerere, regula 184 este numită și „regula drumului” [4] .

• În fizica aerosolilor , regula 184 este folosită pentru a simula depunerea a particulelor pe o suprafață neregulată, unde la următoarea etapă de simulare, fiecare minim local al suprafeței este umplut cu o particulă. În timpul simulării, numărul de particule crește; particula plasată nu se mișcă.

• Automatul regula 184 poate fi privit în contextul anihilării balistice ca un sistem de particule care se mișcă în stânga și în dreapta într-un mediu unidimensional. Când două particule se ciocnesc, ele se anihilează , astfel încât la fiecare pas numărul de particule rămâne același sau scade.

Aparentele contradicții dintre aceste descrieri sunt rezolvate prin diferența dintre modalitățile de stabilire a relației dintre proprietățile automatului celular și elementele problemei.

Primele studii ale regulii 184 par să fi fost făcute de Lee (1987) și Krug și Spon (1988). În special, Krug și Spon au descris toate cele trei tipuri de sisteme de particule modelate folosind regula 184 [5] .

Note

1. ↑ Li (1992).
2. ↑ Boccara și Fukś (1998) și Moreira (2003) au explorat o clasă mai generală de automate celulare cu legi de conservare similare .
3. ↑ Li (1987).
4. ↑ Vezi, de exemplu, Fukś (1997).
5. ↑ În multe lucrări ulterioare, când se face referire la regula 184, se fac referiri la articolele timpurii ale lui Stephen Wolfram , în care, totuși, erau considerate numai automate care sunt simetrice în ceea ce privește schimbarea direcției stânga și dreapta și, prin urmare, regula 184. nu a fost luată în considerare.

Literatură

• Fukś, Henryk. Rezolvarea problemei de clasificare a densității cu două reguli similare de automate celulare  (engleză)  // Physical Review E  : journal. - 1997. - Vol. 55 , nr. 3 . - P.R2081-R2084 . - doi : 10.1103/PhysRevE.55.R2081 . - Cod .
• Fukś, Henryk; Boccara, Nino. Reguli de circulație deterministe generalizate  (neopr.)  // Journal of Modern Physics C. - 1998. - V. 9 , Nr. 1 . - S. 1-12 . - doi : 10.1142/S0129183198000029 . — Cod biblic . Arhivat din original pe 27 septembrie 2007.
• Li, Wentian. Spectrele de putere ale limbajelor obișnuite și ale automatelor celulare  (engleză)  // Sisteme complexe: jurnal. - 1987. - Vol. 1 . - P. 107-130 . Arhivat din original pe 7 octombrie 2007.
• Li, Wentian. Fenomenologia automatelor celulare nonlocale  //  Journal of Statistical Physics : jurnal. - 1992. - Vol. 68 , nr. 5-6 . - P. 829-882 ​​. - doi : 10.1007/BF01048877 . - Cod biblic .
• Moreira, Andres. Universalitatea și determinabilitatea automatelor celulare care conservă numerele  (engleză)  // Teoretică Informatică: jurnal. - 2003. - Vol. 292 , nr. 3 . - P. 711-721 . - doi : 10.1016/S0304-3975(02)00065-8 . - arXiv : nlin.CG/0306032 .

Link -uri

• Regula 184 Arhivat la 30 octombrie 2010 la Wayback Machine într-un atlas de Stephen Wolfram
• Simulator Java Arhivat 3 septembrie 2010 la Wayback Machine (simulare pe o matrice inelă de celule, lungimea matricei este fixă, regula 184 este setată implicit)