 |
 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Raúl Rechtman | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Los autómatas celulares son sistemas dinámicos discretos
que se definen de una manera sencilla y poseen una gran complejidad, aparte de muchas otras bondades. Nos interesa presentar su calidad de instrumento relativamente sencillo para modelar sistemas complejos como gases fuera de equilibrio, ferromagnetos, reacciones químicas, sistemas inmunológicos, interacción entre genes biológicos, y ácidos nucleicos. Como veremos, un autómata celular es esencialmente una regla de evolución temporal sobre un conjunto discreto, es decir, dado un punto de este conjunto, presentamos una regla que le asocia otro punto del conjunto. El estudio de sistemas cuya construcción es sencilla pero cuyo comportamiento resulta extremadamente complicado ha llevado a una nueva disciplina de estudio llamada teoría de sistemas complejos, en la cual los métodos computacionales juegan un papel central. Partiendo de algunos ejemplos sencillos, queremos presentar una breve introducción a esta disciplina.
Para definir un autómata celular empezamos un juego sencillo. Tomamos una hoja de papel cuadriculado y en el primer renglón de arriba para abajo, pintamos o marcamos el cuadrito de en medio. Ésta es la condición inicial del juego cuya regla es la siguiente: pasa al siguiente renglón y marea los cuadritos que estén inmediatamente abajo y a la derecha o a la izquierda de un cuadrito ya marcado. El “0” de la regla debe entenderse como una disyunción exclusiva: a la derecha o la izquierda, pero no ambos. La misma regla se aplica a los siguientes renglones sucesivamente. La primera dificultad a la que nos enfrentamos es que el primer cuadrito del segundo renglón no tiene un cuadrito arriba a la izquierda y el último cuadrito del mismo renglón no tiene un cuadrito arriba a la derecha. Una solución posible consiste en juntar los dos extremos de la hoja para que quede como un cilindro. Así el cuadrito arriba a la izquierda del primer cuadrito del segundo renglón es el último cuadrito del primer renglón, y el cuadrito arriba a la derecha del último cuadrito del segundo renglón es el primer cuadrito del primer renglón. Esta solución se conoce en la literatura respectiva como condiciones periódicas a la frontera. En la figura mostramos el dibujo que se obtiene al aplicar la regla en los primeros cuatro renglones.
Extendiendo un poco el lenguaje, podemos decir que la condición inicial ocurre en el instante de tiempo t = 0, el primer renglón en t = 1 y así sucesivamente. Si continuamos con el juego, no muy divertido al principio pero tal vez útil para presentar una introducción a los autómatas celulares, vemos la aparición de un cierto orden sobre la hoja cuadriculada. Por ejemplo, si continúan rellenando renglones, encontrarán un parecido entre el renglón en t = 3 y t = 7, pues tienen una sección en la que se alternan cuadritos negros con blancos. Con un poco de paciencia y perseverancia empezarán a ver una estructura de triángulos dentro de otros triángulos. Una alternativa para jugar el juego es pedirle a una computadora que lo haga por nosotros. En la figura 2 mostramos la evolución del juego después de 256 generaciones. Con una lupa, nos damos cuenta que el renglón en t = 31 y en t = 63 son parecidos a los renglones en t = 3 y t = 7. Esto quiere decir que la estructura crece exponencialmente pues todos estos números (sumando 1) resultan ser potencias de 2.
En este juego podemos hablar de una estructura espacio temporal, pues el espacio es unidimensional en la dirección horizontal y el tiempo corre en la dirección vertical. El dibujo de la figura 2 nos plantea varias preguntas:
1. ¿Qué podemos decir de la estructura espacio-temporal?
2. ¿Se puede cambiar la regla? 3. ¿Qué quiere decir “cambiar la regla”? 4. ¿Depende la estructura espacio-temporal de la condición inicial? En lo que sigue intentaremos contestar estas preguntas (aunque no necesariamente en orden) y otras que vayan presentándose en el camino. Empezamos con un poco de notación: a cada cuadrito del primer renglón le llamamos un sitio y los numeramos con un índice i que va de 1 al n. A cada sitio i le asociamos un estado que denotamos por σ(i) que puede ser 0 en caso de que el sitio no esté marcado y 1 en caso de que si lo esté. También podemos pensar en σ como una variable booleana que toma el valor falso cuando el cuadrito no está marcado y el valor verdadero cuando el cuadrito está marcado. Una tercera interpretación es pensar que en cada sitio hay un “individuo” que puede estar muerto (cuando el estado es 0) o vivo (cuando el estado es 1). Entonces la regla con la que hemos estado jugando se puede escribir como
σ(i, t + 1) = σ(i - 1, t) ! σ(i + 1, t), i = 1,…, n
donde el símbolo ! significa la disyunción exclusiva que mencionamos al principio. Esto puede entenderse mejor con la tabla de verdad que sigue:
La tabla de verdad se explica sola, en cada renglón aparecen distintos valores de los argumentos de la regla, seguidos del valor que asigna la regla al sitio para dichos valores.
Otra manera de escribir la regla es
σ(i, t + 1) = [σ(i - 1, t) + σ(i + 1, t)] mod 2
donde mod 2 indica el residuo de dividir el valor numérico que se encuentra dentro del paréntesis cuadrado entre dos. Por ello, a la regla con la que hemos estado jugando se le conoce como la regla “módulo 2”.
Con la nueva notación, las condiciones periódicas a la frontera nos indican que el sitio a la izquierda del sitio 1 es el sitio n y el sitio a la derecha del sitio n es el sitio 1.
Ahora regresamos a la primera pregunta. La estructura espacio-temporal de la figura 2 está hecha de triángulos de distintos tamaños, la cual veremos está relacionada con los famosos triángulos de Pascal y de Sierpinski. El primero es una construcción sencilla que nos permite conocer los coeficientes de la expansión de la expresión (a + b)n. Comenzamos con un 1 en el cuadrito del centro del primer renglón de una hoja cuadriculada, el segundo renglón se obtiene sumando los valores de los cuadritos que se encuentran arriba a la izquierda y a la derecha, y así se continúa para construir los renglones siguientes. El enésimo renglón del triángulo contiene los coeficientes de la expansión que buscamos. En la figura 3 mostramos los primeros ocho renglones del triángulo. Si ahora tomamos cada número del triángulo módulo 2, obtenemos los primeros renglones del dibujo de la figura 2.
El triángulo de Sierpinski es un poco menos conocido, pues es una construcción geométrica usada para ilustrar un fractal. Se comienza con un triángulo (figura 4 (a)) al cual se le quita un triángulo pequeño del centro de manera que queden tres triángulos iguales (figura 4 (b)). Se repite el procedimiento para obtener el objeto de la figura 4 (c). Las figuras 4 (d) a (f) muestran la aplicación sucesiva de este procedimiento. En el límite, cuando se aplica este procedimiento un número infinito de veces, se obtiene un objeto que tiene agujeros de todos tamaños y que es auto-similar. Esto significa que una parte del objeto magnificada por un factor adecuado es igual al todo. Además, el objeto no llena el espacio en el que se encuentra; decimos que el objeto es un fractal con dimensión fractal df dada por
df = ln(3)/ln(2) = 1.58
Hay una gran similitud entre la figura 2 y la figura 4 (f). Si jugamos el juego con la regla módulo 2 durante un tiempo infinito, obtendremos una estructura espacio-temporal que es un triángulo de Sierpinski. A partir de una regla sencilla podemos construir objetos sorprendentes.
Pasamos ahora a tratar de responder las preguntas 2 y 3 relacionadas con la posibilidad de cambiar la regla del juego. En el juego que hemos jugado hasta ahora, el estado en el sitio i al tiempo t + 1, σ(i, t + 1), depende del estado en el sitio i - 1, al tiempo t y el estado en el sitio i + 1 al tiempo t. Para hacer las cosas un poco más interesantes, podemos decir que la regla de evolución del juego depende de los estados en los sitios i - 1, i, i + 1 al tiempo t. Si F denota una regla cualquiera escribimos
σ(i, t + 1) = F(σ(i - r, t), σ(i, t), σ(i + 1, t)) (1)
y decimos que la regla depende de los estados en una vecindad que incluye al sitio mismo y a los sitios que se encuentran inmediatamente a la izquierda y a la derecha. Podríamos tomar vecindades mayores que incluyeran r sitios a la derecha y r sitios a la izquierda del sitio i y plantearnos las mismas preguntas.
Como vimos arriba, una regla puede especificarse de varias maneras; una de ellas es una tabla de verdad, sólo que ahora, dado que hay más variables, ésta será un poco más larga, como puede verse en la tabla 1. Puesto que la vecindad de la cual depende el estado del sitio a t + 1 contiene tres sitios, la tabla de verdad estará formada por 23 = 8 renglones, en los cuales aparecen todas las posibles combinaciones de los estados en los tres sitios. La tabla 1 no es más que otra manera de escribir la regla módulo 2.
La primera observación es que podemos construir tantas reglas diferentes como tablas de verdad diferentes haya. Para cada renglón σ(i, t + 1), se puede tomar el valor 0 o el valor 1, por lo que en la última columna de la tabla de verdad, el primer renglón puede llenarse de dos maneras diferentes, el segundo también y así hasta llegar al octavo renglón. El número total de maneras de llenar la última columna es entonces 2 x 2 x … x 2 = 28 = 223 = 256, que es el número de reglas posibles cuando el estado o en un sitio puede tomar sólo dos valores y la vecindad que define la regla de evolución contiene sólo tres sitios.
Wolfram numeró las 256 reglas de una manera sencilla. Cada regla tiene una tabla de verdad distinta y el número asociado a la regla es la expresión en base diez del número binario que forma la última columna de la tabla (de arriba a abajo). Así a la regla módulo 2 de la tabla 1 se le asocia el número (01011010)2 = 90.
Dado que la regla módulo 2 no depende del estado en el sitio central, las reglas número (00010010)2 = 18, (10010010)2 = 146 y (11010010)2 = 210, generan la misma estructura espacio-temporal que la regla 90 que mostramos en la figura 2. ¿De las 256 reglas, cuántas generan patrones interesantes? La regla 0 y la regla 255 son poco interesantes, pero la respuesta a la pregunta anterior requiere la simulación de cada una de las reglas. Un subconjunto interesante son las reglas llamadas legales por Wolfram, que son simétricas y F(0, 0, 0) = 0. Una regla F es simétrica si F(1, 0, 0) = F(0, 0, 1) y F(1, 1, 0) = F(0, 1, 1). Es claro que sólo hay 32 reglas simétricas pues las tablas de verdad que las definen tienen cinco renglones. En la figura 5 mostramos las 16 reglas legales que generan estructuras espacio-temporales interesantes a partir de la condición inicial en la que el estado del sitio central es 1 y en todos los otros sitios es 0. Vemos que la regla 150 posee una estructura fractal distinta de la de la regla 90.
En efecto, tiene una dimensión fractal df = 1.69…
Ahora pasamos a tratar de responder a la pregunta 4, ¿depende la estructura espacio-temporal de la configuración inicial? Empezamos definiendo la densidad ρ como el cociente de sitios vivos respecto al número total de sitios de la red. En la figura 6 mostramos la evolución de la regla 22 partiendo de una configuración inicial aleatoria con ρ0 = 0.5. Es difícil responder a la pregunta anterior viendo la figura, podemos imaginar que la estructura que se genera es un fractal y tratar de encontrar su dimensión fractal.
Podemos también ver cómo cambia la densidad con el tiempo y encontramos que para tiempos largos ésta alcanza el valor de ρ∞ = 0.35, para cualquier valor de ρ0 entre 0.1 y 0.9. Las reglas 90 y 126 tienen un comportamiento similar pero para tiempos largos ρ∞ = 0.5 mientras que para la regla 18 ρ∞ = 0.25 y para la regla 182 ρ∞ = 0.75. Estas densidades finales no dependen de la densidad inicial si ésta no es demasiado pequeña o demasiado grande. ¿Cuáles reglas alcanzan una densidad constante para tiempos largos? ¿Depende esa densidad asintótica del tamaño de la red y de la densidad inicial? ¿Qué otras cantidades se pueden medir que caractericen la evolución temporal del autómata? ¿Qué explicación podemos dar para los valores observados de ρ∞? Las respuestas (a veces sólo parciales) requieren de experimentos en la computadora. Para algunas reglas existe una explicación de por qué llegan a una densidad constante a tiempos largos, para otras se puede establecer una teoría sencilla similar a la teoría de campo medio usada en mecánica estadística para estimar la densidad asintótica.
Podríamos considerar autómatas celulares unidimensionales donde la vecindad que define la evolución es un poco mayor, digamos que contiene al sitio mismo y a r sitios a la derecha y r sitios a la izquierda. En tal caso el numero total de reglas que se pueden construir es 22(2r + 1). Si r = 2, tenemos más de 4,290,000.000 reglas. Otra posibilidad es la de aumentar el número de estados por sitio, digamos que el estado en cada sitio puede tomar los valores 0, 1, 2,…, k. Entonces el número de reglas posibles es kk(2r + 1). No sólo aumenta el número de reglas, la complejidad de las estructuras espacio-temporales cambia cualitativamente.
Una regla particular genera estructuras asintóticas (tiempos largos) similares para distintas condiciones iniciales al azar y distintas reglas generan distintas estructuras asintóticas. Sin embargo, los autómatas celulares unidimensionales elementales (con k = 2 y r = 1) presentan uno de los comportamientos genéricos siguientes:
1) evolucionan a un estado homogéneo;
2) evolucionan a una estructura estable o periódica;
3) evolucionan a una estructura caótica aperiódica.
Los autómatas con k > 1 ó r > 1 (y también los autómatas bidimensionales mencionados más adelante) pueden presentar alguno de los comportamientos anteriores o pueden: 4) evolucionar a estructuras localizadas complejas que pueden propagarse.
La clasificación anterior se debe también a Wolfram. Los autómatas de la clase 1 evolucionan a una configuración final análoga a un punto limite para un sistema dinámico continuo. Los autómatas de la clase 2 evolucionan a un conjunto límite que contiene unas cuantas configuraciones, mientras que los autómatas de clase 3 evolucionan a conjuntos límites aperiódicos, análogos a los atractores extraños de sistemas dinámicos continuos. Respecto a la clase 4 se conoce poco y no está claro que esté bien definida, pues existen problemas para decidir si un autómata pertenece a esta clase o no, y para decidir qué tienen en común los autómatas que pertenecen a esta clase. Con estas reservas, presentamos en la figura 7 dos autómatas celulares con k = 2 y r = 2 que pertenecen a esta clase.
¿Por qué limitarse a un espacio unidimensional? En dos dimensiones se puede jugar en cualquier espacio discreto, digamos una red cuadrada. Las vecindades más usadas son la de von Neumann y la de Moore que mostramos en la figura 8. Dado que la vecindad de Moore contiene nueve sitios, el número de reglas posibles es 229 ≡ 1.34 x 10154, si k = 1.
Los autómatas bidimensionales también caen en las cuatro clases mencionadas anteriormente, y el Juego de la Vida, que discutiremos a continuación, pertenece a la clase 4. Un subconjunto de reglas que se cree posee toda la riqueza del conjunto de reglas definidas en una vecindad de Moore es el conjunto de las reglas totalísticas externas. Una regla totalística externa depende del estado del sitio central y de la suma de los ocho estados de la vecindad. Hay sólo 210 = 1024 reglas totalísticas externas y el Juego de la Vida es la más famosa de ellas. Este autómata, creado por J. Conway y popularizado por M. Gardner se juega con las reglas:
a) un sitio que está vivo al tiempo t estará vivo al tiempo t + 1, si tiene 2 o 3 vecinos vivos, en caso contrario morirá;
b) un sitio que está muerto al tiempo t estará vivo al tiempo t + 1 si tiene exactamente 3 vecinos vivos.
La condición a) indica que un individuo continúa vivo si tiene con quién platicar, pero si hay mucha gente a su alrededor muere de asfixia y si hay poca de aburrimiento. La condición b) indica, contrariamente a lo natural, que son necesarios 3 individuos para la procreación. Podemos plantearnos muchas de las preguntas anteriores para este juego.
La simplicidad de la regla oculta un comportamiento complejo que justifica su nombre. Aquí nos interesan algunas de las propiedades estadísticas del juego. Partiendo de una configuración al azar, la evolución temporal simula la auto- organización presente en los organismos vivos. Lo que queda a tiempos largos son islas de vida estáticas o periódicas con una simetría bien definida que mostramos en la figura 9.
Para una configuración inicial aleatoria con densidad inicial entre 0.1 y 0.7 se alcanza siempre una densidad final ρ∞ = 0.029. La evolución temporal puede dividirse en tres partes. La primera está dominada por la ausencia de correlaciones y sigue las predicciones que se pueden hacer con una teoría de campo medio. La segunda parte muestra un decaimiento de la densidad que va como una potencia del tiempo, resultado de las fuertes correlaciones que se van generando. Sin embargo, este comportamiento se pierde a tc ≈ 2000 - 3000, para dar lugar a un nuevo tipo de comportamiento de evolución más lenta y que conjeturamos continúa por siempre en una red de tamaño infinito, pero que en redes de tamaño finito termina en una configuración de la red, en la cual la densidad toma el valor mencionado anteriormente. Vemos que una regla relativamente sencilla da lugar a un comportamiento espacio-temporal extremadamente complejo.
Del análisis del comportamiento de los autómatas celulares esperamos, por una parte, poder desarrollar modelos para sistemas particulares, y por otra, buscar principios generales aplicables a una gran variedad de sistemas complejos. Dada la gran cantidad de autómatas celulares, no es de extrañar que alguno modele el sistema en el cual estemos interesados, que puede ser un fluido, un ácido nucleico o cualquiera de los otros sistemas mencionados en la introducción. Lo que si es de extrañar es que alguien haya encontrado el autómata adecuado para el sistema bajo estudio. Por ejemplo, si se modifica un poco la regla del Juego de la Vida, se pierde toda la riqueza del comportamiento espacio-temporal original.
El estudio de los autómatas celulares requiere del uso intensivo de computadoras. Se selecciona una regla y una configuración inicial y se sigue la evolución temporal en lo que llamamos un experimento computacional. La clasificación de Wolfram en cuatro clases no es aún definitiva y requiere de mayor estudio. La bibliografía que aparece enseguida contiene los resultados que hemos discutido y puede servir para iniciar el estudio de los autómatas celulares.
|
|
 |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Referencias Bibliográficas
