The emergent computational potential of evolving artificial living systems

Abstract

The computational potential of articial living systems can be studied without knowing
\nthe algorithms that govern their behavior. Modeling single organisms by means of so-
\ncalled cognitive transducers, we will estimate the computational power of AL systems by
\nviewing them as conglomerates of such organisms. We describe a scenario in which an
\nartificial living (AL) system is involved in a potentially infinite, unpredictable interaction
\nwith an active or passive environment, to which it can react by learning and adjusting
\nits behaviour. By making use of sequences of cognitive transducers one can also model
\nthe evolution of AL systems caused by `architectural' changes. Among the examples are
\n`communities of agents', i.e. by communities of mobile, interactive cognitive transducers.
\nMost AL systems show the emergence of a computational power that is not present at
\nthe level of the individual organisms. Indeed, in all but trivial cases the resulting systems
\npossess a super-Turing computing power. This means that the systems cannot be simulated
\nby traditional computational models like Turing machines and may in principle solve non-
\ncomputable tasks. The results are derived using non-uniform complexity theory.