ENCONTRANDO SOLITONES EN EL AUTOMATA CELULAR REGLA 110

El fenómeno solitón es una área de la física bien fundamentada, es este reporte se muestra como un autómata celular en una dimensión puede simular este fenómeno. Una característica importante es que es un sistema dinámico discreto fácil de implementar computacionalmente.

El estudio formal de la ´´onda solitaria'' es toda un área en el campo de la física que no esta ligada directamente al estudio de los autómatas celulares. La primera descripción de este fenómeno se le atribuye al ingeniero escocés John Scott Russell por el año de 1834 [Eil98]. En 1895 dos físicos holandeses Diederick J. Korteweg y Gustav de Vries se dieron a la tarea de describir de manera formal este fenómeno, sin embargo hasta el año de 1965 que el físico Martin Kruskal llama al choque de estas ondas ´´solitón''.

La regla 110 es un autómata celular unidimensional con dos elementos en su alfabeto y una función de transición, en esta regla de evolución se pueden observar estructuras periódicas desplazandose en el espacio de evoluciones, algunas de ellas de construcción simple y otras complejas, todas ellas interactuando en un fondo periódico.

El fenómeno solitón fue observado al efectuar choques binarios entre estructuras periódicas de manera sistemática, obteniendo resultados interesantes como producciones simétricas, grupos de gliders (un glider es una estructura periódica que se desplaza a través del tiempo), gliders individuales, choques complejos y solitones. En este reporte se presentan de maenra general como se produce este fenómeno en la regla 110.

Un autómata celular es un sistema dinámico discreto que evoluciona a través del tiempo, esta constituido por un conjuto de estados y una función de transición, donde el conjunto de estados pertenece al conjunto de los enteros positivos. Los autómatas celulares en una dimensión pueden ser representados con dos parametros (k,r) [Wolf86], donde k es la cardinalidad del conjunto K y r el número de vecinos en cada lado que se encuentran con respecto a una célula central.

Se tiene un arreglo lineal donde cada elemento se le conoce como célula, cada una de ellas toma un elemento del conjunto de estados K, este arreglo es la configuración inicial, el arreglo lineal es acotado por sus condiciones a la frontera, es decir, la célula inicial se concatena con la célula final para formar un anillo y la configuración inicial se verá transformada por la función de transición a través del tiempo.

Una vecindad esta formada por una célula central y r vecinos a cada lado, entonces una vecindad tiene 2r+1 células y una regla de evolución esta formada por k^(2r+1) vecindades, de esta manera la función de transición evalua cada una de las vecindades en la configuración inicial.

La actualización de cada configuración en un paso se hace de manera simultánea o en paralelo, cada actualización induce una transición de manera global, es decir, entre configuraciones.

Regla 110 es un autómata celular unidimensional de orden (2,1), dos elementos en el conjunto de estados y el radio de vecindad de una célula. El número 110 se refiere a la notación decimal de la regla de evolución que se encuentra en binario, las vecindades 001, 010, 011, 101 y 011 se transforman al estado 1 en la siguiente generación y las vecindades 000, 100 y 111 se transforman en 0.

Sthepen Wolfram menciona que la regla 110 puede ser universal y en general aquellos autómatas con comportamientos complejos [Wolf84], por su parte Wentian Li y Mats G. Nordahl en [LN92] realizaron un estudio estadístico de la regla 110 ilustrando algunos de los comportamientos de dicha regla, sin embargo hasta finales de los 90's Matthew Cook presenta resultados interesantes de la regla 110 que dan motivo a este trabajo.

Cook en [Cook99] presenta una clasificación de todos los gliders hasta ahora encontrados en la regla 110, por su parte Harold V. McIntosh en [Mc99] y [Mc00] realiza un estudio sobre dicho autómata, mostrando como el espacio de evoluciones puede ser cubierto con polígonos.

Retomando el estudio realizado por McIntosh en [JM01] se realizó un análisis sistemático para calcular todos los choques binarios que se derivan de los gliders existentes. En este análisis se encontraron que algunos choques tienen comportamiento solitón.

