00:00:00 / 00:00:00

Apparaît dans la 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.

Informations sur la vidéo

Données de citation

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

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




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