La secuencia máxima de estados únicos en una cuadrícula de autómatas celulares de 6x6 con envoltorio es de 1,717, un resultado que desafía las expectativas de una complejidad explosiva a medida que las cuadrículas crecen. Este hallazgo destaca cómo propiedades matemáticas específicas pueden limitar los comportamientos emergentes incluso cuando se aplican reglas simples en espacios finitos.
Mecánica de los autómatas celulares toroidales
Los autómatas celulares (CA) consisten en una cuadrícula de 'células', cada una capaz de estar viva o muerta. En estos modelos de cuadrículas pequeñas, cada célula tiene ocho vecinos, incluidos aquellos en las esquinas y bordes. Debido a que la cuadrícula se envuelve tanto horizontal como verticalmente, funciona geométricamente como un toro.
Esta imagen demuestra la geometría toroidal donde las células en el borde interactúan con las células en el lado opuesto.
A diferencia de algunas versiones del Juego de la Vida de Conway, estas células no rastrean sus propios estados anteriores. El siguiente turno se determina únicamente por cuántos de sus ocho vecinos estaban vivos actualmente de acuerdo con una regla específica: un conjunto de instrucciones que define qué conteos de vecinos resultan en un estado 'vivo' para el paso siguiente.
El GIF ilustra la evolución dinámica de los estados en un sistema de autómatas celulares como se describe en la sección de mecánica.
“La proporción de la cadena más larga de 6x6 respecto a la cadena más larga de 5x5 no es ni siquiera tan grande como la proporción entre 4x4 y 3x3.”
— Small-Grid Wraparound Cellular Automata
Poda por simetría y estrategia computacional
Para determinar la secuencia más larga obtenible antes de que un patrón se repita, los investigadores deben filtrar los puntos de partida funcionalmente idénticos. Al tener en cuenta las traslaciones, rotaciones, reflexiones e inversiones, el número de configuraciones de inicio únicas puede reducirse drásticamente; por ejemplo, el filtrado de simetrías redujo el caso de 4x4 de 65,536 a solo 805 configuraciones únicas.
La inversión también proporciona un atajo significativo: si una regla y una configuración de inicio están ambas totalmente invertidas (intercambiando todos los estados vivos/muertos), producen los mismos patrones. Esto permite a los investigadores dividir significativamente el espacio de búsqueda total de reglas y configuraciones manteniendo la precisión.
Tendencias de complejidad y factores de divisibilidad
El estudio revela un crecimiento no lineal en la complejidad entre los tamaños de las cuadrículas. Mientras que pasar de 4x4 (14 estados) a 5x5 (916 estados) muestra una expansión explosiva a medida que disminuye la densidad, el salto a 6x6 resulta en solo 1,717 estados. Este aumento modesto sugiere que la divisibilidad puede jugar un papel en la limitación de la variedad de estados.
Gráfico elaborado por HN Digest a partir de cifras de justismills.substack.com; los valores se muestran como en la fuente.
Una teoría es que los números altamente divisibles como el 6 permiten que las cuadrículas se comporten de manera más predecible que los números primos como el 5. Si una cuadrícula de 6x6 fuera perfectamente revestida por subcuadrículas más pequeñas, esas secciones podrían actuar de forma independiente, limitando efectivamente la longitud máxima posible de la secuencia en comparación con geometrías menos 'regulares'.
Límites computacionales de cuadrículas más grandes
Aunque los casos pequeños se han resuelto mediante fuerza bruta y optimización por IA, las cuadrículas más grandes siguen siendo esquivas. Una muestra aleatoria de 20,000 configuraciones de inicio en una cuadrícula de 7x7 ya produjo una secuencia de más de 545,000 pasos, lo que indica una alta complejidad.
Encontrar el máximo exacto para una cuadrícula de 7x7 requiere actualmente recursos significativos; las estimaciones sugieren que tardaría cientos de años en una CPU estándar o aproximadamente cinco años de tiempo continuo de GPU sin avances de ingeniería avanzados.