| |
ISSN 1320-0682 | |||
| Volume 02 | April 1995 | |||
Paola Flocchini and Nicola Santoro
School of Computer Science
Carleton University
Ottawa K1S 5B6, Canada
Email: flocchin@scs.carleton.ca, santoro@scs.carleton.ca
Our results can be interpreted in different contexts. When CAs are used to model physical phenomena where the initial state is corrupted by noise, our results give an understanding of how noise and errors influence the evolution. Interpreting a Boolean value as a "healthy" state of a cell, our results can be interpreted as describing the evolution of a disease in simple organisms represented by CAs.
We study the evolution of a class of cellular automata when their initial state is known with uncertainty. Boolean, one-dimensional CAs with circular configurations are considered, and we assume that some cells are known with uncertainty. In other words, we assume not to have precise knowledge about the global state of the CA; in fact, for a portion of the initial configuration, only an estimate of the actual state is available, in the form of a probability.
Specifically, we study the evolution of CAs, as expressed by their space-time diagrams, where the state of each cell is a value in [0,1], representing the probability of that cell to be in state 1.
By analysing the interaction between knowledge (Boolean values) and uncertainty (probabilities), we observe how and how much the uncertainty influences the knowledge of the whole evolution.
The patterns which emerge in the interaction between knowledge and uncertainty describe the evolution of information. The structure of these patterns, which ranges from simple to complex to chaotic, characterises the inherent dynamics of CAs and describes a nature of the CA which was previously unknown. In particular, some CAs which were considered to have similar dynamics, are now shown to have different evolution of information and, thus, different nature.
This framework can be interpreted in many ways and, thus, the results on the evolution of information provide insights to problems arising in different (but related) contexts.
For example, consider the problem of modelling physical phenomena by CAs where the initial state is corrupted by noise or where some physical conditions are not measurable and only an estimate of them is available. In this case, our results give an understanding of how noise and errors influence the evolution.
Also, interpreting a Boolean value as a "healthy" state of a cell, our results can be interpreted as describing the evolution of a disease in simple organisms represented by CAs.
Chaotic behaviours in CAs has been studied and observed in different contexts [3, 4, 5, 6, 7, 8, 9]. We believe that the complex dynamics observed in the interaction between knowledge and uncertainty is an example of chaotic propagation of information.
Fuzzy cellular automata is a new model of CA which has been introduced in [1, 2]. The definition is given below.
Each cell is associated with a state which is a rational value in [0,1].
The fuzzy CA evolves at discrete steps and, at each step, each cell changes
its state according to a local function h.
The local function of a fuzzy CA
is built starting from the disjunctive normal form
of the boolean CA rule
with a "fuzzification" process [1, 2].
This model has been introduced and studied in order to better understand the dynamics of elementary CAs. In this work, Fuzzy CAs have been used to model the evolution of organisms.
In the following sections, we consider one-dimensional, boolean CAs with circular configurations, in which the initial configuration consists of boolean values everywhere, except that in a small number of cells where the state is represented by the probability of that cell to be in the state 1.
The evolution of these cellular automata with uncertainty can be "approximated" by fuzzy cellular automata, where the probablities correspond to fuzzy values.
In this section, we observe the different behaviours interpreting the CAs as physical systems, part of which is known with uncertainty. Errors and noise are present in the initial configuration.
The evolution can have three different behaviours:
The most interesting situations lie in between these two cases.
As already mentioned, this framework can be interpreted in many ways.
We have seen in the previous section that this kind of CA could model physical phenomena where the initial state is corrupted by noise or where only an estimate of some physical conditions is available. In this case, the study of the interaction between probabilities and boolean values is interesting in that it shows how noise and errors influence the evolution.
In this section, we will interpret a Boolean value as a "healthy" state of a cell; this model could describe the evolution of a disease in simple organisms represented by CAs.
In this light, it is interesting to analyse how the structure of the organism (that is, the evolution of the CA in absence of uncertainty) is modified by the presence of noise (or disease) (that is, the probabilistic values).
In other words, we are interested in analysing the co-evolution of correct (that is, boolean) and perturbed (that is, probabilities) cells within the same organism.
There are six distinct types of co-evolutions, each corresponding to a specific type of the organism (that is, the rules of the CA); these types are grouped into three distinct classes:
Two types of CAs (organisms) belong to Class 1. Their structure is not destroyed during the evolution despite the presence of the initial noise; the noise has a different behaviour in the two situations.
The noise disappears in few steps; the evolution of the organism is not affected by the presence of the disease and its structure does not change. The organism recovers and no sign of disease remains.
The noise is initially introduced randomly; however, during the evolution, it assumes the same structure of the organism. The disease could spread or stay limited; it does not disappear in time and it evolves with the organism - in this situation it is possible to observe the co-evolution of the disease within the organism.
The structure of the CAs (organisms) is preserved only partially.
The disease is localised. During the evolution it does not propagate; it does not disappear. It remains confined and does not influence the rest of the organism. Thus, the structure of the organism is preserved everywhere except in the noisy area.
The organism keeps on evolving; also the disease evolves (without spreading) following a different dynamics.
The structure of the CAs (organisms) changes as a consequence of the evolution of noise. Three types of organisms belong to this class. Their structure is destroyed by different propagations of noise.
The noise propagates, forming complex patterns and it totally destroys the structure of the organism. The structure of the organism is not visible any more.
The disease spreads, affecting all the "healthy" cells; after a finite number of steps, the structure of the organism is destroyed, while the disease evolves showing its own structure. A clear example of this behaviour is shown in Figure 1, where it is possible to observe complex ("chaotic") structures in the evolution of uncertainty.
 |
 |
The organisms of this class show an intermediate behaviour between Type 3.1 (structured destructing modification) and Type 3.3 (structureless modification) - see definition of type below.
They have similar dynamics as Type 3.1 but, here, the structured evolution of noise is limited in a bounded region, and after a finite number of steps the disease propagates homogeneously as for the organisms of Type 3.3. Figure 2 shows an organism modelled by Rule 9.
 |
 |
In this situation, the structure of the organism is destroyed, and the noise propagates homogeneously. The organism dies.
It is interesting to observe that organisms which have a very similar behaviour in "healthy" conditions, react in a totally different way when they are affected by a disease.
Consider the two organisms modelled by CA Rule 90 and CA Rule 18 (also 57 and 184). When "healthy", they evolve showing similar patterns with the typical triangular structures. When their initial condition is partially contaminated by a disease, they have very different dynamics. Organism 90 (also Organism 57) is of Type 3.3 (Structureless Modification), while Organism 18 (also Organism 184) is of Type 3.1 (Structured Destructing Modification). This behaviour reveals a hidden difference between the two organisms - a difference which is not evident when the disease is not present in the organisms.
The same situation can be described in terms of spread of information. In fact, the evolution of CA Rules 90 and 57 with the presence of noise shows propagation of disorder while in CA Rule 18 and 184 there is a clear propagation of information.
The same observation can be made for other rules.
Interpreting the CA as a physical system where each state is a number and corresponds to a non-accurate measure of a condition of the system, we can observe the following:
The Chaotic Evolution of Information in the
Interaction Between Knowledge and Uncertainty
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 pfnspape.
The translation was initiated by Pam Milliken on Tue Nov 12 11:59:37 EST 1996