Kenneth Steiglitz ha realizado varios trabajos de solitones en autómatas celulares de una dimensión, una variante conocido como ´´automata filtrado'' utilizando reglas de paridad como puede verse en [PST86].

Un solitón es una onda solitaria con comportamiento no lineal que al interactuar con otras ondas o algún otra interrupción conserva su forma y su velocidad, sufriendo pequeños desplazamientos en cada choque.

Recordemos que los modelos hasta ahora conocidos en autómatas celulares, no presentan alguna relación directa con soluciones de ecuaciones diferenciales parciales no integrables. Algunos trabajos relacionados que han tratado de encontrar tal relación pueden consultarse en algunos artículos de Steiglitz [PST86] y [JSS01].

En el espacio de evoluciones de la regla 110 se pueden ver estructuras periódicas que son creadas de manera natural a través del tiempo, sin embargo existen gliders difíciles de obtener a partir de configuraciones aleatorias, algunos de ellos pueden ser obtenidos a través de choques muy precisos, por ejemplo el glider H, el glider gun o el Bbar8 [Jua02].

En [Mc99] y [JM01] se muestran con detalle la estructura de cada uno de los gliders, McIntosh denota a estos polígonos como Tn, donde n indica el tamaño del triángulo y es mayor igual que uno. El espacio de evoluciones de la regla 110 que está constituido por dos tipos de triángulos rectángulos alfa y beta.

Estos triángulos equilateros pueden cubrir el espacio de evoluciones sin violar la regla de evolución, en este caso el triángulo T3 beta es el fondo periódico que domina en el espacio de evoluciones llamado por Cook ´´ether''. Aunque el espacio de evoluciones puede ser cubierto por cualquier Tn hasta un T4 de manera individual, en el caso donde n>4 solo es posible con combinaciones de ellos y mejor aún, cada uno de los gliders por sí mismos pueden cubrir el espacio de evoluciones como se puede ver en [JMS02].

Es importante notar que este T3 beta determinará las fases de cada uno de los gliders, así como su período y desplazamiento, aún de manera informal estas propiedades son presentadas en [Jua0].

Para determinar una configuración en particular se deben seguir cada una de las fases que representa el T3 beta y obtener una evolución donde cada una de las estructuras puedan ser representadas en una sola fase en dos tipos de alineación.

