Cylindrical cellular automata (Q1109569)

A one-dimensional cellular automaton with periodic boundary conditions may be viewed as a lattice of sites on a cylinder evolving according to a local interaction rule. A technique is described for finding analytically the set of attractors for such an automaton. Given any one-dimensional automaton rule, a matrix A is defined such that the number of fixed points on an arbitrary cylinder size is given by the trace of \(A^ n\), where the power n depends linearly on the cylinder size. More generally, the number of strings of arbitrary length that appear in limit cycles of any fixed period is found as the solution of a linear recurrence relation derived from the characteristic equation of an associated matrix. The technique thus makes it possible, for any rule, to compute the number of limit cycles of any period on any cylinder size. To illustrate the technique, closed-form expressions are provided for the complete attractor structure of all two-neighbor rules. The analysis of attractors also identifies shifts as a basic mechanism underlying periodic behavior. Every limit cycle can be equivalently defined as a set of strings on which the action of the rule is a shift of size s/h; i.e., each string cyclically shifts by s sites in h iterations of the rule. The study of shifts provides detailed information on the structure and number of limit cycles for one-dimensional automata.