APERIODICITY IN ONE-DIMENSIONAL CELLULAR AUTOMATA

Cellular automata are a class of mathematical systems characterized by discreteness (in space, time, and state values), determinism, and local interaction. A certain class of one-dimensional, binary site-valued, nearest-neighbor automata is shown to generate infinitely many aperiodic temporal sequences from arbitrary finite initial conditions on an infinite lattice. The class of automaton rules that generate aperiodic temporal sequences are characterized by a particular form of injectivity in their interaction rules. Included are the nontrivial "linear" automaton rules (that is, rules for which the superposition principle holds); certain nonlinear automata with injectivity properties similar to those of linear automata; and a wider subset of nonlinear automata whose interaction rules satisfy a weaker form of injectivity together with certain symmetry conditions. The evolution of this last subset of automata can be viewed as consisting of multiple domains within which behavior exactly mimics that of a linear automaton. A linearization technique is used to establish that these domains coalesce in finite time to produce at most two domains, and thereby to assert the aperiodicity of their temporal sequences. © 1990.