How to effectively represent and generate 2D cellular automaton rules that are invariant under rotation and reflection of the input matrix?

Question

Consider cellular automaton rules for a two-dimensional universe with two states, where a cell's new state can depend on its previous state and the states of the cells in its Moore neighborhood. Such a rule can be modeled as a function that takes as input a 3 by 3 matrix of bits, and outputs a bit.

Such a rule can be represented easily using a string of 512 bits representing the output for each of the $2^{3 \times 3}$ input states. Since this representation is bijective, a rule can also be randomly generated by sampling 512 bits.

However, it is sometimes preferable for reasons of aesthetics and comprehensibility that the output of the rule be the same when the input matrix is rotated or flipped horizontally or vertically. The rule for Conway's Game of Life is an example of a function satisfying this restriction.

Given a function $r : 2^9 \to 2$ which does not necessarily obey this restriction, we can obtain a function that does by mapping the input to the lexicographically smallest matrix obtainable by reflecting or rotating it before passing to $r$. However, this provides little insight into the questions I am interested in:

• How many functions obey this restriction?
• How can they be compactly representing using a bit string?
• How can they be efficiently randomly generated?

Answer 1

I won't go into the details of your specific case but try to answer the general problem.

In the unrestricted case there is a mapping from each of the $n$ (=512) input states to one of 2 output states and you want to restrict the function as follows:

• Create a partitioning of the initial $n$ input states into subsets.
• Your adapted function maps each of these subsets to an output

Proceed as follows:

• Enumerate all input states from 1 to $n$ (this is then the index of that state)
• Write a function $f(i)$ that generates all rotations/symmetric versions of an input state $i$ and take the lowest index of that set
• Partition the set $1..n$ according to $f$, i.e. if $f(x) = f(y)$, they are in the same class. The result is a pairwise disjoint set of sets, where each set consists of 'similar' input states that should therefore also have the same output.
• Let $P$ be the number of these sets.

Answering your questions should then be easy:

1. You could assign each of the $P$ sets an arbitrary output to get a unique function. $\Rightarrow 2^P$ functions
2. A bitstring of length $P$

3. Generate random integers (with more than $P$ bits each) and take the last $P$ bits.

   a. Maybe consider the distribution of values generated by your RNG, i.e.: are the last $P$ bits uniformly (or whatever you desire) distributed?

Answer 2

You seem to be looking to enumerate (and/or randomly sample from) the set of isotropic two-state two-dimensional cellular automata on the Moore neighborhood.

The general way to this is simply to find all the equivalence classes of the $2^{3\times3}$ possible neighborhoods, where two neighborhoods are considered equivalent if one can be transformed into the other by rotation and/or reflection. Your rule will then be a function from the set of these equivalence classes to the set of single cell states, and the number of such rules (for a two-state automaton) will be $2^N$, where $N$ is the number of these equivalence classes.

As far as I know, there's no obvious "elegant" way to find these equivalence classes other than by a brute force exhaustive search. Fortunately, this tedious work has already been done, and a list of all the $2 \times 51$ equivalence classes can be found e.g. on the wiki page I linked to above.

The page also describes a compact and somewhat human-readable notation developed by Alan Hensel for describing such rules, based on describing each equivalence class using the number of live cells in it (excluding the center cell) and a more or less arbitrary letter denoting the specific configuration of those cells, as shown in the table on the linked wiki page, and quoted below:

For example, using this notation, the rule string B2-a/S12 describes a rule where dead cells become alive if they have exactly two live neighbors and those neighbors are not adjacent, and live cells survive if they have one or two live neighbors in any configuration.

Several programs used for simulating and/or searching for patterns in Game of Life -like cellular automata, such as Golly, can parse rule strings in this notation.