Cellular automata: a model of complexities

We study the model of cellular automata through two complementary aspects: local syntactic representations and global dynamics. We aim at establishing new links between these aspects using a set of approaches ranging from combinatorics to algebraic tools and computability theory. First, while studying local structures of transition rules, we introduce a new class of cellular automata (namely captive cellular automata) which are defined by an elementary local constraint. We establish a 0-1 law over that class and deduce that almost all captive cellular automata are intrinsically universal. However, we show that it is undecidable to determine whether a captive cellular automaton is intrinsically universal or not. In a second part, we focus on global properties of cellular automata while trying to disregard their syntactic representations. Our matter is then to study classifications and notions of complexity according to that global point of view. The key tool is the notion of simulation. We extend previous results from N. Ollinger concerning simulation pre-orders (with new relations of simulation and new properties inducing ideal or filter structures). We also study the Cartesian product over such structures. We establish a construction which can be considered as a limit of Cartesian products and allows us to exhibit infinite increasing chains of length omega+omega in one of the studied pre-orders. Finally, we focus on sequential dynamics and Turing-universal cellular automata. We construct an infinite lattice of Turing-universal cellular automata which are all infinitely far away from any intrinsically universal cellular automaton.Nous étudions le modèle des automates cellulaires en adoptant successivement deux points de vue --celui des représentations syntaxiques locales puis celui des dynamiques globales-- et en cherchant à établir des liens entre eux par différentes approches ou outils --algébrique, combinatoire, et de la théorie de la calculabilité. Au cours de notre étude de la structure des règles de transition locales, nous introduisons une nouvelle classe d'automates (appelés automates cellulaires captifs) définie par une contrainte locale très simple. Nous établissons une loi 0-1 sur cette classe qui a pour corollaire que presque tous les automates cellulaires captifs sont intrinsèquement universels. En revanche, nous montrons qu'il est indécidable de savoir si un automate cellulaire captif est intrinsèquement universel ou pas. Dans une seconde partie, nous poursuivons l'étude des automates cellulaires en cherchant au contraire à nous affranchir le plus possible de leur représentation syntaxique pour insister sur leurs propriétés dynamiques globales. Notre problématique devient celle de la classification et de l'étude de notions de complexité selon ce point de vue global. L'outil fondamental est celui de simulation. Nous étendons les résultats de N. Ollinger sur les structures de pré-ordre (nouvelles relations de simulations et nouvelles propriétés induisant des structures d'idéal ou de filtre) et étudions également l'effet du produit cartésien sur ces structures. Nous établissons une construction qui peut s'interpréter comme un produit cartésien limite et nous permet d'exhiber des chaînes infinies croissantes de longueur omega+omega dans l'un des pré-ordres étudiés. Enfin, nous nous intéressons aux dynamiques séquentielles et aux automates cellulaires universels pour le calcul Turing. Nous construisons un treillis infini d'automates cellulaires Turing-universels qui sont tous à distance infinie de tout automate cellulaire intrinsèquement universel