Se tienen cuatro fases periódicas del ether 11111000100110 - e(f1) (´e(f1)' indica fase uno del ether), 10001001101111 - e(f2), 10011011111000 - e(f3) y 10111110001001 - e(f4). Si la configuración inicial es cubierta con la expresión *e*, tendremos el espacio de evoluciones cubierto de puro ether. Se puede ver que cualquiera de estas cuatro fases es una permutación de la misma cadena. El período del ether es de 14 células a la derecha en 7 generaciones.

El ether puede representar dos tipos de pendientes como se ilustra en la Figura 1, que determinan la velocidad máxima negativa y positiva que puede tener una estructura periódica en el espacio de evoluciones. El desplazamiento de estas pendientes siempre es de 2 células, para obtener los choques entre gliders hay que identificar los puntos de contacto donde los gliders pueden interactuar con otras estructuras.

Estos puntos de contacto van a estar determinados por el número de margenes pares mp e impares mi que tenga un glider en particular.

Entonces los puntos de contacto para un glider g estan determinados por el número de margenes pares de su lado izquierdo y por el número de margenes impares de su lado derecho. Ambos margenes tienen una correspondencia biyectiva y la existencia de un punto de contacto en una parte implica la existencia de un punto que no es de contacto en su contraparte [Jua01].

Los margenes pares tienen una altura de 4 células, mientras que los margenes impares tienen una altura de 3 células. Con estas características se pueden determinar propiedades como período, desplazamiento, velocidad y número de choques entre dos gliders.

Una manera de obtener estas secuencias es utilizando el diagrama de de Bruijn extendido [Mc91], donde el diagrama de de Bruijn calcula todas las secuencias periódicas representadas por los ciclos del diagrama. Una limitante es que para estructuras más elaboradas estos diagramas crecen exponencialmente.

Un estudio interesante en este camino puede ser estudiando los árboles topológicos que describe Andrew Wuensch en [WL92], identificando estructuras periódicas y sus ancestros en ciclos atractores, algo interesante es sobre la busqueda o representación de gliders en reglas de evolución con comportamiento complejo como puede verse en [Wue99].

Utilizando las fases del ether se pueden obtener todas las secuencias para una fase en particular de cualquier estructura periódica, en este análisis solo se toma en consideración un glider y no grupos de ellos o cualquier otra combinación, este problema es tratado en [JMS02].

Los puntos de contacto para los gliders son determinados por los margenes mi y mp, pero a su vez estos margenes estan determinados por las fases del ether. Una vez identificados los puntos de contacto se realizó un estudio sistemático para calcular todos los choques binarios, esta colección se puede consultar en [JM01].

Un trabajo importante que trata de formalizar el número de choques entre gliders de manera general y no particular como en nuestro caso, puede ser consultado en el trabajo de Cosma Rohilla Shalizi [HSC01], donde los resultados obtenidos a través del estudio de mecánica computacional pueden ser aplicados en la regla 110.

Para dos gliders dados no todos los choques producen el fenómeno solitón, esto es originado por la fase en que chocan los gliders. Se tiene que controlar la fase en que los gliders llegan, la manera como controlamos estas fases es desde la configuración inicial.

Es recomendable dar un espacio entre los gliders para poder observar bien el choque, en algunas ocaciones no es necesario introducirlo ya que las cadenas estan alineadas a la fase del ether y esto produce siempre un choque propio.

Para identificar algún glider en particular de la regla 110 utilizaremos la clasificación propuesta por Cook en [Cook99].

Finalmente esta es la manera para obtener los choques que son solitones, se necesita saber en que fase se produce este fenómeno para los dos gliders en cuestión. Por ejemplo evaluemos la expresión F(A2)-e-B que se sabe debe producir un solitón.

En la Figura 2 se puede ver un choque solitón entre el glider F y el glider B, donde los gliders conservan su forma y velocidad despues del choque, finalmente solo sufren un pequeño desplazamiento en sus fases, cumpliendo con las propiedades de un solitón.

En el universo de la regla 110 se pueden obtener solitones que viajen en la misma dirección, en direcciones opuestas o con un glider estático. Los desplazamientos en los gliders siempre se dan en retroceso al original, tal como ocurre en los solitones.

El fenómeno solitón que se representan con los gliders de la regla 110, ofrecen la posibilidad de discutir como corre la información, esta idea esta en proceso de investigación. Por otra parte se puede ver que una manera sencilla de obtenerlos es a través del control que se tiene en la configuración incial, definiendo la fase en que estos gliders deben iniciar.

Una de las ideas a desarrollar es la simulación de algunas operaciones lógicas a través de estas producciones. Tomando algunos artículos de Steiglitz como en [JSS01], donde simula algunas operaciones lógicas a través de solitones utilizando el modelo de Manakov.

Por el momento las simulaciones son sencillas, sin embargo se pueden realizar rapidamente gracias al control de fases desde la configuración inicial y por supuesto apoyandonos en las investigaciones de Steiglitz.

Estas simulaciones pueden ser reproducidas con el sistema OSXLCAU21 [Osx01], es claro que operaciones más complejas deben ser construidas cuidadosamente, algo similar a lo que se obtiene con el Juego de la Vida [BCG82]. De esta manera se pretende obtener una mejor descripción primero de el fenómeno solitón y posteriormente de la simulación de operaciones lógicas.

Un operador que funciona a través de incrementos y decrementos es posible con el glider En, donde el glider A decrementa en uno al glider E y el glider B lo incrementa, este modelo puede verse con detalle en [MSCJ01].

En la Figura 3 se ilustra un choque múltiple entre los gliders Ebar, F, C2 y C1. El comportamiento es interesante ya que estos gliders son alineados desde la configuració inicial y aunque no todos sus choques producen solitones, se puede ver como una alineación adecuada permite obtener una interacción solitón en choques múltiples.

[BCG82] Elwyn Berlekamp, John Conway and Richard Gut, Winning Ways for your Mathematical Plays, vol. 2, chapter 25, 817-849, Academic Press, 1982.

[Eil98] Chris Eilbeck, ´´John Scott Rusell and the solitary wave'', http://www.ma.hw.ac.uk/~ chris/scott _russell.html, November 1998.

[HSC01] Wim Hordijk, Cosma Rohilla Shalizi and James P. Crutchfield, ´´Upper Bound on the Products of Paticle Interactions in Cellular Automata'', Physica D 154, 240-258, 2001.

[JSS01] Mariusz H. Jakubowski, Ken Steiglitz and Richard Squier, ´´Computing with Solitons: A Review and Prospectus'', Multiple-Valued Logic, Special Issue on Collision-Based Computing, vol. 6, Numbers 5-6, 2001 (ISSN 1023-6627).

[JM01] Genaro Juárez Martínez and Harold V. McIntosh, ´´ATLAS: Collisions of gliders like phases of ether in rule 110'', http://delta.cs.cinvestav.mx/~mcintosh, August 2001.

[Jua01] Genaro Juárez Martínez, ´´Margenes periódicos en la regla 110 con correspondencia biyectiva en estructuras periódicas que definen puntos de contacto y velocidad máxima'', http://delta.cs.cinvestav.mx/~mcintosh, Octubre 23, 2001.

[JMS02] Genaro Juárez Martínez, Harold V. McIntosh y Juan Carlos Seck Tuoh Mora, ´´Estructuras periódicas cubriendo el espacio de evoluciones en el autómata celular unidimensional regla 110'', http://delta.cs.cinvestav.mx/~mcintosh, Abril 8, 2002.

[Jua02] Genaro Juárez Martínez, ´´Produciendo gliders a través de choques en la regla 110'', en preparación.

[LN92] Wentian Li and Mats G. Nordahl, ´´Transient behavior of cellular automaton rule 110'', Physics Letters A 166, 335-339, (1992).

[Mc91] Harold V. McIntosh, ´´Linear cellular automata via de Bruijn diagrams'', http://delta.cs.cinvestav.mx/~mcintosh, 1991.

[Mc99] Harold V. McIntosh, ´´Rule 110 as it relates to the presence of gliders'', http://delta.cs.cinvestav.mx/~mcintosh, January 1999.

[Mc00] Harold V. McIntosh, ´´A Concordance for Rule 110'', http://delta.cs.cinvestav.mx/~mcintosh, April 2000.

[MSCJ01] Harold V. McIntosh, Juan Carlos Seck Tuoh Mora, Sergio V. Chapa Vergara y Genaro Juárez Martínez, ´´Gliders en autómatas celulares de una dimensión'', http://delta.cs.cinvestav.mx/~mcintosh, Diciembre 4, 2001.

[PST86] James K. Park, Kenneth Steiglitz and William P. Thurston, ´´Soliton-like behavior in automata'', Physica D 19, 423-432, 1986

[WL92] Andrew Wuensch and Mike Lesser, ´´The Global Dynamics of Cellular Automata'', Santa Fe Institute Studies in the Sciences of Complexity. Addison-Wesley, Massachussetts, 1992 (ISBN 0-201-55740-1).

[Wolf84] Stephen Wolfram, ´´Universality and complexity in cellular automata'', Physica D 10, 1-35, 1984.

[Wolf86] Stephen Wolfram, Theory and Aplications of Cellular Automata, World Scientific Press, Singapore 1986.

[Wue99] Andrew Wuensch, ´´Classifying Cellular Automata Automatically'', Complexity, vol. 4, no. 3, 47-66, 1999.

[Osx01] Programa ´´OSXLCAU21'' desarrollado por Genaro Juárez Martínez disponible en los sistemas OpenStep y Mac OS X, viable de manera gratuita en http://delta.cs.cinvestav.mx/~mcintoshcomun/s2001/s2001.html, Agosto 2001.