Estudio de la regla Spiral Verano de Investigaci´on 2009 Benem´erita Universidad Aut´onoma de Puebla Departamento de microcomputadoras Rogelio Basurto Flores & Paulina Anaid Le´on Hern´andez

1

Introducci´ on

Andrew Adamatzky y Andrew Wensche basados en las reacciones BelouzovZavotinsky dise˜ naron en el 2005 un aut´omata celullar llamado Beehive. Dicho aut´ omata presentaba part´ıculas movibles, tanto gliders como glider-guns, mismas con las que se prob´ o que era posible la implementaci´on de computaci´on mediante la construcci´ on de compuertas l´ogicas; no obstante este avance, era necesario encontrar part´ıculas estacionarias que facilitaran la computaci´on, fue ´este el motivante para seguir buscando dentro de la misma familia de reglas una que presentara glider-guns est´ aticos. De esta manera en el 2006 encontraron la regla Spiral [1]; esta regla presentaba gliders, glider-guns movibles y glider-guns est´ aticos. La din´ amica de la regla ha probado ser adecuada para implementar una l´ogica universal, y es por esta misma raz´ on que es importante hacer un estudio m´as profundo sobre sus part´ıculas y la interacci´ on entre ellas, con el fin de encontrar reacciones que permitan implementar computaci´ on. En el presente trabajo se mostrar´an las part´ıculas b´ asicas encontradas por los autores de la regla, as´ı como otras part´ıculas y configuraciones m´as complejas y algunas otras interesantes. Tambi´en, se plantearan las bases del estudio de la regla por medio del enfoque de vida artificial, mismo que ayudar´ a a la comprensi´ on del comportamiento general de la regla.

1

2

Sistemas complejos

Actualmente con los avances tecnologicos es posible estudiar su comportamiento de sistemas complejos a trav´es de simulaciones computacionales, uno de los modelos m´as utilizados para llevar a cabo dichas simulaciones son los aut´omatas celulares. Un sistema complejo est´ a compuesto, en general, por un conjunto de elementos los cuales interactuan entre s´ı a trav´es de funciones que representan las caracter´ısticas m´as sobresalientes del sistema; sin embargo, no se puede estudiar cada parte del sistema por separado para poder comprender su comportamiento global, debido a que la interacci´ on entre los miembros del sistema propicia el surgimiento de propiedades nuevas que no se pueden explicar a partir de los elementos aislados; estas propiedades son la emergencia y auto-organizaci´ on. Un aut´ omata celular se define como el modelo de un sistema complejo que itera a trav´es del tiempo, con una regla isotropica (que se aplica a cada elemento del sistema) de transici´on para el cambio de estados de las part´ıculas individuales que lo componen, llamadas c´elulas, siendo el conjunto de estados que pueden tomar las c´elulas finito. El uso de los automatas celulares para la simulacion de sistemas complejos se ha venido llevando a cabo cada vez con mas frecuencia debido a que este modelo presenta inherentemente algunas de las caracteristicas principales de los sistemas complejos. Por otro lado, es un modelo abstracto el cual puede adaptarse a muchos problemas y circunstancias de estudio diferentes. Algunas de las caracteristicas que poseen los sistemas complejos y estan presentes de manera inherente en los automatas ceulares son: La emergencia se refiere al proceso por el cual un sistema de elementos interactuando entre si adquiere cualitativamente nuevos patrones y estructuraas que no pueden ser entendidos simplemente como la superposici´on de contribuciones individuales; es decir, la emergencia se da cuando la interacci´ on de los elementos del sistema dar´ a lugar a la creaci´on de nuevos elementos o har´ a que el sistema tenga un comportamiento complejo. La auto-organizaci´ on por su parte, es un proceso en el que los patrones del nivel global de uns sistema emerge solamente de la interacci´ on entre los componentes de m´as bajo nivel del sistema; es decir, la auto-organizaci´ on es cuando cada elemento del sistema al ”efectuar” su funci´ on de transici´on de manera local, contribuye a la formaci´ on de patrones en el sistema global; y esto se dar´ a sin intervenci´on de influencias externas al sistema por lo tanto el patr´on es una propiedad emergente del sistema mismo. Le llamaremos patron al sentido de referirse a un argumento particular de objetos en el espacio, adem´as de la estructura y organizaci´ on en el tiempo.

2

