Autómatas celulares: reglas discretas y patrones colectivos

Módulo 25. Autómatas celulares y modelos basados en agentes

241.1. Una dinámica colectiva definida localmente

Un autómata celular describe un sistema mediante posiciones discretas, estados locales y una regla de actualización. Cada posición cambia según la información de un entorno limitado. Al repetir esa operación aparecen trayectorias colectivas que pueden ser uniformes, periódicas, irregulares o espacialmente organizadas. La descripción local puede ser breve aunque la historia completa resulte difícil de anticipar.

El marco es útil porque hace explícita la relación entre reglas y patrones. Podemos modificar una regla, una condición inicial o una frontera y observar qué cambia. También podemos demostrar propiedades que no dependen de una realización particular, como límites de propagación o la conservación de una cantidad. La simulación y el análisis matemático cumplen funciones complementarias.

Una cuadrícula coloreada, sin interpretación, no explica un fenómeno. Necesitamos saber a qué corresponde cada estado, qué significa una actualización y por qué las interacciones elegidas son pertinentes. Sin esas correspondencias, el autómata sigue siendo un objeto matemático interesante, pero su semejanza visual con una imagen empírica no identifica un mecanismo real.

Los trabajos de Wolfram sobre autómatas elementales impulsaron el estudio sistemático de comportamientos colectivos producidos por reglas simples [1,2]. Su interés no requiere atribuir intención a las celdas. Una celda aplica una función local sin evaluar el patrón global ni intentar construirlo. El patrón pertenece a la evolución conjunta de muchas aplicaciones de esa función.

Conviene separar simplicidad de descripción y simplicidad de comportamiento. Una tabla pequeña puede generar una evolución extensa, pero esa extensión no basta para inferir azar genuino, adaptación o computación universal. Cada propiedad necesita una definición y una comprobación; la apariencia de complejidad solo permite formular preguntas.

Usaremos dos reglas binarias unidimensionales. Una conserva partículas que se desplazan cuando encuentran espacio; la otra sigue la mayoría local. Ambas permiten seguir los cálculos a mano y mostrar cómo una misma densidad puede ocultar organizaciones muy distintas. También estudiaremos qué cambia al pasar de una línea infinita a un anillo finito.

El propósito es aprender a leer un autómata como un modelo completo. Regla, espacio, tiempo, fronteras, inicialización y observables forman una unidad; si omitimos cualquiera de esos elementos, una reproducción puede ejecutar correctamente una tabla de transición y, aun así, estudiar un sistema distinto del que imaginábamos.

241.2. Estados, vecindades y actualización global

Comencemos con una línea de posiciones indexadas por enteros. Cada celda contiene cero o uno y el tiempo avanza en pasos enteros. En un autómata elemental, el estado nuevo de una celda depende de su vecino izquierdo, de ella misma y de su vecino derecho. Todas las celdas aplican la misma regla a los estados del tiempo anterior.

La función local recibe tres bits, por lo que existen ocho entradas posibles. Para cada una debemos elegir una salida entre cero y uno. El número de funciones locales posibles es dos elevado a ocho, igual a doscientas cincuenta y seis. Esa cifra cuenta solo las reglas de esta clase específica.

Con k estados y una vecindad de m posiciones ordenadas, hay k elevado a m configuraciones locales. Una regla determinista asigna una de k salidas a cada configuración, de modo que el número de reglas es k elevado a la potencia k elevado a m. Así, ampliar los estados o la vecindad multiplica rápidamente el espacio de posibilidades.

La vecindad debe especificar posiciones y orientación, porque una regla puede tratar de manera distinta izquierda y derecha. En dos dimensiones podemos usar vecinos que comparten lados, añadir diagonales o definir otros entornos. Esas elecciones alteran rutas de interacción y simetrías. Una imagen cuadrada, sin esa especificación, no determina qué celdas influyen entre sí.

La actualización global es la aplicación simultánea de la función local en todas las posiciones; simultánea significa que todas leen el mismo estado anterior. En un programa suele implementarse construyendo una configuración nueva antes de reemplazar la antigua. Actualizar una lista sobre sí misma mientras se recorre puede introducir una dependencia del orden que corresponde a otra dinámica.

