Sobre los autómatas celulares | Juego de la vida, Regla 30, Regla 110 y más

Las cuatro partes básicas

Todo autómata celular se construye con las mismas cuatro partes. La cuadrícula es el espacio en el que viven las celdas. Puede ser una línea unidimensional, un plano bidimensional como un tablero de ajedrez o incluso un espacio tridimensional. Los estados son lo que puede ser una celda. En el caso más simple, una celda es binaria: negra o blanca, 1 o 0. La vecindad es el conjunto de celdas que influyen directamente en una celda. En una cuadrícula cuadrada suele ser la vecindad de Moore, las ocho celdas que la rodean, o la vecindad de von Neumann, solo norte, este, sur y oeste. Las reglas son el cerebro del autómata: la lógica que da a cada celda su nuevo estado. Por ejemplo: si estoy viva pero tengo menos de dos vecinas vivas, muero de soledad. Cada celda aplica las mismas reglas en el mismo instante.

1. El juego de la vida de Conway

Reglas: B3/S23. Una celda viva sobrevive con 2 o 3 vecinas vivas. Una celda muerta cobra vida con exactamente 3. Cualquier otra celda está muerta en la siguiente generación. John Conway lo diseñó en 1970, y la columna de Martin Gardner en Scientific American lo hizo famoso. Produce planeadores, osciladores y naves espaciales. Bill Gosper encontró el primer cañón de planeadores ese mismo año: un patrón que dispara un nuevo planeador cada 30 generaciones, para siempre. El juego de la vida puede realizar cálculos, ya que los planeadores pueden transportar señales y chocar como puertas lógicas. Sobre todo, muestra cómo un comportamiento complejo surge de reglas simples.

Cañón de planeadores de Gosper en el juego de la vida disparando una corriente diagonal de planeadores — Cañón de planeadores de Gosper tras 330 generaciones. Creado en PictorX.

2. Regla 30

Tipo: un autómata celular elemental unidimensional. El siguiente estado de cada celda depende de sí misma y de sus dos vecinas, y cada generación se dibuja como una nueva fila debajo de la anterior. Stephen Wolfram presentó la Regla 30 en 1983. Si empiezas con una sola celda negra, crece un triángulo caótico. Parece aleatoria a pesar de su regla determinista, tan aleatoria que su columna central se ha usado como generador de números pseudoaleatorios. El mismo tipo de triángulos aparece en el pigmento de la concha del Conus textile.

Triángulo de la Regla 30 crecido a partir de una sola celda negra, caótico a la derecha y a rayas a la izquierda — Regla 30 a partir de una celda negra, 224 generaciones. Creado en PictorX.

3. Regla 110

Tipo: un autómata celular elemental unidimensional, como la Regla 30, con otra tabla de ocho respuestas. Está demostrado que la Regla 110 es computacionalmente universal: Matthew Cook mostró que, con una primera fila adecuada, puede emular cualquier cálculo que realice un ordenador de propósito general. Admite estructuras móviles que viajan sobre un fondo repetido e interactúan cuando se encuentran. Esas colisiones son lo que la demostración usa como lógica. Muestra cómo reglas muy simples pueden emular un cálculo arbitrario.

Regla 110 crecida a partir de una celda a la derecha, que se extiende hacia la izquierda en triángulos anidados — Regla 110 a partir de una celda negra en el borde derecho. Creado en PictorX.

4. Brian's Brain

Estados: apagado, encendido (activo) y refractario. Reglas: una celda apagada se enciende si exactamente 2 vecinas están encendidas. Una celda encendida pasa a refractaria. Una celda refractaria se apaga. Lo diseñó Brian Silverman. Como una celda debe descansar una generación después de encenderse, cada pulso sigue alejándose de donde ya ha estado. El resultado es una multitud de patrones autopropulsados que se parece a las ondas en medios excitables, como el tejido nervioso o el músculo cardíaco, y que a menudo parece vivo y orgánico.

Brian's Brain extendiéndose desde una mancha aleatoria, con las celdas encendidas en amarillo y estelas que se desvanecen en violeta — Brian's Brain 70 generaciones después de una mancha aleatoria, con estelas que se desvanecen. Creado en PictorX.

5. Wireworld

Estados: vacío, cabeza de electrón, cola de electrón y conductor. Reglas: una cabeza se convierte en cola, una cola se convierte en conductor y un conductor se convierte en cabeza cuando exactamente 1 o 2 de sus vecinas son cabezas. Las celdas vacías siguen vacías. Brian Silverman también diseñó Wireworld, en 1987. Las celdas conductoras son cables, y una cabeza seguida de una cola es un electrón que corre por ellos. Puede simular circuitos electrónicos: un bucle de cable con un electrón es un reloj, una pequeña muesca es un diodo y unas pocas celdas forman una puerta lógica. Dentro de él se han construido ordenadores completos, como el ordenador Wireworld de David Moore y Mark Owen, que calcula números primos.

