Open-Ended Evolution and Innovation in a Deterministic Cellular Automata Universe

One of the most remarkable features of life on Earth is the apparent open-ended evolution and innovation of the biosphere over its > 3.5 billion year history. This is also one of the most perplexing features of biological evolution from the perspective of theoretical and computational modeling. Here we show that state-dependent dynamical rules can generate open-ended evolution for simple cellular automata (CA) “organisms” coupled to an external “environment” in a fully deterministic system. We present formal definitions of open-ended evolution as patterns that are non-repeating within the expected Poincare recurrence time of an isolated organism, and of innovation as trajectories not observed in isolated organisms. We demonstrate that a small subset of CA organisms implementing a state-dependent update rule, which is a function of the organism’s current state and rule and the state of the environment, satisfy these minimal requirements for open-endedness and innovation. Our results demonstrate that an additional requirement for open-ended evolution and innovation is to remove the segregation of states and (fixed) dynamic laws characteristic of the physical sciences in attempts to model biological complexity.