On Discovering Gliders and Glider Guns with Evolutionary Algorithms
Emmanuel Sapin and A. Adamatzky
University of the West of England
Gliders and glider guns are essential components of theoretical studies in emergence of computation and computational universality of cellular automata. We show how to discover novel gliders and glider guns using evolutionary algorithms. Evolutionary algorithms are stochastic algorithms that incorporate aspects of natural selection or survival of the fittest determined by the value of a fitness function for each individual. We apply the algorithms to evolve binary and ternary state automata and search for mobile localizations and their generators.
A fitness function is calculated as follows. A cellular automaton with a randomly selected cell-state transition function is allowed to develop, and then its configurations are automatically scanned for gliders. The value of the fitness function is the number of gliders found divided by the total number of cells. Such an algorithm succeeds in finding novel glider guns for over half the gliders, and we have located around five thousand glider guns generating the same gliders. We propose classification of the glider guns based on the number of gliders emitted and the types of gliders. Computational universality of discovered automata is demonstrated via simulation of a NAND gate and direct simulation of a Turing machine.
When studying ternary state automata we focused on those with the Moore neighborhood and totalistic cell-state transition function. Over one thousand different gliders are discovered using the fitness function based on a number of isolated patterns in configurations of cellular automata. Glider-supporting rules discovered are interpreted in terms of reaction-diffusion chemical systems. Such rules are considered to be basic building blocks of future massively parallel chemical computers.
All the discovered patterns can be found at
http://uncomp.uwe.ac.uk/sapin/. This work was
supported by the
Engineering and Physical Sciences Research Council (EPSRC) of the United Kingdom, Grant EP/E005241/1.