Information Technology Reference
In-Depth Information
particular configurations of states within the lattice of automata, they can
compute over the very set of symbols out of which they are constructed.
In the following part, we will discuss the growth of cellular automata in the
2-dimensional space. Let
V
be the cell state set, in which there is an element
v
0
taken as the static state. Let
f
be the function of
V*V* ··· *V
ŗ
V
, which satisfies
that
f
(
v
0
, v
0
, ···, v
0
)=
v
0
. Then, we call (
V, v
0
, f
) and
f
the cellular automaton of m
neighbors,
and
the
transformation
function
of
this
cellular
automaton,
respectively.
Because any complete cellular automaton is always an infinite set, the cellular
automaton discussed here is embedded to 2-dimensional plane. The cells in this
cellular automaton have 8 states, i.e., 0, 1, 2, 3, 4, 5, 6, and 7. In these states, 0, 1,
2, and 3 constitute the basic structure of the cellular automaton, and then 04, 05,
06, and 07 are the signals. The cells in state 1 are called the nuclear cells, and the
cells in state 2 are called the shell cells. In the figures below, both of the symbol
* and the blank space represent the cells in state 0.
The process of signal propagation can be explained with the following
example:
2 2 2 2 2 2 2 2 2 2 2 2
1 1 0 s 1 1
ŗ
1 1 1 0 s 1
2 2 2 2 2 2 2 2 2 2 2 2
The above example shows the propagation process of the signal 0s. Herein,
=
4, 5, 6, 7, so it is called the data path. As its name suggests, it can propagate data
in the “signal” form. A signal contains two state cells which move together. The
signal (4, 5, 6, 7) itself has the state 0, and the data path can branch and fan out.
At the branch point, the signal can replicate itself. The following figure shows
the process of signal replication at time
s
+2.
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
1 0 s 1 1 1
ŗ
1 1 0 s 1 1
ŗ
1 1 1 0 s 1
t
,
t
+1, and
t
2 2 1 2 2 2 2 2 s 2 2 2 2 2 0 2 2 2
* 2 1 2 * * * 2 1 2 * * * 2 1 2 * *
* 2 1 2 * * * 2 1 2 * * * 2 1 2 * *
time
t
time
t
+1
time
t
+2
