Convergence and Feedback:
A Framework for Bounded Cellular Automata Design
David H. Jones, Richard McWilliam and Alan Purvis
Cellular automata (CAs) are a class of parallel processing architectures that are useful for computation and simulation of complex systems. We present a deterministic technique for designing the inter-cellular interactions of a bounded CA such that it forms specified global patterns or sequences, and can detect and respond to distributed inputs. The task of designing the local interactions from a given global behaviour is traditionally termed the inverse problem and has limited the size, complexity and usefulness of CAs to those which can be designed by stochastic methods. We first show that, for a bounded CA to converge to a single static pattern regardless of initial conditions, the local interactions of each cell must rely on information from one neighbouring cell per axis. We then demonstrate a means of designing bounded CAs to assemble any static global pattern. Then we introduce a local clause to the inter-cellular interactions such that the CA will only converge if it detects a global pattern in its inputs. Finally we superimpose orthogonally opposing layers of assembling and detecting arrays to design bounded CAs that are capable of computation and sequence assembly.
Keywords: Cellular Automata, Inverse rule, Convergence