Neural Networks and Cellular Automata Complexity
J. Gorodkin
A. Sørensen
O. Winther
CONNECT, The Niels Bohr Institute,
Blegdamsvej 17, 2100 Copenhagen O, Denmark
Abstract
The genotype-phenotype relation for the 256 elementary cellular automata is studied using neural networks. Neural networks 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.
