Fundamentals of Computing and Discrete Mathematics

Complex Systems and Computing
– Cellular Automata

Cellular automata are among the oldest computational models inspired by nature. A cellular automaton is a discrete dynamical system that consists of an infinite array of cells, each in some state from a finite state set. The cells change their states according to a local update rule that provides the new state based on the old states of the cell and its neighbors. All cells use the same update rule, and the change of states happens simultaneously everywhere. Iterating such updates over and over again at discrete time steps may lead to an amazingly complex dynamics, even if the individual cells are very simple. Mathematically, cellular automata are endomorphisims of the shift dynamical system.

The group has studied algorithmic issues concerning cellular automata dynamical systems. We have shown, for example, that it is undecidable whether a given two-dimensional cellular automaton is reversible or surjective. We have also proved the algorithmic undecidability of several questions concerning one-dimensional cellular automata. Recently we gave a complete characterization of entropies of one- and two-dimensional cellular automata.

We actively participate on international collaboration on cellular automata research. J.Kari is the current chair of the IFIP working group 1.5 on Cellular Automata and Discrete Dynamical Systems. He has edited special issues of international journals on the topic of cellular automata, and published a survey

  • J. Kari. Theory of Cellular Automata: a survey. Theoretical Computer Science 334, 3-33, 2005

on theoretical aspects of cellular automata. He is also the area editor on cellular automata in the Handbook of Natural Computing.

Last modified: