SOFSEM 2001 28th Annual Conference on Current Trends in Theory and Practice of Informatics November 24 - December 1, 2001 Piestany, Slovak Republic, Europe

Beyond the Turing Limit: Interactively Evolving Systems

by Jan van Leeuven and Jiri Wiedermann

The computing systems in contemporary information and communication technology follow scenarios that differ from those of classical Turing machines and that are more akin to information processing by living organisms. For example, the architecture and functionality of the systems may change and develop over time as components enter or disappear. Also, as a rule the components interact with each other and with their environment at unpredictable times and in an equally unpredictable manner, and they 'evolve' in ways that are not pre-programmed. Finally, although the life span of the individual components may be finite, the life span of the system as a whole is practically unlimited. The examples range from families of cognitive automata to (models of) the Internet and to communities of intelligent communicating agents. Amorphous and morphogenetic computing systems also fit this emerging paradigm of 'interactively evolving systems'.

We will present several models for describing the computational behaviour of interactively evolving systems, in order to characterize their computational power and efficiency. The analysis leads to new uses of non-uniform complexity theory, including 'interactive' Turing machines with advice and new, natural characterisations of nonuniform complexity classes. Based on the examples and the underlying results, we will argue that 'interactive Turing machines with advice' can serve as an adequate reference model to capture the essence of the computations by interactively evolving systems. It not only shows that 'in theory' these systems are provably more powerful than the standard model, but also gives new motives for nonuniform computational complexity theory.