Model de la pila de sorra

autòmat cel·lular dissenyat per analitzar i explicar el comportament d'autoorganització a través de la teoria de grafs i la teoria d'autòmats cel·lulars

El model de la pila de sorra, també conegut com a model Bak–Tang–Wiesenfeld (BTW), és un autòmat cel·lular dissenyat per analitzar i explicar el comportament d'autoorganització a través de la teoria de grafs i la teoria d'autòmats cel·lulars, utilitzant eines algebraiques.[1][2] Va ser el primer exemple descobert d'un sistema dinàmic que mostra autoorganització crítica, és a dir, que té punts crítics com un atractor en la seva evolució temporal. Fou introduït l'any 1987 per Per Bak, Chao Tang i Kurt Wiesenfeld.[3]

Element identitat d'una graella rectangular. Els colors representen el nombre de grans a cada cel·la; daurat (3), lila (2), verd (1), i negre (0).

En la seva formulació original, cada cel·la d'una graella finita té un valor associat que correspon a l'alçada de la pila. Si se sobrepassa un llindar d'alçada màxima en una cel·la, aquesta passa una unitat a cadascuna de les cel·les adjacents.

Funcionament de la pila de sorra. Exemple d'addició amb la identitat, obtenint la mateixa configuració de grans de sorra que en l'original.

DescripcióModifica

Al model BTW original, es descriu una graella quadrada finita N x N ( ) amb grans de sorra distribuïts a l'atzar. Cada vegada que s'afegeix un nou gra a un punt a l'atzar, pot provocar una redistribució en cadena dels altres grans, a vegades afectant una gran quantitat de cel·les com si es tractés d'una allau. Quan una de les cel·les dels marges es redistribueix, els grans que anirien fora de la graella desapareixen del sistema.[2] A causa d'aquest buidatge, per qualsevol distribució amb punts crítics finits (cel·les amb un nombre finit de grans, però que està per sobre del llindar necessari per provocar la redistribució), està garantit que després d'un nombre finit d'iteracions s'arribarà a un estat estable en la graella. Una única cel·la amb un nombre de grans molt per sobre del llindar és capaç de crear una allau molt extensa i fer que el sistema s'auto-organitzi fins a arribar a una configuració estable.

L'addició de graelles (indicada amb el símbol  ) funciona sumant els grans cel·la per cel·la, i posteriorment resolent-la fins a arribar a la posició estable.[4]

L'element identitat correspon a una configuració de grans que en afegir-la a la distribució actual de grans de la graella, i posteriorment a tota la redistribució de grans, es torna a la distribució original. Aquesta identitat actua, per tant, com a valor "zero" de la funció de redistribució per aquella graella.

Es defineix com   el conjunt de totes les possibles configuracions de grans de sorra en una determinada graella. En aquest cas, l'element identitat correspon a aquella on totes les cel·les tenen 0 grans, també anomenada graella mínima o buida. D'altra banda, la graella màxima correspon a aquella on totes les cel·les tenen el màxim de grans possibles. Es pot obtenir un subconjunt   a partir de totes les graelles obtingudes de sumar cada possible configuració de   a la graella màxima.

Aquest subconjunt   no pot incloure la graella mínima, però segueix incloent un element identitat   que actua com a "zero" específicament per aquell subconjunt. Per tant, si i només si una graella   es troba al subconjunt  , es compleix que  .[5] El subconjunt   també té la particularitat que per cada graella   es pot trobar una graella   també inclosa al subconjunt de tal manera que  .[6]

Obtenció de l'element identitatModifica

El mètode per obtenir l'element identitat   per una determinada graella, independentment de la seva forma, funciona de la següent manera:[7]

  • Es defineix al voltant de la graella un pla on totes les cel·les tenen un excés de grans de sorra, mentre que la graella en si mateixa no conté cap gra.
  • S'aplica un sol pas en l'algorisme de distribució. La graella resultant s'anomena graella generadora, perquè actua com una funció generadora de l'element identitat.
  • Es parteix d'una graella buida, de forma que se li va sumant la graella generadora repetidament, i es resol a l'estat estable cada vegada. Finalment, s'arriba a un punt d'equilibri en el qual la graella resultant és igual que la graella anterior a la darrera addició; aquesta correspon a l'element identitat.[8]

