The computational potential of artificial living systems can be studied without knowing the algorithms that govern the behavior of such systems. What is needed is a formal model that neither overestimates nor underestimates their true computational power. Our basic model of a single organism will be the so-called cognitive automaton. It may be any device whose computational power is equivalent to a finite state automaton but which may work under a different scenario than standard automata. In the simplest case such a scenario involves a potentially infinite, unpredictable interaction of the model with an active or passive environment to which the model reacts by learning and adjusting its behaviour or even by purposefully modifying the environment in which it operates. One can also model the evolution of the respective systems caused by their architectural changes. An interesting example is offered by communities of cognitive automata. All the respective computational systems show the emergence of a computational power that is not present at the individual level. In all but trivial cases the resulting systems possess a super-Turing computing power. That is, the respective models cannot be simulated by a standard Turing machine and in prin-ciple they may solve non-computable tasks. The main tool for deriving the results is non-uniform computational complexity theory.
展开▼