Bagnoli, F., R. Rechtman, S. Ruffo, 1991, Some facts of life, Physica A.
Gardner, M., 1983 Wheels, life and other mathematical amusements, Freeman, San Francisco. Grassberger, P., 1986, Long range effects in an elementary cellular automaton, J. Stat. Phys. 45:27. Kaufmann, S.A., 1969, J. Theor. Biol. 22:437. Packard, N., S. Wolfram, 1985, Two dimensional cellular automata, J. Stat. Phys. 38:901. Stauffer, D. 1991, J. Phys. A 24:909. Wolfram, S. 1983, Statistical mechanics of cellular automata, Rev. Mod. Phys. 55:601. Wolfram, S., 1984, Universality and complexity in cellular automata, Physica 10D:1. Wolfram, S., 1984, Cellular automata as models of complexity, Nature 311:419. Wolfram, S. (comp.), 1986, Theory and Applications of Cellular Automata, World Scientific Publications, Singapore. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
____________________________________________________________
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Raúl Rechtman
Departamento de Física, Facultad de Ciencias,
Universidad Nacional Autónoma de México.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ____________________________________________________________ | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
cómo citar este artículo →
Rechtman, Raúl. 1991. Una introducción a autómatas celulares. Ciencias núm. 24, octubre-diciembre, pp. 23-29. [En línea]
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
