Chaotic dynamical systems have received a great deal of attention in recent years. Many efforts have been done in determining which properties a dynamical system must obey to be considered chaotic (see for instance [2,2,3,6]). In spite of this, no universally accepted definition of chaos does exist. This is due to at least two different kinds of reasons:

- dynamical systems are studied in different fields so that the word
*chaos*assumes different meanings, - in certain fields, the theory of chaos is not yet completely developed.

*Mathematics. *

A dynamical system *(X,f)* consists of a space of
configurations X and a map *f, f:X -> X*. A dynamical system *(X,f)* is chaotic if *f* satisfies some topological properties. The set of properties *f* must satisfy to
be chaotic is not uniquely defined. Transitivity is a widely accepted feature of chaos. We say that *f* is transitive if for all non empty open subsets *U andV ofX* there exists a natural number *n* such that *the intersection of f^n(U) and V is not empty*. Another feature of chaos is the denseness of the periodic orbits. We say that *(X,f)* has dense periodic orbits if the set of the periodic points of *f* is a dense subset of *X*. Another way for detecting the chaoticity of a system *(X,f)* is to show that it is topologically conjugate to another system *(Y,g)* which has already been proved chaotic (see for instance [2]).

*Physics.*

The notion of chaos captures the concept of non-measurability. A
dynamical system *(X,f)* is chaotic if small errors in experimental readings lead to large scale divergence, i.e., if the systems is very *sensitive*. More formally, let *d* be a distance on *X*. *(X,f)* is chaotic if there exists *delta>0* such that for any
*s an element of X* and for
any neighborhood *N(s)* of *s*, there is a point *y an element of N(s) * and a natural
number *n*, such
that *d( f^n (s) , f^n(y) ) > delta*. Delta is called sensitivity constant.
Another feature of chaos is captured by expansiveness [2]. *(X,f)* is expansive if
there exists *delta > 0* such that for any *s ,y elements of X*, *s not equal to y*, *d(x,y)< delta*, there is a natural
number *n*, such that
*d(f^n(s),f^n(y))>delta*.$ Note that expansiveness is stronger than sensitivity.
*Computer Science.*

This area deals with computations in a resource bounded environment (e.g., the digital computer).
In particular, computational complexity studies the amount of resources needed for computing a given function *f*. In this framework, a process *P= [ s, f(s), ..., f^n(s), ... ]* can be seen as a repeated
application of *f* on a certain input *s*. In the presence of infinite
resources, *P* is a deterministic process. This is not true, in general, when *P* has to be
computed with finite resources. A *sensitive* process is such that *f(x)* might be very
different from *f(s')* although *s* is very close to *s'*. Thus, if we are not
able to appreciate the difference between *s* and *s'*, *P* becomes in
practice a *non deterministic* process. It follows that the notion of chaos
in computer science captures the idea of a process which lies between determinism
and nondeterminism.

Let us consider a particular type of dynamical system: the cellular automaton (CA). CA are dynamical systems in which an infinite lattice of finite state machines updates itself in parallel according to the same local rule. CA were introduced by Von Neumann [5] for modelling self-reproducing systems such as biological systems. The dynamics of CA are based on the facts that in physical systems information travels a finite distance in a finite time, and that the laws of physics are independent of the position of the observer. Moreover, Von Neumann made some other simplifying assumptions: discrete time and space, and a regular grid topology. The above mentioned definitions of chaos are interrelated. We can state the following claims.

- Mathematical chaos implies physical chaos, i.e., a dynamical system which is
transitive and has dense periodic orbits, is sensitive to initial conditions
[1].
In particular, for CA, this claim holds even for
*weaker*definitions of mathematical chaos, e.g., transitivity alone implies sensitivity [4]. - Mathematical chaos implies
*low complexity*. A dynamical system which is chaotic according to the mathematical notion of chaos is not a universal model of computation, in fact, it cannot simulate step by step a universal Turing machine. - A CA which is chaotic according to the mathematical
definition of chaos keeps the
*information content*of the input string. - In order to be a universal computing machine, a CA needs to be
*moderately*sensitive to initial conditions.

PHYSICAL CHAOS ************** ORDERED COMPLEX MATH. SYSTEMS SYSTEMS CHAOS ------------------------------------------------> Information complexity

In the picture, we display dynamical systems according to increasing *Information
complexity* (IC). Information complexity measures the ability of a dynamical
system
in keeping the information content of the input configuration, e.g., its *randomness*
or, equivalently, its *entropy*.
On the left side of the
picture we have ordered systems. They exibhit a trivial non
chaotic behaviour. On the right side of the picture we have systems which are
chaotic from the
physical point of view. For these systems, a small error in the input
configuration leads, after few
iterations, to an output configuration which might be very different from the
exact one. They include
both complex systems and mathematically chaotic systems.
Note that the
mathematical definition of chaos is stronger than the physical definition. A
classical example
of dynamical system with high topological complexity is the full shift map.
Complex dynamical
systems have an intermediate IC. These systems include *universal
machines*, i.e., machines capable of simulating any other machine (for example,
Turing
machines). One can show that a CA with maximum IC is not
universal.

**References:**