The Evolution of Complexity - Abstracts. The Evolution of Complexity - Abstracts. 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:
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.
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: