Autómatas Celulares
Autómatas Celulares
Los autómatas celulares (AC) surgen en la década de 1940 con John Von Neumann, que intentaba modelar una maquina que fuera capaz de autoreplicarse, llegando así a un modelo matemático de dicha maquina con reglas complicadas sobre una red rectangular. Inicialmente fueron interpretados como conjunto de células que crecían, se reproducían y morían a medida que pasaba el tiempo. Su nombre se debe a esta similitud con el crecimiento de las células.
|
|
|
|
|
Elementos de un Autómata Celular
- Un espacio regular. Ya sea una línea, un plano de 2 dimensiones o un espacio n-dimensional. Cada división homogénea del espacio es llamada célula.
- Conjunto de Estados. Es finito y cada elemento o célula del espacio toma un valor de este conjunto de estados. También se denomina alfabeto. Puede ser expresado en valores o colores.
- Configuración Inicial. Es la asignación inicial de un estado a cada una de las células del espacio.
- Vecindades. Define el conjunto de células que se consideran adyacentes a una dada, así como la posición relativa respecto a ella. Cuando el espacio es uniforme, la vecindad de cada célula es isomorfa (es decir, que tiene el mismo aspecto).
- Función de Transición Local. Es la regla de evolución que determina el comportamiento del AC. Se calcula a partir del estado de la célula y su vecindad. Define cómo debe cambiar de estado cada célula dependiendo su estado anterior y de los estados anteriores de su vecindad. Suele darse como una expresión algebraica o un grupo de ecuaciones.
- Frontera Abierta. Se considera que todas las células fuera del espacio del autómata toman un valor fijo.
- Frontera Reflectora. Las células fuera del espacio del autómata toman los valores que están dentro, como si se tratara de un espejo.
- Frontera Periódica o Circular. las células que están en la frontera interaccionan con sus vecinos inmediatos y con las células que están en el extremo opuesto del espacio, como si lo dobláramos en forma de cilindro.
- Sin Frontera. La representación des autómata no tiene limites, es infinito.
Clasificación de los Autómatas Celulares
Stephen Wolfram comenzó a trabajar en autómatas celulares a mediados de 1981 después de considerar cómo los patrones complejos parecían formarse en la naturaleza en violación de la segunda ley de la termodinámica. Sus investigaciones fueron inicialmente impulsados por un interés en sistemas de modelado, como las redes neuronales. Tras ver la inesperada complejidad del comportamiento de estas reglas simples Wolfram llevó a sospechar que la complejidad en la naturaleza puede ser debida a mecanismos similares. En 2002 Wolfram publicó un texto de 1.280 páginas, A New Kind of Science, que sostiene ampliamente que los descubrimientos sobre autómatas celulares no son hechos aislados sino que son robustos y tienen importancia para todas las disciplinas de la ciencia.
Wolfram define cuatro clases en las que los AC. Mientras que los estudios anteriores en autómatas celulares tienden a tratar de identificar el tipo de patrones de reglas específicas, la clasificación de Wolfram fue el primer intento de clasificación global. En orden de complejidad las clases que identifica son:
- Clase I: Casi todos los patrones iniciales evolucionan rápidamente en un estado estable y homogéneo. Cualquier aleatoriedad en el patrón inicial desaparece.
- Clase II: Casi todos los patrones iniciales evolucionan rápidamente hacia estructuras estables u oscilantes. Parte de la aleatoriedad del patrón inicial puede permanecer, pero solo algunos restos. Los cambios locales en el patrón inicial tienden a permanecer locales.
- Clase III: Casi todos los patrones iniciales evolucionan de forma pseudo-aleatoria o caótica. Las estructuras estables que aparecen son destruidas rápidamente por el ruido circundante. Los cambios locales en el patrón inicial tienden a propagarse indefinidamente.
- Clase IV: Casi todos los patrones iniciales evolucionan en las estructuras que interactúan de manera compleja e interesante, con la formación de las estructuras locales que son capaces de sobrevivir por largos períodos de tiempo. Podría ser el caso de que apareciesen estructuras estables u oscilantes, pero el número de pasos necesarios para llegar a este estado puede ser muy grande, incluso cuando el patrón inicial es relativamente simple. Los cambios locales en el patrón inicial pueden extenderse indefinidamente. Wolfram ha conjeturado que muchos, si no todos, los AC de esta clase son capaces de realizar computación universal. Algo que ha sido demostrado para el autómata 110 y para el juego de la vida de John Conway.
Estas definiciones son de carácter cualitativo y hay cierto margen de interpretación. Según Wolfram, "... con casi cualquier esquema de clasificación general, hay casos en los que, inevitablemente, se asignan a una clase por una definición y otra clase por otra definición, y lo mismo ocurre con los autómatas celulares: hay veces que las reglas muestran algunas de las características de una clase y otras veces de otra clase".
La importancia de los Autómatas Celulares
Los autómatas celulares se sitúan en el campo de los sistemas complejos, un campo con unas fronteras muy difuminadas, lo que hace muy díficil su definición. Es por ello que el estudio de los sistemas complejos se encuentra en una etapa muy preliminar... están dadas ciertas puntadas, pero falta coserlo todo. Como añadido, las distintas comunidades que pueden encontrar interesante el campo, o para las que podría ser útil, a menudo no mantienen una comunicación demasiado fluída entre sí, con lo que la información está dispersa.
Los autómatas celulares son interesantes por la creencia de que pueden contribuir, quizás de forma substancial, al desarrollo de un punto de vista del mundo en el que lo que vemos deja de convertirse en algo misterioso para convertirse en algo natural. La razón para esta creencia es el hecho de que los autómatas celulares son capaces de generar comportamientos globales con patrones muy complejos sobre la base de unas reglas de interacción muy simples y locales. Además, los autómatas celulares tienen dos virtudes fundamentales: son bien definibles desde el punto de vista matemático y son fáciles de representar utilizando ordenadores.
El paradigma de modelado de los autómatas celulares supone considerar una representación muy especial del espacio, del tiempo y de los estados del sistema lo que, como veremos, los sitúa en el vértice opuesto al ocupado por los modelos matemáticos continuos.
Algunos Ejemplos de Autómatas Celulares
La regla exactamente 1
Consideremos la regla determinada por la tabla
| 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
En este caso, la regla local consiste simplemente en poner un 1 si y solo si existe un único 1 en el entorno. El patrón obtenido a partir de la configuración inicial consistente en poner un 1 en posición 0 y ceros en el resto es la siguiente:
Este patrón geométrico es muy interesante, pues se corresponde con una figura fractal (concretamente, el triángulo de Sierpinski). Esto significa que si observamos el dibujo global y ahora nos quedamos con uno de los subtriángulos que aparecen dentro de él, obtenemos la misma figura que al inicio: ésto se llama autosimilitud y es una característica de los cuerpos fractales. Si ponemos una condición inicial aleatoria el patrón ordenado desaparece y se obtienen formaciones muy complejas:
La regla de la mayoría
La tabla de este autómata celular es la siguiente:
| 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
| 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 |
Efectivamente, cada autómata calcula cuál es el estado mayoritario en su entorno y se actualiza de acuerdo con la mayoría. En directa la interpretación de los estados 0 y 1 como dos opiniones diferentes en una población o inclinaciones políticas, de modo que el autómata celular se convierte en modelo de evolución de opiniones o de intención de voto. Obviamente, en este modelo no tiene mucho sentido partir de la semilla inicial considerada en los dos casos anteriores. Es mucho más interesante ver cómo evoluciona a partir de una condición inicial al azar y ver si alguno de los dos estados termina imponiéndose al otro.
Ejemplos Bidimensionales
En este caso, si queremos hacer una representación similar a la que hemos hecho para los autómatas celulares 1d, tendríamos que utilizar tres dimensiones, dos de ellas para el espacio y una más para el tiempo. Nos contentaremos por ello en representar los estados para algunos instantes de tiempo específicos.
Si usamos el vecindario de Von Neumann, el vecindario de una célula bidimensional estará formado por nueve células: ella misma y las ocho células que la rodean (ver Figura xx). Los estados, como en el caso 1d, son dos: 0 y 1.
Solidificación. En este autómata celular, cada célula se actualiza siguiendo el siguiente proceso:
- Si la célula está en estado 1 (activada) entonces permanecerá en estado 1, independientemente de los estados de sus vecinas.
- Si la célula está en el estado 0 (inactiva) entonces sumará los estados de las células vecinas. Si el número de celdas activadas en su entorno es 1 o 2, entonces la célula actualizará su estado a 1; en caso contrario permanecerá desactivada.
En las siguientes figuras podemos ver una secuencia en la evolución de esta regla partiendo de la semilla inicial en la que todas las celdas están desactivadas excepto la central. Esta regla se llama de solidificación porque una vez que una célula es activada permacene así para el resto de la evolución.
 |
 |
 |
 |
 |
