Departamento de Computación

Esta tesis aborda un problema abierto en autómatas celulares conocido como comportamiento colectivo no trivial (CCNT). El CCNT consiste en la estabilidad de la densidad en un ciclo de periodo o cuasiperiodo 3. El interés de estudiar este fenómeno tiene dos motivaciones, la primera es lograr un mejor entendimiento sobre los sistemas dinámicos complejos, y la segunda es la necesidad de encontrar modelos sencillos que representen oscilaciones dinámicas encontradas en sistemas biológicos. Los autómatas celulares con comportamiento colectivo no trivial son modelos que presentan comportamiento oscilatorio, pero después de 16 años de investigación siguen sin una solución analítica satisfactoria. El objetivo de esta tesis es generar conocimientos que ayuden a entender el mecanismo que logra que los autómatas celulares presenten un comportamiento periódico de ciclo 3 en la dinámica de sus densidades. La manera en que abordamos el problema fue proponiendo un método analíco para caracterizar el comportamiento de las densidades en los autómatas celulares. Esta propuesta la llamamos "Polinomios de densidad" y consiste en el cálculo de polinomios probabilísticos tomados a partir de un análisis de campo medio en las preimágenes de las generaciones antecesoras de un autómata celular. Los resultados de esta propuesta son:
* La determinación de todas las condiciones iniciales bajo las cuales se presenta el CCNT.
* El cálculo de la robustez del comportamiento colectivo no trivial.
* El fenómeno del CCNT tiene muy pocas probabilidades de ser metaestable.
Como sucede en muchas investigaciones, la motivación de resolver un problema nos lleva a encontrar resultados en otras vertientes. Uno de estos resultados es la propuesta de un nuevo mecanismo para calcular preimágenes para cualquier autómata celular en una dimensión. Otro resultado es haber encontrado que los autómatas celulares en altas dimensiones pueden simularse en bajas dimensiones considerando autómatas celulares con vecinos de largo alcance.
Finalmente, abordar el problema del comportamiento colectivo no trivial nos condujo a encontrar un resultado fundamental en el área de autómatas celulares: la caracterización de las densidades. Los polinomios de densidad, herramienta usada para caracterizar la densidad, además de apoyarnos en el estudio de la fenomenología de los autómatas celulares con CCNT, es una herramienta útil que puede ser usada para estudiar otros problemas del área de autómatas celulares tales como, el problema de la clasificación de densidades ("Task Density Classification" [TDC]), la caracterización de los autómatas celulares que preservan su densidad ("Number Conservative Cellular Automata" [NCCA]) , el problema de la clasificación de autómatas celulares y la caracterización de la densidad de los autómatas celulares que son utilizados como modelos de problemas reales.