×

The mathematics of cellular automata. (English) Zbl 07814697

Student Mathematical Library 108. Providence, RI: American Mathematical Society (AMS) (ISBN 978-1-4704-7537-6/pbk; 978-1-4704-7670-0/ebook). xv, 228 p. (2024).
Cellular automata are discrete models of organisms: arrays of cells, each evolving according to the same pre-established rule and depending on the cell’s internal state as well as on the states of its immediate neighbours. As such, they are a fundamental model of how complexity may emerge from very simple building blocks.
The book under review introduces some of the main features and properties of cellular automata, from a mathematical viewpoint. It should not be treated as a reference (though it does make pleasant reading), but rather as the support of an introductory course on cellular automata, introducing basic mathematical concepts along the way.
In fact, I believe the reverse is also true: {it is a course on basic mathematics (calculus), motivated by cellular automata as a running example.} In particular, the reader will learn about metric spaces, (equi)continuity, etc. The text contains proofs of the main results, often richly illustrated via cellular automata.
A few caveats for the professional mathematician: the results presented in this book heavily focus on one-dimensional cellular automata, those for which the cells are arranged in a linear array. There is a single chapter on two-dimensional cellular automata, focussing on Conway’s “game of life”, and the celebrated Moore-Myhill theorems, while valid in arbitrary-dimensional grids, are only proven in dimension one. As such, the beautiful connection between \((d+1)\)-dimensional tiling problems and \(d\)-dimensional cellular automata is missing.
For a mathematically more thorough treatment, I would recommend T. Ceccherini-Silberstein and M. Coornaert’s [Cellular automata and groups. 2nd edition. Cham: Springer (2023; Zbl 1531.37003)].

MSC:

37-02 Research exposition (monographs, survey articles) pertaining to dynamical systems and ergodic theory
37B15 Dynamical aspects of cellular automata
37B10 Symbolic dynamics
68Q80 Cellular automata (computational aspects)

Citations:

Zbl 1531.37003
Full Text: DOI