Como veremos más adelante, las posibilidades de definición son enormes, y los patrones resultantes también. Por ejemplo, si la regla es:
- Si la célula está en estado 1 (activada) entonces permanecerá en estado 1, solo si el número de células vecinas está comprendido entre 0 y 4. En caso contrario se desactivará.
- Si la célula está en el estado 0 (inactiva) entonces se activará sólo si número de celdas activas de su entorno es 3 exactamente. En cualquier otro caso permanecerá desactivada.
el resultado es el siguiente partiendo de una pequeña semilla de celdas activadas en el centro.
Autómatas Celulares con más de 2 estados
Si añadimos un posible tercer estado entonces las posibilidades son casi ilimitadas. Mostramos aquí la evolución de un autómata celular 1d con tres estados 0,1 y 2, que son representados por tres colores diferentes. La regla consiste en sumar los estados de las celdas vecinas, obteniéndose un valor comprendido entre 0 y 6. El nuevo estado es asignado en función de la siguiente tabla:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 2 | 1 | 1 | 2 | 0 | 2 |
Con estos ejemplos podemos intuir que los autómatas celulares pueden generan sistemas dinámicos con comportamientos extremadamente diversos y ricos. Es por ello por lo que son utilizados en ciencias como modelos de comportamientos complejos. Dentro del mundo matemático los autómatas celulares se encuadran como sistemas dinámicos simbólicos.