**Autómatas Celulares**
![](./img/719999898_2fe8f23617.jpg width=300px align="left") Los autómatas celulares (AC) surgen en la década de 1940 con **John Von Neumann**, que intentaba modelar una máquina que fuera capaz de autoreplicarse, llegando así a un modelo matemático de dicha máquina 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.
Un **autómata celular** _es un modelo matemático para un sistema dinámico compuesto por un conjunto de celdas o células que adquieren distintos estados o valores_. Estos estados son alterados de un instante a otro en unidades de tiempo discreto, es decir, que se puede cuantificar con valores enteros a intervalos regulares. De esta manera este conjunto de células logran una evolución según una determinada expresión matemática, que es sensible a los estados de las células vecinas, y que se conoce como **regla de transición local**.
El aspecto que más caracteriza a los AC es su capacidad de lograr una serie de propiedades que surgen de la propia dinámica local a través del paso del tiempo y no desde un inicio, aplicándose a todo el sistema en general. Por lo tanto, no es fácil analizar las propiedades globales de un AC desde su comienzo, complejo por naturaleza, si no es por medio de una simulación, partiendo de un estado o configuración inicial de células y cambiando en cada instante los estados de todas ellas de forma síncrona.
# Elementos
!!!def: Autómata Celular
La definición de un AC requiere mencionar sus elementos básicos:
* **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.
Adicionalmente, es necesario especificar el tipo de límite o frontera del espacio, entre los que podemos destacar:
* **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 límites, es infinito.
 Es importante destacar la complejidad que se logra con un AC. De acuerdo a la dimensión en la que se genere (línea, plano, espacio,etc.) tendrá un número potencial de vecinos. Por ejemplo, supongamos que la vecindad se considera de radio 1, es decir, solo las células inmediatas o más cercanas serán tomadas en cuenta. Para el caso de una sola dimensión cada célula tendrá solo 2 vecinos. Para un AC en dos dimensiones contará con 4 (arriba, abajo, izquierda, derecha) u 8 vecinas si tomamos en cuenta también las diagonales. Y en el caso de un AC en 3D llegará a tener hasta 26 vecinos cada célula. Como el siguiente estado de cada célula se computa en base al estado anterior y de sus vecinas (es decir que el estado 2 surge del estado 1 y el 3 del 2,etc.), se puede tener un sistema con una función de transición muy rica y que, a veces, puede presentar un comportamiento muy difícil de predecir.
# Clasificación
[Stephen Wolfram](http://es.wikipedia.org/wiki/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.
!!!def:Clasificación de Wolfram
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](http://es.wikipedia.org/wiki/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 AC
En el artículo titulado _Systems of logic based on ordinals_ , **A. M. Turing** enumera tres habilidades requeridas para ser un buen matemático: la _intuición_, la _ingenuidad_ y la que considera la más importante de todas, la _capacidad de distinguir las cuestiones interesantes de las no interesantes_. En los proceedings del _Workshop on Cellular Automata_ celebrado en Los Alamos en 1989, **H. A. Gutowitz** discutió sobre los diversos aspectos que pueden hacer de los autómatas celulares un campo interesante para su investigación. Por supuesto, el interés depende del contexto científico que se considere, puesto que lo que es interesante para algunos no tiene por qué serlo para otros: para un matemático, los autómatas pueden tener importancia como ejemplos de sistemas dinámicos discretos o como un modelo de computación en paralelo; para un biólogo, el interés puede residir en que los autómatas celulares proporcionar una herramienta para modelar y comprender los fenómenos biológicos de una forma simple.
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 difícil 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 fluida 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
## 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: esto 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.
## Ejemplo bidimensional: *solidificación*
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. 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:
1. Si la célula está en estado 1 (activada) entonces permanecerá en estado 1, independientemente de los estados de sus vecinas.
2. 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 permanece 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:
1. 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á.
2. Si la célula está en el estado 0 (inactiva) entonces se activará solo 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.
## AC 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**.
(insert menu.md.html here)