Review | Undecidability and Irreducibility Conditions for Open-Ended Evolution and Emergence

Introduction

Open-ended evolution (OEE)—the capacity of a system to continually produce novel, diverse, and increasingly complex structures or behaviors—remains one of the most elusive phenomena in theoretical biology, artificial life, and complexity science. Despite its centrality in understanding the dynamics of living systems, no universally accepted formal framework has yet captured the mechanisms enabling OEE. At the heart of this difficulty lies a fundamental tension between two modeling paradigms. On one hand, the dominant approach in science has been to define a system via a fixed state space and transition function, assuming all possible behaviors are derivable from an initial set of rules. On the other hand, living systems appear to routinely transgress such limitations, continually generating new “rules” and expanding the very space of what is possible.

This disconnect has led to a conceptual bifurcation. Some theorists argue that the state space of possibilities is simply so vast that evolution merely explores novel but pre-existing regions: newness is revealed, not created. Others contend, more radically, that this view fails to capture the essence of biological novelty: that living systems are capable of generating entirely new dimensions of possibility. From this perspective, life is not just a search within a state space but a process that rewrites its own rules; adding new dimensions, operators, or constraints previously unimaginable. In the spirit of Cantor’s diagonal argument, Gödel’s incompleteness theorems, and Turing’s uncomputable functions, one can argue that any formal system grounded in a fixed symbolic foundation will inevitably fail to capture the capacity for unbounded novelty generation.

In this context, the paper Undecidability and Irreducibility Conditions for Open-Ended Evolution and Emergence by Hernández-Orozco, Hernández-Quiroz, and Zenil offers a compelling and rigorous attempt to reframe this problem. Rather than assuming a fixed state space, the authors explore how undecidability, traditionally a limitation of formal systems, can serve as a necessary precondition for OEE. Through an algorithmic information-theoretic lens, they propose formal criteria under which open-endedness becomes not only definable but formally provable to require undecidability. In doing so, the authors provide a unifying framework that may reconcile the dichotomy between exploration and construction, between revealing and inventing.

Irreducibility and Adaptation in Computable Systems

In the opening sections of the paper, the authors lay the theoretical groundwork by recalling the classic results of Church, Turing, and related thinkers: even for systems with full and finite descriptions, there exist future states that cannot be predicted; chief among them, the infamous halting state. Building on this foundation, they integrate insights from Calude and Jurgensen on complexity-induced undecidability, and from Delvenne et al. on the computability of dynamical systems, to argue that unpredictability is not merely a byproduct of information loss or chaotic sensitivity, but a fundamental feature even in deterministic, well-defined systems.

With these insights, the authors define OEE in computable dynamical systems as the persistent appearance of novel, surprising, and increasingly complex structures over time. This is formalized as follows: given a complexity measure $C$, a system $S(M_0, t)$ exhibits OEE if for every $t$, there exists $t’ > t$ such that $C[S(M_0, t’)] > C[S(M_0, t)]$. Recognizing that complexity may fluctuate, they introduce a stronger condition (strong OEE) requiring that such complexity does not significantly decrease over time, thereby excluding systems that oscillate between trivial and complex states without sustained novelty.

To make these ideas concrete, the authors construct a computational model of adaptation. Here, the organism’s internal structure $M_t$ is computable and paired with a behavior-generating program $p_t$, while the environment $E$ is likewise encoded as a computable structure. A system is said to be adapted if $p_t(M_t) = E$, or more generally, if the conditional Kolmogorov complexity $K(E \mid S(M_0, E, t)) < \epsilon$. This adaptation criterion is robust to the actual content of the representation: it can include behavioral strategies, predictive models, or biochemical responses and reflects the capacity to approximate environmental demands effectively.

Importantly, the authors then prove that time becomes the primary driver of descriptive complexity in evolving computable systems. As time increases, so too does the irreducibility of the future states, a result they term the “time complexity stability theorem.” This implies that the more time elapses, the less likely it becomes that future behaviors can be compressed or predicted by shorter descriptions. From this, they deduce a key result: if a convergent state (i.e., an adapted state) has high descriptive complexity, then no reasonable algorithm—no matter how complete the knowledge of the system and its initial state—can predict when such a state will emerge.

This line of reasoning culminates in a striking conclusion: there exist convergent states (adapted behaviors) whose appearance is formally undecidable. That is, no algorithm can in general identify them in advance even when the system’s rules and initial conditions are fully known. In such systems, adaptation itself becomes a generalization of the halting problem, a profound insight that reframes evolution as not merely a search through a possibility space but as an ongoing construction of uncomputable futures.