Una configuración es el conjunto de estados de todas las celdas en un instante. La evolución transforma configuraciones completas. Aunque la regla sea local, podemos estudiar la función global que produce, sus puntos fijos, ciclos y estados alcanzables.

El marco admite variantes con ruido, heterogeneidad o actualización asincrónica, que deben declararse como cambios del modelo. En este capítulo usaremos reglas homogéneas, deterministas y sincrónicas para aislar sus consecuencias. Más adelante examinaremos por qué modificar el calendario de actualización puede cambiar cualitativamente un patrón.

241.3. Leer una regla sin depender de una imagen

La convención usual de numeración de reglas elementales ordena las entradas desde ciento once en binario hasta cero cero cero. Las ocho salidas forman un número binario cuyo valor decimal identifica la regla. La convención debe acompañar la tabla, porque invertir el orden de lectura cambia el número aunque no cambien las ocho correspondencias.

Conviene contrastar la regla ciento ochenta y cuatro con la regla doscientos treinta y dos. La primera puede interpretarse mediante partículas que avanzan a la derecha si la celda siguiente está vacía. La segunda asigna uno cuando al menos dos de las tres posiciones de la vecindad contienen uno; en ella, la propia celda participa en la mayoría.

Las salidas de la regla ciento ochenta y cuatro son uno, cero, uno, uno, uno, cero, cero, cero. Sus posiciones activas valen ciento veintiocho, treinta y dos, dieciséis y ocho, que suman ciento ochenta y cuatro. Para la regla de mayoría, la suma es ciento veintiocho más sesenta y cuatro más treinta y dos más ocho, igual a doscientos treinta y dos.

Podemos comprobar la interpretación de movimiento con casos particulares. En la vecindad uno uno cero, la celda central está ocupada y tiene espacio a la derecha, por lo que queda vacía. En uno cero uno, la celda central estaba vacía y recibe la partícula de la izquierda. En cero uno uno, la partícula central permanece porque su destino está ocupado.

La actualización simultánea impide que una partícula aproveche dentro del mismo paso un hueco creado por otra que acaba de moverse, ya que cada decisión usa la ocupación anterior. Esta restricción forma parte del mecanismo y determina la velocidad de reorganización. Una implementación secuencial podría permitir movimientos adicionales o favorecer una dirección de recorrido.

En la regla de mayoría, una celda aislada entre dos estados opuestos cambia para coincidir con ellos. Sin embargo, no debemos concluir que toda configuración termina homogénea. Dos vecinos más la propia celda pueden sostener dominios persistentes o ciclos, según la organización inicial. La intuición verbal de «seguir a la mayoría» necesita contrastarse con la tabla completa.

Una tabla de transición es una especificación reproducible. Permite comprobar un programa con las ocho entradas y comparar implementaciones sin depender del color o de la orientación de un gráfico. En reglas más grandes rige el mismo principio; una descripción clara del mecanismo debe permitir decidir la salida de cualquier configuración local admisible.

241.4. Fronteras y velocidad de propagación

Una línea infinita es un objeto matemático distinto de una fila finita en una pantalla. Para simular una fila debemos decidir qué ocurre en sus extremos. Podemos conectarlos mediante condiciones periódicas, fijar estados externos, permitir entradas y salidas o usar reglas especiales. Cada opción define una dinámica diferente.

Las condiciones periódicas convierten la fila en un anillo. El vecino derecho de la última celda es la primera y el vecino izquierdo de la primera es la última. Esta elección elimina los extremos especiales, pero introduce una conexión que puede ser artificial respecto del fenómeno representado. Una perturbación puede rodear el anillo y volver a la región donde comenzó.

Con estados externos fijos, las fronteras pueden influir sobre el interior. En una regla de radio uno, esa influencia no puede recorrer más de una celda por paso. Después de t pasos, el estado de una celda depende solo de posiciones situadas a distancia no mayor que t en la configuración inicial. La afirmación se demuestra encadenando las dependencias locales.

Para una regla de radio r, el límite es r por t posiciones. Se trata de una cota superior para la propagación de la influencia; no todas las reglas transmiten información a esa velocidad. Algunas borran perturbaciones, otras las mantienen inmóviles y otras las desplazan más lentamente. La estructura local establece lo que es posible; la regla concreta determina lo que sucede.

