The Evolution of Complexity - Abstracts.

Chaos in Mathematics, Physics, and Computer Science: Similarities and Dissimilarities.

By B. Codenotti
  • Via S. Maria 46
  • 56100-Pisa (Italy).
  • E-mail:
  • and Luciano Margara
  • Department of Computer Science
  • University of Pisa
  • Corso Italia 40
  • 56100-Pisa (Italy).
  • E-mail:
  • Abstract:

    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:

    1. dynamical systems are studied in different fields so that the word chaos assumes different meanings,
    2. in certain fields, the theory of chaos is not yet completely developed.
    In this work we consider three different environments in which the notion of chaos arises, e.g., mathematics, physics, and computer science, and discuss similarities and dissimilarities in the corresponding definitions.


    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]).


    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.

    1. 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].
    2. 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.
    3. A CA which is chaotic according to the mathematical definition of chaos keeps the information content of the input string.
    4. In order to be a universal computing machine, a CA needs to be moderately sensitive to initial conditions.
    We conclude by proposing the following structural interpretation.

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

    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.


  • [1] J. Banks, J. Brooks, G. Cairns, G. Davis, and P. Stacey, On the Devaney's Definition of Chaos, Amer. Math. Monthly, 332-334, 1992.
  • [2] R. L. Devaney, An Introduction to Chaotic Dynamical Systems. Addison Wesley,1989.
  • [3] P. Favati, G. Lotti, and L. Margara, Additive Monodimensional Cellular Automata are Chaotic According to the Devaney's Definition of Chaos. Submitted for Publication, 1994.
  • [4] L. Margara, For Cellular Automata, Transitivity Implies Sensitivity. Submitted for Publication,1995.
  • [5] J. Von Neumann, Theory of Self-Reproducing Automata. ed. A. W. Burks, Univ. of Illinois Press, Champaign,1966.
  • [6] S. Wiggins, Global Bifurcations and Chaos. Springer-Verlag, New York, 1988.