Autómata celular

Autómata celular

Un autómata celular (A.C.) és un model matemàtic i computacional per a un sistema dinàmic que evoluciona en passos discrets. És adequat per a modelar sistemes naturals que puguen ser descrits com una colecció massiva d'objectes simples que interactuen localment uns en uns atres.

És un model matemàtic per a un sistema dinàmic que consistix en una reixeta formada per celes que poden canviar d'estat o no depenent diverses lleis. És un espai regular. Té un conjunt d'estats finit i cada element pren un valor d'este conjunt d'estats. Presenta una funció de transició local que és la regla d'evolució que determina el comportament de l'autómata.

La definició d'un A.C. requerix mencionar els seus elements bàsics:

• Un espai regular: Ya siga una llínea, un pla de 2 dimensions o un espai n-dimensional. Cada divisió homogénea de l'espai és cridada cèlula.
• Conjunt d'Estats: És finit i cada element o cèlula de l'espai pren un valor d'este conjunt d'estats. També es denomina alfabet. Pot ser expressat en valors o colors.
• Configuració Inicial: És l'assignació inicial d'un estat a cada una de les cèlules de l'espai.
• Veïnats: Definix el conjunt de cèlules que es consideren adjacents a una donada, aixina com la posició relativa respecte a ella. Quan l'espai és uniforme, el veïnat de cada cèlula és isomorfa (és dir, que té el mateix aspecte).
• Funció de Transició Local: És la regla d'evolució que determina el comportament de el A.C. Es calcula a partir de l'estat de la cèlula i el seu veïnat. Definix cóm deu canviar d'estat cada cèlula depenent el seu estat anterior i dels estats anteriors del seu veïnat. Sol donar-se com una expressió algebraica o un grup d'equacions.

Es classifiquen principalment de la següent manera:

• Classe I: Du a un estat homogéneu perdent la aleatorietat de l'estat inicial.

Classe II: Es generen estructures cíclicas, separades i simples. Els canvis en la configuració inicial només afecten una regió finita de cèlules propenques Classe III: Casi tots els patrons inicials evolucionen de forma caòtica. Els canvis en la configuració inicial tendixen a propagar-se indefinidament. Classe IV: Es produïxen estructures complexes no explicades per les classes anteriors. Tenen combinació de patrons cíclicos i comportament aleatori

Són sistemes descoberts dins del camp de la física computacional per John von Neumann en la década de 1950. La teoria dels autómates celulars s'inicia en el seu precursor John von Neumann a finals de la década de 1940 en el seu llibre Theory of Self-reproducing Automata (editat i completat per A. W. Burks).

Encara que John von Neumann va posar en pràctica els AA.CC., estos varen ser concebuts en els anys 40 per Konrad Zuse i Stanislaw Ulam. Zuse va pensar en els “espais de còmput” (computing spaces), com a models discrets de sistemes físics. Les contribucions de Ulam varen vindre al final dels 40, poc despuix d'haver inventat en Nicholas Metropolis el Método de Montecarlo.

¿Qué compon a un autómata celular?

La seua característica principal és la seua capacitat de conseguir una série de propietats emergents que sorgixen de la pròpia dinàmica local a través del temps i no des d'un inici. Per lo tant, no és fàcil predir les propietats globals d'un AC des del seu començ, sent complex per naturalea. La definició d'un AC requerix mencionar els seus elements bàsics:

• Un espai celular
• Conjunt d'Estats
• Veïnats.
• Regles de transició.

• La geometria dels veïnats és el conjunt de cèlules que rodeja a una cèlula que s'està analisant. Existixen dos tipos comuns de veïnats en els AC d'espai bidimensional en reixeta quadrada:
  • Von-Neuman. Considera 4 cèlules veïnes, és dir, la de dalt, avall, esquerra i dreta.
  • Moor. Considera 8 cèlules veïnes, incloent les del veïnat de Von Neumann més els quatre cantons.

Descripció

No existix una definició formal i matemàtica acceptada d'autómata celular; no obstant, es pot descriure a un A.C. com una tupla, és dir, un conjunt ordenat d'objectes caracterisat pels següents components:

• Una reixeta o cuadriculado (lattice) de sancers (conjunt $\mathbb{Z}$) infinitament estesa, i en dimensió $d\in {\mathbb{Z}}^{+}$. Cada cela de la cuadrícula es coneix com cèlula.
• Cada cèlula pot prendre un valor en $\mathbb{Z}$ a partir d'un conjunt finit d'estats $k$.
• Cada cèlula, ademés, es caracterisa per la seua veïnat, un conjunt finit de cèlules en les rodalies de la mateixa.
• D'acort en açò, s'aplica a totes les cèlules de la cuadrícula una funció de transició ( $f$ ) que pren com a arguments els valors de la cèlula en qüestió i els valors dels seus veïns, i retorna el nou valor que la cèlula tindrà en la següent etapa de temps. Esta funció $f$ s'aplica, com ya es va dir, de forma homogénea a totes les cèlules, per cada pas discret de temps.

