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.[-]

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.[-]

An automorphism of a subshift $X$ is a self-homeomorphism of $X$ that commutes with the shift map. The study of these automorphisms started at the very beginning of the symbolic dynamics. For instance, the well known Curtis-Hedlund-Lyndon theorem asserts that each automorphism is a cellular automaton. The set of automorphisms forms a countable group that may be very complicated for mixing shift of finite type (SFT). The study of this group for low complexity subshifts has become very active in the last five years. Actually, for zero entropy subshift, this group is much more tame than in the SFT case. In a first lecture we will recall some striking property of this group for subshift of finite type. The second lecture is devoted to the description of this group for classical minimal sub shifts of zero entropy with sublinear complexity and for the family of Toeplitz subshifts. The last lecture concerns the algebraic properties of the automorphism group for subshifts with sub-exponential complexity. We will also explain why sonic group like the Baumslag-Solitar $BS(1,n)$ or $SL(d,Z), d >2$, can not embed into an automorphism group of a zero entropy subshift.[-]

I shall discuss old and new results on amenability of groups, and more generally G-sets. This notion traces back to von Neumann in his study of the Hausdorff-Banach-Tarski paradox, and grew into one of the fundamental properties a group may / may not have -- each time with important consequences.
Lecture 1. I will present the classical notions and equivalent definitions of amenability, with emphasis on group actions and on combinatorial aspects: Means, Folner sets, random walks, and paradoxical decompositions.
Lecture 2. I will describe recent work by de la Salle et al. leading to a quite general criterion for amenability, as well as some still open problems. In particular, I will show that full topological groups of minimal Z-shifts are amenable.
Lecture 3. I will explain links between amenability and cellular automata, in particular the "Garden of Eden" properties by Moore and Myhill: there is a characterization of amenable groups in terms of whether these classical theorems still hold. [-]

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.[-]