INFLUENCIA DE LA RED ESPACIAL EN EL COMPORTAMIENTO DE UN SISTEMA DINáMICO: LA HORMIGA DE LANGTON

En la presente tesis se estudia un sistema dinámico particular, la hormiga de Langton, que tiene interés en el ámbito de física estadística. El sistema consiste en un grafo a cuyos vértices hay un estado binario asociado (blanco o negro), y en un autómata (la hormiga) que se desplaza por sus vértices y los cambia de estado. El movimiento de la hormiga está completamente determinado por el estado de los vértices que visita. Este sistema ha sido estudiado desde hace más de una década. Fenómenos curiosos e interesantes han sido descubiertos, sin embargo pocos de ellos tienen una explicación teórica.

El sistema es fuertemente dependiente del grafo sobre el cual se desplaza. El objetivo principal de este trabajo de tesis es conocer esta dependencia desde un punto de vista teórico.

A través de métodos combinatoriales se demostró que la trayectoria de la hormiga es simétrica bajo reflexiones cuando en un comienzo, en la grilla hexagonal, todos los vértices en el mismo estado. Además, en el caso de los grafos Γ(k,d) se demostró que si el grafo tiene grado mayor o igual que 5, la hormiga no puede alcanzar todos los vértices del grafo y que si en un comienzo todos los vértices están en el mismo estado, a excepción de un número finito, entonces a partir de un momento la trayectoria de la hormiga es regular.

Se demostró que el sistema es universal cuando el grafo es la grilla hexagonal o cuadrada. La demostración de esto se llevó a cabo mediante la simulación de puertas y circuitos lógicos.

Finalmente el sistema se estudió desde el punto de vista de los sistemas dinámicos simbólicos, clasificando los grafos Γ(k,d) según diferentes propiedades del sistema, tales como la transitividad, regularidad del lenguaje asociado, etc..

Los resultados confirman el hecho que el sistema presenta una alta complejidad en los casos de las grillas hexagonal y cuadrada, y muestra que el caso de los grafos Γ(k,d) son más simples cuando d ≥ 5, que es, en particular, el caso de la grilla triangular.