ISSN 1320-0682
|
|
|
|
ISSN 1320-0682 |
| Source: | http://www.complexity.org.au/ci/vol06/suzudo/suzudo.html | Received: | 01/07/1998 | ||
| Vol 6: | Copyright 1998 | Accepted for publication: | 15/10/1998 |
Tomoaki Suzudo
Control and Artificial Intelligence Laboratory
Japan Atomic Energy Research Institute
Email: suzudo@clsu3a0.tokai.jaeri.go.jp
WWW: http://www.jaeri.go.jp
The cellular automata (CAs) which
asymptotically lead to uniform regular patterns, namely crystalline
CAs are discussed. The two-dimensional and two-states-per-cell CAs
with five neighbour structure are particularly focused. First, various
CA evolution patterns are analysed by the entropy
function, and it is suggested that there are two types of CAs with
static or chaotic evolution. Analyses using a
newly-introduced rule parameter, called
parameter, ensure that
the crystalline CAs appear at the phase transition point between
static and chaotic CAs. The observed phenomena are probably
considered as a generalised model of liquid/solid phase
transition.
Many systems composed of countless elements in nature have their own temporal and/or spatial patterns, e.g. galaxies, the weather, biological and ecological systems and societies. These patterns appear without explicit pressure or constraint from outside the systems, and such phenomena are called self-organisation. The objective of studies of self-organisation is to understand the underlying properties of such phenomena in general, and has been explored by many scientists, e.g. [1, 2, 3, 4].
Crystallisation from a liquid state, which is a common example of self-organisation, governs physical characteristics of solid-state materials and is of great importance in science and engineering. The traditional explanation of this phenomenon starts from the microscopic laws applicable to their components, the quantum mechanics in this case. However, as seen in Figure 1, it is possible to embody similar dynamics by exploiting dynamical systems artificially defined in the discrete space with a simple rule of evolution. This fact indicates that the essence of crystallisation in general is not quantum force but something else: This paper attempts to describe what this is.
Cellular Automaton (CA) is a common tool for studying such self-organising phenomena, e.g. [5, 6, 7, 8, 9], and was adopted also in this paper. Due to the simplicity of method, CA is expected to yield the results which could be applicable to crystallisation in general. Another advantage of using CAs is easy implementation of the computer algorithm.
This paper discusses two-dimensional CAs causing crystalline patterns from theoretical and empirical perspectives, and focuses on their statistical features to extract some general properties of such phenomena.
Figure 1: Crystalline structure created from a random configuration by a particular CA rule.
Consider an integer value
assigned at a
two-dimensional discrete site (i,j),
and
, where
is a time step. The site
value 
at the next time step is deterministically given by
the mapping
where f is an arbitrary function which specifies the CA rule, hence
the value of a given site depends on the last values of five
``neighbour'' sites. This neighbourhood pattern is called five
neighbour structure, and is sometimes referred to as the von Neumann
neighbourhood. The total number of
neighbour state patterns is
, therefore a CA rule is composed
of 32 mapping functions. In other words, there are 32 rule ``entries''
per rule. In this paper the value-0 state (or the ``empty'' state) is
considered as a quiescent state, which means
is satisfied, i.e. the value-1 state (or ``occupied'' state) is never generated only by ``empty'' neighbours. This requirement is useful when the CA is used to model interacting particle systems. In addition, the CA space is assumed to be isotropic, i.e. the rule is always rotationally and reflectionally symmetric. If a CA rule is defined such that each site value at the next time step is calculated by the ``home'' site value and the sum of the last value of the other neighbour sites such as
the rule is called an outer-totalistic rule, and provides a subset of symmetric CA rules. The Game of Life [10, 11] is an example of the outer-totalistic rule with the nine neighbour structure.
It is surmised that the occupied cells in the background of empty cells always multiply toward the four directions when
is satisfied, as in Fig. 2 for example (see Appendix A for the reason). The analyses in this paper focus on CAs satisfying eq. (4), otherwise the occupied cells may disappear, or may become localised, as in Fig. 3. Such CAs must be eliminated from our scope in advance.
Figure 2: An example of expanding CAs given by the rule outputting 0 except for g(0,1)=1.
Let us tentatively swap the empty and occupied states in Fig. 2, and consider empty cells expanding into an occupied-state background. The expandable condition for an empty state can be derived by reversing all the input and the output states of eq. (4) such as
By taking account of this condition it is possible to remove the CAs whose evolution leads to localized empty cells such as in Fig. 4. Together with eq. (4), the condition of eq. (5) ensures that both occupied and empty cells do not become localised. In this way, the two types of cells are mixed with each other so that the CA pattern may become crystal-like, as in Fig. 1.
If eq. (2) is not satisfied, i.e. if
is satisfied, then the ``empty'' background as seen in Fig. 2 will change to an occupied-state background one time-step later. As mentioned above, rules that include such a mapping are not considered in this paper, but the reverse of eq. (6)
does not violate the quiescent condition, and prohibits a large space filled with occupied sites such as in Fig. 4. Therefore, as with eq. (5), eq. (7) can also avoid the localisation of empty cells in the background of occupied cells.
Figure 3: The evolution leads to localized occupied cells: The rule outputs 0 except for g(0,3)=g(1,1)=g(1,2)=1.
From the discussion above, CA rules satisfying
are expected to lead random configurations to become neither homogeneous nor localised patterns of both empty and occupied cells, which was confirmed by empirical studies. Consequently the CAs in this condition are those which can potentially cause a crystalline structure, and are examined in the next section.
Figure 4: The evolution leads to localized empty cells: The rule outputs 0 except for g(0,1)=g(0,2)=g(1,2)=g(1,3)=g(1,4)=1..
To understand the crystalline structure of CAs, it is useful to look at the entropy associated with their spatial pattern. The information entropy H is defined as
where 
is a probability of the
event k [12], and this can be used to evaluate the randomness
(or regularity) of statistical variables. Consider four adjacent sites such as
(i,j), (i+1,j), (i,j+1) and (i+1,j+1); there are
possible patterns for this local patch. The entropy of the spatial
pattern of CA configuration
at an arbitrary time step
can
be defined by
where 
is the probability for a particular pattern of
the local patch at the time step
. Note that a base of 16 is
used for the logarithmic function as the entropy assumes a position
between nil and unity. Typical CA configurations varying with
are shown in Fig. 5. CAs with high
have random
spatial patterns, whereas those with low
have regular
patterns, i.e. crystalline structure. Figure 6 shows
the distribution
for all 768 cases satisfying
eq. (8). The figure indicates that low-
(i.e.
crystalline) CAs are in the minority and most CAs have random spatial
patterns.
Similarly to
, it is possible to define the entropy associated
with the temporal pattern. Consider an arbitrary site (i,j). There
are four mapping patterns to the next time step per site,
i.e. 
,
,
and
, and assume we sample the
mapping pattern of the site during a certain period. From the
probability of each mapping pattern, the entropy of the temporal CA
development at the site can be defined by
where 
and
are the respective initial and final
time steps of the data collection. The base of 4 is used for the
logarithmic function as the entropy assumes a position between nil and
unity. By collecting the entropy of all sites the average entropy of
the temporal CA development (
) can be given.
Figure 7 shows the distribution of the CAs on the
space, where the data
are collected at the time
step 2000 and those for
are collected during 1900-2000 time
steps. The
clearly classifies the CAs into two groups, random
and regular time-developing groups. Some points with moderate
correspond to CAs which are still transient even after 2000 time
steps, and are expected to drop to the low-
region soon or
later according to their past tracks. The high-
CAs always
have a high-
value, and these are generally recognized as
chaotic. The
of static (low-
) CAs, on the other
hand, have various values and it is difficult to clearly separate
crystalline CAs from non-crystalline ones. The graph also indicates
that the crystalline structures are stable once they are produced,
because all the crystalline (low-
) CAs have regular
time-development (low-
) after the transient period.
parameterIf a rule is configured such that all cell states never change whatever state the neighbour sites have, that is,
then it is expected that the evolution leads to a constant development. On the other hand, if a rule is configured such that all cell states perpetually change whatever state the neighbour sites have, that is,
then the CA evolution becomes periodic with the period two. These are the two extreme cases, and in the case of general rules, the mapping may or may not change cell states depending on the neighbour state. As a descriptor of how the cell state is changeable, we consider a parameter uniquely determined for each rule
where m is a total number of the rule entries which update the cell
state unchanged. The value of eq. (14) is hereafter called
the parameter. For
instance, the
parameters for the rules of eqs.
(12) and (13) are nil and unity
respectively. Note that the
parameters is different from the
parameter [13].
Figure 5: Typical CA patterns with various
Figure 8 shows the frequency distribution of the
parameter for static and chaotic CAs. CAs in the static group have a
-value near the extrema, and the value for those in the chaotic
group is in the central range of
. Thus the graphs imply that
the transition from static to chaotic takes place as the
parameter changes from
(or
) to the moderate value,
where and
are the smallest and largest values of
parameter satisfying eq. (8) (
,
).
Figure 8: The) and chaotic (
) CAs.
Consider CAs with
. If
a rule has
close to
, we can presume that from the
definition of
that there are many kinds of local patterns which
remain unchanged through the updating by the rule. Therefore, CA
evolutions starting from a random configuration remain random,
although these time-developments are regular; these CAs are thought to
be located at the high-
and low-
range in Fig. 7. As the
parameter increases the number of such constant
local patterns decreases, and accordingly the CA's spatial pattern
after the transient period becomes less random. At the same time, the
position of the CA on the
space (Fig. 7) shifts
gradually to the low-
and low-
range. If
becomes
so large that only a few kinds of local patterns can remain unchanged,
these particular patterns must be spread all over the CA space through
the continuation of this process, because each local pattern keeps
changing unless it fits one of the particular patterns: This is
considered to be the mechanism of crystallisation. For this reason,
relatively longer transient times can be observed for the crystalline
CAs compared to the others. There is a certain point in the
parameter, say
, at which all constant local patterns
disappear. The rules with
therefore lead to random
time development and random spatial configuration, and correspond to
the high-
and high-
group (namely the chaotic group) in
Fig. 7. The value of
is, however, not uniquely
determined, because the largest
which leads to the crystalline
structure is dependent on the type of patterns.
A similar discussion is possible for the CA rules with
. The crystalline structure in this case is determined not
by the constant local pattern but by the period-2 local pattern.
Figure 9 shows the
distribution of CAs
with 
, namely static CAs. Crystalline CAs have moderate
values of
, while the non-crystalline ones have values near the
extrema. These results also support the above scenario.
To sum up, the
parameter statistically parameterises the CA
rules, and is a key value of the crystallisation and the phase
transition between static and chaotic performances. As mentioned in
[13], the
parameter is related to the four
Wolfram Classes [6]:
plane as seen in Fig.
10.
It is worthwhile to compare such CA dynamics to crystallisation in
nature. The static and chaotic classes correspond to solid and liquid
phases, respectively; the
parameter corresponds to
temperature. The initial condition is ``liquid'' as shown in
Fig. 1. The ``liquid'' is cooled rapidly when
is
low, and a non-crystalline structure (or amorphas) is produced. If the
``liquid'' is slowly cooled at around melting point, i.e. at
,
crystal is produced. The initial ``liquid'' continues to be liquid if
is high. The major difference is only that the
is not
uniquely determined like the melting point. Consequently, the
macroscopic properties of the crystallisation in CAs is fairly similar
to those in nature. The microscopic mechanism of crystallisation is
commonly understood to be that existing crystalline structures allow a
local pattern (a molecular) join if it is matching in structure,
whereas those unsuitable (impurities) are likely to remain in
solution. This is clearly similar to the mechanism of CA
crystallisation as explained above.
Two-dimensional CAs
causing the crystalline structure were studied.
The spatial and temporal pattern entropy functions successfully
characterise them, and classified
them into two groups, static and chaotic. The background
for this classification was investigated
using the
parameter, the probability for a cell-state to
remain unchanged at the next time step; the
parameter is
uniquely determined by the rule definition. Theoretical and
experimental studies confirmed that the
parameter statistically
parameterises the CA
rules, and that it is a key value to the phase
transition between static and chaotic performances. In addition, it
was surmised that
crystallisation appears when the rule has a
parameter near the
critical point between static and chaotic CA evolutions. The observed
phenomena are probably considered as a generalised form of
crystallisation, including ones in nature and computers.
One-dimensional CAs with 3-neighbour structure are defined by
and rules satisfying the quiescent condition considered as
and
Let us assume an initial condition of a single occupied site at the
position of i=0 with the background of empty sites. When t=1, two
cells at the position of i=1 and -1 are occupied. Similarly, two
cells at i=2 and -2 become occupied when t=2. Generally, when
, the sites at
and
have an occupied state,
and a ``triangle" is formed in the spatio-tempo CA space, as seen in
Fig. 11. The sites inside the triangle have either an
occupied or an empty state, but it is never totally empty because an
isolated occupied cell at
again becomes another ``seed'' of
the triangle. In this way, occupied cells spread all over the CA
space, and this property is not influenced by the other entries such
as 
. The evolution from the random configuration also
leads to expansive dynamics as seen in
Fig. 11a. Therefore the condition of
eq. (17) ensures the expandability of the 1-dimensional
CA. Equation (4) is the extension of this condition to
two dimensions and ensures the expanding dynamics of 2-dimensional
CAs.
Figure 11: One-dimensional expandable CAs given by the rule outputting 0 except for.
 |
EMail Contact: Complexity International Editor
