Enciclopedia/Diccionario de Psicología y Neurociencias:

ıllı Autómata celular wiki: info, libros pdf y vídeos

  Autómata celular 

---

No hay una definición formal y matemática admitida de robot celular; no obstante, se puede describir a un A.C. como una tupla, o sea, un conjunto ordenado de objetos caracterizado por los próximos componentes:

• Una reja o bien cuadriculado (lattice) de enteros (conjunto Z ) interminablemente extendida, y con dimensiónd?Z+ . Cada celda de la cuadrícula se conoce como célula.
  
• Cada célula puede tomar un valor en Z desde un conjunto finito de estadosk .
  
• Cada célula, además de esto, se identifica por su vecindad, un conjunto finito de células en las cercanías de exactamente la misma.
  
• De pacto con esto, se aplica a todas y cada una de las células de la cuadrícula una función de transición ( f ) que toma como razonamientos los valores de la célula en cuestión y los valores de sus vecinos, y retorna el nuevo valor que la célula va a tener en la próxima etapa de tiempo. Esta función f se aplica, como ya se afirmó, de forma homogénea a todas y cada una de las células, por cada paso prudente de tiempo.

Condiciones de frontera

Topología del robot celular de 2D plegado en 3D para el caso de frontera periódica.

Por definición, un A.C. consiste en una retícula infinita de enteros. No obstante, para cuestiones prácticas (como en modelos de sistemas físicos llevados a cabo en ordenadores de memoria finita), se requiere tomar ciertas consideraciones en el momento de incorporar un A.C. Por este motivo, la definición original se altera para dar cabida a retículas finitas en las que las células del A.C. interaccionen. Esto acarrea la consideración extra de lo que debe ocurrir con aquellas células que se hallen en los bordes de la retícula. A la implementación de una o bien múltiples consideraciones concretas se le conoce como condición de frontera.

Dentro del campo de los A.C., se pueden incorporar numerosas condiciones de frontera, en función de lo que el inconveniente real requiera para su modelado. Por ejemplo:

• Frontera abierta. Se cree que fuera de la lattice radican células, todas y cada una con un valor fijo. En el caso en particular del juego de la vida y de otros A.C. con 2 estados en conjunto k , una frontera se afirma fría si las células fuera de la frontera se consideran fallecidas, y caliente si se consideran vivas.
  
• Frontera periódica. Se considera a la lattice tal y como si sus extremos se tocaran. En una lattice de dimensión uno con cero esto puede visualizarse en 2 dimensiones como una circunferencia. En dimensión dos, la lattice podría visualizarse en 3 dimensiones como un toroide.
  
• Frontera reflectora. Se estima que las células fuera de la lattice "reflejan" los valores de aquellas en la lattice. De esta forma, una célula que estuviese junto al filo de la lattice (fuera de ella) tomaría como valor el de la célula que esté junto al filo de la lattice, dentro de ella.
  
• Sin frontera. Usando implementaciones que hagan medrar dinámicamente el empleo de memoria de la lattice incorporada, se puede aceptar que toda vez que las células deben interaccionar con células fuera de la lattice, esta se hace más grande para dar cabida a estas interactúes. Evidentemente, hay un límite (impuesto por la memoria libre) para esta condición. Es fundamental no confundir esta condición de frontera con la definición original de A.C. cuya lattice es en un inicio infinita. En el caso de un A.C. sin frontera, la lattice empieza con un tamaño definido y finito, y conforme se requiera va medrando en el tiempo, lo que no lo hace necesariamente un modelo más próximo a la realidad, puesto que si se inicializara la lattice de manera aleatoria, con esta condición solo se pueden iniciar las células en la lattice inicial finita, al paso que en el caso de la definición original, teóricamente todas y cada una de las células de la lattice infinita habrían de ser iniciadas.

Los A.C. pueden cambiar en ciertas peculiaridades ya antes mentadas, derivando en robots celulares no estándar.

Por ejemplo, un A.C. estándar tiene una cuadrícula donde se acepta que las células son cuadros; o sea, que la retícula tiene una geometría cuadrada. Esto no necesariamente es un requisito, y se puede cambiar el A.C. para presentar una geometría triangular o bien exagonal (en A.C. de dos dimensiones, el cuadrado, el triángulo y el exágono son las únicas figuras geométricas que llenan el plano).

También puede cambiarse el conjunto de estados k que cada célula puede tomar, la función de transición f de manera que ya no sea homogénea, emplear elementos estocásticos (aleatoriedad) en f (lo que es conocido como A.C. probabilístico), cambiar las vecindades de cada célula, etc.

La historia de los robots celulares puede ser clasificada en 3 etapas asociadas a los nombres de los científicos que en todos y cada instante marcaron un punto de cambio en el desarrollo de la teoría: la era de Von Neumann, la era de John Horton Conway y la era de Stephen Wolfram.

Era de Von Neumann