Por otro lado la vida artificial intenta desarrollar un nuevo tipo de paradigma computacional basado en procesos naturales como una herramienta para explorar la din´ amica de las interacciones entre los elementos de un sistema vivo. La vida artificial comienza viendo un organismo como una poblaci´on grande de m´aquinas simples y trabaja analiticamente hacia el interior construyendo reglas que gobiernan los elementos internos para que interactuen entre ellos; el mejor ejemplo de esto son los aut´omatas celulares.

3

La regla Spiral

Un aut´ omata celular esta compuesto por la tupla: • Q, es un conjunto finito de estados. • d, un n´ umero entero positivo que representa la dimensi´ on del aut´omata. • e, es la configuraci´on inicial de las c´elulas. • f : S e → S, la funci´ on de transici´on.

Figura 1: Vecindad hexagonal En el particular caso de la regla Spiral se tiene un conjunto Q = {0, 1, 2} representados mediante los colores blanco, rojo y negro respectivamente; la dimensi´on d = 2 y adem´as, es importante mencionar que la forma de las c´elulas es hexagonal y debido a ello la vecindad utilizada ser´a como la presentada en la figura 1, con 6 vecinos inmediatos; e representa la configuraci´on inicial, es decir, los estados de las c´elulas para el tiempo t = 0; y finalmente, la funci´ on de transici´on estar´ a dada mediante una matriz de transici´on, donde las columnas representan el n´ umero de c´elulas en estado 1 y las filas el n´ umero de c´elulas en estado 2, dicha matriz de transici´on es presentada en la tabla 1.

3

i

0 1 2 3 4 5 6 7

0 0 0 0 0 0 0 0 0

1 1 2 0 2 0 0 0

2 2 2 2 2 2 2

3 1 1 1 1 1

4 2 2 2 2

5 2 2 2

6 2 2

7 2

Tabla 1: Matriz de evoluci´ on de la regla Spiral

4

Part´ıculas en la regla Spiral

La regla Spiral es rica en part´ıculas tanto simples como complejas. En la regla pueden encontrarse gliders, glider-guns tanto est´ aticos como din´amicos, as´ı como eaters (still life). Andrew Adamatzky y Andrew Wensche en [1] muestran un compendio de part´ıculas que presenta la regla Spiral, tanto b´ asicas como algunas complejas, estos resultados son mostrados en la figura 3 y tambien pueden ser consultados en [4]. A continuci´ on se detallar´a cada tipo de part´ıcula dando las generalidades de cada una de ellas y algunas de sus particularidades.

4.1

Gliders

Un glider es una part´ıcula que tiene la capacidad de moverse dentro del espacio de evoluciones en seis direcciones mostraas en la fig 2, la regla Spiral tiene 5 gliders b´ asicos que pueden observarse en la figura 3 como g1 a g5 .

Figura 2: Direcci´on de los gliders en la regla Spiral.

4

Figura 3: Part´ıculas en la regla Spiral. Estos gliders tienen la principal caracter´ıstica de emerger facilmente a partir de evoluciones iniciales aleatorias, as´ı como ser los tipos de gliders m´as abundantes dentro de la regla Spiral, aunque no son los u ´ nicos tipos de gliders existentes es importante hacer notar el hecho de que todos los gliders de la regla Spiral encontrados hasta ahora comparten algunas caracter´ısticas como el per´ıodo, desplazamiento o velocidad mismas caracter´ısticas que pueden ser consultadas 5

en la tabla 3; los conceptos son explicados a continuaci´on: • Peso: se refiere a la cantidad de c´elulas que forman una part´ıcula; de tener m´as de una fase (o forma) se toma la mayor como su peso. • Per´ıodo: es el n´ umero de evoluciones necesarias para que una part´ıcula vuelva a tener su estructura inicial. • Desplazamiento: se refiere al n´ umero de c´elulas que avanza el glider por per´ıodo, se define su direcci´ on en base al plano cartesiano, en la figura 2 se presentan las direcciones posibles en la regla Spiral. • Velocidad: esta determinada como P/D, es decir, Per´ıodo/Desplazamiento. De los gliders b´ asicos surgen otros a partir de mutaciones, estos son mostrados en la figura 3 los gliders g6 a g9 y g12 , y en la imagen4 del g15 al g19 ; estos gliders son combinaciones entre gliders b´ asicos conservando en algunos casos el desplazamiento y peri´odo, gliders g6 a g8 y en otros casos creando un glider totalmente diferente como los gliders g9 , g1 2 en 3 y del g15 al g19 . Adem´as de estos gliders existe una gama de gliders de mayor peso y por ende m´as dificiles de generarse mediante configuraciones aleatorias, no obstante surgen ocasionalmente dentro de la propia din´amica de la regla. Este tipo de gliders son los mostrados en la imagen 4 y van del g20 y g50 y los gliders g9 al g14 en la imagen 3. Este tipo de gliders son facilmente mutables a trav´es de colisiones con otros gliders, a esto se debe la gran variedad existente y las similitudes entre muchos de ellos as´ı como la igualdad de peso y peri´odo en la mayoria de sus mutaciones.

