Information Technology Reference
In-Depth Information
Here the terms
upper
,
right
etc. on the rectangular array are interpreted in a
usual way, shown in Fig. 2, although the array is rotated by 45
◦
in the counter-
clockwise direction. Rules (8) and (9) correspond to the case where
m
=1,
n ≥
2 and
m ≥
2,
n
= 1, respectively. When
a
=
w
, that is,
δ
1
(
w, b, c
)=
d
,
where
b, c, d ∈{Q−{w}}
, then
N
has three rules, as shown in Type (II). These
rules are used by the cell located in the upper left corner. Rules (2) and (3) in
Type (II) are special cases corresponding to rules (8) and (9) in Type (I). When
c
=
w
, that is,
δ
1
(
a, b, w
)=
d
, where
a, b, d ∈{Q−{w}}
, then
N
has three rules,
as shown in Type (III). These rules are used by the cell located in the lower right
corner. Rules (2) and (3) in Type (III) are special cases corresponding to rules
(8) and (9) in Type (I).
Now let
M
have
m
+
n −
1 cells. Here we show that the construction of 2-D
CA
N
can generate the configuration of
M
in real-time. Specifically, for any
i
,
1
≤ i ≤ m
+
n −
1, the state of any cell in
g
i
at any step is the same and is
identical to the state of
C
i
at the corresponding step. Let
S
i
,
S
i,j
and
S
g
i
denote
the state of
C
i
,
C
i,j
at step
t
and the set of states of the cells in
g
i
at step
t
,
respectively. Then, we can establish the following lemma.
[Lemma 1]
Let
i
and
t
be any integers such that 1
≤ i ≤ m
+
n −
1, 0
≤ t ≤
T
(
m
+
n −
1).
1.
|| S
g
i
||
= 1. That is, the set
S
g
i
is a singleton and all cells in
g
i
at step
t
are
in the same state. We denote the state as
S
g
i
.
2.
S
g
i
=
S
i
.
(Proof sketch)
This is proved by mathematical induction on
t
. At time
t
=0,
it is easily seen that the lemma holds, because the cell
C
1
assumes a general state
and other cells
C
j
,2
≤ j ≤ m
+
n−
1, assume a quiescent state, while
C
1
,
1
takes a
general state and all other cells are in a quiescent state at time
t
= 0. We assume
that
S
g
i−
1
=
S
i−
1
=
a
,
S
g
i
=
S
i
=
b
,
S
g
i
+1
=
S
i
+1
=
c
, and
δ
1
(
a, b, c
)=
d
,a,
b, c, d
∈ Q
, for some integer
k
such that 0
≤ k ≤ T
(
m
+
n −
1)
−
1, and then
we show that, for any
i
,1
≤ i ≤ m
+
n −
1,
|| S
k
+1
g
i
g
i
=
S
k
+
i
.
Without loss of generality, we assume that
m ≥ n
. We then prove the case of
1
≤ i ≤ n −
1. Considering any cell
C
x,y
in
g
i
, where
x
+
y
=
i
+1:
||
= 1 and
S
k
+1
1. Case 2
≤ x ≤ i −
1, 2
≤ y ≤ i −
1: It is clear that
C
x−
1
,y
,C
x,y−
1
∈ g
i−
1
and
C
x
+1
,y
,C
x,y
+1
∈ g
i
+1
. From the assumption,
S
x−
1
,y
=
S
x,y−
1
=a,
S
x
+1
,y
=
S
x,y
+1
=
c
. Following rule (1) in Type (I), we have that
S
k
+1
=
x,y
d
. In addition, from the assumptions
S
i−
1
=
a
,
S
i
=
b
,
S
i
+1
=
c
, and
x,y
=
S
k
+
i
.
2. Case
x
=1
,y
=
i
: The cell
C
1
,i
has a border cell as its north neighbor. It can
be seen that
C
1
,i−
1
∈ g
i−
1
and
C
2
,i
,C
1
,i
+1
∈ g
i
+1
. From the assumption,
S
1
,i−
1
=
a
,
S
1
,i
=
b
,
S
2
,i
=
S
1
,i
+1
=
c
. Following rule (2) in Type (I), we
have that
S
k
+1
δ
1
(
a, b, c
)=
d
, we obtain
S
k
+1
=
d
. Thus, we have
S
k
+1
i
1
,i
=
d
. In addition, from the assumptions
S
i−
1
=
a
,
S
i
=
b
,
S
i
+1
=
c
, and
δ
1
(
a, b, c
)=
d
, we obtain
S
k
+1
=
d
. Thus, we have
S
k
+1
1
,i
=
i
S
k
+1
i
.
