McCaskill, John S., and Norman H. Packard. “Analysing Emergent Dynamics of Evolving Computation in 2D Cellular Automata.” In International Conference on Theory and Practice of Natural Computing , pp. 3-40. Springer, Cham, 2019.
Conway’s Game of Life (GoL), a famous 2D cellular automaton (CA), is extended to allow evolution by associating genetic information with individual live cells, that specifies variant local CA rules. Genomes are formed by copying (potentially with mutation) or movement from one of the live neighbour cells and are destroyed at death. Just as biological evolution discovers innovations in the space of chemical and physical functionalities, we explore how the addition of genetic information enables an evolutionary process that can coordinate robust complex dynamics by exploring spatially inhomogeneous local modifications to the non-robust GoL rules.
We discovered a large family of deterministic rules which avoid stochastic choices of ancestor for genetic inheritance. Systematic genetic variations near to the game of life rule are investigated and found to produce signs of computational complexity with an abundance of spaceship and glider gun structures. We investigated evolution for four successively more differentiated symmetry cases in the nearest neighbour rules: semi-totalistic, corner-edge totalistic, 8-rotation symmetric, and physical 2D symmetric (4-rotations and 4-reflections).
The genetic evolution is analysed by fast ongoing genealogy construction and population weighted activity statistics. The spatial structure is captured using hash encoded quadtrees of the connected components, which are also mapped through time for novelty and with activity statistics. This together with a novel genetic tracking of the dynamical displacement ancestry of live genes allows an efficient recognition of regular dynamical structures such as spaceships which transport information while changing shape, solving an open problem in finding efficient alternatives to ε-machines for 2D automata.