Universos simulados y autómatas celulares

12/02/2014 3 comentarios
Menear

Mundos complejos con reglas sencillas.

"Las leyes de la naturaleza están hechas de forma tal que hacen el universo lo más interesante posible" -- Freeman Dyson --

El juego de la vida

En el año 1930 J. Conway inventó el juego de la vida. El mundo en el que transcurre el juego de la vida es un tablero de N filas y M columnas. Cada casilla puede estar en dos estados: 0 o 1. Normalmente interpretamos que las casillas en el estado 1 están ocupadas por una célula, mientras que las casillas en estado 0 están vacías. Las reglas del juego de la vida nos dicen como las células de nuestro mundo se reproducen o mueren de una generación a la siguiente y son extremadamente sencillas:

  1. Si una célula está rodeada de menos de 2 vecinos o más de 3, la célula muere (por aislamiento y superpoblación respectivamente).
  2. Si una casilla vacía está rodeada de exactamente 3 células nace una célula nueva.

El juego de la vida consiste simplemente en "cargar" un patrón inicial y observar cómo las sencillas reglas hacen evolucionar este patrón. El programa vida.py implementa estas reglas. Las líneas 72-107 cargan un patrón inicial: ponemos tablero[x,y]=1 si queremos que la casilla de coordenadas [x,y] esté ocupada. El lector puede cambiar estas líneas y ver cómo distintas configuraciones evolucionan.

Resulta increíble cómo estas sencillas reglas dan lugar a un mundo que literalmente parece estar lleno de vida. Hay grupos de varias células (¡a veces cientos o miles!) que se mueven todas a la vez, como un organismo pluricelular. Otros grupos de células son capaces de reproducirse tras una metamorfosis que dura varias generaciones. Incluso hay estructuras capaces de crear copias de otras estructuras. Estamos frente a un mundo que ha fascinado durante años tanto a científicos como a aficionados. Tenemos el ejemplo perfecto de lo impredecibles y complejos que pueden llegar a ser los resultados de unas reglas en apariencia sencillas.

Las reglas originales del juego de la vida se suelen abreviar con el código "B3/S23", que quiere decir que nace ("B"orn en inglés) una nueva célula si tiene exactamente 3 vecinos, mientras que si tiene 2 o 3 vecinos permanece viva ("S"tays en inglés). Las líneas 35-42 del programa vida.py implementan las reglas del juego de la vida, y el lector también puede divertirse cambiándolas. Si lo hace, se dará cuenta de que las reglas originales están muy bien escogidas. Si resulta demasiado fácil que aparezcan nuevas células (por ejemplo, las reglas "B2345/S234"), el tablero se nos llena rápidamente de células por todos los lados. Por otro lado si hacemos que las células mueran muy fácilmente (por ejemplo con las reglas "B3/S2"), casi siempre terminaremos con un tablero vacío. Conway escogió precisamente estas reglas con cuidado y después de experimentar mucho con el objetivo de imitar lo más posible las reglas que parecen gobernar la vida en nuestro mundo: por un lado no hay ningún patrón inicial que sea obvio que crece para siempre, y por otro lado existan patrones que sin crecer ni decrecer pueden vivir para siempre (bien oscilando o permaneciendo estáticos),

Autómatas celulares y máquinas de Turing

El juego de la vida es un ejemplo de lo que se llama autómata celular, que en general se puede definir como una rejilla o retículo (en cualquier número de dimensiones) en la que cada celda de la rejilla puede estar en un número de estados.

El concepto de autómata celular fue inventado por Stanislaw Ulam y John von Neumann en los años cuarenta. El estudio de los patrones de crecimiento de cristales y de las máquinas autorreplicadoras (que pueden hacer copias de ellas mismas) les llevo a formalizar el concepto de autómata celular. Aunque fueron objeto de estudio durante un par de décadas, fue John Conway y su juego de la vida quien convirtió a los autómatas celulares en un tema de estudio popular.

Wolfram (el creador del entorno Methematica) se ha dedicado mucho tiempo a estudiar los autómatas celulares. En particular a él se debe una clasificación de autómatas celulares en cuatro categorías

  1. Todos los patrones iniciales acaban rápidamente en un patrón homogéneo e independiente del estado inicial.
  2. Los patrones iniciales acaban rápidamente en un patrón estable u oscilatorio.
  3. Casi cualquier patrón inicial termina en un patrón caótico. Los cambios pequeños en una región rápidamente se expanden por todo el tablero.
  4. Los patrones tienden a desarrollar estructuras aisladas que muestran un comportamiento complejo.

