  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.