La primera etapa la comienza von Neumann, quien una vez terminada su participación en el desarrollo y terminación de la primera computadora ENIAC tenía en psique desarrollar una máquina con la capacidad de edificar desde sí otras máquinas (auto-reproducción) y aguantar comportamiento complejo. Con la ayuda de su amigo Stanislaw Ulam, von Neumann incorpora la teoría de los robots celulares en un vector de 2 dimensiones Z×Z (donde Z representa el conjunto de los enteros). El vector es llamado el espacio de evoluciones y cada una de las situaciones (llamadas células) en el vector toma un valor del conjunto de estados |k|=29=29. La función de transición que determina el comportamiento del robot celular emplea la vecindad de von Neumann, consistente en un factor central x(i,j) (llamada célula central) y sus vecinos que son las células x(i,j-1), x(i,j+1), x(i-1,j) y x(i+1,j) (o sea, la célula en cuestión y sus células vecinas más próximas, arriba, abajo, izquierda y derecha, respectivamente).

Era de John Horton Conway

En mil novecientos setenta, John Horton Conway dio a conocer el androide celular que seguramente sea el más conocido: el Juego de la vida (Life), publicado por Martin Gardner en su columna Mathematical Games en la gaceta Scientific American. Life ocupa una cuadrícula (lattice bidimensional) donde se pone al comienzo un patrón de células "vivas" o bien "fallecidas". La vecindad para cada célula son ocho: los vecinos formados por la vecindad de Von Neumann y las 4 células de las 2 diagonales (esta vecindad se conoce como vecindad de Moore). De forma repetida, se aplican simultáneamente sobre todas y cada una de las células de la cuadrícula las próximas tres reglas:

1. Nacimiento: se sustituye una célula fallecida por una viva si dicha célula tiene precisamente tres vecinos vivos.
   
2. Muerte: se sustituye una célula viva por una fallecida si dicha célula no tiene más de 1 vecino vivo (muerte por aislamiento) o bien si tiene más de tres vecinos vivos (muerte por sobrepoblación).
   
3. Supervivencia: una célula viva continuará en ese estado si tiene dos o bien tres vecinos vivos.

Una de las peculiaridades más esenciales de Life es su capacidad de efectuar cómputo universal, esto es, que con una distribución inicial apropiada de células vivas y fallecidas, Life se puede transformar en una computadora de propósito general (máquina de Turing).

Era de Stephen Wolfram

Stephen Wolframha efectuado numerosas investigaciones sobre el comportamiento cualitativo de los A.C. Con base en su trabajo sobre AC unidimensionales, con 2 o bien 3 estados, sobre configuraciones periódicas que se presentan en el A.C., observó sus evoluciones para configuraciones iniciales azarosas. De esta forma, dada una regla, el A.C. exhibe diferentes comportamientos para diferentes condiciones iniciales.

De esta forma, Wolfram clasificó el comportamiento cualitativo de los A.C. unidimensionales. Conforme con esto, un AC pertenece a una de las próximas clases:

• Clase I. La evolución lleva a una configuración estable y homogénea, o sea, todas y cada una de las células acaban por venir al mismo valor.
  
• Clase II. La evolución lleva a un conjunto de estructuras simples que son estables o bien periódicas.
  
• Clase III. La evolución lleva a un patrón anárquico.
  
• Clase IV. La evolución lleva a estructuras apartadas que muestran un comportamiento complejo (o sea, ni totalmente embrollado, ni absolutamente ordenado, sino más bien en la línea entre uno y otro, este acostumbra a ser el género de comportamiento más interesante que un sistema activo puede presentar).

El caparazón de Conus textile muestra un patrón caracterizable en concepto de robots celulares.

Los androides celulares pueden ser utilizados para modelar abundantes sistemas físicos que se caractericen por un elevado número de componentes homogéneos y que interaccionen de forma local entre sí. En verdad, cualquier sistema real al que se le puedan analogar los conceptos de "vecindad", "estados de los componentes" y "función de transición" es aspirante para ser modelado por un A.C.

Las peculiaridades de los robots celulares van a hacer que dichos modelos sean prudentes en tiempo, espacio o bien los dos, en dependencia de la variación de la definición de A.C. que se use. Ciertos ejemplos de áreas en donde se emplean los robots celulares son:

• Modelado del flujo de tráfico y de viandantes.
  
• Modelado de fluidos (gases o bien líquidos).
  
• Modelado de la evolución de células o bien virus como el SIDA.
  
• Modelado de procesos de percolación.

AC de una dimensión

Androide celular generado con la regla treinta.

El AC no trivial más simple consiste en una retícula unidimensional de células que solo pueden tener 2 estados (« 0 » o bien « 1 »), con un vecindario constituido, para cada célula, por ella misma y por las 2 células lindantes (23=8 configuraciones posibles). Existen 28=256 modos de acotar cuál debe ser el estado de una célula en la generación siguiente para cada una de estas configuraciones, entonces existen doscientos cincuenta y seis AC diferentes de esta clase.

Consideremos el AC definido por la tabla siguiente, que nos da la regla de evolución:

Motivo inicial111110101100011010001000Valor siguiente de la célula central00011110

Juego de la vida

Artículo principal: Juego de la vida

Modelo Nagel-Schreckenberg

Artículo principal: Modelo Nagel-Schreckenberg

---

• Anterior
• Siguiente