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

Area of Science:

• Complex Systems
• Artificial Life
• Computational Theory

Background:

• Cellular automata (CAs) are mathematical models used to study complex systems.
• Self-replication in CAs has been achieved, but often requires specifically designed rules or initial conditions.
• Open-ended evolution in CAs remains a significant research challenge.

Purpose of the Study:

• To discover a novel transition rule for binary CAs that promotes emergent self-replication.
• To investigate self-replication across multiple spatial and temporal scales.
• To identify CA rules capable of fostering open-ended evolution.

Main Methods:

• A novel transition rule, named 'Outlier,' was discovered using genetic programming.
• The rule was applied to 2-D binary cellular automata with Moore neighborhood.
• Simulations were conducted using sparse random initial conditions to observe emergent behaviors.

Main Results:

• The 'Outlier' rule facilitates the emergence of self-replicating structures from sparse initial conditions.
• Nontrivial self-replication was observed at two distinct spatial scales: lower-level clusters and larger formations.
• These formations can act as boundaries for even larger, expanding complex structures.

Conclusions:

• The 'Outlier' rule is a significant advancement, demonstrating emergent self-replication across scales in binary CAs without explicit design for this purpose.
• This discovery provides a new mechanism for studying open-ended evolution and complex emergent behaviors in artificial systems.
• The rule's rotational symmetry and application to 2-D Moore neighborhoods offer a robust model for future research.