Research
Cellular automata
A cellular automaton is a synchronous parallel computing model, which consists in a juxtaposition of finite state automata (cells) whose state changes over time according to that of their neighbors. Despite the simplicity of this local evolution rule, the overall behavior that appears in the evolution of a population of cells can be very complex.Chaos
Among the numerous notions attempting to comprehend the idea of complexity, sensitivity to initial conditions, transitivities, expansivities still seem rather mysterious, especially in their prediction from the local rule.Asymptotic behavior
Running the same program in parallel may allow to deduce global properties from local ones. The Cantor topology permits to express this in another way: some particular asymptotic behaviors can only happen within a finite time, such as nilpotency of cells. As a generalised problem are the links between the set of configurations that can be reached in an arbitrarily long time and the set of cluster points of orbits.Decidability
Moreover, we can try to understand the complexity of the evolution of the system with respect to predictibility. In which cases could we be able to algorithmically predict where the trajectory of a given set of configurations would go?Simulations
But a cellular automaton can also be seen as a computing system itself: it can run an algorithmic procedure, and even simulate another system, of which it will contain the dynamics in a certain way. Containing a lot of various dynamics can be seen as a sign of complexity.Directionnal dynamics
Defining complexity topologically presents the problem that the cellular automaton that simply shifts the state of all cells is considered chaotic. A solution to this problem is to study the cellular automaton up to a shift. New classifications arise, allowing a better understanding of the intrinsic action of the local rule.Restrictions
What do all these classifications attempting to capture the different behaviors of cellular automta become, when restricting the set of initial configurations (to a subshift)? For instance, sand automata are an interesting restriction which lies between one-dimensionnal and two-dimensionnal cellular automata.Trace
A trace of the cellular automaton is the infinite word representing the evolution of a particular cell. The set of traces is a subshift, i.e, a set of infinite words which can be characterized by a set of forbidden finite factors. Its dynamics as a shift is directly linked to that of the cellular automaton, since reading a letter forward in the trace corresponds to applying an evolution step of the cellular automaton. Being given a particular subshift, it is not obvious to know whether it is the set of traces of some cellular automaton. Conversely, most properties of the trace subshift are undecidable.
For further details, please contact me or look at the links (in french).