Information Technology Reference
In-Depth Information
po
1
p
1
p
1
p
y
1
p
1
p
p
y
..
p
p
p
y
3
2
1
0
3
2
1
1
3
2
1
7
p pp y
y
y
y
y
y
y
y
pp y
y
y
y
(7.13)
3
2
1
7
6
5
4
3
2
1
0
3
2
6
4
2
0
ppyy yy ppyy yy py y
py y
3
1
5
4
1
0
2
1
3
2
1
0
3
4
0
py y
y
.
22
0
11
0
0
The above clearly indicates that
FP
is a nonlinear function in the input prob-
abilities, of a polynomial structure, while the coefficients of the polynomial are
solely determined by the bits defining the ID of the cell.
Similar formulae may be deduced for any possible Boolean cell, including the
semitotalistic cells with five inputs used in either “1s5” or “2s5” CAs. Assuming
input probabilities
pp
with
p
indicating the probability that the cen-
tral input is 1, the resulting formulae for the output probability is:
,
,
p
,
p
,
p
1
2
3
4
5
>
@
po
S
1
p
y
4
y
6
y
4
y
y
p
y
4
y
6
y
4
y
y
1
3
0
1
2
3
4
3
5
6
7
8
9
>
@
S
1
p
y
3
y
3
y
y
p
y
3
y
3
y
y
2
3
0
1
2
3
3
5
6
7
8
>
@
(7.14)
S
1
p
y
2
y
y
p
y
2
y
y
3
3
0
1
2
3
5
6
7
>
@
S
1
p
y
y
p
y
y
4
3
0
1
3
5
6
1
p
y
p
y
3
0
3
5
where
,
,
S
p
p
p
p
S
p
p
p
p
p
p
p
p
p
p
p
p
1
1
2
4
5
2
1
2
5
1
2
4
2
4
5
1
4
5
, and
S
p
p
p
p
p
p
p
p
p
p
p
p
S
p
p
p
p
3
1
2
1
4
1
5
2
4
2
5
4
5
4
1
2
4
5
Note again the polynomial nonlinear structure of
FP
, with coefficients calcu-
lates as linear combinations of the ID bits.
7.4.4 Computing the Probabilistic Exponent of Growth
Before giving explicit formulae for computing the effective exponents of growth
in both one-dimensional (1s5) and two-dimensional (2s5) cases, we must consider
four distinct cases in relationship with the transformations of the quiescent states
(the certain states that might be “0” or “1”). These cases are induced by the way a
CA-cell with a given ID is transforming an input with all cells in a quiescent state.
It may be easily checked that using our previous notations, only the MSB (most
significant bit) and the LSB (least significant bit) of the binary representation of
the cells' ID determine any of the four particular cases. For the sake of simplicity
in the next we will consider an initial state profile with “0” quiescent states:
(a)
Case 1:
(MSB = 0, LSB = 0). In this case, the stable quiescent state is
always “0”.
The following formulae will be used to compute the uncertainty index
ue
as an
average over all cells within the expansion area:
The one-dimensional case
(four cells in the expansion area, see Fig. 7.5.):
Search WWH ::
Custom Search