Esta propiedad permite simular una región de una línea infinita durante un tiempo finito. Si añadimos un margen suficientemente amplio y conocemos los estados pertinentes, las fronteras artificiales no alcanzarán la región observada dentro del horizonte. Debemos justificar el margen a partir del radio y la duración, porque una fila larga no siempre basta.

La elección de fronteras afecta también a las conservaciones. En la regla de partículas, un anillo conserva el número total porque toda salida de una celda entra en otra del mismo sistema. En un dominio abierto, una partícula puede abandonar el extremo y reducir el total observado. Esa pérdida puede ser correcta para el modelo; no implica necesariamente un error de programación.

La forma de representar el espacio debe elegirse según la pregunta. Un anillo puede servir para estudiar la dinámica interna sin extremos, mientras que un tramo abierto permite examinar entradas y evacuación. Comparar ambos ayuda a distinguir patrones sostenidos por reglas locales de efectos de conectividad. El tamaño y la frontera deben acompañar cualquier afirmación sobre comportamiento colectivo.

241.5. Conservación y flujo en la regla 184

La interpretación de partículas puede expresarse mediante un flujo local. Sea J_i igual a uno cuando la celda i está ocupada y su vecina derecha vacía; en los demás casos vale cero. Ese indicador cuenta una partícula que cruza hacia la derecha durante el paso. La actualización suma entradas desde la izquierda y resta salidas hacia la derecha.

En un anillo, al sumar sobre todas las celdas, las entradas y salidas se cancelan y el número total de partículas permanece constante. La demostración no necesita simular cada configuración ni suponer una distribución aleatoria inicial; es una propiedad algebraica de la regla y de la frontera periódica.

Consideremos ocho celdas con cuatro partículas inicialmente agrupadas. La tabla muestra las configuraciones sucesivas y el número de movimientos posibles desde cada una. Las cadenas binarias son estados exactos del anillo, escritos a partir de una posición inicial fija; la última celda se conecta con la primera.

La densidad permanece en una mitad, pero el flujo aumenta mientras la organización cambia. Al principio solo la partícula situada al frente del bloque encuentra espacio. Después aparecen más huecos entre partículas y más movimientos simultáneos. Finalmente, el patrón alternante permite que todas avancen en cada paso, con un flujo medio por enlace de una mitad.

La densidad no describe completamente el estado dinámico. Dos configuraciones con cuatro partículas pueden tener flujos distintos porque sus pares ocupada-vacía se distribuyen de manera diferente. Para predecir el movimiento necesitamos información espacial adicional. Este ejemplo relaciona la descripción microscópica, las correlaciones entre vecinos y los observables colectivos sin atribuir intenciones a las partículas.

La conservación tampoco significa inmovilidad. Una cantidad global puede permanecer fija mientras cambian distribución, flujo y estructura; del mismo modo, un patrón espacial puede desplazarse sin modificar su forma. Separar estas propiedades evita llamar equilibrio a cualquier estado en que una media deja de cambiar.

La regla es una idealización de transporte con exclusión y velocidad máxima de una celda por paso. No incluye aceleración, trayectorias continuas ni diferencias entre partículas. Sirve para aislar cómo la ocupación y el espacio disponible producen restricciones colectivas. Aplicarla a un sistema real exigiría justificar a qué corresponden una celda, una partícula y una unidad temporal.

241.6. Mayoría local y límites de una descripción promedio

La regla doscientos treinta y dos asigna a cada celda la mayoría de su vecindad de tres posiciones. Parece una dinámica de consenso, pero su comportamiento depende de la disposición espacial. La regla compara un entorno pequeño y no conoce la proporción global de unos. Por eso no podemos deducir un resultado colectivo solo a partir de la palabra «mayoría».

En un anillo de ocho celdas, la configuración alternante cero uno cero uno cero uno cero uno pasa al patrón complementario en un paso, porque cada celda tiene dos vecinos del estado opuesto. En el paso siguiente vuelve a la configuración original. Todas las celdas permanecen activas, aunque la densidad global sea siempre una mitad.

La configuración cero cero uno uno cero cero uno uno tiene la misma densidad, pero es un punto fijo. Cada celda comparte su estado con al menos uno de sus vecinos y, contando su propio estado, forma una mayoría local. Ninguna cambia. Dos configuraciones con idéntica proporción de estados producen actividad máxima o actividad nula.

