Appears in collection : Research School in Discrete Mathematics and Computer Science / École de recherche en mathématiques discrètes et informatique - WEEK 1

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.