Sequences of Preimages in Elementary Cellular Automata
Henryk Fukś
Brock University,
Department of Mathematics,
St. Catharines, ON L2S 3A1, Canada
Abstract
Regularities are searched for in the sequences of numbers of preimages for elementary cellular automata (CA). For 46 out of 88 "minimal" rules, recognizable patterns are found, usually in the form of second order recurrence equations with constant coefficients. After introducing the concept of asymptotic emulation of CA rules, it is shown how the regularities in the sequences of preimage numbers can be used to find rules emulating identity. It is also shown that the average density of nonzero sites after an arbitrary number of steps (starting from a disordered configuration) can be computed using the sequences of preimage numbers.
