Autómatas celulares: El Juego de la Vida y la Regla 110

John von Neumann.

¿Qué es un Autómata Celular?

 ¿Quién los descubrió?

Los autómatas celulares fueron descubiertos dentro del campo de la física computacional por John von Neumann en la década de 1950. Aunque von Neumann puso en práctica los autómatas celulares, estos fueron concebidos en los años 40 por Konrad Zuse y Stanislaw Ulam.

Pero, ¿qué es exactamente un autómata celular?

Los autómatas celulares son redes de autómatas simples conectados localmente. Como sabemos, cada autómata simple produce una salida a partir de varias entradas, modificando en el proceso su estado según una función de transición. Sin embargo, y por lo general, en un autómata celular, el estado de una célula en una generación determinada depende única y exclusivamente de los estados de las células vecinas y de su propio estado en la generación anterior.

Ahora bien, no existe una definición formal y matemática aceptada de autómata celular. Sin embargo, se puede describir a un autómata celular como una tupla, es decir, un conjunto ordenado de objetos que cumple las siguientes características:

• Una rejilla de enteros infinitamente extendida, con dimensión d ∈ Z+. Cada celda de la cuadrícula se conoce como célula.
• Cada célula puede tomar un valor en Z a partir de un conjunto finito de estados k.
• Cada célula se caracteriza por su vecindad, que es un conjunto finito de células en las cercanías de ésta.
• A todas las células de la cuadrícula se les aplica una función de transición f, que toma como argumentos los valores de la célula en cuestión y los valores de sus vecinos, y devuelve el nuevo valor que la célula tendrá en la siguiente etapa de tiempo.

Y, ¿qué utilidades tiene este tipo de autómatas?

Los autómatas celulares son herramientas útiles para modelar cualquier sistema en el universo. Pueden considerarse como una buena alternativa a las ecuaciones diferenciales y han sido utilizados para modelar sistemas físicos, como interacciones entre partículas, formación de galaxias, cinética de sistemas moleculares y crecimiento de cristales, así como diversos sistemas biológicos a nivel celular, multicelular y poblacional.

Estos autómatas pueden ser usados para modelar numerosos sistemas físicos que se caractericen por un gran número de componentes homogéneos y que interactúen localmente entre sí. De hecho, cualquier sistema real al que se le puedan aplicar los conceptos de "vecindad", "estados de los componentes" y "función de transición“, es candidato para ser modelado por un autómata celular.

Algunas áreas donde se utilizan los autómatas celulares son:

• Modelado del flujo de tráfico y de peatones.
• Modelado de fluidos (gases o líquidos).
• Modelado de la evolución de células o virus (como el VIH).
• Modelado de procesos de percolación (paso lento de fluidos a través de materiales porosos).

El Juego de la Vida

¿Qué es?

Uno de los autómatas celulares más conocidos es el que John Horton Conway llamó el Juego de la Vida.
El Juego de la Vida es un autómata celular bidimensional en cuadrícula con dos estados por celda.
Cada celda o célula puede estar viva o muerta, y en cada generación se aplica un algoritmo que sigue estas tres reglas: 

1. Cada célula viva con dos o tres células vecinas vivas sobrevive a la siguiente generación. 
2. Cada célula viva con ninguna, una, o más de tres células vivas a su alrededor pasa a estar muerta. 
3. Cada célula muerta con tres células vecinas vivas resucita en la siguiente generación.

El Juego de la Vida es equivalente a una máquina universal de Turing, es decir, todo lo que se puede computar algorítmicamente se puede computar en él.

Además, es interesante el hecho de que presenta configuraciones finales estables. Langton defiende que presenta propiedades de catálisis (acciones de construcción arbitrarias), de transporte (borrando estructuras y reconstruyéndolas en otro lugar del espacio celular), estructurales (como elementos estáticos, barreras, etc.), de regulación, defensa e incluso informativas, y que por tanto estos autómatas virtuales tienen capacidades computacionales suficientes para cumplir los papeles funcionales que juegan las macromoléculas en la lógica molecular de la vida. En definitiva, que funcionalmente, estos autómatas son equiparables a los componentes básicos de la vida en nuestro planeta.

Patrones

Existen numerosos tipos de patrones que pueden tener lugar en el Juego de la Vida, como patrones estáticos (“vidas estáticas”), patrones recurrentes ("osciladores", un conjunto de vidas estáticas) y patrones que se trasladan por el tablero ("naves espaciales”).
En la imagen inferior se pueden observar ejemplos de estas tres clases de patrones.

El bloque y el barco son vidas estáticas, el parpadeador y el sapo son osciladores, y el planeador y la nave ligera son naves espaciales que recorren el tablero a lo largo del tiempo.

Existen, además, más tipos de patrones, como los llamados "Matusalenes", que pueden evolucionar a lo largo de muchos turnos, o generaciones, antes de estabilizarse. Dos ejemplos de este tipo de patrones son el patrón "Diehard", que desaparece después de 130 turnos, y el patrón "Acorn", el cual tarda 5206 turnos en estabilizarse en forma de muchos osciladores, y en ese tiempo genera 13 planeadores.

Ejemplos de patrones del tipo "matusalenes".

En la aparición original del juego, Conway ofreció un premio de 50 dólares por el descubrimiento de patrones que crecieran indefinidamente. El primero fue descubierto por Bill Gosper en noviembre de 1970.
Entre los patrones que crecen indefinidamente se encuentran las "pistolas", que son estructuras fijas en el espacio que generan planeadores u otras naves espaciales; "locomotoras", que se mueven y dejan un rastro de basura; y "rastrillos", que se mueven y emiten naves espaciales.
Posteriormente, Gosper descubrió un nuevo tipo de patrón que crece cuadráticamente llamado "criadero", que deja atrás un rastro de pistolas.
Desde entonces se han creado construcciones más complicadas, como puertas lógicas de planeadores, un sumador, un generador de números primos…

Pistola de planeadores de Gosper.

Ejemplo de cómo evolucionan tres patrones inicialmente muy similares.

La Regla 110

¿Qué es?

Otro autómata celular conocido es el llamado la Regla 110, el cual es unidimensional y tiene un conjunto de 0s y 1s que va evolucionando de acuerdo a un conjunto de reglas. El hecho de que un elemento sea 0 ó 1 en la nueva generación depende de su valor actual, así como del valor de dos de sus vecinos.

Reglas

Las reglas que sigue el autómata son las siguientes:

 

El nombre “Regla 110” se deriva del hecho de que esta regla puede ser resumida en la secuencia binaria 01101110 la cual, interpretada como un número binario, corresponde al valor decimal 110.

Ejemplo

En la siguiente imagen se muestra un ejemplo de una evolución de la regla 110 tomada a partir de una configuración global inicial aleatoria con distribución pseudouniforme en el cual el espacio celular es de 250 células, donde el estado 0 se muestra en color claro y el estado 1 se muestra en color oscuro.
Se muestra la historia del autómata a través de 250 generaciones.

La Regla 110.

 

Bibliografía

• http://www.redcientifica.com/gaia/ac/auto_c.htm
• http://es.wikipedia.org/wiki/Aut%C3%B3mata_celular
• http://es.wikipedia.org/wiki/Juego_de_la_vida
• http://www.cienciaxplora.com/divulgacion/conoces-juego-vida-conway_2014103100163.html
• https://vonneumannmachine.wordpress.com/2013/12/04/la-regla-110/
• http://en.wikipedia.org/wiki/Rule_110
• http://computacion.cs.cinvestav.mx/~acaceres/docs/dinR110/node5.html