PDF files of articles are only available for institutions which have paid for the online version upon signing an Institutional User License.

Universal groups of cellular automata

Volume 169 / 2022

Ville Salo Colloquium Mathematicum 169 (2022), 39-77 MSC: Primary 37B10; Secondary 20B27. DOI: 10.4064/cm8368-9-2021 Published online: 27 January 2022


We prove that the group of reversible cellular automata (RCA), on any alphabet $A$, contains a subgroup generated by three involutions which contains an isomorphic copy of every finitely generated group of RCA on any alphabet $B$. This result follows from a case study of groups of RCA generated by symbol permutations and partial shifts (equivalently, partitioned cellular automata) with respect to a fixed Cartesian product decomposition of the alphabet. For prime alphabets, we show that this group is virtually cyclic, and that for composite alphabets it is non-amenable. For alphabet size four, it is a linear group. For non-prime non-four alphabets, it contains copies of all finitely generated groups of RCA. We also prove this property for the group generated by RCA of biradius one on any full shift with large enough alphabet, and also for some perfect finitely generated groups of RCA.


  • Ville SaloDepartment of Mathematics and Statistics
    University of Turku
    20014 Turku, Finland

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image