Binomial Exhaustion

Binary Rules Orient Invariant Bit Sums

Michael Schreiber

Wolfram Research

Binary rule numbers can be classified by their bit sums. The decimal rule number 110 of the elementary binary cellular automaton, which was already shown to be universal, has the binary representation {0,1,1,0,1,1,1,0}. Its simple classification number would thus be its digit sum, which is 5.

Binomial exhaustions test rules with given digit sums for given constellation dimensions. The ArrayPlot illustrates all rules sharing a binomial classification number 5. There are Binomial[8,5] such class 5 rules, namely 56.

Rules classified by identical digit sums can be interpreted as orientations of a common rule number that can be compressed into its bit sum invariant.

Hence complementing (1) the constellation dimension and (2) the bit sum, is the third meta-coordinate of this pseudo-factorization, (3) the binomial selection number that can be interpreted as an index into possible topologic orientations of these constellations.

The 256 elementary cellular automata rules, for example, are usually applied to a row of inputs. However, they can also be interpreted for a plane of evolution in 3D. The binomial class number 5 gives the number of constellations that return the output 1. An orientation of the arguments for this constellation is indicated by a selection number between 1 and 56.

Evolutions of binary CA in a hyper-lattice can thus be browsed by manipulation of the (1) constellation dimension, (2) binomial class number, and (3) binomial selection number for (a) rules and (b) initial conditions specified in a similar way. Exhaustion of initial conditions that are inconvenient to enumerate can be simulated by specification of one repetitive background or by its randomized topologic reorientations.

A prototype binomial exhaustion browser projects hyper-evolutions as either 2D rasters or 3D cuboids.