Self-organizing behavior in parasitic cellular automata
P. Flocchini 
and F. Geurts 
and N. Santoro
Carleton University, School of Computer Science, Ottawa K1S 5B6,
Canada;
Université catholique de Louvain, FSA/INGI, B-1348
Louvain-la-Neuve, Belgium
One-dimensional, Boolean Cellular Automata (CA) are dynamical systems discrete
in space, time, state, and characterized by a local mechanism of
interaction [1].
They have been extensively used to model a
variety of complex natural phenomena and biological systems (e.g. [2]),
are capable of self-organization and replication, and
can exhibit chaotic behavior.
CA can define simple organisms in which, at any time, the state of each cell
is either 0 or 1, and the next state only depends on its current
state and that of its neighbours (according to a predefined local
evolution rule).
An interesting problem is to
investigate the impact that an alteration (mutation, change, noise)
has on the evolution of the organism. In particular, how does
the organism react if a cell is alterated and suddenly assumes a state
different from the ``normal'' (i.e. boolean) states? To answer these
questions, the CA model must be clearly extended so to include
``altered states'' as well as their computation by the local evolution
rule. The needed extension is provided by the continuous version of
CA, called Fuzzy Cellular Automaton (Fuzzy CA), recently
introduced to classify complex behaviors [3],
and to study the dynamics of noise in physical systems [4].
A Fuzzy CA is obtained by ``fuzzification'' of the local evolution rule of
the corresponding CA and is a particular form of Couple Map Lattice [5].
Interpreting a normal state (i.e. in 
) as an healthy
condition, and an altered state (i.e. in (0,1)) as the presence of
disease, the evolution of the Fuzzy CA describes both the
behavior of the disease inside the organism and the reaction of the
organism. Thus, it provides the mechanisms for analyzing the impact of
change on evolution in CA.
An alteration from the healthy state
can affect the evolution of the organism in several different ways.
For example [4]:
the disease could spread quickly affecting
all the healthy cells and destroying the structure of the organism
(Structure Destroying) either in an homogeneous way or
forming complex self-reproducing structures;
it could stay bounded in a small region
(Partially Structure Preserving);
it could disappear leaving the organism totally healthy
(Self-Healing Structure).
In this paper, we study a class of organisms which exibit a similar behavior when a disease is introduced in their state. In this class of organisms, called ``moss'' CA or ``reinforced shifts'' [6], there is a co-evolution of the disease within the organism and the disease exhibits a parasitic behavior. In particular, the co-evolution is symbiotic and the overall evolutionary structure of the organism is preserved. The most interesting characteristic of these organisms is their self-organizing behavior, i.e., their ability to regenerate their evolutionary structure in spite of a total sudden alteration of all cells. Interestingly, the study of the dynamics of the corresponding CA reveals their chaotic nature; in fact, they are chaotic in the classical sense on some subsets of the configuration space and their dynamics can be characterized.