Predicting Emergence from Cell’s Structure - Systematic Design for Emergence in Cellular Nonlinear Networks - page 116

is what are the probabilities of all cells after one iteration, and how this situation
allows to predict the general behavior of the CA?
Before answering this question let us discuss several preliminary issues. An
uncertainty index will be defined as a basic tool, then an example is given on how

these uncertainties can be computed for a certain cell and a given CA neighbor-

hood. In the end we will see that a probabilistic exponent of growth can be defined
and computed entirely as a function of the bits defining the gene (the binary repre-

sentation of the ID) and of the neighborhood arrangement.

7.4.1 Uncertainty Index of a Cell, Active and Expansion Areas

Let us define an uncertainty index P for a cell k as follows:

P

1
12 (7.3)

p 1,

k k

1

p is the probability of cell k to be in state 1. Note that if all cells are in
an uncertain state then

where

P . The
above uncertainty index is a computationally simpler alternative to the entropic
uncertainty

, while if they are all in certain states then P 1 0

. One can easily verify that both H p log p 1 p log 1 p

k k 2 k k 2 k

functions coincide for , , and . An important property of the

p 0 p 1 / 2 p 1

k k k

uncertainty index is that it is independent on the quiescent status (1 or 0) con-
sidered for the cell k.

In what follows we will call any of these states (common for a group of cells
except those randomly selected in a initial state cluster) a quiescent state. A cell in
a quiescent state has 0 uncertainty.
In the next we will observe the transition of a minimal set of cells (connected
according to the specified cellular automata topology and neighborhood) and will
use tools of information theory to compute the uncertainty profile for all cells

within this set, in the next iteration. The profile of the initial state is chosen such
that it will represent a cluster of n adjacent uncertain cells (i.e.

1 p )
within a larger number N of quiescent cells (being in either “1” or “0” state and
therefore in a certain situation characterized by

P , or 1 1 / 2

P ). Let us denote all cells
which were initially in a certain state as belonging to the expansion area of the
CA while the remaining cells are in the active area of the CA. By simply evaluat-
ing the uncertainty of the cells in the expansion area after one iteration one can
predict if there is a growth or not. If uncertainty stays 0 there is no growth and the
degree of uncertainty obtained in the active area indicates whether the process of
“implosion” is a faster or a slower one. By the contrary if uncertainty is observed
in the expansion area , there is a growth of the initial cluster of uncertain cells and
its magnitude may be quantified as the average of uncertainties over all cells in the
expansion area.

0