Podemos definir la actividad como la fracción de celdas que cambian entre dos pasos. En el patrón alternante vale uno; en el patrón de parejas, cero. Esta medida añade información que la densidad pierde. También podemos estudiar longitud de dominios, correlaciones y distribución de vecindades, según qué propiedad del patrón queremos explicar.

Una aproximación de campo medio supone que los tres estados de una vecindad son independientes y valen uno con probabilidad p. Bajo ese supuesto, la probabilidad de una mayoría de unos es la suma de los tres casos con exactamente dos unos y del caso con tres. La expresión resultante es tres p al cuadrado menos dos p al cubo.

Si la configuración inicial es una secuencia de variables independientes con probabilidad p, esta expresión da exactamente la marginal del primer paso en una línea infinita. Después, las actualizaciones comparten entradas y generan dependencias, de modo que en los pasos posteriores la fórmula es solo una aproximación.

Con p igual a una quinta parte, la fórmula produce cero coma ciento cuatro; con p igual a cuatro quintas partes, cero coma ochocientos noventa y seis. Con una mitad, produce una mitad. Esta última predicción es compatible tanto con el ciclo alternante como con el patrón fijo de parejas, por lo que no distingue sus dinámicas.

El ejemplo muestra que una descripción colectiva exige seleccionar observables y justificar qué información podemos omitir. Una ecuación para la densidad puede ser útil sin describir actividad ni estructura. Su éxito para una media no autoriza a tratar como equivalentes todas las configuraciones con esa media.

241.7. Patrones, ciclos y tamaño finito

Un autómata determinista en un espacio finito tiene un número finito de configuraciones. Si hay N celdas binarias, existen dos elevado a N estados globales posibles. Al iterar una regla fija, alguna configuración debe repetirse después de visitar como máximo ese número de estados distintos. Desde la repetición, la trayectoria entra en un ciclo.

La demostración usa solo determinismo y finitud. Cuando reaparece una configuración, su sucesora es la misma que antes y lo mismo ocurre en todos los pasos posteriores. Una trayectoria puede contener primero un tramo transitorio y luego un período. La suma de las longitudes del transitorio y del ciclo no supera el número de configuraciones disponibles.

Para ocho celdas binarias, observar doscientas cincuenta y siete configuraciones sucesivas garantiza una repetición. Si además la regla conserva cuatro partículas, solo son accesibles las configuraciones con cuatro unos. Hay setenta combinaciones de ese tipo, de modo que la cota puede reducirse. La conservación restringe el espacio dinámico, aunque no basta para determinar qué ciclo se alcanza.

Esta periodicidad eventual no significa que el ciclo aparezca pronto en sistemas grandes. El número de configuraciones crece exponencialmente y una cota general puede ser enorme. Una simulación breve puede mostrar un transitorio largo que parece irregular. A la inversa, detectar un ciclo corto en un anillo pequeño no demuestra que una línea infinita tenga el mismo comportamiento.

Aumentar primero el tiempo en un sistema de tamaño fijo lleva finalmente a un ciclo; aumentar el tamaño, en cambio, puede permitir estructuras y períodos nuevos. Una afirmación sobre comportamiento a gran escala debe indicar cómo se relacionan tamaño y horizonte. Extrapolar una observación finita exige estudiar esa dependencia.

Los diagramas de espacio y tiempo colocan configuraciones sucesivas una debajo de otra. En ellos, un patrón que se desplaza deja una trayectoria inclinada y un patrón estacionario puede producir una columna repetida. La orientación y la proporción entre ejes son convenciones gráficas. Una pendiente visual solo se convierte en velocidad después de fijar las unidades espaciales y temporales.

Las clasificaciones de comportamiento propuestas por Wolfram distinguen, de manera descriptiva, evolución hacia homogeneidad, estructuras periódicas, irregularidad extendida y combinaciones de estructuras localizadas persistentes [2]. Sirven para organizar observaciones, pero no sustituyen las definiciones formales de caos, universalidad o estabilidad ni son una prueba exhaustiva para cualquier regla e inicialización.

Un estudio reproducible debe conservar trayectorias o resúmenes suficientes para comprobar esas descripciones. Etiquetar una regla después de mirar una sola imagen puede ocultar condiciones iniciales excepcionales, efectos de frontera o transitorios. La clasificación es más útil cuando se acompaña de medidas, rangos de condiciones y criterios explícitos.

