La hormiga de Langton: dos reglas, 10,000 pasos de caos y una autopista que nadie ha sabido explicar, con animación

Imagina una hormiga sobre un tablero infinito de casillas blancas. Solo sigue dos reglas: si está en una casilla blanca, gira a la derecha; si está en una negra, gira a la izquierda. En los dos casos cambia el color de la casilla y avanza una. Nada más: no hay azar ni memoria. Y sin embargo, durante unos 10,000 pasos deja un rastro que parece puro caos, hasta que de repente se pone a construir una «autopista» perfecta que se aleja para siempre. Es la hormiga de Langton, y todavía nadie ha sabido demostrar por qué lo hace.

Las reglas

La inventó en 1986 Chris Langton, un investigador estadounidense que estudiaba cómo surgen comportamientos complejos a partir de reglas sencillas y que poco después dio nombre a un campo entero, la vida artificial. La hormiga es un autómata celular, como el famoso juego de la vida de Conway: un tablero de casillas que cambian según unas reglas fijas. Estas son todas:

1. El tablero empieza todo en blanco, y la hormiga, en una casilla cualquiera mirando hacia arriba.
2. Si la casilla en la que está es blanca, la hormiga gira 90° a la derecha. Si es negra, gira 90° a la izquierda.
3. Cambia el color de la casilla: la blanca pasa a negra y la negra, a blanca.
4. Avanza una casilla en la dirección en la que mira, y vuelve al paso 2.

Pruébalo

La animación simula la hormiga en un tablero de 160 por 160 casillas. La hormiga es el cuadrado rojo. Con la regla de Langton, el texto de debajo te dice en qué fase está, y cuando aparece la autopista te avisa del paso exacto en que empezó. Usa «Paso a paso» para ver las reglas en acción y «Rápida» para llegar antes al final. Puedes también tocar el tablero para pintar casillas mientras la hormiga camina, y ver cómo reacciona a los obstáculos. Los otros botones cambian la regla, como se explica más abajo.

Tres fases: orden, caos y orden

Si se empieza con el tablero en blanco, la hormiga siempre pasa por las mismas tres fases:

• Simplicidad. Durante los primeros cientos de pasos dibuja formas pequeñas y ordenadas, a menudo simétricas.
• Caos. Después, el dibujo se vuelve irregular. La hormiga va y viene sin ningún patrón a la vista, y deja una mancha de casillas negras que crece despacio. Esta fase dura casi diez mil pasos.
• Orden. En el paso 9,976, la hormiga empieza a repetir un mismo recorrido de 104 pasos. Al final de cada uno ha avanzado dos casillas en diagonal y ha dejado doce casillas negras más, siempre con la misma forma. Ese ciclo, repetido sin fin, va trazando una franja diagonal: la autopista. Como el tablero es infinito, nada la detiene.

Lo inquietante es que no hay ninguna pista de lo que va a pasar. A los 9,000 pasos, el tablero parece tan desordenado como a los 2,000, y la única forma de saber que la hormiga acabará construyendo la autopista es dejarla caminar hasta el paso 9,976.

Lo que se sabe y lo que no

Con reglas tan sencillas, cabría esperar que los matemáticos lo tuvieran todo resuelto. No es así. Esto es lo que se sabe:

• La hormiga nunca se queda encerrada. Empiece el tablero como empiece, aunque tenga casillas negras en cualquier posición, su recorrido no tiene límite: siempre acaba alejándose tanto como se quiera del punto de partida. Es el llamado teorema de Cohen-Kong, demostrado a principios de los noventa.
• La autopista parece inevitable, pero nadie lo ha demostrado. Con todas las configuraciones iniciales finitas que se han probado, la hormiga acaba construyendo la misma autopista, antes o después. Es la conjetura de la autopista, y sigue sin demostrar. Si pintas casillas en la animación, lo más probable es que veas lo mismo: más caos, pero al final la autopista.
• Puede calcular cualquier cosa. En 2002, Anahí Gajardo, Andrés Moreira y Eric Goles demostraron que, colocando bien las casillas negras al principio, la trayectoria de la hormiga puede calcular cualquier circuito lógico. Es decir, que este juego de dos reglas puede hacer, en teoría, cualquier cálculo que haga un ordenador.

