A cellular automaton inverse problem

This thesis addresses the existence of cellular automaton rules that generate a given pattern. Methods of finding exact and best fit rules that generate a given pattern are presented. Methods of examining the structure of rules to determine when they are equivalent to smaller rules are presented.; Necessary and sufficient conditions for a given two-dimensional, two-state pattern to be generated by a one-dimensional cellular automaton with toroidal boundaries are presented. A sufficient condition for one row of a two-state pattern to be the image of another under a one-dimensional cellular automaton with infinite boundaries is presented. Theorems and algorithms on the size reduction of two-state rules are presented. Implications of the 1D toroidal existence theorems for cycle and transient lengths of 1D cellular automaton rules are discussed.; Necessary and sufficient conditions for a given three-dimensional, multi-state pattern to be generated by a two-dimensional cellular automaton with toroidal boundaries are presented. Theorems and algorithms on the size reduction of multistate rules are presented.; Methods of detecting noise in patterns generated by 1D cellular automata are discussed. A pattern is generated by a cellular automaton and then noise is added by changing the states of some cells. In many cases, all cells with incorrect states can be found and the original rule can be recovered.