241.8. Irregularidad, información y capacidad de cómputo

Un patrón determinista puede resultar visualmente irregular sin recibir azar nuevo en cada paso. La regla transforma información presente en la condición inicial y en su propia especificación. Para medir incertidumbre necesitamos definir un conjunto de configuraciones posibles y una distribución sobre ellas; una imagen aislada no la contiene.

En un sistema finito determinista, la entropía de Shannon de la configuración completa no aumenta al aplicar una función fija a una configuración aleatoria. Distintas entradas pueden producir la misma salida, con lo que se pierden distinciones, pero la transformación no añade una fuente aleatoria independiente. Esta afirmación sobre el estado completo no impide que ciertos resúmenes o marginales aparenten mayor variabilidad.

La proporción de unos es un ejemplo de resumen insuficiente. Los patrones alternante y de parejas tienen proporciones iguales y, por tanto, la misma entropía calculada solo a partir de las frecuencias de cero y uno. Sin embargo, sus relaciones espaciales y su actividad bajo mayoría son distintas. Medir organización requiere examinar dependencias además de abundancias de estados.

La complejidad algorítmica pregunta, en cambio, cuánto cuesta describir una configuración. Una trayectoria generada por una regla breve desde una condición simple puede describirse mediante esos datos y el tiempo de evolución, aunque imprimir todos sus estados requiera mucho trabajo. Longitud de descripción y costo de cálculo son propiedades distintas, como vimos en el módulo anterior.

La capacidad de cómputo universal exige una demostración más específica. Cook probó que la regla ciento diez puede simular computación universal mediante una construcción de patrones e interacciones [3]. El resultado incluye codificaciones y condiciones iniciales organizadas, con patrones periódicos de fondo. No afirma que cualquier semilla breve o cualquier ejecución típica realice espontáneamente un cálculo útil.

Tampoco convierte un anillo fijo de ocho celdas en una máquina de memoria ilimitada. Los resultados de universalidad consideran familias de codificaciones y recursos espaciales adecuados, mientras que el anillo tiene una cantidad fija de estados globales. La periodicidad eventual de un sistema finito y la universalidad de una construcción sin esa limitación no se contradicen.

Para evaluar un patrón computacional debemos identificar qué representa la entrada, qué reglas procesan la información y cómo se lee la salida. Sin esa identificación, llamar cómputo a cualquier evolución puede volver el término demasiado amplio para explicar algo. Una construcción universal es relevante precisamente porque establece una correspondencia verificable con una clase definida de procedimientos.

Estas distinciones permiten apreciar el alcance de los autómatas sin exagerarlo. Pueden mostrar organización, transporte, memoria y capacidad computacional bajo condiciones concretas, aunque cada propiedad necesita evidencia propia. Un dibujo sorprendente puede motivar el análisis, pero la comprensión llega cuando podemos explicar qué conserva, transforma o permite calcular la dinámica.

241.9. Diseñar un experimento con autómatas celulares

El protocolo comienza especificando estados, vecindad, regla, calendario, tamaño y fronteras. Después define condiciones iniciales y observables. Si usamos una inicialización aleatoria, debemos indicar su distribución y sus semillas. Una densidad inicial fija puede significar un número exacto de partículas distribuidas al azar o estados independientes con esa probabilidad; ambas construcciones generan conjuntos distintos.

En la primera, el total de partículas es constante entre réplicas; en la segunda, fluctúa alrededor de su media. Para una regla que conserva ese total, la diferencia de inicialización persiste durante toda la evolución. Si se mezclan ambos diseños, puede atribuirse a la dinámica una variación que ya estaba presente en la preparación del sistema.

Los observables deben responder a la pregunta. Para transporte podemos medir flujo, velocidad y congestión; para reorganización, actividad, dominios y correlaciones; para memoria, dependencia respecto de perturbaciones iniciales. Una colección de imágenes puede complementar esos resúmenes, pero no reemplaza criterios que permitan comparar reglas y escenarios.

