Autómatas celulares

La idea

Un autómata celular es una cuadrícula de celdas con un estado discreto que evoluciona en pasos de tiempo según una regla local: el estado siguiente de cada celda depende solo de su estado actual y del de sus vecinas. No hay coordinación central ni memoria global, y sin embargo el comportamiento colectivo puede ser extraordinariamente rico. En los autómatas elementales de Wolfram la cuadrícula es una única fila de celdas binarias y la vecindad son tres celdas (izquierda, centro, derecha): hay 2³ = 8 configuraciones posibles y a cada una se le asigna 0 o 1, lo que da 2⁸ = 256 reglas, numeradas por el byte resultante.

Dibujando las generaciones sucesivas una debajo de otra aparecen cuatro clases de conducta: reglas que mueren (clase 1), reglas periódicas (clase 2), reglas caóticas como la regla 30, cuya columna central pasa pruebas de aleatoriedad y se usó como generador pseudoaleatorio, reglas fractales como la regla 90, que reproduce el triángulo de Sierpiński a partir de una sola celda encendida, y reglas de estructuras complejas como la regla 110, de la que se ha demostrado que es computacionalmente universal: puede simular cualquier máquina de Turing.

En dos dimensiones el ejemplo canónico es el Juego de la vida de Conway, con vecindad de Moore (las ocho celdas contiguas) y dos reglas: una celda viva sobrevive con 2 o 3 vecinas vivas y una celda muerta nace con exactamente 3. De ahí emergen objetos con nombre propio: bloques y panales estables, osciladores como el pulsar de periodo 3 y naves como el planeador, que se desplaza una celda en diagonal cada cuatro generaciones. El Juego de la vida también es universal, lo que ilustra una idea profunda: la complejidad no requiere reglas complicadas, solo interacción local repetida.

Fórmulas clave

• Regla elementalsᵢ(t+1) = R[ 4·sᵢ₋₁(t) + 2·sᵢ(t) + sᵢ₊₁(t) ], R = bits del número 0-255
• Número de reglas elementales2^(2³) = 2⁸ = 256
• Bit de la reglabit k de r = (r >> k) & 1, con k = patrón de la vecindad
• Juego de la vida (supervivencia)viva y vecinas ∈ {2, 3} → sigue viva
• Juego de la vida (nacimiento)muerta y vecinas = 3 → nace
• Planeadorperiodo 4, desplazamiento (1, 1): velocidad c/4 en diagonal

Dónde se aplica

Los autómatas celulares se usan como modelos de sistemas donde la interacción es local: la propagación de incendios forestales y de epidemias en mallas espaciales, el flujo de tráfico con el modelo de Nagel-Schreckenberg (que reproduce atascos fantasma a partir de reglas triviales) y la formación de patrones en conchas y pieles de animales. En ingeniería se emplean redes de Boltzmann de red, parientes cercanos, para simular fluidos, y en ciencias de la computación las reglas caóticas como la 30 se han usado para generar números pseudoaleatorios y como componente de funciones hash.

Con programación (Python)

def paso_elemental(fila, regla):
    n = len(fila)
    nueva = []
    for i in range(n):
        izq, cen, der = fila[(i - 1) % n], fila[i], fila[(i + 1) % n]
        patron = 4 * izq + 2 * cen + der
        nueva.append((regla >> patron) & 1)
    return nueva

ancho = 41
for regla in (90, 30):
    fila = [0] * ancho
    fila[ancho // 2] = 1
    print(f"--- regla {regla} ---")
    for _ in range(12):
        print("".join("#" if c else "." for c in fila))
        fila = paso_elemental(fila, regla)

# Juego de la vida: un planeador se desplaza (1,1) cada 4 generaciones
vivas = {(1, 2), (2, 3), (3, 1), (3, 2), (3, 3)}
def paso_vida(vivas, alto, ancho):
    cuenta = {}
    for (r, c) in vivas:
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                if dr or dc:
                    k = ((r + dr) % alto, (c + dc) % ancho)
                    cuenta[k] = cuenta.get(k, 0) + 1
    return {k for k, v in cuenta.items() if v == 3 or (v == 2 and k in vivas)}

print("planeador inicial:", sorted(vivas))
for g in range(4):
    vivas = paso_vida(vivas, 20, 20)
print("tras 4 generaciones:", sorted(vivas), "(desplazado 1 fila y 1 columna)")

La versión en JavaScript, editable y ejecutable en el navegador, está en la página interactiva del tema.

Temas relacionados

Recursión y memoización · Crecimiento logístico · Método Monte Carlo · Complejidad y notación O grande