| |
ISSN 1320-0682 | ||
| Complexity International is a
refereed journal for scientific papers dealing with any area of complex
systems research. |
Paola Flocchini
School of Computer Science
Carleton University
Ottawa K1S 5B6, Canada
Email:flocchin@scs.carleton.ca
Frédéric Geurts
Départment d'Ingénierie Informatique
Université Catholique de Louvain
Place Sainte Barbe 2
B1348 Louvain-la-Neuve, Belgium
Email: gf@info.ucl.ac.be
Among all discrete-time discrete-space multi-dimensional systems, cellular automata (CA) are very interesting to study because they offer a rich variety of behaviours that allow modelling of specific physical systems, as well as universal computational devices.
In the theory of CA, classification of behaviours is a central theme. The goal is to impose a structure in the space of CA rules, grouping together CA related to equivalent properties. Many different behaviours are possible, from very simple (destruction of information) to very complex (propagation of information following complex rules). In general, simple behaviours are easy to understand and to characterise a priori, which is not the case when analysing complex behaviours. Different tools have been introduced, leading to different classification schemes.
The main problem appearing in (almost) every classification scheme is the qualitative definition; several classes are not formally defined. Thus, there is an ambiguity inside each classification.
The goal of this paper is twofold: to propose a new classification of CA, formally and precisely defined, and to investigate the class of complex behaviours (particularly "aperiodic" behaviours).
We propose new tools, transfinite attraction and shifted Hamming distance, that define a new classification of CA in which every class is formally defined. We also analyse three different ways of grouping these classes, which brings new insights in understanding chaotic behaviours. Finally, we present related works and draw some conclusions.
Let us consider a space E. Classically, an iteration scheme is
defined as follows. Starting from an initial value
,
It can be shown that strong conditions on function (or relation) f are to be assumed to prove convergence theorems in this classical framework. However, if we relax the hypothesis of finite (and their limit, infinite) iterations, then it is possible to get more general results. The relations involved only need to be monotonic. Therefore, we need to introduce transfinite iterations.
The class of ordinal numbers (denoted
) is well ordered by
the classical 
. The expression
is
used to denote the upper bound of the ordinals family
. A limit ordinal
is such that
. A successor ordinal
is such that
, where the predecessor of
is denoted by
.
Let us assume that
is a
complete lattice, with ordering relation
, infimum
, supremum E, least upper bound operator
, and
greatest lower bound
. With the same notations,
denotes
the smallest ordinal number such that
.
Let us take a relation
, and a
predicate (or set of states) P included in its domain. We define the
pre-image of P,
, as the set of states from which a state in P
can be reached by an application of f, and the post-image of P,
, as the set of states which can be reached from a state in P by
an application of f [2, 3].
These operators are called predicate transformers and can be seen as inverse (resp. direct) extensions of relations from point-to-point to set-to-set.
It is easy to see that we have
,
, and monotonicity of these predicate transformers; that is,
Finally, let us recall the definition of cellular automata. We consider one-dimensional cellular automata, the cells of which are arranged on a linear bi-infinite lattice.
A configuration of a CA is a function that specifies a state for each
cell
and can be represented by a doubly infinite sequence
.
Thus, the set of the configurations of the CA is
.
The neighbourhood of a cell
is the vector
The global transition function of the CA,
,
specifies the next state of each cell as the local function applied to
the states of the neighbourhood
:
In the following sections, we will only use elementary cellular automata;
that is, with r=1 and k=2. We will also use
instead of
to denote the configuration space.
We now extend Definition 2 and split it into three forms
using Theorem 3. Working in a space or
set E, we consider the set of its subsets, namely
. As
is well known, this set is a complete lattice. We denote it as above:
.
Classically, one says that a state x is attracted by p under
iteration of f iff
.
We can extend this definition as follows.
A set P is asymptotically attracted by a set Q iff
. In general, we consider the
smallest such Q.
We can also give a finite version of this notion.
P is finitely
attracted by Q iff
.
The previous definitions are not new but we can extend them in a third
way, using transfinite iterations.
In general, the symbol
used in the previous definitions is
equivalent to the first transfinite ordinal
. We extend the
notion to all ordinal numbers (finite,
, and all other
transfinite ones) to simplify further developments.
To find the global attractor of configuration space
,
we have to compute, for a certain ordinal number
, the
negative invariant of the system [2,
3]:
This expression is computable by successive approximations, and leads
to the attractor, thanks to monotonicity of
.
Let us try to justify transfinite iterations intuitively. We consider
a single deterministic automaton with a finite number of possible
states. We let the system iterate and we examine the orbits generated
from different initial states. If we only take a smaller orbit than
the total number of states, different behaviours are observable:
fixed-point attraction, periodicity, and seemingly random orbits.
Otherwise, since the system is deterministic, random orbits vanish.
Everything becomes eventually fixed or periodic. We consider now
larger and larger state spaces, until we reach some kind of infinity.
For example, we take a state space of positive integers
of
cardinality 
, the first transfinite cardinal, also equal to
. The same behaviours appear and we have to allow more than
iterations to see only periodic behaviours.
We introduce here a notion of distance that is very close to the very
well known "Hamming distance". We work with a finite alphabet
isomorphic to
. On
this alphabet we define a distance
For two strings of symbols
, the Hamming distance
between a and b, H(a,b) is defined as the number of places (or
indices) where a and b differ:
For two bi-infinite sequences a and b of symbols,
Let us now introduce the new notion.
Our motivation to classify the different behaviours with respect to transfinite attraction is to provide a formal definition of behaviours with a technical tool intuitively close to our observation.
Analytic studies and simulation reveal three kinds of observable
behaviours: finitely regular (null, fixed-point or periodic rules),
completely irregular (our type
), and "chaotic" behaviours
(subshift rules).
Let us discuss the third class. These rules are chaotic
in the sense of Devaney's definition [5]. However, when we observe
their long term behaviour, what we see is a beautiful regularity. The
problem is a bit technical; the proof is based on a metric assigning a
weighting to the cells of the cellular automaton, which strongly
influences the consideration made, whereas we don't have this
weighting in mind when we observe the successive configurations
generated. Thus, we have to find a technical aspect closer to our own
observation. It is proposed to use attraction as
technical tool but, since we work with doubly infinite lattices of
cells, we need to consider transfinite iterations and attraction.
Let us
consider bi-infinite configurations in zero backgrounds. We study
the successive iterations of each system f over a certain amount of
time (finite, infinite, or transfinite),
, from two kinds
of initial conditions: random configurations
( 
), or the
whole configuration space
(
).
Let us now examine the different classes
separately.
cellular automata
cellular automata
cellular automata
cellular automata
cellular automata
cellular automata
These cellular automata evolve quickly to homogeneous
configurations. Any configuration is finitely attracted to the
same configuration, homogeneously composed of quiescent cell states;
that is, without information.
The homogeneous state is a function of the rule itself:
More globally, we have
This class is called
because another version is possible, with
several possible quiescent configurations:
More globally, we have
We call this subclass
.
cellular automata
These cellular automata evolve to fixed configurations
after finite transients.
This class contains the first one as a particular
case. The final fixed configuration is, in general,
dependent on the initial one. We have here finite attraction too:
More globally, we have
For the sake of simplicity, we will include
in
and keep
equal to
.
cellular automata
These cellular automata
evolve to cycles of configurations after finite transients.
This class contains the two previous ones.
The limit cycle is dependent
on the initial condition. We have finite attraction to a set of
points rather than to a single fixed-point:
More globally, we have
cellular automataThese cellular automata behave like generalised alternating subshifts. Here is a definition of this behaviour, generalising [4].
It is possible to prove that this kind of behaviour leads to chaos in the sense of Devaney (topological transitivity, density of periodic points) [5, 6].
When observing a
specific cellular automaton starting from a random initial
configuration, what we see is the initial configuration progressively
shifting to the right or to the left, together with a kind of periodic
behaviour. If we take an initial finite configuration in a zero
background, for example, we will see our configuration escaping the
finite observation domain, unless this domain can indefinitely grow.
If we iterate more times than the total amount of
cells composing the CA, even if this lattice
possesses a bi-infinite number of cells, then, starting from any
initial configuration, we observe an attraction to a homogeneous
configuration, exactly as type
cellular automata behave. From this
point of view, the behaviour of type
cellular automaton becomes
more regular than chaotic, if we accept transfinite iterations:
or, more generally,
where H is a cycle of homogeneous configurations.
It is also possible to write
Here, we see a difference regarding the use of finite/transfinite iterations. Finite iterations lead to a typical shift behaviour which can be seen as chaotic (classical definition). Transfinite iterations show a simple behaviour of attraction to homogeneous configurations.
cellular automataThese cellular automata have an aperiodic behaviour which is responsible for the observable (spatio-temporal) chaos. This is the same class as type "c" of [7]. We prefer calling it "aperiodic" because it is not really chaotic in the sense of Devaney's definition. Actually, there does not exist any analytical definition for these phenomena. Aperiodicity seems to be the least restrictive definition for the moment: a configuration is aperiodic if it is not eventually periodic (neither periodic nor one of its forward iterations). Phenomenologically, we observe patterns growing, vanishing, and moving towards space-time. There is a kind of regularity (these forms are far from noise) but also a diversity (different forms). There is no stabilisation as such, but there is no real disorder. We remark that aperiodicity entails that almost the whole domain is visited through successive iterations.
Back to attraction, we have here an "attraction" to a huge cycle
containing (almost) the whole configuration space:
where the symbol "
" means "dense subset of" but is still to be made more formally precise.
It is important because it makes the
difference with type
cellular automata.
It is also possible to write
Here, also, we have a difference between finite and transfinite iterations. Finite iterations show irregular behaviours, spatio-temporal chaotic patterns, aperiodic evolutions. The problem is that it is difficult to give an explicit characterisation of this kind of behaviour. On the other hand, transfinite iterations allow us to give a very simple definition, saying that the system involved is periodic with a huge period very close to the cardinality of the configuration space itself.
Though we have the following inclusions:
it is difficult to compare the first classes with type
and type
.
However, if we try to see all classes with respect to transfinite
iterations, we can see a hierarchy of periodic systems. From type
to type the period grows from one to an ordinal "close" to the
cardinality of our configuration space, and the resulting attractor
grows from a homogeneous fixed configuration to almost the whole
configuration space.
Hence, we have a linear hierarchy,
where we voluntarily do not give a precise definition to "
":
.
In this second organisation, we introduce two criteria - (in)dependence to initial conditions, and (trans)finite iterations, allowing us to build a classification table of our different sources of behaviours:
With the help of the tool previously introduced, we can classify our different behaviours in a very simple way. Thanks to shifted Hamming distance we are able to show that subshifts behaviours are simple.
If the system is n-periodic or if it has a generalised subshift
behaviour including a n-periodicity, they both appear very simple
through the eye of our shifted Hamming distance. For any x in the
orbit of an initial configuration, after some possible transient,
The opposite behaviour is aperiodicity. This gives us a new
characterisation. There is no x in the configuration space
for which the previous condition applies and, thus, for all states
x, and all n, we have
We summarise this last organisation as follows:
Under "center-first" metrics, subshifts can be considered as chaotic (Devaney's definition [5]). Under SHD, subshifts are very simple, just as periodic behaviours.
In this section we would like to cite some other works and compare them with our approach. Two themes are important: classification and aperiodicity.
Classification. This is one of the central themes in the theory of CA. A structure is imposed on the space of CA, grouping together CA with related properties. Several authors have proposed different classifications, starting with Wolfram in 1983 [8].
Two problems appear when classification is studied: (1) it is difficult to give a formal definition of each class of CA (in particular, spatio-temporal chaos is not precisely defined in this context), (2) these definitions are often based on undecidable properties.
Our classification is strongly influenced by [7]. We present new tools allowing us to give a precise formal definition of each class. These tools can be related to the characterisation appearing in [9]. Our classification is not decidable for all CA rules but only for simple basic ones. We are trying to extend these results to more complex rules, with the help of composition operators [10].
Aperiodicity. The notion of "chaos" is still not well defined in the context of discrete-time discrete-space multi-dimensional dynamical systems such as, for example, cellular automata. Several authors propose ways of defining complex behaviours in CA. This is one of the goals of classification.
In [11], the author presents a classification of chaotic behaviours, based on notions of randomness, complexity measures, computability of initial conditions and (non)determinism of rules.
Finally, in [12], the author studies aperiodicity of some CA analytically. We take this point of view in our classification scheme because it is easier to define than complex or chaotic rules. However, we do not make use of linearity and injectivity notions presented by Jen. This point of view is interesting because aperiodicity includes complex and chaotic behaviours, in some sense.
Our goal was to find a classification of elementary cellular automata in which each class is defined by a mathematical expression. In particular, we wanted to characterise the most "chaotic" classes.
We have refined a given classification and added new tools to go deeper; namely, predicate transformers, transfinite attraction and shifted Hamming distance. With these tools we gave an explicit characterisation of each class and saw that spatio-temporal or aperiodic systems are, in fact, periodic systems with huge periods.
In a future work, we will use this explicit definition of CA classes to find equivalent classes of more general dynamical systems. In parallel, we will also investigate different composition operators and analyse how they behave in this framework, regarding properties of invariance, attraction, etc.
This paper has been partially supported by grant 94.00452.CT12, C.N.R. (Italy), and by the National Funds for Scientific Research (Belgium). We wish to thank Carla Quaranta Vogliotti and Petr Kurka for their valuable comments.
Searching for Chaos in Cellular Automata: New Tools for Classification
This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html pfgfattr2.
The translation was initiated by Pam Milliken on Tue Nov 19 15:00:34 EST 1996
