Boundary Growth in One-Dimensional Cellular Automata
Charles D. Brummitt
Department of Mathematics
and
Complexity Sciences Center
University of California
One Shields Avenue
Davis, CA 95616, USA
Eric Rowland
LaCIM, Université du Québec à Montréal
Montréal, QC H2X 3Y7, Canada
Abstract
The boundaries of one-dimensional, two-color cellular automata depending on four cells and begun from simple initial conditions are systematically studied. The exact growth rates of the boundaries that appear to be reducible are determined. The reducible boundaries are characterized by morphic words. For boundaries that appear to be irreducible, curve-fitting techniques are applied to compute an empirical growth exponent and (in the case of linear growth) a growth rate. The random walk statistics of irreducible boundaries exhibit surprising regularities and suggest that a threshold separates two classes. Finally, a cellular automaton is constructed whose growth exponent does not exist, showing that a strict classification by exponent is not possible.
