Collapsing a coevolutionary process into a computable function.

It is shown how the entire dynamics of a class of evolutionary systems can be used to perform a computation. The argument is constructive by presenting a Turing-machine-based set-up implemented in Enact, an artificial-life world embedded in a family of cellular automata; in this system, a population of agents move about in a two-dimensional space, interacting with their environment, reproducing and undergoing developmental and coevolutionary processes. As a byproduct, the paper also serves to characterise the main model of computation underlying Enact. This model is essentially parallel, and relies upon the machinery defined by the artificial-life processes. According to the model, a particular computation is considered to have been performed, if and only if, for some initial population and environmental configuration, at least one agent has developed into a state configuration that is insensitive to any further environmental interactions; in this situation, if the computation involved is a function, this individual has the result. If the population ever vanishes, or if the environment becomes short of the resources needed for development, the cellular space has to be re-initialized, and the process iterated. The presentation relies on the implementation of a function that recognises a particular context-free language. Implications of the model of computation are then discussed, in particular the model of coupled computations suggested by it.