4.2

Eaters

Los eaters son un tipo de part´ıcula est´ atica que tiene la propiedad de permanecer en el espacio de evoluciones indefinidamente (still life) y que adem´as posee la capacidad de eliminar las part´ıculas que colisionen con ella. En [1] se presentan dos tipos de gliders, estos son mostrados en la figura 3, E1 y E2 , as´ı mismo son mostradas algunas de las uniones que soportan estas part´ıculas entre ellas mismas. Dentro del estudio de la regla se encontro que a partir del eater E1 era posible la expansi´ on de tama˜ no del “nucleo”, de esta manera generar una part´ıcula de mayor tama˜ no pero conservando sus mismas propiedades. Esta “familia” de eaters es mostrada en la figura 5. La uni´ on de eaters produce eaters del doble de tam˜an ˜ o, y en algunos casos su peso minimo disminuye. Un caso interesante de las uniones entre eaters es la generaci´ on de osciladores, part´ıculas que cambian su forma en cada evoluci´ on en cliclos infinitos. En la imagen 3 se puede apreciar un oscilador y el resto de ellos en l la figura 6, estos son algunos osciladores que aparecen comunmente en la regla a partir de configuraciones aleatorias, y en la figura 7 se muestran oscladores construidos.

6

Part´ıcula g1 g2 g3 g4 g5 g6 g7 g8 g9 g10 g11 g12 g13 g14 g15 g16 g17 g18 g19 g20 g21 g22 g23 g24 g25 g26 g27 g28 g29 g30 g31 g32 g33 g34 g35 g36 g37 g38 g39 g40 g41 g42 g43 g44 g45 g46 g47 g48 g49 g50

Peso 5 5 6 5 5 10 8 9 10 14 16 11 17 32 11 11 12 11 11 14 14 11 12 10 12 16 16 15 17 25 32 26 23 18 19 17 22 19 18 25 24 20 29 33 43 47 36 29 31 31

Velocidad 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Per´ıodo 2 1 1 2 2 1 1 1 4 2 2 4 2 4 4 4 4 4 4 2 2 1 1 1 2 2 2 2 4 8 4 8 4 4 4 4 4 8 4 4 4 8 4 8 4 4 4 8 4 4

Desplazamiento 2 1 1 2 2 1 1 1 4 2 2 4 2 4 4 4 4 4 4 2 2 1 1 1 2 2 2 2 4 8 4 8 4 4 4 4 4 8 4 4 4 8 4 4 4 4 4 8 4 8

Tabla 2: Caracter´ısticas de gliders.

References [1] Andrew Adamatzky and Andrew Wuensche (2005), “On spiral glider-guns in hexagonal cellular automata: activator-inhibitor paradigm”. [2] Andrew Adamatzky, Andrew Wuensche and B. De Lacy Costello (2005), “Glider-based computing in reaction diffusion hexagonal cellular automa-

7

Figura 4: Gliders en la regla Spiral

Figura 5: Familia de eaters E2 ta”, Journal Chaos, Solitons & Fractals. [3] Andrew Adamatzky and Andrew Wuensche (2006), “Computing in Spiral Rule Reaction-Diffusion Hexagonal Cellular Automaton,” Complex Sys8

Figura 6: Osciladores b´ asicos Oscilador O1 O2 O3 O4 O5 O6 O7 O8 O9 O10 O11 O12

Peso 23 20 20 20 24 24 63 61 130 36 63 66

Per´ıodo 8 6 6 6 4 4 6 3 2 3 2 2

Tabla 3: Caracter´ısticas de gliders. tems 16 (4). [4] Andrew Wuensche, Discrete Dynamics Lab (DDLab), www.ddlab.org, 2009, also follow the links “Spiral rule” and “self-reproduction”. [5] Andrew Ilachinski (2001), Cellular Automata: A Discrete Universe, World Scientific Press.

9

Figura 7: Osciladores construidos

10