Más colores, otras figuras

Greg Turk y Jim Propp extendieron la idea a más de dos colores. Las casillas pasan por los colores en orden, y la regla se escribe con una letra por color: R (derecha) o L (izquierda), según hacia dónde gira la hormiga al pisar ese color. La hormiga original es RL. Algunas de las variantes que puedes probar en la animación:

Hay incluso una regla para saber qué variantes crecen con simetría: basta con que en la palabra, leída en círculo, todas las letras vayan en parejas iguales seguidas, como en LLRR o RLLR. Otras, como RLR, crecen de forma caótica, y nadie sabe si alguna vez construirán una autopista.

La hormiga en Python

Este programa simula 11,000 pasos sobre un tablero infinito: solo guarda las casillas negras, en un conjunto. Después busca el paso desde el que la hormiga repite el ciclo de 104 pasos y dibuja el tablero en la terminal con caracteres de medio bloque, que meten dos casillas en cada carácter:

negras = set()                     # casillas negras; todas las demás son blancas
x, y, dx, dy = 0, 0, 0, -1         # posición y dirección: empieza mirando hacia arriba
posiciones = [(x, y)]

for paso in range(11000):
    if (x, y) in negras:           # casilla negra: gira a la izquierda y la vuelve blanca
        dx, dy = dy, -dx
        negras.remove((x, y))
    else:                          # casilla blanca: gira a la derecha y la vuelve negra
        dx, dy = -dy, dx
        negras.add((x, y))
    x, y = x + dx, y + dy
    posiciones.append((x, y))

# La autopista empieza en el primer paso desde el que cada 104 pasos la hormiga se mueve igual
def avance(i):
    return posiciones[i + 104][0] - posiciones[i][0], posiciones[i + 104][1] - posiciones[i][1]

inicio = len(posiciones) - 105
while avance(inicio - 1) == avance(inicio):
    inicio -= 1
print("Casillas negras:", len(negras))
print("La autopista empieza en el paso", inicio, "y avanza", avance(inicio), "cada 104 pasos")

# Dibujo: cada carácter son dos casillas, una encima de otra
xs = [c[0] for c in negras]
ys = [c[1] for c in negras]
for fila in range(min(ys), max(ys) + 1, 2):
    print("".join(" ▀▄█"[((col, fila) in negras) + 2 * ((col, fila + 1) in negras)]
                  for col in range(min(xs), max(xs) + 1)))

