Autòmat cel·lular

De Viquipèdia
Salta a la navegació Salta a la cerca
Animació del Joc de la vida de Conway, un autòmat cel·lular.

Un autòmat cel·lular (A.C.) és un model matemàtic per a un sistema dinàmic que evoluciona en passos discrets. És adequat per modelar sistemes naturals que puguin ser descrits com una col·lecció massiva d'objectes simples que interaccionin localment uns amb els altres.[1][2]

Són sistemes descoberts dins de l'àmbit del camp de la física computacional per John von Neumann els anys 1950.[3] Tot i això, els autòmats cel·lulars van ser posats ja en pràctica per Konrad Zuse i Stanislaw Ulam uns anys abans.[4]

Descripció[modifica]

No hi ha una definició formal i matemàtica acceptada d'autòmat cel·lular però es pot descriure com una tupla, és a dir, un conjunt ordenat d'objectes caracteritzat pels següents components:

  • Una reixeta o quadriculat de nombres enters (conjunt ) infinitament estesa, i amb dimensió . Cada cel·la de la quadrícula rep el nom de cèl·lula.
  • Cada cèl·lula pot prendre un valor en a partir d'un conjunt finit d'estats .
  • Cada cèl·lula, a més, es caracteritza pel seu veïnatge, un conjunt finit de cèl·lules als seus voltants.
  • D'acord amb això, s'aplica a totes les cèl·lules de la quadrícula una funció de transició ( ) que pren com arguments els valors de la cèl·lula en qüestió i els valors de les cel·les veïnes, i torna el nou valor que la cèl·lula tindrà en la següent etapa de temps. Aquesta funció s'aplica de forma homogènia a totes les cèl·lules per cada pas discret de temps.

Condicions de frontera[modifica]

Per definició, un autòmat cel·lular consisteix en una retícula infinita d'enters. Tot i això, per qüestions pràctiques (com en models de sistemes físics duts a terme en ordinadors de memòria finita), es requereix prendre certes consideracions a l'hora d'implementar un autòmat. Per aquest motiu, la definició original es modifica per donar cabuda a retícules finites en les que les cèl·lules de l'autòmat interactuïn. Això comporta la consideració extra del que ha de succeir en aquelles cèl·lules que es trobin als marges de la retícula, el que es coneix com condició de frontera.

Es poden implementar diverses condicions de frontera, en funció d'allò que el problema real requereixi pel seu modelat. Per exemple:

  • Frontera oberta. Fora de la graella hi resideixen cèl·lules, totes amb un valor fix. En el cas particular del joc de la vida i altres autòmats similars amb dos estats al seu conjunt , una frontera s'anomena "freda" si les cèl·lules fora de la graella es consideren mortes, i "calenta" si es consideren vives.
  • Frontera periòdica. Es considera que la graella té una propietat toroidal, com si els seus extrems es toquessin. Per tant, si una cèl·lula surt de la graella, reapareix pel costat oposat.
  • Frontera reflectora. Les cèl·lules de fora la graella reflecteixen els valors de les de les de dins. Així, una cèl·lula que toqués la frontera per fora agafaria com a valor el de la cèl·lula que toca la frontera per dins.
  • Sense frontera. Fent ús d'implementacions que facin créixer dinàmicament l'ús de memòria de la graella implementada, es pot assumir que cada vegada que les cèl·lules han d'interactuar amb les de fora de la graella, aquesta es fa més gran per dur a terme aquestes interaccions. Tot i tendir a infinit, degut a que la frontera inicial és finita no és equivalent a la definició general de l'autòmat cel·lular, perquè en aquest cas no pots activar qualsevol cèl·lula de la graella des del principi.

Variacions[modifica]

Alguns autòmats cel·lulars tenen graella triangular o hexagonal enlloc de rectangular. També existeixen versions tridimensionals o amb moltes més dimensions, com en el cas dels autòmats cel·lulars quàntics. Altres possibles variacions són augmentar el nombre d'estats que cada cèl·lula pot tenir (com en el cas dels autòmats cel·lulars totalistes), la funció de transició de manera que ja no sigui homogènia, utilitzar elements estocàstics (aleatorietat) en (el que es coneix com autòmat cel·lular probabilístic) o variar els veïnatges de cada cèl·lula.

Aplicacions[modifica]

La closca de Conus textile mostra un patró caracteritzable en termes d'autòmats cel·lulars.

