Un automat cel·lular (A.C.) es un model matematic per a un sistema dinamic que evoluciona en passos discrets. Es adequat per modelar sistemes naturals que puguin ser descrits com una col·leccio massiva d'objectes simples que interaccionin localment uns amb els altres. ^{[1] [2]}

Son sistemes descoberts dins de l'ambit del camp de la fisica computacional per John von Neumann els anys 1950. ^[3] Tot i aixo, els automats cel·lulars van ser posats ja en practica per Konrad Zuse i Stanislaw Ulam uns anys abans. ^[4]

Descripcio [ modifica ]

No hi ha una definicio formal i matematica acceptada d' automat cel·lular pero es pot descriure com una tupla , es a dir, un conjunt ordenat d'objectes caracteritzat pels seguents components:

• Una reixeta o quadriculat de nombres enters (conjunt ${\displaystyle \mathbb {Z} }$) infinitament estesa, i amb dimensio ${\displaystyle d\in \mathbb {Z} ^{+}}$. Cada cel·la de la quadricula rep el nom de cel·lula .
• Cada cel·lula pot prendre un valor en ${\displaystyle \mathbb {Z} }$ a partir d'un conjunt finit d'estats ${\displaystyle k}$.
• Cada cel·lula, a mes, es caracteritza pel seu veinatge , un conjunt finit de cel·lules als seus voltants.
• D'acord amb aixo, s'aplica a totes les cel·lules de la quadricula una funcio de transicio ( ${\displaystyle f}$) que pren com arguments els valors de la cel·lula en questio i els valors de les cel·les veines, i torna el nou valor que la cel·lula tindra en la seguent etapa de temps. Aquesta funcio ${\displaystyle f}$ s'aplica de forma homogenia a totes les cel·lules per cada pas discret de temps.

Condicions de frontera [ modifica ]

Per definicio, un automat cel·lular consisteix en una reticula infinita d'enters. Tot i aixo, per questions practiques (com en models de sistemes fisics duts a terme en ordinadors de memoria finita), es requereix prendre certes consideracions a l'hora d'implementar un automat. Per aquest motiu, la definicio original es modifica per donar cabuda a reticules finites en les que les cel·lules de l'automat interactuin. Aixo comporta la consideracio extra del que ha de succeir en aquelles cel·lules que es trobin als marges de la reticula, el que es coneix com a condicio de frontera .

Es poden implementar diverses condicions de frontera, en funcio d'allo que el problema real requereixi pel seu modelat. Per exemple:

• Frontera oberta. Fora de la graella hi resideixen cel·lules, totes amb un valor fix. En el cas particular del joc de la vida i altres automats similars amb dos estats al seu conjunt ${\displaystyle k}$, una frontera s'anomena "freda" si les cel·lules fora de la graella es consideren mortes, i "calenta" si es consideren vives.
• Frontera periodica. Es considera que la graella te una propietat toroidal , com si els seus extrems es toquessin. Per tant, si una cel·lula surt de la graella, reapareix pel costat oposat.
• Frontera reflectora. Les cel·lules de fora la graella reflecteixen els valors de les de les de dins. Aixi, una cel·lula que toques la frontera per fora agafaria com a valor el de la cel·lula que toca la frontera per dins.
• Sense frontera. Fent us d'implementacions que facin creixer dinamicament l'us de memoria de la graella implementada, es pot assumir que cada vegada que les cel·lules han d'interactuar amb les de fora de la graella, aquesta es fa mes gran per dur a terme aquestes interaccions. Tot i tendir a infinit, ates que la frontera inicial es finita no es equivalent a la definicio general de l'automat cel·lular, perque en aquest cas no pots activar qualsevol cel·lula de la graella des del principi.

Variacions [ modifica ]

Alguns automats cel·lulars tenen graella triangular o hexagonal enlloc de rectangular. Tambe existeixen versions tridimensionals o amb moltes mes dimensions, com en el cas dels automats cel·lulars quantics . Altres possibles variacions son augmentar el nombre d'estats ${\displaystyle k}$ que cada cel·lula pot tenir (com en el cas dels automats cel·lulars totalistes ), la funcio de transicio ${\displaystyle f}$ de manera que ja no sigui homogenia, utilitzar elements estocastics (aleatorietat) en ${\displaystyle f}$ (el que es coneix com a automat cel·lular probabilistic ) o variar els veinatges de cada cel·lula.

Aplicacions [ modifica ]

Els automats cel·lulars es poden usar per a modelar nombrosos sistemes fisics 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 " veinatge ", "estats dels components" i "funcio de translacio" es candidat per ser modelat per un A.C.

Les caracteristiques dels automats cel·lulars faran que siguin discrets en temps, espai o les dues coses, depenent de la variant de la definicio de A.C. que s'utilitzi. Alguns exemples d'us son:

