Enumeration of Preimages in Cellular Automata
Erica Jen
Center for Nonlinear Studies and Theoretical Division,
Los Alamos National Laboratory, Los Alamos, NM 87545, USA
Abstract
For a given rule and arbitrary spatial sequence, the preimages of the sequence are defined to be the set of tuples that are mapped by the rule onto the sequence. The enumeration of preimages provides information on the probability distribution associated with an automaton rule, determining, for example, the probability of occurrence of a sequence after one iteration of the rule operating on a random initial condition. It is shown here that formulae can be obtained for the exact number of preimages under an arbitrary one-dimensional nearest-neighbor automaton rule for any spatial sequence. The qualitative features of these formulae are determined by the combinatorial structure of the automata rule tables. The formulae are analytically and computationally useful for a wide variety of problems, including the identification of gardens-of-Eden (spatial sequences with no preimages), the evaluation of quantities that require knowledge of the probabilities of occurrence for all possible spatial sequences, and the characterization of statistical features such as the tendency to produce long runs of 1's and 0's.
