The study of self-replicating structures is a very important field in Artificial Life. Cellular automata have studied two kinds of replicating structures: self-replicating ones and universal constructors. Von Neumann designed complex universal constructors consisting of multiple components. A second type of replicators, self-replicated loops, were studied by Langton, showing that looplike structures used in universal constructors could independently reproduce themselves. The replication process underlying both universal constructors and self-replicating loops, uses a sequential construction in which an arm extends from the parent structure and deposits the child structure. It depends on manually programmed sequential instructions depending on the presence of totalistic transition functions. But today Genetic programming facilitates the evolution of cellular automata given initial structures where cells may have several possible states. Pan and Reggia (2010) obtain replicating structures that are qualitatively different from past manually designed universal constructors and self-replicating loops. As a consequence, it is possible to produce many replicators that vary in just a single property.
To build a Genetic programming system that can program a cellular automata to support self-replication, the authors use trees as data structures ("chromosomes") that represent both structural information and the rules forming the state transition functions. They use a fitness function that generates the ocurrence of multiple copies of an initial structure in the cellular space over time. These self-replicating structures produced by Genetic programming are different from those found in self-replicating loops and universal constructors: there is no an identifiable instruction sequence and no construction arm. An initial structure grows and then divide, making replication very fast. The structures move and it is not possible distinguish between parents and childrens. In some ways, their fissionlike replication process is similar to the splicing during mitosis in biological cells. Replicators can also support the construction of secondary structures as they replicate, either with or without a given initial seed structure. When the replication rules are executed in parallel in each cell, they often employ a strategy that has not been manually created in old constructions. For instance, the moving-wall strategy consisting in a line of replicating structures depositing secondary structures behind it. Thus, Genetic programming is a very powerful tool in the discovery of novel self-replicating structures in cellular automata.