Circuito de Wireworld con dos bucles de reloj, dos diodos y una puerta XOR, con electrones en azul y rojo sobre cable amarillo — Dos relojes, dos diodos y una puerta XOR en Wireworld. Creado en PictorX.

Las 256 reglas y las cuatro clases de Wolfram

Una celda unidimensional con dos vecinas ve uno de ocho patrones, de 111 a 000. Una regla da el nuevo estado para cada uno de ellos, así que ocupa ocho bits, y hay 2⁸ = 256 reglas elementales. Lee las ocho respuestas como un número binario y obtendrás el nombre de la regla: la Regla 30 es 00011110 y la Regla 110 es 01101110. Stephen Wolfram clasificó las reglas según lo que hacen, del orden al caos. 1. La clase 1 acaba en un estado uniforme. 2. La clase 2 acaba en estructuras estables o repetitivas. 3. La clase 3 sigue siendo caótica y de aspecto aleatorio, como la Regla 30. 4. La clase 4 construye estructuras que se mueven e interactúan en la frontera entre el orden y el caos, como la Regla 110.

Clasificación por dificultad

Juego de la vida ★☆☆☆☆ · Regla 30 ★☆☆☆☆ · Brian's Brain ★★☆☆☆ · Wireworld ★★★★☆ · Regla 110 ★★★★★. Los dos primeros se explican solos mientras los miras. La Regla 110 esconde sus estructuras móviles en un fondo que se repite.

Los más bonitos visualmente

1. Brian's Brain · 2. Juego de la vida de Conway · 3. Regla 30 · 4. Regla 110 · 5. Wireworld.

Los más importantes matemáticamente

1. Regla 110, por la universalidad · 2. Juego de la vida, por la universalidad y la emergencia · 3. Regla 30, por el caos y la aleatoriedad · 4. Wireworld, por la lógica digital · 5. Brian's Brain, por los sistemas excitables.

En la naturaleza, la física y la criptografía

Los autómatas celulares se usan para simular sistemas complejos en la naturaleza, la física y la criptografía. La idea se remonta a Stanisław Ulam y John von Neumann en la década de 1940, que usaron una cuadrícula de celdas para diseñar una máquina capaz de copiarse a sí misma. En el mundo real se ven autómatas celulares en el pigmento de algunas conchas, como la del Conus textile, cuyos triángulos se parecen a la Regla 30, y en las escamas del lagarto ocelado, que cambian entre verde y negro según una regla cercana a un autómata celular. Los físicos los usan para modelar el flujo de gases, montones de arena e incendios forestales. La aparente aleatoriedad de la Regla 30 la convirtió en candidata para generadores de números aleatorios y cifrados de flujo.

Explóralos en PictorX

Abre Autómatas celulares para ejecutar los cinco. Mira el cañón de planeadores, una flota de naves espaciales o el R-pentominó, que tarda 1.103 generaciones en estabilizarse. Escribe cualquier regla de tipo juego de la vida como B36/S23, o cualquier número de regla elemental de 0 a 255. Dibuja y borra celdas, envía electrones por los circuitos de Wireworld, une los bordes y cambia al modo colorido. Guarda un PNG o abre el lienzo en el editor de PictorX.

Preguntas frecuentes

¿Qué es un autómata celular?

Una cuadrícula de celdas en la que cada celda tiene un estado. En cada paso todas las celdas se actualizan a la vez según una única regla fija que solo mira una celda y sus vecinas. A pesar de lo simples que son las reglas, los patrones pueden ser complejos e impredecibles.

¿Quién inventó los autómatas celulares?

Stanisław Ulam y John von Neumann, en la década de 1940 en Los Álamos. El juego de la vida de John Conway (1970) popularizó la idea, y Stephen Wolfram estudió las 256 reglas elementales en la década de 1980.

¿Qué autómatas celulares son Turing completos?

De los cinco que hay aquí, está demostrado que la Regla 110 y el juego de la vida son universales, y Wireworld puede contener un ordenador completo. Universal significa que, con el patrón inicial adecuado, pueden realizar cualquier cálculo que haga un ordenador de propósito general.

¿Cuáles son las cuatro clases de Wolfram?

La clase 1 se extingue en un estado uniforme, la clase 2 acaba en estructuras estables o repetitivas, la clase 3 sigue siendo caótica como la Regla 30 y la clase 4 construye estructuras móviles que interactúan, como la Regla 110.

¿Por qué la Regla 30 parece aleatoria?

Cada paso está fijado, pero cada celda mezcla su vecina izquierda con las otras dos de una forma que propaga rápido las pequeñas diferencias. No se ha encontrado ningún patrón simple en su columna central, y por eso se ha usado para generar números aleatorios.