Universal groups of cellular automata

Ville Salo

Published 2018-08-27Version 1

We prove that the group of reversible cellular automata (RCA), on any alphabet $A$, contains a perfect subgroup generated by six 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 with respect to a fixed full 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, while for non-prime non-four alphabets, it is not a subdirect product of linear groups. For all composite alphabets of size at least ten, the group contains copies of all finitely-generated groups of RCA. We also obtain that RCA of biradius one on all large enough alphabets generate copies of all finitely-generated groups of RCA. We ask a long list of questions.