salidaCasillas negras: 834
La autopista empieza en el paso 9976 y avanza (-2, 2) cada 104 pasos
                            ▄▀▀▄▄██▀▀▀▀▀▀▀▀▀▀▄ ▀█▄                 
                           █▀█  ▄▀▀       ▄  ▄ ▀▀ █                
                    ▄▄▄▀█  █▀ ▀▄▀    ▄    ▀██ ▄▄  ▄▄█              
                     █ █▄▄▀██  █▀▄█▀▀█▄█▀▄ ▄▀ ▀  █▄█▀  ██▄         
                  ▄█▄ ▄▄ ▀ ▄ ████▀ █▄▀▄▄▀███▄▄█ ▄ ███ █ ▀ █        
                  ▀ ▀▀█ █ ▀▀▄▀▄█ ██▄▀▀ █▀ ▀▄ ▄▀▀███▄▀▀▀ █▀▄▄       
                  ▄█▄ ▀ ▄ ▄ ▄▄ ▄██ ▀█  ▄█  ▀▀ ▄   ██▄▀▄▄  ▄█▀▄     
                ▄█▄ ▀▀█  ▀█ ▄ ▀█ █▀▄▄▄█▀█▄ ▀▄ ▄▄▀▄▄█▀ █▀▀▀  ▄▀     
              ▄█▄ ▀▀█  ▀ ▀█ ▄▄ █ ▄█ ▀██  █▄▄▄▄ ▄███ ▀█▄█▄ █▄ ▀▀▄   
            ▄█▄ ▀▀█  █▄▀▄█▄ ▀▄█▀█ ▀ █▄▀▀     ▄██▄ ▄█▄█ ▀ ▄  ▀   █  
          ▄█▄ ▀▀█  █▄▀  ▀  ▄▀█▄▄█▀▀██▀▀████▄█▄▄█▀▀█  █▄   ▀▄  ▄█   
        ▄█▄ ▀▀█  █▄▀  ▄▀▀▄ █▄██▄▄ ██ █▀▄█▀█ █▀▀  ▄█▄ █▄█▀  ██▀▀ █  
      ▄█▄ ▀▀█  █▄▀   █     █▀██▀▄█▄██▀██  ▄ ▄▀ ▀▄ ▀█ ▀▄▄ ▄▀▀▄  █   
    ▄█▄ ▀▀█  █▄▀     █ ▄▄ ▀ ▄▄▀▀▀█ ▀▄ ▀▀███▄▀▀▄  ▀██▀████▀█▄  ▀▀   
  ▄█▄ ▀▀█  █▄▀        ▀██▀▀▄█ ▄▀█ ▄ ▀▀ █▄ ▄█ ▄ ▄▀▄█  █  █▄ ▀▄█     
▄█▄▄█▀█  █▄▀                 █  █   ▄▀ ▀▀▀▀▀██▀▄█ ▀ █▀ ▄▀▀██ █     
▀█▀  █ █▄▀                    ▀▄▄▀  █      ▀▄▄▀▀▄▄▀▀  ▄▀▀ █▀██▄    
▄▀  ██▄▀                            ▀▄█▀ ▄███▀   ▄█▀▀█ ██▀▄▀█▀▀▄   
▀▄█▀ ▀                                ▀▀    ▀▀    ▀▀ █▀█▄▀█ ▀████  
  ▀▀                                                     ██ ▀▀ ▀▀  
                                                      ▄▀ █▀▄▄█▀▀█▄█
                                                      ▀▄█▀ ▀  ▀▄▄▀ 
                                                        ▀▀         

El giro se hace sin ángulos: con y creciendo hacia abajo, como en una pantalla, girar a la derecha es convertir la dirección (dx, dy) en (-dy, dx), y girar a la izquierda, en (dy, -dx). En la salida se ve la mancha del caos arriba a la derecha y la autopista bajando en diagonal hacia la izquierda. Como no hay ningún azar, el resultado es idéntico cada vez que se ejecuta, en cualquier ordenador.

Por qué fascina

En el juego del caos, el azar acababa dibujando una figura perfecta. La hormiga de Langton es lo contrario: no tiene nada de azar, sus reglas caben en una línea y se puede simular con lápiz y papel, y aun así su comportamiento no se puede predecir sin ejecutarla paso a paso. Es uno de los ejemplos más claros de emergencia: un comportamiento complejo que no está escrito en ninguna de las reglas, sino que sale de cómo se combinan. Es la misma idea que ayuda a entender cómo las hormigas reales organizan un hormiguero sin que ninguna lo dirija. Y es también un recordatorio útil para cualquier programador: que un código sea corto no quiere decir que sea fácil saber lo que hará.

Fuentes: Christopher G. Langton, «Studying artificial life with cellular automata», Physica D (1986); A. Gajardo, A. Moreira y E. Goles, «Complexity of Langton’s ant», Discrete Applied Mathematics (2002); la página de Wikipedia sobre la hormiga de Langton. Las cifras de la autopista (paso 9,976, ciclo de 104 pasos, dos casillas en diagonal y doce casillas negras por ciclo) las hemos comprobado simulándola. El programa se ejecutó con Python 3.13. La animación y las imágenes, incluida la portada, las genera el propio algoritmo: decodigo.com.