Emergence of Self-Replicating Hierarchical Structures in a Binary Cellular Automaton

Abstract We have discovered a novel transition rule for binary cellular automata (CAs) that yields self-replicating structures across two spatial and temporal scales from sparse random initial conditions. Lower-level, shape-shifting clusters frequently follow a transient attractor trajectory, generating new clusters, some of which periodically self-duplicate. When the initial distribution of live cells is sufficiently sparse, these clusters coalesce into larger formations that also self-replicate. These formations may further form the boundaries of an expanding complex on an even larger scale. This rule, dubbed “Outlier,” is rotationally symmetric and applies to 2-D Moore neighborhoods. It was evolved through genetic programming during an extensive search for rules that foster open-ended evolution in CAs. While self-replicating structures, both crafted and emergent, have been created in CAs with state sets intentionally designed for this purpose, the Outlier may be the first known rule to facilitate nontrivial emergent self-replication across two spatial scales in binary CAs.