Information Technology Reference
In-Depth Information
probability 1 of being in either 0 or 1 state (quiescent state) and after one iteration
the following may happen:
(a) The total number of cells in uncertain state (probability is ½) grows -
this situation correspond to a growing or “explosion” process (
U >
1).
(b) The total number of cells in an uncertain state (probability is ½) de-
creases - this situation correspond to an “implosion” process (
U<
1).
(c) There is a delicate balance between growing and implosion such that
almost the same number of cells maintain an uncertain probability dur-
ing the time evolution of the CA.
Here we intentionally describe the growing or imploding processes based on
probabilities. In terms of probabilities each cell can be considered a nonlinear
system with
n
inputs and one output. The cells output probability
po
for being in a
certain state (1 or 0) can be computed as a nonlinear function
FP
of the probabi-
lities for each input of being in a given state (e.g. 1 or 0):
(7.2)
po
1
PIDpp n
,1, 2 .
1
1
1
,
where
p
denotes a probability of being in state “1”. In the following we will call
FP
the
cells function of probability
. One can easily calculate the probability of be-
ing in state “0” as
The theory of random variables ensures that a
nonlinear function
FP
is uniquely defined by the cells ID and therefore it can be
computed using a deterministic algorithm
1
. This is the basis of the method ex-
posed next to calculate a complexity measure similar to
U
but solely based on
knowing the
FP
associated with a given cell ID. The neighborhood connectivity is
considered in the definition of a probability profile among all cells in the
neighborhood as exemplified nest for the case of one-dimensional CA, while a
global measure of emergence is in a direct relationship with the probability pro-
file.
Let us assume that a group of
n
adjacent cells in a CA are initially in an uncertain
state (with such a cell being characterized by
0
1.
p
p
1
0
pp
. The remaining cells
are either in “1” or “0” state. We might consider all four possibilities: (1) all re-
maining cells are in “1”; (2) all remaining cells are in “0”; (3) the cells to the left
of the initial cluster are in “0” and the cells to the right in “1”; (4) the opposite of
(3). For semi-totalistic cells (i.e. symmetric) (4) and (3) are the same. The question
1
Our algorithm is based on the piecewise-linear representation of any type of cell, as
indicated in Chap. 3. Once the probability density of certain input variables are known,
the probability density of their sum can be easily computed. Since that sum is the entry
“j” in a look-up table defining the cell, it gives the probability that cells' output is
y
, i.e.
one of the bits defining the ID. The probability
po
is thus defined as the weighted sum
¦
0
N
1
po
y
j
p
.
j
j
0
Search WWH ::
Custom Search