Formal Definitions of Unbounded Evolution and Innovation Reveal Universal Mechanisms for Open-Ended Evolution in Dynamical Systems

Abstract

Open-ended evolution (OEE) is relevant to a variety of biological, artificial and technological systems, but has been challenging to reproduce in silico. Most theoretical efforts focus on key aspects of open-ended evolution as it appears in biology. We recast the problem as a more general one in dynamical systems theory, providing simple criteria for open-ended evolution based on two hallmark features: unbounded evolution and innovation. We define unbounded evolution as patterns that are non-repeating within the expected Poincare recurrence time of an isolated system, and innovation as trajectories not observed in isolated systems. As a case study, we implement novel variants of cellular automata (CA) where the update rules are allowed to vary with time in three alternative ways. Each is capable of generating conditions for open-ended evolution, but vary in their ability to do so. We find that state-dependent dynamics, regarded as a hallmark of life, statistically out-performs other candidate mechanisms, and is the only mechanism to produce open-ended evolution in a scalable manner, essential to the notion of ongoing evolution. This analysis suggests a new framework for unifying mechanisms for generating OEE with features distinctive to life and its artifacts, with broad applicability to biological and artificial systems.

Figure 1

State diagrams: A hypothetical example demonstrating the concepts of INN and UE. The possible set of states are S = {1, 2, 3, 4, 5, 6} and rules R = {α, β}. For each panel, the example state trajectory s is initialized with starting state s _o = 3. For panels c and d the rule trajectory r is also shown. Highlighted in bold is the first iteration of the attractor for states (all panels) or rules (panel (c,d) only). For a discrete deterministic system of six states, the Poincaré recurrence time is t _P = 6. Panel (a) shows the state transition diagram for hypothetical rule α where a trajectory initialized at s(t ₀) = 3 visits two states. Panel (b) shows the state transition diagram for hypothetical rule β where a trajectory initialized at s(t ₀) = 3 visits only one state. Since the trajectories in (a,b) evolve according to a fixed rule (are isolated) they do not display INN or UE and in general the recurrence time $t_r\ll t_P$. Panel (c) demonstrates INN, where the trajectory shown cannot be fully described by rule α or rule β alone. The state trajectory s and rule trajectory r both have a recurrence time of t _r = 5, which is less than t _P so this example does not exhibit UE. Panel (d) exhibits UE (and is also an example of INN). The trajectory shown cannot be described by rule α or rule β alone. The recurrence time for the state trajectory is t _r = 13, which is greater than t _P. The rule trajectory also satisfies the conditions for UE, with a recurrence time in this example that is longer than that of the state trajectory due to the fact that the state transition 2 → 5 could be driven by rule α or β depending on the coupling to an external system.

Figure 2

Illustrations of the time evolution of a standard ECA (left) and of a Case I state-dependent CA (right). ECA evolve according to a fixed update rule (here Rule 30), with the same rule implemented at each time step. In an ECA rule table, the cell representation of all possible binary ordered triplets is shown in the top row, with the cell representation of the corresponding mapping arising from Rule 30 shown below. Rule 30 therefore has the binary representation 00011110. In a Case I CA (right), the environment subsystem e evolves exactly like an ECA with a fixed rule. The organism subsystem o, by contrast, updates its rule at each time-step depending on its rule at the previous time-step, its own state (green arrows) and the state of e (red arrows). The new rule for o is then implemented to update the state of o (blue arrows). The rules are therefore time-dependent in a manner that is a function of the states of o and e and the past history of o (through the dependence on the rule at the previous time-step).

Figure 3

Example of the implementation of a Case I organism in our example. Shown is an organism o of width w _o = 4, coupled to an environment e with width w _e = 6, where the rule of o at time step t is r _o(t) = 30. (a) At each time step t, the frequency of ordered triplets are compared in the state of the organism and that of the environment, s _o and s _e respectively, and used to update $r_o(t)\to r_o(t+1)$ (see text for algorithm description). (b) Table of the calculated frequency of ordered triplets in the state of the environment and in the state of the organism for time step t shown in the left panel. (c) Update of r _o from Rule 30 to Rule 62, based on the frequency of triplets in the table (b).

Figure 4

Examples of Case I CA exhibiting OEE. In each panel the environment e is shown on the left, and organism o on the right. For each o, the Poincaré recurrence time (t _P) for an isolated system is highlighted in blue, and the recurrence time of the states of o, t _r, is highlighted in red.

Figure 5

Distribution of recurrence times t _r for the state trajectory of o for Case I CA. From top to bottom are distributions for w _e = 1/2w _o, w _o, 3/2w _o, 2w _o and 5/2w _o, respectively. In all panels the black horizontal line indicates where t _r/t _P = 1 (shown on a log scale). Sampled trajectories displaying UE occur for t _r/t _P > 1.

Figure 6

Distribution of recurrence times t _r for the state trajectory of o for ECA (top left), Case II (top right), and Case III CA (bottom). In all panels the black horizontal line indicates where t _r/t _P = 1 (shown on a log scale). Sampled trajectories displaying UE occur for t _r/t _P > 1.

Figure 7

Relative innovation as a function of recurrence times for Case I (left) and Case II (right) CA. Highlighted in red are cases exhibiting OEE.

Figure 8

Heat maps of compression C (left) and Lyapunov exponent values k (right) for all state trajectories of sampled o for Case I CA. From top to bottom w _o = 3, 4, 5, 6 and 7, with distributions shown for $w_e=\frac{1}{2}{w}_o$, w _o, $\frac{3}{2}{w}_o$, 2w _o and $\frac{5}{2}{w}_o$ (from top to bottom in each panel, respectively) for each w _o. Distributions are normalized to the total size of sampled trajectories for each w _o and w _e (see statistics in Table S3).

Figure 9

Rank ordered frequency distributions of rules implemented in the attractor dynamics of o for all sampled Case I CA (top) and OEE cases only (bottom). Highlighted are Wolfram Class III (light blue) and IV rules (dark blue).