• Modelat de flux de transit de vehicles i de vianants.
• Modelat de fluxs ( gasos o liquids ).
• Modelat de l'evolucio de cel·lules o virus com el VIH .
• Modelat de processos de percolacio .

Exemples d'automats cel·lulars [ modifica ]

Automat cel·lular unidimensional [ modifica ]

L'exemple mes basic d'automat cel·lular no trivial es la versio unidimensional . Es defineix una sequencia de cel·lules que nomes poden tenir dos estats, i es llegeixen ordenadament aplicant canvis segons l'estat de la cel·lula i les seves veines (cel·lula anterior i posterior). El resultat es sol mostrar com una nova linia a sota de l'actual que sera la llegida a continuacio, i aquest proces es va repetint. El conjunt de normes que defineix el valor de la nova cel·lula segons els estats de les cel·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 sequencia senar de cel·lules on totes estan desactivades excepte la del mig. A partir d'aquesta configuracio inicial, els Rule Sets es poden classificar en amfiquirals o no amfiquirals segons si el patro format es simetric. A mes, els patrons obtinguts es poden classificar en: ^[1]

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

Automat de Von Neumann [ modifica ]

L' automat de Von Neumann es considerat el primer automat cel·lular, ideat per John von Neumann a partir dels suggeriments de Stanislaw Ulam . El seu proposit original era proporcionar informacio sobre els requisits logics per a fer una maquina autoreplicant , i es van utilitzar en el constructor universal de Von Neumann. ^[3]

Les cel·lules, es a dir els automats finits , estan disposades sobre un pla cartesia i interfereixen amb les quatre cel·lules veines , formant diferents estats de transmissio de senyals, el resultat del qual pot ser la construccio o destruccio de circuits. Cada cel·lula pot tenir 29 estats diferents, ordenats en cinc grups: buit, transitori, confluent, transmissor ordinari i transmissor especial. Aixi doncs, els estats "excitats" transporten dades, a la velocitat d'un bit per pas de transicio d'estat i aplicant canvis sobre la graella.

Existeixen diverses variants similars; l' automat de Nobili incorpora la capacitat de les cel·lules confluents de creuar senyals i emmagatzemar informacio, i l' automat de Hutton permet replicar un bucle de dades analeg als bucles de Langton. ^[6]

L' automat de Codd va ser proposat per Edgar F. Codd al 1968 per recrear la universalitat de calcul i construccio de l'automat de von Neumann pero amb nomes 8 estats. ^[7] De manera similar, Edwin Roger Banks en va fer un de nomes 4 estats, anomenat automat Banks IV pero que finalment no va implementar. ^[8] Al 1973, John Devore va optimitzar l'automat de Codd per reduir-ne la mida de la maquina autoreplicant. Christopher Langton va fer una modificacio de l'automat de Codd per crear els bucles de Langton , els quals son autoreplicants amb moltes menys cel·les pero ja no tenen universalitat de calcul i construccio. ^[9]

Bucles de Langton [ modifica ]

Els bucles de Langton son "especies" amb vida artificial que consisteixen en un bucle de cel·lules que contenen informacio genetica , que flueix continuament al voltant del bucle i surten al llarg d'un "brac" ( pseudopode ) que es convertira en el bucle fill. Els "gens" li indiquen que faci tres girs a l'esquerra, completant el bucle, que despres es desconnecta del seu pare. Els bucles son incapacos de reproduir-se a l'espai que ocupa un altre bucle, per aixo un cop estan envoltats pels bucles fills es consideren "morts". Igual que amb l'automat de Codd, els bucles de Langton consisteixen en senyals que viatgen passivament al llarg dels circuits, fins que arriben als extrems oberts, on s'executa l'ordre que porten.

Els bucles de Langton formen tota una familia d'automats cel·lulars amb caracteristiques similars:

• Bucles de Langton originals (1984) creats per Christopher Langton . ^[9]
• Bucles de Byl (1989), amb una reduccio de la mida del bucle al treure'n l'espai interior. ^[10]
• Bucles de Chou-Reggia (1993), amb reduccio total de les parets del bucle. ^[11]
• Bucles de Tempesti (1995), amb noves capacitats de construccio, permetent escriure patrons dins del bucle despres de la reproduccio. ^[12]
• Bucles de Perrier (1996), fent-lo universalment computable. ^[13]
• Bucle SDSR (1998), amb un estat addicional que permet la dissolucio d'estructures; cada bucle te una vida util limitada i es dissol al final del seu cicle de vida. Aixo permet un creixement continu al llarg de les generacions. ^[14]
• Evoloop (1999), extensio del bucle SDSR que es capac d'interaccionar amb bucles veins, aixi com d' evolucionar a causa de la competencia per l'espai, on la seleccio natural afavoreix els bucles funcionals mes petits. ^{[15] [16]}
• Sexyloop (2007), modificacio de l'Evoloop on els bucles auto-reproduibles tenen la capacitat de reproduccio sexual . Amb aquesta capacitat, els bucles son capacos de transferir material genetic a altres bucles. Aixo augmenta la diversitat en l'evolucio de noves especies de bucles. ^[17]

