Los autómatas celulares son modelos matemáticos que han tenido gran relevancia en numerosas áreas de la ciencia. Se tratan de modelos discretos en el sentido de que el espacio donde existen no varía continuamente: sus componentes están separados y son distintos entre sí. Su objetivo principal es capturar las propiedades fundamentales de algunos fenómenos del mundo físico: sus interacciones son locales y homogéneas en todo el espacio.
Inicialmente, los autómatas celulares fueron estudiados por John von Neumann, uno de los padres de las computadoras digitales, en un intento por diseñar sistemas artificiales autorreplicables. La idea de von Neumann estuvo motivada por el propósito de construir robots que pudieran copiarse a sí mismos.
Informalmente, la definición matemática de autómata celular es la siguiente.
Supongamos que G es una cuadrícula infinita en n dimensiones y que A es un conjunto de colores, o estados. A cada elemento de la cuadrícula lo llamamos una célula. Una configuración sobre G y A es una coloración de G usando los colores de A. Por ejemplo, una configuración sobre la cuadrícula bidimensional y A = {rojo, verde, azul} es:
Una vez que fijamos la cuadrícula G y el conjunto A de colores/estados, denotamos como AG al conjunto de todas las configuraciones posibles sobre G y A. Un autómata celular es una función F : AG → AG que satisface la siguiente propiedad:
⋆ Para cualquier configuración c, el color de cualquier célula en F(c) está establecido por una regla fija que sólo depende de los colores de una vecindad finita de la célula.
Esta propiedad es la que determina el comportamiento local y homogéneo de los autómatas celulares.
Algunos de los ejemplos más importantes de autómatas celulares son la Regla 110 y el Juego de la Vida de John H. Conway (explicado en este video en español por Eduardo Sáenz de Cabezón, y en este otro en inglés por el mismo Conway).
Los autómatas celulares tienen muchas conexiones interesantes con otras áreas de la ciencia. Aquí una lista de cinco de estas conexiones:
1. Sistemas dinámicos: los autómatas celulares han sido extensamente investigados como sistemas dinámicos discretos, donde el sistema evoluciona al iterar la función F : AG → AG. Por ejemplo, la siguiente animación ilustra la evolución de una configuración al iterar el Juego de la Vida:
Los puntos fijos, la periodicidad y la estabilidad de estas órbitas han sido temas centrales en estas investigaciones.
2. Física digital: algunos científicos han propuesto que las leyes físicas del universo podrían comportarse como un autómata celular. Esto podría resultar razonable en un modelo discreto del universo, ya que se cree que las mismas leyes físicas se aplican en cualquier punto del universo (excepto en las singularidades de los agujeros negros) y que estas leyes sólo dependen de una vecindad finita del punto. En esta plática de Ted, Stephen Wolfram habla sobre su exploración del universo computacional de los autómatas con la esperanza de encontrar un modelo del universo físico.
3. Teoría de la computación: algunos autómatas celulares, como la Regla 110 y el Juego de la Vida, pueden simular cualquier máquina de Turing. De acuerdo con la tesis de Church-Turing, esto significa que estos autómatas celulares tienen la capacidad de hacer los mismos cálculos que cualquier computadora programable. Este video muestra cómo es posible implementar una máquina de Turing universal usando el Juego de la Vida.
4. Teoría de grupos: la cuadrícula G de un autómata celular puede reemplazarse por cualquier grupo; esto es, por cualquier conjunto equipado con una operación binaria asociativa, con identidad y con inversos. Esta generalización proporciona conexiones muy interesantes entre la teoría de autómatas celulares y la teoría de grupos. Por ejemplo, existe una caracterización en términos de autómatas celulares de los grupos amenables, los cuales, coincidentemente, también fueron definidos por John von Neumann pero en un contexto totalmente diferente: surgieron en el estudio de descomposiciones paradójicas de grupos, al estilo del Teorema de Banach-Tarski.
5. Biología y química: los autómatas celulares pueden simular diversos procesos biológicos y químicos que involucran interacciones entre neuronas, células y moléculas. Un ejemplo famoso es el de las configuraciones producidas por la Regla 30, descubierta por Stephen Wolfram, ya que son muy similares a los patrones encontrados en las conchas de algunos caracoles.
Blog Idempotente 