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 metacoordinate of this pseudofactorization, (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 hyperlattice 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 hyperevolutions as either 2D rasters or 3D cuboids.