Joc de la vida [ modifica ]

El joc de la vida es un automat ortogonal bidimensional basic, creat per John Horton Conway el 1970. A cada unitat de temps, es donen les seguents transicions: ^[18]

1. Tota cel·la viva amb menys de dos veins vius mor (de solitud ).
2. Tota cel·la viva amb mes de tres veins vius mor (de sobreconcentracio ).
3. Tota cel·la viva amb dos o tres veins vius, segueix viva per a la seguent generacio.
4. Tota cel·la morta amb exactament tres veins vius torna a la vida.

Per fer la comprovacio s'utilitza el veinatge de Moore , es a dir, les 8 cel·les veines de cada cel·la; adjacents i diagonals. Aquesta idea compren tot un seguit d'automats amb caracteristiques similars, i per tant de la mateixa familia que el joc de la vida. ^[19] En son exemples les llavors de Brian o el cervell de Brian , creades per Brian Silverman. ^[20]

En les llavors totes les cel·les vives moren i les mortes viuen si tenien exactament n veins vius. El cervell de Brian es mes complex; es parteix del joc de la vida pero les cel·les tenen tres estats; vives, morint-se o mortes. ^[21]

Wireworld [ modifica ]

Wireworld es una modificacio 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 logiques . A mes, Wireworld es Turing complet . ^[22]

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

1. Tota cel·la buida segueix sent buida.
2. El cap d'electro passa a ser cua.
3. La cua d'electro passa a ser conducte.
4. El conducte forma un cap d'electro si una o dues cel·les veines son caps d'electro, si no segueix sent conducte.

Formiga de Langton [ modifica ]

La formiga de Langton es un automat ortogonal bidimensional creat per Chris Langton . En aquest cas es defineix una cel·la especial que actua de formiga que es va desplacant, i al fer-ho modifica els estats de les altres cel·les (al trepitjar una cel·la activada la desactiva, i al reves). La direccio de la formiga depen de l'estat de la cel·la actual a la que es troba, si esta activada fa un gir a dreta, si esta desactivada fa un gir a l'esquerra.

Tot aixo es recreable com un automat normal definint mes estats ${\displaystyle k}$ possibles per cada cel·lula, segons si s'hi troba la formiga, segons la direccio d'aquesta i segons si la casella a la que es troba esta activada o desactivada. ^[23]

Model Nagel-Schreckenberg [ modifica ]

El model Nagel-Schreckenberg es un automat cel·lular probabilistic unidimensional creat per Kai Nagel i Michael Schreckenberg que serveix de model simple de transit vehicular . En aquest cas el que varia segons els vehicles veins es la velocitat del vehicle, i a mes hi ha una certa probabilitat que el vehicle freni sense un motiu aparent. ^[24]

Automat d'Ulam?Warburton [ modifica ]

L' automat d'Ulam?Warburton ( UWCA ) es un automat ortogonal bidimensional que te la particularitat de que les cel·les activades no es poden tornar a desactivar. A cada iteracio s'activen les cel·les inactivades en que nomes un dels costats es adjacent ortogonalment a una d'activada. ^[25]

CoDi [ modifica ]

CoDi ( Collect and Distribute ) va ser ideat per Felix Gers l'any 1998 per crear xarxes neuronals d'impulsos , es a dir xarxes neuronals artificials que mimetitzen les xarxes neuronals naturals . Utilitza una versio tridimensional del veinatge de Neumann , on cada cel·lula veu sis cel·lules veines. ^[26]

En fase de creixement, es crea una xarxa neuronal a l'espai de l'automat, basada en un cromosoma subjacent que ha estat distribuit al llarg de l'espai de l'automat de manera que cada cel·lula en te una copia. Hi ha quatre tipus de cel·lules: cossos de les neurones (base estructural), axons , dendrites i espai no ocupat. Un cop finalitzada la fase de creixement s'inicia la fase de senyalitzacio (o processament); els senyals son distribuits des dels cossos neuronals a traves del seu axo i recollits de les dendrites de connexio. CoDi no utilitza sinapsi de manera explicita, perque les dendrites que estan en contacte amb un axo en recullen els senyals neuronals directament. ^[26]

Referencies [ modifica ]

Vegeu tambe [ modifica ]

• Teoria d'automats
• Automat cel·lular quantic

Bibliografia [ modifica ]

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

Enllacos externs [ modifica ]

A Wikimedia Commons hi ha contingut multimedia relatiu a: Automat cel·lular

• Una Introduccion a los Automatas Celulares , arxivat de l' original (castella)
• Automata Celular (castella)
• MathWorld - Elementary Cellular Automaton - Llista de tots els Rule Sets en la versio unidireccional (angles)