Susan Stepney.
Nonclassical Computation: a dynamical systems perspective.

In Grzegorz Rozenberg, Thomas Bäck, Joost N. Kok, eds. Handbook of Natural Computing, volume 4, chapter 59, pp.1979-2025, Springer, 2012

Introduction

In this chapter we investigate computation from a dynamical systems perspective.

A dynamical system is described in terms of its abstract state space, the system’s current state within its state space, and a rule that determines its motion through its state space. In a classical computational system, that rule is given explicitly by the computer program; in a physical system, that rule is the underlying physical law governing the behaviour of the system. So a dynamical systems approach to computation allows us to take a unified view of computation in classical discrete systems and in systems performing non-classical computation. In particular, it gives a route to a computational interpretation of physical embodied systems exploiting the natural dynamics of their material substrates.

We start with autonomous (closed) dynamical systems: those whose dynamics is not an explicit function of time, in particular, those with no inputs from an external environment. We begin with computationally conventional discrete systems, examining their computational abilities from a dynamical systems perspective. The aim here is both to introduce the necessary dynamical systems concepts, and to demonstrate how classical computation can be viewed from this perspective. We then move on to continuous dynamical systems, such as those inherent in the complex dynamics of matter, and show how these too can be interpreted computationally, and see how the material embodiment can give such computation “for free”, without the need to explicitly implement the dynamics.

We next broaden the outlook to open (non-autonomous) dynamical systems, where the dynamics is a function of time, in the form of inputs from an external environment, and which may be in a closely coupled feedback loop with that environment.

We finally look at constructive, or developmental, dynamical systems, where the structure of the state space is changing during the computation. This includes various growth processes, again investigated from a computational dynamical systems perspective.

These later sections are less developed than for the autonomous cases, as the theory is less mature (or even non-existent); however these are the more interesting computational domains, as they move us into the arena of considering biological and other natural systems as computational, open, developmental, dynamical systems.

@incollection(SS-NCDynSys,
  author = "Susan Stepney",
  title = "Nonclassical Computation: a dynamical systems perspective",
  chapter = 59,
  pages = "1979-2025",
  doi = "10.1007/978-3-540-92910-9_59",
  crossref = "HBNC"  
)

@book(HBNC,
  editor = "Grzegorz Rozenberg and Thomas B{\"a}ck and Joost N. Kok",
  title = "Handbook of Natural Computing, volume 4",
  booktitle = "Handbook of Natural Computing, volume 4",
  publisher = "Springer",
  year = 2012
)