Is undecidability a requirement for open-ended evolution (OEE)? Using  algorithmic complexity theory methods , we propose robust computational definitions for open-ended evolution and  adaptability of computable dynamical systems. Within this framework, we show that decidability imposes absolute limits to the  growth of complexity on computable dynamical systems up to a double logarithmic term . Conversely, systems that exhibit (strong) open-ended evolution must be undecidable, establishing undecidability as a requirement for such systems. Complexity is assessed in terms of three measures: sophistication, coarse sophistication and busy beaver logical depth. These three complexity measures assign low complexity values to random (incompressible) objects. We conjecture that, for similar complexity measures that assign low complexity values, decidability imposes comparable limits to the stable growth of complexity and such behaviour is necessary for non-trivial evolutionary systems. We show that  undecidability of adapted states imposes novel and unpredictable behaviour on the individuals or population being modelled. Such behaviour is irreducible. Finally, we offer an example of a system, first proposed by Chaitin, that exhibits strong OEE.
Is undecidability a requirement for open-ended evolution (OEE)? Using methods derived from algorithmic complexity theory , we propose robust computational definitions of open-ended evolution and the adaptability of computable dynamical systems. Within this framework, we show that decidability imposes absolute limits to the stable growth of complexity in computable dynamical systems . Conversely, systems that exhibit (strong) open-ended evolution must be undecidable, establishing undecidability as a requirement for such systems. Complexity is assessed in terms of three measures: sophistication, coarse sophistication and busy beaver logical depth. These three complexity measures assign low complexity values to random (incompressible) objects. As time grows, the stated complexity measures allow for the existence of complex states during the evolution of a computable dynamical system. We show, however, that finding these states involves undecidable computations. We conjecture that for similar complexity measures that assign low complexity values, decidability imposes comparable limits to the stable growth of complexity , and that such behaviour is necessary for non-trivial evolutionary systems. We show that the undecidability of adapted states imposes novel and unpredictable behaviour on the individuals or populations being modelled. Such behaviour is irreducible. Finally, we offer an example of a system, first proposed by Chaitin, that exhibits strong OEE.
A
methods derived from
D
methods
R
for
of
A
the
A
stable
R
on
in
D
up to a double logarithmic term
R
We conjecture that,
As time grows, the stated complexity measures allow for the existence of complex states during the evolution of a computable dynamical system. We show, however, that finding these states involves undecidable computations. We conjecture that
R
and
, and that
A
the
R
population
populations