The Calculus of Binary Cellular Automata

Abstract

The study of cellular automata has attracted considerable interest in recent years, which stems from the fact that they are fundamentally simple in construction, and yet have the capacity for profoundly complex behaviour. Cellular automata may be described as fully discrete dynamical systems, the evolution of which is determined locally and homogeneously. Thus defined, they are inherently suitable for digital computer implementation. Indeed, the growing interest in cellular automata corresponds with the increasing sophistication and accessibility of computer technology. Equipped with a standard microcomputer and some basic programming skills, one has a 'laboratory' in which an extraordinary range of behaviour may be observed - including such things as self organisation and replication, soliton formation and interaction, and chaos. ... It would appear that this thesis actually bears stronger connection with the area of symbolic dynamics, central to which is the study of shift dynamical systems. To begin with, one-dimensional cellular automata have been precisely characterised as the endomorphisms of shift dynamical systems in the work of Curtis, Hedlund and Lydon [7]. From this research emerged the commuting block maps problem studied by Coven, Hedlund and Rhodes [3, 16, 17] which has been solved in special cases. Interestingly enough, the form of the block maps for which solution was obtained bears strong resemblance to the cellular automata for which results are achieved in Chapter 5 of this thesis.