Computational Complexity of Observing Evolution in Artificial-Life Forms
This addresses the challenge of precise observation in heterogeneous AES models for researchers in artificial life and complex systems, though it appears incremental as it builds on an existing algebraic framework.
The paper tackles the problem of characterizing the computational complexity of automatically detecting life-like evolutionary behavior in artificial-evolutionary systems (AES), estimating worst-case bounds for identifying reproduction in Langton's Cellular Automata model.
Observations are an essential component of the simulation based studies on artificial-evolutionary systems (AES) by which entities are identified and their behavior is observed to uncover higher-level "emergent" phenomena. Because of the heterogeneity of AES models and implicit nature of observations, precise characterization of the observation process, independent of the underlying micro-level reaction semantics of the model, is a difficult problem. Building upon the multiset based algebraic framework to characterize state-space trajectory of AES model simulations, we estimate bounds on computational resource requirements of the process of automatically discovering life-like evolutionary behavior in AES models during simulations. For illustration, we consider the case of Langton's Cellular Automata model and characterize the worst case computational complexity bounds for identifying entity and population level reproduction.