Las pruebas de implementación incluyen todas las transiciones locales, configuraciones uniformes y ejemplos pequeños calculados a mano. En la regla ciento ochenta y cuatro comprobamos la conservación con fronteras periódicas y los límites del flujo; en la regla de mayoría, el ciclo alternante y el patrón fijo de parejas. Cada prueba examina una propiedad que podría fallar por un error concreto.

Para estudiar la sensibilidad a condiciones iniciales podemos modificar una celda y comparar trayectorias mediante la distancia de Hamming, el número de posiciones diferentes. Su evolución describe la propagación de una perturbación bajo ese diseño. Que la distancia crezca durante algunos pasos todavía no demuestra caos en sentido formal; para ello hacen falta una definición y un análisis acordes con el sistema discreto.

Una conclusión de gran escala exige variar el tamaño y la duración. Si un patrón desaparece al duplicar el anillo o al cambiar las fronteras, necesitamos explicar esa dependencia. También conviene distinguir transitorios de regímenes persistentes y declarar qué intervalo temporal se resumió, porque el promedio de toda una trayectoria puede mezclar fases con propiedades distintas.

La comparación con datos exige además establecer correspondencias de escala y de mecanismos. Una celda puede representar una región, una unidad de ocupación o una entidad, pero esas interpretaciones no son equivalentes. El éxito visual de una simulación no elimina la necesidad de contrastar observables y alternativas que podrían producir patrones semejantes.

241.10. Qué enseña una regla local

Un autómata celular permite estudiar cómo restricciones locales producen consecuencias colectivas. La definición contiene pocos elementos (qué estados existen, quién interactúa con quién, cuándo se actualiza y qué ocurre en los límites) y cada uno condiciona la dinámica. La claridad de esa especificación hace posible demostrar propiedades y reproducir trayectorias.

La regla de partículas mostró que conservar densidad no conserva flujo ni organización. Un bloque congestionado y un patrón alternante pueden contener el mismo número de partículas y permitir cantidades distintas de movimientos. La regla de mayoría mostró que una densidad idéntica puede sostener actividad completa o inmovilidad. En ambos casos, las relaciones espaciales explican diferencias invisibles para una media.

El análisis de fronteras y tamaño separó propiedades locales de posibles artefactos del dominio. La influencia tiene un alcance limitado por paso, pero puede recorrer un anillo y regresar. Los sistemas finitos acaban entrando en ciclos, mientras que las preguntas sobre espacios crecientes o infinitos requieren otro tratamiento. Estas distinciones evitan tomar una pantalla finita como representativa de todas las escalas.

También separamos irregularidad, información y computación. Una evolución determinista no recibe azar nuevo por parecer desordenada. Un patrón comprimible puede ser costoso de calcular. La universalidad requiere una construcción formal con codificación y recursos adecuados. Mantener esas diferencias permite usar resultados fuertes sin extenderlos a afirmaciones que no demuestran.

Los autómatas son especialmente útiles cuando una simplificación explícita permite aislar un mecanismo. Podemos preguntar qué ocurre si existe exclusión, si una regla local conserva partículas o si la mayoría incluye a la propia celda. El resultado no necesita representar todos los detalles de un sistema real para ser informativo, pero debe mantenerse dentro del alcance de la pregunta que respondió.

El siguiente capítulo ampliará el marco hacia modelos basados en agentes. Las entidades podrán diferir en atributos, decisiones, recursos y relaciones. El espacio de interacción, por su parte, no tendrá que ser una cuadrícula regular. Permanecerá la exigencia metodológica de describir mecanismos con precisión, distinguir supuestos de resultados y evaluar qué patrones dependen de cada decisión del modelo.

Referencias

1. Wolfram, S. (1983). Statistical mechanics of cellular automata. Reviews of Modern Physics, 55(3), 601–644. DOI: 10.1103/RevModPhys.55.601.
2. Wolfram, S. (1984). Universality and complexity in cellular automata. Physica D: Nonlinear Phenomena, 10(1–2), 1–35. DOI: 10.1016/0167-2789(84)90245-8.
3. Cook, M. (2004). Universality in elementary cellular automata. Complex Systems, 15(1), 1–40. DOI: 10.25088/ComplexSystems.15.1.1. Texto original.

Nota de los ejemplos. Las trayectorias de ocho celdas, las verificaciones de tablas y los cálculos de densidad, flujo y mayoría son desarrollos propios bajo las reglas y fronteras especificadas.