Condicions de frontera

Topología de l'autómata celular de 2D plegat en 3D per al cas de frontera periòdica.

Per definició, un A.C. consistix en una retícula infinita de sancers. No obstant, per a qüestions pràctiques (com en models de sistemes físics portats a terme en ordenadors de memòria finita), es requerix prendre certes consideracions a l'hora d'implementar un A.C. Per això, la definició original es modifica per a donar cabuda a retículas finitas en les que les cèlules del A.C. interactuen. Açò comporta la consideració extra de lo que deu succeir en aquelles cèlules que es troben en els vores de la retícula. A l'implementació d'una o vàries consideracions específiques se li coneix com a condició de frontera.

Dins de l'àmbit dels A.C., es poden implementar numeroses condicions de frontera, en funció de lo que el problema real requerixca per a la seua modelació. Per eixemple:

• Frontera oberta. Es considera que fòra de la lattice residixen cèlules, totes en un valor fix. En el cas particular del joc de la vida i d'atres A.C. en dos estats en el seu conjunt $k$, una frontera es diu frigga si les cèlules fòra de la frontera es consideren mortes, i calenta si es consideren vives.
• Frontera periòdica. Es considera a la lattice com si els seus extrems es tocaren. En una lattice de dimensió 1, açò pot visualisar-se en dos dimensions com una circumferència. En dimensió 2, la lattice podria visualisar-se en tres dimensions com un toroide.
• Frontera reflectora. Es considera que les cèlules fòra de la lattice "reflectixen" els valors d'aquelles dins de la lattice. Aixina, una cèlula que estiguera junt a la vora de la lattice (fòra d'ella) prendria com a valor el de la cèlula que estiga junt a la vora de la lattice, dins d'ella.
• Sense frontera. Fent us d'implementacions que facen créixer dinàmicament l'us de memòria de la lattice implementada, es pot assumir que cada volta que les cèlules deuen interactuar en cèlules fòra de la lattice, esta es fa més gran per a donar cabuda a estes interaccions. Òbviament, existix un llímit (impost per la memòria disponible) per a esta condició. És molt important no confondre esta condició de frontera en la definició original de A.C. que la seua lattice és inicialment infinita. En el cas d'un A.C. sense frontera, la lattice comença en un tamany definit i finit, i conforme es requerixca va creixent en el temps, lo que no ho fa necessàriament un model més propenc a la realitat, puix si es inicializara la lattice aleatoriamente, en esta condició només es poden inicializar les cèlules dins de la lattice inicial finita, mentres que en el cas de la definició original, en teoria totes les cèlules de la lattice infinita deurien ser inicializadas.

Variacions

Els A.C. poden variar en alguna de les característiques abans mencionades, derivant en autómates celulars no estàndar.

Per eixemple, un A.C. estàndart té una cuadrícula a on s'assumix que les cèlules són quadros; és dir, que la retícula té una geometria quadrada. Açò no és necessàriament un requisit, i es pot variar el A.C. per a presentar una geometria triangular o hexagonal (en A.C. de 2 dimensions, el quadrat, el triàngul i l'hexàgon són les úniques figures geomètriques que omplin el pla).

També pot variar-se el conjunt d'estats $k$ que cada cèlula pot prendre, la funció de transició $f$ de manera que ya no siga homogénea, utilisar elements estocàstics (aleatorietat) en $f$ (lo que es coneix com A.C. provabilístic), variar els veïnats de cada cèlula, etc.

Complexitat d'un autómata celular

La complexitat d'un autómata celular es determina conforme aumenta el seu dimensionalidad (llineal, pla, espai, etc), puix el número de possibles veïns incrementa d'acort a les geometria o distribucions espacials en les que es genere. Per al cas d'una dimensió cada cèlula tindrà solament 2 veïns, en dos dimensions (o pla) contara en 4 veïns (dalt, avall, esquerra, dreta), 8 veïns si es prenen en conte les diagonals i en 3D aplegara a tindre fins a possibles 26 veïns.

Vore també

• Autómata celular quàntic
• Emergència (filosofia)
• Màquina de Turing
• Teoria d'autómates
• Ciutat Permutació
• Lenia
• Regla 184
• Cucs de Paterson

Bibliografia

• S. Wolfram, A New Kind of Science, 2002
• B. Cipra, What's happening in the Mathematical Sciences, vols. 3 i 5, American Mathematical Society, EU, 1996, 2002
• Alejandro, D., Gómez, R., En, L., Aplicades I Computació, M., & Acatlán, F. (n.d.). Descripció i Aplicacions dels Autómates Celulars. Cinvestav.Mx. Retrieved December 17, 2022, from http://delta.cs.cinvestav.mx/mcintosh/cellularautomata/Summer_Research_files/Arti_Vore_Inv_2011_DARG.pdf
• Penya, E., & Sayama, H. (2021). Life worth mentioning: Complexity in Life-Like Cellular Automata. Artificial Life, 27(2), 105–112. https://doi.org/10.1162/artl_a_00348