Influence du réseau spatial sur le comportement d'un système dynamique : la fourmi de Langton
Institution:
École normale supérieure (Lyon ; 1987-2009)Disciplines:
Directors:
Abstract EN:
In this thesis, the interest is centered in a particular dynamical system: the Langton's ant, which has been principally studied in statistical physics. From more than a thenth of years, many curious ans interesting phenomena has been remarked, but there is still a lack of exact results. The system consists of an automaton (the ant) that walks over a planar graph whose vertices (cells) can be in one of two states, white or black. The ant's movement is entirely determined by the cell's state, and this state is switched by the ant presence. In our approach, we consider several graphs to evaluate the system complexity dependence; We have proved, through combinatory methods, that in the hexagonal grid, the ant comes back to its starting point an infinite number of times, if at the beginning all the cells are in the same state. We have studied the ant in graphs corresponding to the tessealtions of the hyperbolic and Euclidean plane by regular k-gons, the Gamma(k,d) graphs. In the Gamma(k,d) graphs, if the degree is larger than 5, we have proved that for a fixed initial position, the ant cannot reach all the cells of the graph, no matter what the states are; and that when starting with a finite amount of black cells, its trajectory eventually becomes regular. We have shown the Turing universality of the system in the case of the square an hexagonal grids. We have described the system in terms of Symbolic Dynamics. We have proved properties such as transitivity, soficity, etc. . . The highest complexity is attained on the square and hexagonal grids, while on the triangular grid and the Gamma(k,d) graphs of degree larger than 5, the system's behavior is simpler.
Abstract FR:
Dans cette thèse, nous nous intéressons à un système dynamique particulier, la fourmi de Langton, introduit dans le cadre de la physique statistique. Depuis plus d'une dizaine d'années ce système est très étudié, des phénomènes curieux et intéressants ont été mis en évidence, mais beaucoup d'eux restent mal compris. Il s'agit d'un graphe dont les sommets sont munis d'un état (balc ou noir), plus un automate (la fourmi) qui se déplace sur les sommets d'état. Le mouvement de la fourmi est entièrement déterminé par l'état des sommets qu'elle visite. L'objet principal de notre travail de thèse a été de faire varier le graphe sur lequel se déplace la fourmi pour voir comment la complexité du système en dépendait. Par des méthodes combinatoires, nous avons montré que sur le réseau hexagonal, partant d'une configuration vide, la fourmi revenait un nombre infini de fois à son point de départ. En outre, dans le cas des graphes Gamma(k,d) avec d plus grand que 5, la fourmi ne pouvait pas atteindre tous les sommets du graphe et que si au départ il n'y a qu'un nombre fini de sommets en état noir, sa trajectoire devenait régulière au bout d'un moment. Nous avons montré que ce système était universel pour le calcul dans le cas de la grille carrée et du réseau hexagonal. La preuve se fonde sur la simulation de portes et circuits logiques. Finalement, le système a été étudié du point de vue des systèmes dynamiques symboliques, en classifiant les graphes Gamma(k,d) selon des propriétés du système comme la transitivité, régularité du langage, etc. Notre travail confirme le fait que ce système est plus complexe lorque le graphe sous-jacent est la grille carrée et le réseau hexagonal. Le cas des graphes Gamma(k,d) ou d est plus grand que 5, est plus simple.