Cellular automata and groups

  • Lecturer: Nhân Phú Chung
  • Date: Thursday 9.30 - 11.00
  • Room: MPI MiS A02
  • Language: English
  • Target audience: MSc students, PhD students, Postdocs
  • Content (Keywords): Cellular automata, Amenable groups, Residually finite groups, Sofic groups, Entropy, The Garden of Eden theorem


Cellular automaton was introduced by von Neumann. It has many important applications in dynamical systems. In this course I will explain the relations between amenability, residually finiteness, soficity, and surjunctivity of groups and cellular automata theory. More precisely, I am planning to teach

  • The dynamical characterization of residually finiteness.
  • Both surjectivity and pre-injectivity of the cellular automata over an amenable groups are equivalent to the fact that the image of the configuration space has maximal entropy. Then one can get the Garden of Eden theorem for the case of amenable groups.
  • A characterization of amenability of groups in terms of cellular automata (Ceccherini Silberstein,Machi,Scarabotti and Bartholdi). 
  • Gromov-Weiss's proof of Gottschalk conjecture for sofic groups.
  • Using cellular automata to give another proof of the Kaplansky's Direct Finiteness conjecture for sofic groups (Elek-Szabo, Ceccherini Silberstein-Coornaert).
  • Zero divisor conjectures of group rings and their reformulations in linear cellular automata.


Ceccherini-Silberstein, Coornaert, Cellular Automata and Groups. Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2010.

01.03.2017, 13:57