5 videos

62 videos

7 videos

5 videos

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

Organisateur(s) Cassaigne, Julien ; Chalopin, Jérémie ; Chepoi, Victor ; Guillon, Pierre ; Moutot, Etienne ; Theyssier, Guillaume
Date(s) 29/01/2024 - 02/02/2024
URL associée https://conferences.cirm-math.fr/3148.html
00:00:00 / 00:00:00
7 11

## Tutorial on cellular automata - lecture 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.

### Données de citation

• DOI 10.24350/CIRM.V.20136603
• Citer cette vidéo Ollinger, Nicolas (31/01/2024). Tutorial on cellular automata - lecture 1. CIRM. Audiovisual resource. DOI: 10.24350/CIRM.V.20136603
• URL https://dx.doi.org/10.24350/CIRM.V.20136603

### Bibliographie

• DELORME, Marianne. An introduction to cellular automata: some basic definitions and concepts. In : Cellular automata: a parallel model. Dordrecht : Springer Netherlands, 1999. p. 5-49. - http://dx.doi.org/10.1007/978-94-015-9153-9_1
• KARI, Jarkko. Theory of cellular automata: A survey. Theoretical computer science, 2005, vol. 334, no 1-3, p. 3-33. - https://doi.org/10.1016/j.tcs.2004.11.021
• BÄCK, Thomas, KOK, Joost N., et ROZENBERG, G. Handbook of natural computing. Springer, Heidelberg, 2012. -

### Dernières questions liées sur MathOverflow

Pour poser une question, votre compte Carmin.tv doit être connecté à mathoverflow

### Poser une question sur MathOverflow

• 01:36:20
publiée le 19 février 2024

## Randomness and complexity - lecture 1

De Sylvain Perifel

01:39:40
publiée le 19 février 2024

## Diagram groups and their geometry - lecture 1

De Rachel Skipper

01:28:48
publiée le 19 février 2024

## Diagram groups and their geometry - lecture 2

De Anthony Genevois

01:34:47
publiée le 19 février 2024

## An introduction to Walnut - lecture 1

01:00:43
publiée le 19 février 2024

## The crossing paths of Mandelbrot and Schützenberger: an episode of crossovers between maths and computing (1953-1963)

De Maarten Bullynck

54:56
publiée le 19 février 2024

## Lost in ecological transition ? The trajectory of a (computer) scientist in the Anthropocene

De Julien Lefèvre

01:27:27
publiée le 19 février 2024

## Tutorial on cellular automata - lecture 1

De Nicolas Ollinger

01:25:44
publiée le 19 février 2024

## Randomness and complexity - lecture 2

De Sylvain Perifel

01:38:03
publiée le 19 février 2024

## An introduction to Walnut - lecture 2

01:31:37
publiée le 19 février 2024

## Tutorial on cellular automata - lecture 2

De Nicolas Ollinger

59:57
publiée le 19 février 2024

## Complexity and the hat

De Chaim Goodman-Strauss

## Inscrivez-vous

• Mettez des vidéos en favori
• Ajoutez des vidéos à regarder plus tard &
conservez votre historique de consultation
• Commentez avec la communauté
scientifique
• Recevez des notifications de mise à jour
de vos sujets favoris
Donner son avis