Complexity in One-D Cellular Automata: Gliders, Basins of Attraction and the Z Parameter

What do we mean by compexity in the changing patterns of a discrete dynamical system? Complex one-D CA rules support the emergence of interacting periodic configurations---gliders, glider-guns and {\it compound} gliders made up of interacting sub-gliders---evolving within quiescent of periodic backgrounds. This paper examines gliders and their interactions in one-D 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---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.