Els autòmats cel·lulars es poden usar per a modelar nombrosos sistemes físics que es caracteritzin per un gran nombre de components homogenis i que interaccionin localment entre ells. De fet, qualsevol sistema real al que se li puguin analogar els conceptes de "veïnatge", "estats dels components" i "funció de translació" és candidat per ser modelat per un A.C.

Les característiques dels autòmats cel·lulars faran que siguin discrets en temps, espai o les dues coses, depenent de la variant de la definició de A.C. que s'utilitzi. Alguns exemples d'ús són:

  • Modelat de flux de trànsit de vehicles i de vianants.
  • Modelat de fluxs (gasos o líquids).
  • Modelat de l'evolució de cèl·lules o virus com el VIH.
  • Modelat de processos de percolació.

Exemples d'autòmats cel·lulars[modifica]

Autòmat cel·lular unidimensional[modifica]

Animació que mostra la manera com les normes d'un autòmat cel·lular unidimensional determinen la següent generació. En l'exemple es mostra el Rule 30.
1-D A.C., cada iteració es mostra com una nova fila. Rule 30.

L'exemple més bàsic d'autòmat cel·lular no trivial és la versió unidimensional. Es defineix una seqüència de cèl·lules que només poden tenir dos estats, i es llegeixen ordenadament aplicant canvis segons l'estat de la cèl·lula i les seves veïnes (cèl·lula anterior i posterior). El resultat es sol mostrar com una nova línia a sota de l'actual que serà la llegida a continuació, i aquest procés es va repetint. El conjunt de normes que defineix el valor de la nova cèl·lula segons els estats de les cèl·lules comprovades s'anomena Rule Set, i hi ha 256 casos diferents.[5]

Per comprovar l'efecte al llarg del temps d'un determinat Rule Set, s'aplica a una seqüència senar de cèl·lules on totes estan desactivades excepte la del mig. A partir d'aquesta configuració inicial, els Rule Sets es poden classificar en amfiquirals o no amfiquirals segons si el patró format és simètric. A més, els patrons obtinguts es poden classificar en:[1]

  • Uniformes. Es genera un patró pla, on totes les cel·les acaben tenint el mateix estat. Exemple: Rule 222.
  • Oscil·lants. Es tendeix a un patró regular, per exemple [A, A, B, A, A, B ...] en el cas de Rule 190.
  • Atzarosos. S'obté un patró de pseudo-aleatorietat. Exemple: Rule 30.
  • Complexes. S'obtenen patrons regulars complexes, per exemple el Rule 110. Un altre exemple intessant és el Rule 90, on s'obté un patró similar al Triangle de Sierpinski.

Joc de la vida[modifica]

Article principal: Joc de la vida

El joc de la vida és un autòmat ortogonal bidimensional bàsic, creat per John Horton Conway el 1970. A cada unitat de temps, es donen les següents transicions:[6]

  1. Tota cel·la viva amb menys de dos veïns vius mor (de solitud).
  2. Tota cel·la viva amb més de tres veïns vius mor (de sobreconcentració).
  3. Tota cel·la viva amb dos o tres veïns vius, segueix viva per a la següent generació.
  4. Tota cel·la morta amb exactament tres veïns vius torna a la vida.

Per fer la comprovació s'utilitza el veïnatge de Moore, és a dir, les 8 cel·les veïnes de cada cel·la; adjacents i diagonals. Aquesta idea comprèn tot un seguit d'autòmats amb característiques similars, i per tant de la mateixa família que el joc de la vida.[7] En són exemples les llavors de Brian o el cervell de Brian, creades per Brian Silverman.[8]

En les llavors totes les cel·les vives moren i les mortes viuen si tenien exactament n veïns vius. El cervell de Brian és més complex; es parteix del joc de la vida però les cel·les tenen tres estats; vives, morint-se o mortes.[9]

Wireworld[modifica]

Wireworld és una modificació del joc de la vida on la majoria de cel·les no es poden activar, i la resta formen circuits conductors on les cel·les actives representen els electrons. Va ser proposat per Brian Silverman per simular transistors i portes lògiques. A més, Wireworld és Turing complet.[10]

Es defineixen quatre tipus de cel·les: buida, cap d'electró, cua d'electró i conducte.

  1. Tota cel·la buida segueix sent buida.
  2. El cap d'electró passa a ser cua.
  3. La cua d'electró passa a ser conducte.
  4. El conducte forma un cap d'electró si una o dues cel·les veïnes són caps d'electró, si no segueix sent conducte.

Formiga de Langton[modifica]