Generalització per models infinitsModifica

 
Redistribució en una graella infinita després d'haver col·locat 30 milions de grans en una única cel·la. Els colors representen en nombre de grans en cada cel·la; daurat (3), lila (2), verd (1) i blanc (0). El quadre de delimitació és de 3967 × 3967 cel·les.

Existeixen diverses generalitzacions del model en graelles infinites. El repte en aquest cas és que, en general, ja no està garantit que les allaus arribin a aturar-se a un estat estable. Per això, moltes de les generalitzacions consideren només l'estabilització de configuracions en les quals això està garantit. Un d'aquests casos especials es dóna quan tota la graella està buida excepte un únic punt inicial amb una quantitat de grans molt elevat. En aquest cas, la gran allau resultant forma patrons fractals.[9] Quan aquest nombre inicial de grans tendeix a infinit, s'ha demostrat que les configuracions estabilitzades amb escala normalitzada convergeixen fins a un límit únic.[10]

Altres generalitzacions i variantsModifica

El model es pot generalitzar per graelles no rectangulars; exemples típics en són la graella en forma de diamant o la corresponent a una matriu triangular. També es pot variar la forma de les cel·les, per exemple els models amb cel·les triangulars o amb cel·les hexagonals.[11]

Una altra manera d'obtenir variants és modificant l'algorisme de distribució. Si la cel·la desplaça els grans a les diagonals en lloc de les adjacents, com una peça Ferz d'escacs màgics, llavors la graella queda dividida com en un escaquer amb dues graelles diagonals en forma de diamant que se superposen sense interactuar. Altres adaptacions poden implicar un augment del nombre màxim de grans per cel·la, per exemple emprant un veïnatge de Moore (adjacents i diagonals) en lloc del veïnatge de Neumann del model clàssic, o bé desplaçant els grans com un cavall d'escacs, en forma de creu, etcètera. Alternativament es pot considerar el model clàssic un desplaçament a les cel·les amb una distància de Manhattan  , i per tant generalitzar-lo per a qualsevol  .

ReferènciesModifica

  1. Ivashkevich, E.V.; Priezzhev, V.B. «Introduction to the sandpile model». Physica A: Statistical Mechanics and its Applications, 254, 1-2, 1998, pàg. 97-116. DOI: 10.1016/S0378-4371(98)00012-0.
  2. 2,0 2,1 Levine, Lionel; Propp, James «What is... a sandpile?» (PDF). Notices of the AMS, 57, 2010, pàg. 976-9.
  3. Bak, P.; Tang, C.; Wiesenfeld, K. «Self-organized criticality: an explanation of 1/ƒ noise». Physical Review Letters, 59, 4, 1987, pàg. 381-384. Bibcode: 1987PhRvL..59..381B. DOI: 10.1103/PhysRevLett.59.381. PMID: 10035754.
  4. Dhar, Deepak; Ruelle, Philippe; Sen, S.; Verma, D.-N. «Algebraic aspects of abelian sandpile models». Journal of Physics A: Mathematical and General, 28, 1994, pàg. 805-831.
  5. Creutz, Michael «Playing with sandpiles» (PDF). Brookhaven National Laboratory, 2004, pàg. 4.
  6. Doman, Noah «The Identity of the Abelian Sandpile Group» (PDF). University of Groningen, 2020.
  7. Dartois, Arnaud; Magnien, Clémence «Results and conjectures on the Sandpile Identity on a lattice». DBLP, 2003, pàg. 89-102.
  8. Járai, Antal A. «Sandpile models». Probab. Surveys, 15, 243, 2018, pàg. 260-261. arXiv: 1401.0354. DOI: https://doi.org/10.1214/14-PS228.
  9. Pegden, Wesley & Smart, Charles (2017), "Stability of patterns in the Abelian sandpile.", arΧiv:1708.09432 [math.AP]
  10. Pegden, Wesley; Smart, Charles «Convergence of the Abelian sandpile». Duke Mathematical Journal, 162, 4, 2013, pàg. 627–642. arXiv: 1105.0111. DOI: 10.1215/00127094-2079677.
  11. Poncelet, Adrien; Ruelle, Philippe «Sandpile probabilities on triangular and hexagonal lattices» (PDF). Université catholique de Louvain, Institut de recherche en mathématique et physique [Louvain-la-Neuve, Belgium], 2, 1348, 2018. arXiv: 1708.03493.

Vegeu tambéModifica

BibliografiaModifica

Enllaços externsModifica