This tutorial surveys computational aspects of cellular automata, a discrete dynamical model introduced by S. Ulam and J. von Neumann in the late 40s: a regular grid of finite state cells evolving synchronously according to a common local rule described by a finite automaton.

Formally, a cellular automaton is a tuple $(d, S, N, f)$ where $d \in \mathbb{N}$ is the dimension of the cellular space, $S$ is the finite set of states, $N \subseteq_{\text {finite }} \mathbb{Z}^d$ is the finite neighborhood and $f: S^N \rightarrow S$ is the local rule of the cellular automaton.

A configuration $c \in S^{\mathbb{Z}^d}$ is a coloring of the cellular space by states.

The global transition function $G: S^{\mathbb{Z}^d} \rightarrow S^{\mathbb{Z}^d}$ applies $f$ uniformly according to $N$, i.e. for every configuration $c \in S^{\mathbb{Z}^d}$ and every position $z \in \mathbb{Z}^d$ it holds
$$G(c)(z)=f\left(c\left(z+v_1\right), \ldots, c\left(z+v_m\right)\right) \quad \text { where } N=\left\{v_1, \ldots, v_m\right\} .$$
A space-time diagram $\Delta \in S^{\mathbb{Z}^d \times \mathbb{N}}$ is obtained by piling successive configurations of an orbit, i.e. for every time step $t \in \mathbb{N}$ it holds $\Delta_{t+1}=G\left(\Delta_t\right)$.

Computing inside the cellular space: The first part of the tutorial considers cellular automata as a universal model of computation. Several notions of universality are discussed: boolean circuit simulation, Turing universality, intrinsic universality. Special abilities of cellular automata as a model of massive parallelism are then investigated.

Computing properties of cellular automata: The second part of the tutorial considers properties of cellular automata and their computation. De Bruijn diagrams and associated regular languages are introduced as tools to decide injectivity and surjectivity of the global transition function in the one-dimensional case. Both immediate and dynamical properties are introduced, in particular the notion of limit set.

Computation and reduction: undecidability results: The last part of the tutorial considers computing by reduction to establish undecidability results on some properties of cellular automata: injectivity and surjectivity of the global transition function in higher dimensions, nilpotency and intrinsic universality in every dimension, a Rice's theorem for limit sets.[-]

Deciding whether two one-dimensional subshifts are conjugate remains one of the most important question in symbolic dynamics. In this talk, we will highlight a new approach, using the diagrammatic calculus approach popular in category theory and especially in categorical quantum mechanics. We will explain how matrices (and subshifts of finite type) can be represented graphically and how this representation may help us find new conjugacy invariants.[-]

We say that a CA F stabilises an SFT X if (1) every element of X is a fixed point of F, and (2) starting from any finite perturbation of a configuration in X, the CA returns to X in finitely many steps. Does every SFT admit a stabilising CA? If so, what is the optimal stabilisation time for a given SFT? Do conjugate SFTs have the same optimal stabilisation times? What about stabilisation from random perturbations? I will present a joint work with Nazim Fatès and Irène Marcovici providing (partial) answers to these questions.[-]

This tutorial surveys computational aspects of cellular automata, a discrete dynamical model introduced by S. Ulam and J. von Neumann in the late 40s: a regular grid of finite state cells evolving synchronously according to a common local rule described by a finite automaton.

Formally, a cellular automaton is a tuple $(d, S, N, f)$ where $d \in \mathbb{N}$ is the dimension of the cellular space, $S$ is the finite set of states, $N \subseteq_{\text {finite }} \mathbb{Z}^d$ is the finite neighborhood and $f: S^N \rightarrow S$ is the local rule of the cellular automaton.

A configuration $c \in S^{\mathbb{Z}^d}$ is a coloring of the cellular space by states.

The global transition function $G: S^{\mathbb{Z}^d} \rightarrow S^{\mathbb{Z}^d}$ applies $f$ uniformly according to $N$, i.e. for every configuration $c \in S^{\mathbb{Z}^d}$ and every position $z \in \mathbb{Z}^d$ it holds
$$G(c)(z)=f\left(c\left(z+v_1\right), \ldots, c\left(z+v_m\right)\right) \quad \text { where } N=\left\{v_1, \ldots, v_m\right\} .$$
A space-time diagram $\Delta \in S^{\mathbb{Z}^d \times \mathbb{N}}$ is obtained by piling successive configurations of an orbit, i.e. for every time step $t \in \mathbb{N}$ it holds $\Delta_{t+1}=G\left(\Delta_t\right)$.

Computing inside the cellular space: The first part of the tutorial considers cellular automata as a universal model of computation. Several notions of universality are discussed: boolean circuit simulation, Turing universality, intrinsic universality. Special abilities of cellular automata as a model of massive parallelism are then investigated.

Computing properties of cellular automata: The second part of the tutorial considers properties of cellular automata and their computation. De Bruijn diagrams and associated regular languages are introduced as tools to decide injectivity and surjectivity of the global transition function in the one-dimensional case. Both immediate and dynamical properties are introduced, in particular the notion of limit set.

Computation and reduction: undecidability results: The last part of the tutorial considers computing by reduction to establish undecidability results on some properties of cellular automata: injectivity and surjectivity of the global transition function in higher dimensions, nilpotency and intrinsic universality in every dimension, a Rice's theorem for limit sets.[-]

Subshifts of finite type are central objects in symbolic dynamics. In the classical one-dimensional case, namely subshifts of finite over the group of integers Z , important structural results have been known for decades (although other basic problems remain wide open). Any Z-subshift of finite type decomposes into irreducible components and wandering points. Any irreducible SFT becomes topologically mixing after passing to some power of the shift. Krieger's embedding theorem provides (essentially) decidable necessary and sufficient conditions for an arbitrary subshift to embed in a given topologically mixing SFT. Boyle's factor theorems give (essentially) decidable for factoring between mixing SFTs.
The situation for multidimensional subshifts is far less structured and far more mysterious. It is well-known that multidimensional subshifts of finite type can exhibit a wild variety of "pathological behavior". One is soon faced with undecidability issues, and there seems to be little hope to obtain a tractable structure theory in complete generality. Over the years various properties of multidimensional subshifts have been introduced and studied, in an attempt to recover and generalize some structural aspects of the one-dimensional theory (eg “square mixing”, “block gluing”, “strong irreducibility”, “topological strong spatial mixing”, “the finite extension property”). Lightwood has obtained a partial extension of Krieger's embedding theorem for square-filling mixing square-filling mixing Zˆ2-subshifts of finite type. Briceno, McGoff and Pavlov have obtained a partial extension of Boyle's lower entropy theorem for Zˆd-subshifts of finite type with the finite extension property. In this talk I will describe new (and in a suitable "sensecomplete”) multidimensional generalizations of both Krieger's embedding theorem and of Boyle's lower entropy factor theorem. The formulation of these results involves the introduction of a new and seemingly fundamental property of some multidimensional subshifts: The map extension property, introduced implicitly by Mike Boyle in the early 1980's for Z-subshifts. This new property also turns out to be the natural adaptation of the notion of an absolute retract, introduced by Borsuk in the 1930's, to the category of subshifts.[-]