Neural Networks and Cellular Automata Complexity



J. Gorodkin, A. Sørensen, and O. Winther
Complex Systems 7, 1-23, 1993.
(Cover Illustration is from Figure 4.)


Abstract


The genotype-phenotype relation for the 256 elementary cellular automata is studied using neural networks. Neural network are trained to learn the mapping from each genotype rule to its corresponding Li-Packard phenotype class. By investigating learning curves and networks pruned with Optimal Brain Damage on all 256 rules, we find that there is a correspondence between the complexity of the phenotype class and the complexity (net size needed and test error) of the net trained on the class. For Li-Packard Class A (null rules) it is possible to extract a simple logical relation from the pruned network. The observation that some rules are harder for the networks to classify leads to an investigation of rule 73 and its conjugate rule 109. Experiments reveal 3-cycles in magnetization in agreement with observations in higher dimensional cellular automata systems.


Paper