Paper #: 94-04-025
What do we mean by compexity in the changing patterns of a discrete dynamical system? Complex one-dimensional CA rules support the emergence of interacting periodic configurations--gliders, glider-guns and “compound” gliders made up of interacting sub-gliders--evolving within quiescent of periodic backgrounds. This paper examines gliders and their interactions in one-dimensional CA on the basis of many examples. The basin of attraction fields of complex rules are typically composed of a small number of basins with long transients (interacting gliders) rooted on short attractor cycles (non-interacting gliders, or backgrounds free of gliders). For CA rules in general, a relationship is proposed between the quality of dynamical behavior, the topology of the basin of attraction field, the density of Garden-of-Eden states counted in attractor basins or sub-trees, and the rule-table's Z parameter. High density signifies simple dynamics, and low density chaotic, with complex dynamics at the transition. Plotting Garden-of-Eden density against the Z parameter for a large sample of rules shows a marked correlation that increases with neighborhood size. The relationship between Z and $\lambda$ parameter is described. A method of recognizing the emergence of gliders by monitoring the evolution of the lookup frequency spectrum, and its entropy, is suggested.