Las líneas que dividen estas cuatro categorías son algo subjetivas. Desde luego la categoría 4, que representa un delicado equilibrio entre que todos los patrones terminen siendo simples oscilaciones, o terminen en un estado caótico que arrasa todo el tablero son los más interesantes. De hecho se conjetura que todos los autómatas celulares que se encuentran en esta categoría son capaces de imitar el comportamiento de cualquier ordenador. Es decir, que son "máquinas universales de Turing" capaces de realizar cualquier cálculo. En particular las reglas originales de Conway pertenecen a este interesante grupo, y uno puede programar el juego de la vida dentro del juego de la vida.

Po fueno, po fale, po malegro

Conway eligió la famosa columna de Juegos matemáticos de Martin Gardner en Scientific American (de la que Investigación y Ciencia es la edición en español) para presentar su juego al mundo. Desde ese momento el juego de la vida ha fascinado a biólogos, físicos, filósofos, matemáticos, economistas... Es el ejemplo perfecto de cómo a partir de unas reglas básicas sencillas puede surgir un comportamiento extremadamente complejo. Leyes que rigen el comportamiento de miles de células emergen de las sencillas reglas del juego de la vida (al igual que las leyes de la química o la evolución emergen de las leyes físicas fundamentales). Las estructuras que surgen en la pantalla parecen diseñadas, e incluso parece que se mueven o actúan con un propósito. Sin duda alguna el juego de la vida es un ejemplo del que se pueden sacar lecciones útiles, tanto si estamos hablando del origen de la vida, del de la conciencia o del papel que juegan las leyes físicas fundamentales en nuestra comprensión del mundo. Los ordenadores personales han jugado un papel fundamental en la popularización del juego de la vida, ya que la posibilidad de jugar y explorar distintos patrones está al alcance de cualquiera.

Nuestra implementación del juego de la vida es muy pobre y poco eficiente, pero afortunadamente el que quiera explorar las ilimitadas posibilidades que ofrece tiene a su disposición varios programas de gran calidad, de los cuales puedo recomendar Golly, que viene con varios patrones interesantes predefinidos. El wiki dedicado al juego de la vida es, sin lugar a dudas, una fuente de información muy útil para el que entienda el inglés.

Los autómatas celulares tienen otras habilidades menos lúdicas, pero más útiles. Se pueden usar para crear procesadores capaces de realizar cálculos, para cifrar datos o crear mecanismos de corrección de errores en la transmisión de información.

Pero, quizás inspirados por el juego de la vida, hay quien se ha atrevido a aventurar que todo nuestro universo es simplemente una simulación, el resultado de un autómata celular operando en un retículo gigantesco. Al igual que nosotros los seres humanos disfrutamos experimentando con el juego de la vida; es posible que una civilización lo suficientemente avanzada como para realizar simulaciones de este tipo las esté realizando (a no ser que no lo hagan por motivos éticos, por ejemplo).

Esta hipótesis se podría refutar simplemente encontrando alguna propiedad de las leyes fundamentales que rigen nuestro mundo que no pueda ser reproducido por un ordenador (máquina de Turing). Roger Penrose, un famoso físico matemático de la Universidad de Oxford ha argumentado varias veces que las leyes de la física deben contener elementos no computables, ya que el cerebro humano, que sigue esas leyes de la física, es capaz de resolver problemas que ninguna máquina de Turing es capaz de resolver (el lector interesado disfrutará de su libro "La nueva mente del emperador"). Roger Penrose cree que la mecánica cuántica, con sus entrelazamientos y colapsos de funciones de onda, es una candidata ideal para encontrar leyes que no puedan simularse. Pero hay quien no está de acuerdo, y piensa que hasta el bizarro comportamiento de la mecánica cuántica puede ser reproducido por un autómata celular. Ni más ni menos que Gerardus 't Hooft, premio de Nobel de física por poner su granito de arena en la construcción del Modelo estándar de la física de partículas. 't Hoof ha llegado a discutir y defender en internet estas ideas con varias personas que las calificaban de poco más que charlatanería. Quién sabe, a lo mejor si miramos muy de cerca los electrones, en vez de super-cuerdas nos encontramos pequeños cuadraditos del juego de la vida, siguiendo escrupulosamente unas reglas similares al "B3/S23". ¿Qué pensáis vosotros?