Skip navigation
PDF 258 KB
DOI: http://dx.doi.org/10.7551/978-0-262-33936-0-ch039
Page 200
First published July 1 2016

The Limits of Decidable States on Open-Ended Evolution and Emergence

Santiago Hernndez-Orozco, Francisco Hernndez-Quiroz, and Hector Zenil

Abstract (Excerpt)

Using algorithmic complexity theory methods, we propose a robust computational definitions for open-ended evolution (OEE) and adaptability of computable dynamical systems. With this framework, we show that decidability imposes absolute limits to the growth of complexity on computable dynamical systems up to a logarithm of a logarithmic term. Conversely, systems that exhibit open-ended evolution must be undecidable and have irreducible behaviour through the evolution of the system. Complexity is assessed in terms of three measures: sophistication, coarse sophistication and busy beaver logical depth.