Emergence Beyond Prediction: Complexity and OEE

The middle sections of the paper deepen the theoretical analysis by turning to specific measures of complexity designed to distinguish random from meaningful structure. The authors introduce three central tools: sophistication, coarse sophistication, and busy beaver logical depth. Each of these aims to capture the presence of internal structure in a string or state; structure that is neither trivial (highly regular) nor random (incompressible), but computationally deep and informative.

Sophistication, following Koppel, partitions a string’s description into a “model” (a structured program) and a random input. It quantifies the size of the minimal model necessary to generate the string with some allowable slack. Coarse sophistication refines this by penalizing large significance levels, integrating the cost of the model and input together. Bennett’s logical depth, in contrast, measures the computational time needed to generate a string from a near-minimal description: deep objects take a long time to produce, whereas random or regular strings can be generated quickly.

The authors then apply these measures to sequences of adapted states in weakly converging systems. They show that if the adapted times $y_i$ are computable, then for all three measures, the complexity of the corresponding adapted states is bounded, growing at most logarithmically (or even more slowly). This constraint implies that if a system were to exhibit strong OEE (i.e., sustained, significant growth in complexity) then the sequence of adaptation times must be undecidable. Otherwise, the system would be trapped in a low-complexity regime, failing to reach the richness seen in biological evolution.

They further show that this undecidability implies irreducibility of behavioral strategies themselves: if the time sequence $y_i$ is uncomputable, then the mapping from time index to adaptive behavior $p_i$ is also uncomputable. In this way, the behavior of the system over time cannot be compressed into a finite predictive model, even in principle. This is a strong form of emergence, where each new adapted state is causally contingent on but not derivable from its predecessors.

To illustrate these abstract results, the authors revisit a model proposed by Gregory Chaitin, in which evolution seeks to approximate the busy beaver function, a famously uncomputable function that grows faster than any computable function. Chaitin’s model, viewed through this lens, provides an explicit example of a system that exhibits strong OEE with respect to busy beaver logical depth, and whose adaptation dynamics are inherently undecidable. The analogy with biological evolution is especially evocative: just as we cannot generally predict whether a Turing machine will halt, we cannot foresee which organisms will adapt and persist. However, extinction, like non-halting, is always observable after the fact.

This leads the authors to a bold generalization: adaptation, in the full richness of life, is akin to solving a generalized halting problem. Strong OEE, then, is not just hard to achieve; it is undecidable and irreducible by design. Any system capable of it must escape the confines of algorithmic predictability. This is totally consistent with recent work by Prokopenko and Jaeger.

Conclusion

The authors conclude by formalizing the core insight of the paper: that undecidability is not merely a barrier to prediction but a requirement for systems exhibiting strong open-ended evolution. Any computable system that generates sustained, unbounded complexity—measured via sophistication, coarse sophistication, or busy beaver logical depth—must do so through undecidable processes. Otherwise, its future behaviors remain confined to a predictable, compressible, and ultimately limited subset of possibilities.

This reconceptualization has significant implications. It suggests that most artificial life systems and simulations, which rely on computable rules and finite state spaces, are inherently incapable of strong OEE. At best, they approximate novelty within a predefined horizon. This reminds us of Pattee’s lesson: rule-based self-organization models can only yield limited novelty. Truly open-ended systems, in contrast, must embody undecidable dynamics: they cannot be fully modeled, simulated, or compressed. This aligns with the intuition that life does not just explore a state space, but it builds new state spaces.

Still, some limitations and open questions remain. The authors’ definition of OEE leans on a complexity-increasing dynamic suggestive of relentless organismal sophistication. Yet, biological evolution does not always favor increasing complexity. Organisms may simplify, specialize, or enter long periods of stasis. Adaptation is not synonymous with complexity growth. While the authors do acknowledge this in part, a fuller theory would need to distinguish functional adaptation from structural complexity more clearly.

Moreover, although the authors hint at the possibility of generalizing their results to other complexity measures that assign low values to randomness, they do not yet prove such generality. The case of Bennett’s original logical depth is acknowledged as open, tied to deep problems in computational complexity such as P vs PSPACE. These gaps do not detract from the central insight but do point to fertile directions for future work.

In sum, this paper represents a profound and rigorous contribution to the conception of open-ended evolution. It reframes undecidability not as an obstacle but as a necessary feature of systems capable of genuine novelty and emergence. By doing so, it opens a path forward for understanding life; not as a fixed algorithm, but as an irreducible, ever-unfolding computation.