The attractor—basin portrait of a cellular automaton

Abstract

Local space-time structures, such as domains and the intervening dislocations, dominate a wide class of cellular automaton (CA) behavior. For such spatially-extended dynamics regular domains, vicinities, and attractors are introduced as organizing principles to identify the discretized analogs of attractors, basins, and separatrices: structures used in classifying dissipative continuous-state dynamical systems. We describe the attractor-basin portrait of nonlinear elementary CA rule 18, whose global dynamics is largely determined by a single regular attracting domain. The latter's basin is analyzed in terms of subbasin and portal structures associated with particle annihilation. The conclusion is that the computational complexity of such CA is more apparent than real. Transducer machines are constructed that automatically identify domain and dislocation structures in space-time, count the number of dislocations in a spatial pattern, and implement an isomorphism between rule 18 and rule 90. We use a transducer to trace dislocation trajectories, and confirm that in rule 18, isolated dislocation trajectories, as well as a dislocation gas, agree extremely well with the classical model of annihilating diffusive particles. The CA efficiently transforms randomness of an initial pattern ensemble into a random walk of dislocations in space-time.