next up previous
Next: Preliminares Up: Autómatas celulares en tres Previous: Autómatas celulares en tres

Introducción

El autómata celular The Game of Life (también conocido como ``Life'') muestra comportamientos muy complejos en su espacio de evoluciones, este tipo de comportamientos han encontrado su culminación demostrando que Life puede realizar computación universal en [BCG82], entre otro tipo de descubrimientos importantes que se han realizado durante su estudio. Sin embargo en la actualidad no se tienen estudios formales que expliquen los comportamientos de Life, solo se han realizado estudios de tipo estadísticos como en [SS78], [Wol83], [PW85], [GV87], [McI90] y [GGJ93]. En estos estudios se ha logrado calcular la densidad de los estados en Life para un largo tiempo. En este artículo se hace uso de la teoría del campo promedio para reproducir dicho resultado, además se muestra la utilidad de los polinomios de Bernstein para calcular de manera directa el polinomio del campo promedio y determinar el comportamiento de la curva de probabilidad de generación en generación.

Primero se hace un análisis de Life determinando sus características a través de su curva de probabilidad y la existencia de sus puntos fijos, en base a estos resultados se aplica el mismo análisis a los autómatas celulares en tres dimensiones similares a Life propuestos por Bays. Con este estudio comparativo es claro ver que reglas de evolución presentan características similares a Life desde un punto de vista estadístico.

A principios del año 1970, Conway muestra varios de sus resultados en la columna mensual de Martin Gardner en la revista Scientific American [Gard70]. Entre estos, Conway presenta un juego llamado The Game of Life, un autómata celular con dos estados en su alfabeto {0,1}, {blanco, negro} o {muerto,vivo}, donde cada uno de estos estados es representado en un arreglo de células bidimensional infinito. La función de transición está definida por la vecindad de Moore, donde la célula central depende de la suma de sus vecinos de generación en generación.

El mecanismo de Life es muy sencillo en general, sin embargo cumple con dos propiedades fundamentales dentro de la teoría de autómata celular, la primera es que pueda soportar comportamientos complejos y la segunda es que el sistema pueda auto-reproducirse. John von Neumann precursor de la teoría de autómata celular ya había desarrollado un modelo que cumplía con estas propiedades en [Neu66], su modelo es en dos dimensiones pero con 29 estados en su alfabeto y la función de transición está definida por la vecindad de von Neumann. El modelo de von Neumann resulta ser complejo de desarrollar, en cambio el modelo de Conway es más fácil de analizar, por esta razón el modelo de Conway ha sido muy estudiado. Por otra parte Conway demostró que el modelo de von Neumann no es el único, ni el más sencillo modelo que pueda demostrar las propiedades fundamentales establecidas en la teoría de autómata celular.

En el año 1986 Bays presento varios autómatas celulares que son similares a Life en tres dimensiones. El estudio es muy extenso y presentado en varios artículos [Bays87], [Bays88b], [Bays90], [Bays91], [Bays92] y [Bays94]. Bays plantea el problema en ver que regla de evolución es ``meritoria'' a ser llamada Life en tres dimensiones. La relación que presenta Bays en sus reportes se basan en simulaciones dentro del espacio tridimensional, encontrando que varias reglas de evolución mantienen una cierta cantidad de células vivas en un largo tiempo, además de que estas reglas de evolución pueden generar estructuras fijas, estructuras periódicas fijas y estructuras periódicas con desplazamientos.

La teoría del campo promedio determina la densidad de los estados en el espacio de evoluciones en un largo tiempo de manera global. Howard Gutowitz utiliza la teoría del campo promedio como un caso especial de la teoría de estructura local en [GVK87], para caracterizar el tipo de clases que pueden derivar los autómatas celulares en una dimensión a través de la densidad de sus estados. Hugues Chaté y Paul Manneville utilizan la teoría del campo promedio en [CM92] para deteminar comportamientos colectivos periódicos y quasiperiódicos no triviales en autómatas celulares de altas dimensiones utilizando mallas acopladas.

Harold V. McIntosh hace notar la relación y utilidad que existe entre la teoría del campo promedio y los polinomios de Bernstein en [McI90]. Utilizando el enfoque dado por McIntosh y Chaté-Manneville obtenemos los polinomios de las reglas de evolución en autómatas celulares de tres dimensiones que sean similares a Life propuestos por Bays, desde un punto de vista estadístico. Por otra parte se muestra la utilidad de usar los polinomios de Bernstein para calcular el polinomio del campo promedio, esto nos proporcionó información valiosa para poder diferenciar de manera más clara, cada una de las reglas de evolución en tres dimensiones que sean meritorias a ser llamadas Life en tres dimensiones. Se presenta el método con detalle y los resultados obtenidos así como las limitaciones de este tipo de estudio.


next up previous
Next: Preliminares Up: Autómatas celulares en tres Previous: Autómatas celulares en tres
ice 2002-03-11