Group-theoretic interpretation of Margolus neighborhood cellular automata

Abstract

A set-theoretic structure of Margolus neighborhood cellular automata is developed to accommodate a group structure in an intuitive way. It is proven that pairs of reversible Margolus rule-global maps generate a group of bijections on a finite 2n x 2m grid of binary cells with function composition. This group can further be understood as a group action on the grid. We focus on the subgroup that consists of pairs of reversible, conservative rules and, in particular, the action of this group on the set of all possible "lonely universes" (grids with one living cell). We examine the permutation representation of this action and compute the sizes of the subgroups that are the isomorphic copies of the group under the permutation representation map.