Article principal: Formiga de Langton

La formiga de Langton és un autòmat ortogonal bidimensional creat per Chris Langton. En aquest cas es defineix una cel·la especial que actua de formiga que es va desplaçant, i al fer-ho modifica els estats de les altres cel·les (al trepitjar una cel·la activada la desactiva, i al revés). La direcció de la formiga depèn de l'estat de la cel·la actual a la que es troba, si està activada fa un gir a dreta, si està desactivada fa un gir a l'esquerra.

Tot això és recreable com un autòmat normal definint més estats possibles per cada cèl·lula, segons si s'hi troba la formiga, segons la direcció d'aquesta i segons si la casella a la que es troba està activada o desactivada.[11]

Model Nagel-Schreckenberg[modifica]

Article principal: Model Nagel-Schreckenberg

El model Nagel-Schreckenberg és un autòmat cel·lular probabilístic unidimensional creat per Kai Nagel i Michael Schreckenberg que serveix de model simple de trànsit vehicular. En aquest cas el que varia segons els vehicles veïns és la velocitat del vehicle, i a més hi ha una certa probabilitat que el vehicle freni sense un motiu aparent.[12]

Autòmat d'Ulam–Warburton[modifica]

Article principal: Autòmat d'Ulam–Warburton

L'autòmat d'Ulam–Warburton (UWCA) és un autòmat ortogonal bidimensional que té la particularitat de que les cel·les activades no es poden tornar a desactivar. A cada iteració s'activen les cel·les inactivades en què només un dels costats és adjacent ortogonalment a una d'activada.[13]

Referències[modifica]

  1. 1,0 1,1 Wolfram, Stephen «Universality and Complexity in Cellular Automata». Physica D, 10, 1984, pàg. 1-35.
  2. Hedlund, G. A. «Endomorphisms and Automorphisms of the Shift Dynamical System». Mathematical Systems Theory, 3, 4, 1969.
  3. von Neumann, John. Arthur W. Burks. Theory of self-reproducing automata. Urbana, University of Illinois Press, 1966. 
  4. Zuse, Konrad «Rechnender Raum, Schriften zur Datenverarbeitung Band». Friedrich Vieweg & Sohn, Braunschweig, 1969.
  5. Kari, J. «The Nilpotency Problem of One-dimensional Cellular Automata». SIAM Journal on Computing, 21, 1992, pàg. 571-586.
  6. Gardner, Martin «The fantastic combinations of John Conway's new solitaire game 'life'». Scientific American, 223, 1970, pàg. 120-123.
  7. Wójtowicz, Mirek «Cellular Automaton Rules Lexicon - Family: Life». Mirek's Cellebration.
  8. Silverman, Brian. «Changing the Rules». The Virtual Computer. Mathematical Association of America. Arxivat de l'original el 2 de juliol de 2013.
  9. Resnick, Mitchel. «Exploring Emergence: The Brian Rules». MIT Media Laboratory, Lifelong Kindergarten Group, 04-02-1996. Arxivat de l'original el 2008-12-23.
  10. Dewdney, A. K. «Computer recreations: The cellular automata programs that create Wireworld, Rugworld and other diversions». Scientific American, 262, 1, 1990, pàg. 146-149. JSTOR: 24996654.
  11. Gajardo, A.; Moreira, A.; Goles, E. «Complexity of Langton's ant». Discrete Applied Mathematics, 117, 1-3, 2002, pàg. 41-50. DOI: 10.1016/S0166-218X(00)00334-6.
  12. Nagel, K.; Schreckenberg, M. «A cellular automaton model for freeway traffic». Journal de Physique I, 2, 12, 1992, pàg. 2221. Bibcode: 1992JPhy1...2.2221N. DOI: 10.1051/jp1:1992277.
  13. Applegate, David; Pol, Omar E.; Sloane, N. J. A. (2010). «The toothpick sequence and other sequences from cellular automata». Proceedings of the Forty-First Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congressus Numerantium. 206. pp. 157–191. arXiv: 1004.3036. Bibcode: 2010arXiv1004.3036A. MR: 2762248.

Vegeu també[modifica]

Bibliografia[modifica]

  • S. Wolfram, A New Kind of Science, 2002 (anglès) [Consulta: 28 març 2020]
  • B. Cipra, What's happening in the Mathematical Sciences, vols. 3 y 5, American Mathematical Society, EU, 1996, 2002

Enllaços externs[modifica]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Autòmat cel·lular