Departamento de Computación

A mediados de la década de 1980, Steven Wolfram propuso que en las evoluciones del autómata celular lineal elemental regla 110, se podría obtener un comportamiento global equivalente a hacer computación universal. Esta conjetura se originó por la aparente interacción entre los patrones gráficos generados en las evoluciones de ese autómata celular, la conjetura fue demostrada recientemente por Matthew Cook, elaborando un intrincado y complejo sistema de choques de gliders, simulando de ese modo los datos de entrada, el intercambio de información y los resultados de los cálculos hechos. A partir de entonces se ha tomado la regla 110 como un objeto de estudio.
En esta tesis se toman los patrones emergentes en las evoluciones de la regla 110 para generar mosaicos, con los que es posible dar un sentido algorítmico al proceso de hacer cubrimientos del plano con estos mosaicos. Se descubre el origen de los patrones gráficos y se verifican las condiciones necesarias para que estos patrones gráficos sean llamados mosaicos.
Los mosaicos considerados ofrecen interesantes regularidades que permiten la definición de herramientas para manejarlos; se estudia entonces la relación de estos patrones gráficos con problemas como el “máximo número de besos” y el 18vo problema de Hilbert. Estudiar estas regularidades será útil para posteriormente crear otro tipo de reglas.
Cambiamos el punto de vista a un manejo simbólico y definimos un alfabeto de símbolos. Con esos símbolos construimos palabras y aprovechamos las regularidades encontradas para crear reglas de agregación, lo que nos da el sentido algorítmico deseado. Aplicar estas reglas provoca que el cubrimiento cambie en cada paso de tiempo, definiendo un comportamiento dinámico llamado “evoluciones de Post”. Hacia el final de la tesis se describe la construcción de las máquinas celulares de computación basada en mosaicos.
Palabras y frases claves. Autómatas celulares, Decibilidad, Computabilidad, Mosaicos, Espacios métricos Computación simbólica.