Information Technology Reference
In-Depth Information
defined in this space. The state of a cellular automaton is determined by a limited
number of cells together with their states. And it can be considered that all of the
other cells are in the empty state.
In the following part, we will discuss the problems of cellular automata.
In order to avoid discussing the boundary problem, we consider an infinite
space, which is the
-dimensional Euclidean space divided into square cells of
the same size. We call this space the tessellation. The neighbor of a given cell is
the cell the coordinate of which differs from the given cell's coordinate by 1 at
the most. The tessellated structure can be formally defined as a five-element
group (
N
N, T, S, q, f
). Herein,
N
is a positive integer, and
T
is the subdivision of
N
-dimensional Euclidean space, i.e., the set of cells. Each cell of
T
is the
N
-dimensional hypercube (line segment, square, or cube in low-dimensional
spaces) the side length of which is 1. The center of
T
is a positive integer
coordinate.
S
is a finite set of states, in which
q
is the distinguishing state called
static state. Herein,
f
is the mapping function, which maps the set of all the states
of cell
.
The limited square of trellis cells is named the array, the state or configuration
of this kind of array is the function related to the state of each cell. That is to say,
the state of an array is determined by the state of each cell of the array at time
x
and its neighbors at time
t
-1 onto the set of the states of cell
x
at time
t
t
.
If there is a surjective map from array
C
' onto array
C
in which each cell and its
image have the same state, the state of
C
' will be a copy of the state of
C
. Given
an array
subsets, if any two of these subsets do not intersect with each
other and each subset is a copy of
C
* with
n
C
, the state of
C
* will contain
n
copies of the
state of
C
.
15.6 Morphogenesis Theory
The typical morphogenesis theory is the L-Systems proposed by Lindenmayer in
1968. L-Systems consist of sets of rules for rewriting symbol strings, and are
closely related to the Chomsky formal grammars. In the following, “
X
ŗ
Y
”
means that each occurrence of symbol “
X
” in the structure is replaced with string
“
” may appear on the right as well as the left sides of
rules, the set of rules can be used recursively to rewrite new structures.
Here is a simple example of L-system. The rules are context free, which
means that when a particular part changes, its context need not to be considered.
Take the following rules as an example:
(1) A
ŗ
CB
Y
”. Since the symbol “
X
