The emergent computational potential of evolving artificial living systems

Article type: Research Article

Authors: Wiedermann, Jiří | van Leeuwen, Jan

Affiliations: Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod Vodárenskou věží 2, 182 07 Prague 8, Czech Republic E‐mail: [email protected] | Information and Computing Sciences, Utrecht University, Padualaan 14, 3584 CH Utrecht, The Netherlands E‐mail: [email protected]

Abstract: The information processing capabilities of artificial living (AL) systems are far more powerful than commonly believed. Modelling single organisms by means of so‐called cognitive transducers, we estimate the computational power of AL systems by viewing them as conglomerates of organisms. We describe a scenario in which an AL system is engaged in a potentially unbounded, unpredictable interaction with an environment, to which it can react by learning and adjusting its behaviour. By means of lineages of cognitive transducers we also model the evolution of AL systems. Among the examples are “communities of agents”, i.e., communities of mobile, interactive cognitive transducers. Most AL systems show the emergence of a computational power that is not present at the level of the individual organisms. Indeed, in all but trivial cases the resulting systems possess a super‐Turing computing power. This means that the systems cannot be simulated by traditional computational models like Turing machines and may in principle solve non‐computable tasks. The results derive from recent results from the theory of interactive evolutionary computing systems in terms of AL systems.

Keywords: Artificial living systems, cognitive transducers, super‐Turing computational power, Turing machines with advice, interactive evolutionary computing systems

Journal: AI Communications, vol. 15, no. 4, pp. 205-215, 2002