Beyond the Turing limit: Evolving interactive systems.

*(English)*Zbl 1052.68045
Pacholski, Leszek (ed.) et al., SOFSEM 2001: Theory and practice of informatics. 28th conference on current trends in theory and practice of informatics, Piešt’any, Slovak Republic, November 24 – December 1, 2001. Proceedings. Berlin: Springer (ISBN 3-540-42912-3). Lect. Notes Comput. Sci. 2234, 90-109 (2001).

Summary: Modern networked computing systems follow scenarios that differ from those modeled by classical Turing machines. For example, their architecture and functionality may change over time as components enter or disappear. Also, as a rule their components interact with each other and with the environment at unpredictable times and in unpredictable manners, 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 systems 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.

We present several models for describing the computational behaviour of evolving interactive systems, in order to characterize their computational power and efficiency. The analysis leads to new models of computation, including ‘interactive’ Turing machines (ITM’s) with advice and new, natural characterizations of non-uniform complexity classes. We will argue that ITM’s with advice can serve as an adequate reference model for capturing the essence of computations by evolving interactive systems, showing that ‘in theory’ the latter are provably more powerful than classical systems.

For the entire collection see [Zbl 0983.00059].

We present several models for describing the computational behaviour of evolving interactive systems, in order to characterize their computational power and efficiency. The analysis leads to new models of computation, including ‘interactive’ Turing machines (ITM’s) with advice and new, natural characterizations of non-uniform complexity classes. We will argue that ITM’s with advice can serve as an adequate reference model for capturing the essence of computations by evolving interactive systems, showing that ‘in theory’ the latter are provably more powerful than classical systems.

For the entire collection see [Zbl 0983.00059].

##### MSC:

68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |

68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |