In this programmatic talk, we will sketch both a conceptual and formal framework for reasoning about the notion of algorithm. This framework will arise from the analysis we will make of the relationships existing between the notion of algorithm and other similar (but still different) notions, like that of computation and that of program. We will first show that the Turing-Church thesis concerning effective computability is not sufficient to capture the notion of algorithm, as it identifies programs which are intensionally different. We will then show the limits of the existing models of computation in capturing some basic construction processes that we are willing to call algorithmic. In order to solve this problem, we propose a formalisation of the notion of model of computation on the base of which we claim that the notion of algorithm could eventually be analyzed. This approach centered around the dynamics of program execution, reconciles the more mechanical view of computation (such as formalized by Turing machines and automata) with the logical view - as it in particular stems from a generalization of Jean-Yves Girard's Geometry of Interaction programme.[-]

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

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