The University of Sussex

Complexity in One-D Cellular Automata: gliders, basins of attraction and the Z parameter

Andrew Wuensche

What do we mean by complexity 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 compound gliders made up of interacting sub-gliders - evolving within quiescent or 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 behaviour, 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 neighbourhood size. The relationship between Z and the lambda parameter is described. A method of recognising the emergence of gliders by monitoring the evolution of the lookup frequency spectrum, and its entropy, is suggested.

This paper is not available online