| |
ISSN 1320-0682 | |||
| Volume 02 | April 1995 | |||
Syed Mustafa Ali and R. M. Zimmer
Brunel University
Uxbridge UB8 3PH England (UK)
Email: Syed.Mustafa.Ali@brunel.ac.uk
Standard cellular automata (CA) models of naturalistic processes largely ignore the geometric relationships between the components in the physical system under study; this results in a "coarse grain" model of a natural phenomenon. For certain classes of natural phenomena such as crystal growth processes, this granularity problem may be significant.
In order to demonstrate the significance of geometrical considerations to the modelling and interpretation of natural phenomena with CA, a relativistic variant of the Game of Life [1] based on an abstraction of crystal growth processes - Proto-Life - is described. A new CA model is proposed, Masked Cellular Automata (MCA), in which geometrical properties of the CA lattice are taken into consideration in the definition of neighbourhood templates. Three binary classification criteria: (i) homogeneity of state-transition rule, (ii) homogeneity of neighbourhood template, (iii) referentiality. These are presented to distinguish between the two types of MCA used in a series of simulation experiments designed to determine whether the Proto-Life rule, as applied to MCA, can support universal computation. Universal computation provides a useful benchmark for studying potential "artificial life" and is the basis of the computational definition of life [2]. The results of experiments conducted under initial conditions of a randomised lattice of specified density are described, and the behaviours of the structures generated are classified according to the Wolfram classification scheme. It is observed that "phase" transitions between behavioural classes are constrained by the granularity of the simulation substrate - the computer hardware on which the CA executes.
Parallels between the Life rule, the Proto-Life rule and crystal growth processes are presented with a view to determining the relevance of Proto-Life to CA studies of the origin and evolution of life via emergent self-organisation. The Game of Life is a metaphor for biological life; Proto-Life is a metaphor for the processes involved in the construction of a crystalline precursor to life from an initially random prebiotic "soup".
Euclidean geometry describes very accurately the physical space of the world in which we live, but this is not a logical necessity - rather it is a (nearly exact) observed feature of the physical world. Other geometries are possible; for example, Lobachevskian or hyperbolic geometry which is similar to Euclidean geometry with certain important differences. It is conceivable that hyperbolic geometry describes the world when considered on a cosmological scale; however, for this to be the case, the proportionality constant between the angle deficit for a triangle and its area would have to be exceedingly small (Figure 1). Einstein's general theory of relativity demonstrates that the geometry of our world is, in fact, non-Euclidean, but in an "irregular", more complicated way than is suggested by hyperbolic geometry. As such, Euclidean geometry provides an excellent approximation to hyperbolic geometry on any ordinary observational scale and is the standard geometry for modelling naturalistic systems.
Figure 1: (a) A triangle in Euclidean space, (b) a triangle in Lobachevskian space.
Figure 2: (a) Von Neumann neighbourhood, (b) Moore neighbourhood, (c) Hexagonal neighbourhood.
Cellular automata (CA) are a class of mathematical and
geometrical formalisms which are widely used in modelling the
behaviour of naturalistic systems. Examples include lattice gas CA
used to model the behaviour of gases and ecological CA used in
macroevolutionary modelling. In order to describe natural systems
accurately on an ordinary scale, CA models need to approximate
Euclidean geometry as closely as possible. The tessellation (lattice
structure) produced by a number of tiles (cells) is dependent on the
geometry of the individual tiles: standard two-dimensional CA adopt a
homogeneous tile (cell) geometry which is usually regular square,
although hexagonal tile structures have been investigated in the
literature. There are two standard cell neighbourhood templates for
the standard CA with regular square cell geometry: (i) Von Neumann
neighbourhood: 4 cells edge-connected to the central cell (Figure 2(a)),
(ii) Moore neighbourhood: (Von Neumann neighbourhood
4 cells
vertex-connected to the central cell) (Figure 2(b)). The standard
neighbourhood template in lattices composed of hexagonal cells
comprises 6 cells edge-connected to the central hexagonal cell
(Figure 2(c)). The hexagonal lattice has been shown to have a geometry
which is suitable for modelling the behaviour of a large class of
natural systems including the diffusion of gases and crystal growth
processes in which packing density is assumed to be uniform and
optimal (hexagonal close packing). However, the regular square
geometry is usually adopted in CA models because it simplifies the
computer implementation of the automaton.
Conventional neighbourhood templates ignore an important property connected with the geometry of a lattice; that is, intercellular distance. Intercellular distance is determined according to lattice geometry and the distance metric adopted, but the property itself is geometry- and metric-independent: a cell occupies space in a lattice and since no two cells can ever occupy the same space in the same lattice, they must occupy different spaces separated by a distance equal to the positions of the two cells relative to each other; the magnitude of the separation is calculated according to lattice geometry and distance metric. Intercellular distance has implications for the validity of CA models of natural phenomena in which geometrical considerations such as distance are significant.
Examples of such phenomena include crystal growth processes in which the strength of a chemical bond varies with interatomic distance according to an inverse proportionality relationship which determines the stability of the crystal structure generated. In CA models of such processes, incorporating Euclidean geometry with respect to distance metric becomes significant. However, standard CA assume that cells in a Moore neighbourhood are equidistant from the central cell; hence, Euclidean geometry is only coarsely approximated. Other "finer-grain" distance metrics are available which "correct" the imprecision associated with CA models. This correction is necessary because CA generate visual patterns which are interpreted as simulations of observed natural phenomena; in order for such interpretations to be valid, the models must approximate reality (including geometric reality) as closely as possible. The class of CA which incorporate geometrical properties such as intercellular distance explicitly in the model are known as masked cellular automata (MCA).
A Masked Cellular Automaton (CA) is a finite n-dimensional lattice of
cells (
) in which each cell is a finite state automaton.
Each lattice dimension has periodicity 
: assuming the
standard square cell geometry, with n=1, the lattice is a torus;
with n=2, it is a toroid. Each automaton may be defined as a
triplet <N,S,U>, where N is a finite set of inputs, S
is a finite
set of states and U is the next-state function. The inputs are the
states of cells in the neighbourhood template; however, the
neighbourhood template is model-specific and affects the number of
elements in S. We shall investigate two different n=2 models:
The neighbourhood template (input set) N is state-specific
(inhomogeneous): a cell in state s at time t,
, where
, has a Moore neighbourhood of radius r=s; that is,
. For example, s=1,
; s=4,
. By convention, a cell is included within its
neighbourhood template: the Game of Life is an example of such a
self-referential CA. However, environmentally-determined CA are
mentioned in the literature; for example, Fredkin's 3-4 Life [3].
Environmentally-determined MCA of Type 1 exclude
from
N when computing 
, the next state of the cell.
The neighbourhood template N is generic
, where
, and is a Moore neighbourhood of radius r=1. However, only s
cells in N-1 are considered by 
, where N-1 is the Moore
neighbourhood excluding 
; whether or not
is considered
during computation of 
depends on the referentiality of
the MCA. Self-referential MCA include the cell in N when computing
the next state of the cell; for example, a cell in state s=1 considers both
itself and 1 cell from amongst its 
neighbours. As stated
above, environmentally-determined MCA exclude
from the
computation. In both cases, the s cells are selected (a)
deterministically, (b) stochastically or (c) randomly.
MCA differ from standard CA in that the geometric properties of the neighbourhood template, N, are considered during next-state computation. MCA are derived from standard CA by associating a weighting mask, W, with N. Masks are widely used in digital image-processing techniques; for example, noise reduction, region thinning and feature detection [4], each technique having an associated mask which is application-specific. In the context of CA models of naturalistic processes in which geometric properties of the lattice such as intercellular distance are significant, W functions as a "correction factor" to N. W is obtained
Figure 3: (a) chessboard, (b) city-block, (c) Euclidean distance templates, D and corresponding, weighting masks, W (above and below respectively).
from the distance template, D, which is calculated according to the
chosen distance metric. In standard CA, for which N is generic and
largely independent of lattice geometry, an n=2 CA implicitly
adopts a chessboard distance metric and its distance template, D is
as shown in Figure 3(a). However, the city-block and Euclidean distance
templates approximate Euclidean reality much more closely and are
shown in Figure 3(b)-(c). W may be derived from D in a number of
ways: for the MCA described in this paper, (i)
and (ii)
,
where 
and
denote corresponding elements in W and
D respectively. Term (ii) (the identity) preserves
during computation of 
. W thus defined ensures that
vertex-connected cells in the same state as edge-connected cells are
considered to be more loosely coupled (connected, bonded) to a
central cell 
.
The environment of a cell 
,
, is defined as the
scalar product of N and W when suitably expressed as row and
column vectors of length 
(or length
, since
).
may be computed as follows:
where 
is the state of the cell at
lattice site 
at time t with respect to
. For Type 1 MCA,
is the summation operator,
. For Type 2 MCA,
, where
is a variant of 
that considers only
cells selected
from a neighbourhood N according to one of three schemes: (i)
deterministic (maximum of the 
products
selected), (ii) stochastic (roulette-wheel selection of the
products), (iii) random.
The life-ratio for 
,
,
is defined as
for Type 1 MCA and 
for Type 2
MCA. 
is the environment when each element of N assumes the
MEAN state value, 
,
in N; 
is the environment when each
element of N
assumes the MAXIMUM state value, 
, in N.
is
utilised by U, the next-state function which is described below.
In standard CA, 
; in MCA
. A specific instantiation of
U is defined by specifying the values of
,
and
which
denote thresholds demarcating four types of next-state function
behaviour based on an abstraction of crystal growth processes in
solution; that is, decay, stasis, growth and fracture respectively.
There are four Proto-Life operators analogous to the four sub-rules in Conway's Life rule and the four conditions necessary for crystal growth in solution [5] that generate the above-mentioned behavioural types:
Proto-Life operator: DECAY
Crystal Precursor: IF undersaturated THEN dissolution
Proto-Life operator: STASIS
Crystal Precursor: IF saturated THEN balanced growth/dissolution
Proto-Life operator: GROWTH
Crystal Precursor: IF low-level supersaturated THEN growth
Proto-Life operator: FRACTURE
Crystal Precursor: IF high-level supersaturated THEN fracture
Figure 4: Type 1 MCA (inhomogeneous N, homogeneous U, self-referential); k=20;
;
;
;
;
;
An MCA may be homogeneous or inhomogeneous with respect to the
definition of U: in homogeneous MCA, 
,
and
are fixed
ūs; in inhomogeneous MCA the three parameters are s-specific; that is,
state dependent.
Pam Milliken
Simulation experiments were conducted on software implementations of
the Types 1 and 2 MCA described above under initial conditions
of a randomised lattice ("soup"). Parameters generic to Types 1 and
2 included k, 
,
(the maximum cell state in the soup at t=0;
),
(the density of the soup at t=0). Two binary
parameters were used to differentiate between MCA: (i) U
(homogeneous/inhomogeneous), (ii) referentiality
(self-referential/environmentally-determined). An additional
parameter for Type 1 MCA - (iii) N (homogeneous/inhomogeneous; that is,
r=constant or r=s respectively) - and Type 2 MCA - (iii) selection
scheme (deterministic/stochastic/random) - was specified. The
space-time evolution of Type 1 and Type 2 MCA were classified
according to the Wolfram classification scheme [6] which identifies
the following types of behaviour:
Experiments were run for 1000 time steps in lattices with k=20,
;
. If the behaviour of an MCA did not stabilise by
t=1000, it was categorised as Class III. It was discovered that
Type 1
MCA were biased towards either (i) unbounded growth or (ii) rapid
decay to a stable residue (debris) for a wide range of parameter
settings. The most interesting behaviour observed in Type 1 MCA was
growth by cells in state on the boundary of an expanding
structure composed of cells in state 
and is shown in Figure 4.
Type 2 MCA were found to generate a much wider range of behaviours.
In particular, it was found that for 
and
, the
structures generated resembled the "frozen elements" and
Figure 5: Type 2 MCA (deterministic selection, homogeneous U, self-referential);
k=20;
;
;
;
;
;
(a) 
;
(b) 
;
(c) 
Figure 6: Type 2 MCA (deterministic selection, homogeneous U, self-referential);
k=20;
;
;
;
;
;
(a) ;
(b) ;
(c)
"islands of activity" observed in simulations of autonomous random boolean
networks [7]. Phase transitions were also observed in
Type 2
MCA: 
,
(see Figure 5);
,
(see
Figure 6). The 
MCA is particularly interesting for
: a long transient is observed before the lattice
freezes into a stable structure containing sporadic Class II
(periodic) structures. It is conjectured that this may in fact
be a region of Class IV (complex) behaviour capable of
supporting universal computation, postulated as a defining
property of life [2]. A map of the behaviour space for a
restricted class of Type 2 MCA is shown in Figure 7.
Figure 7: Variation in behaviour for type 2 MCA (deterministic selection, homogeneous U,
self-referential); k = 20;
;
;
;
;
;
Crystal growth in solution provides a metaphor for the processes involved in the emergent construction of an inorganic precursor to life from an initial random prebiotic "soup"; that is, an environment containing the component molecules that bond to generate the crystalline proto-life structure. The Proto-Life rule is an abstraction of the processes involved during the growth of a crystal. Application of the Proto-Life rule to Type 2 MCA may be viewed as analogous to selective self-organisation: bonds between "molecules" (cells) are made and broken in an attempt to stabilise the resulting "crystal" (lattice) structure generated. The Class II behaviour observed in Type 2 MCA is analogous to the behaviour of an open system such as a continuous crystalliser [5] which supports indefinite crystallisation by maintaining the cycle of decay, stasis, growth and fracture (appearing as self-regenerative periodic "waves" in the MCA).
However, the validity of correlating CA behaviour with natural phenomena depends on the granularity of the match between model and phenomenon. A "coarse" match gives rise to the Hodge/B-Z/Slime Fallacy [8]; that is, the error of interpreting appearance (CA behaviour) as reality (phenomenon). MCA approximate reality more finely by incorporating geometrical properties of Euclidean reality into the CA, thereby reducing the degree to which the Hodge/B-Z/Slime Fallacy applies to the model.
Games of Proto-Life in Masked Cellular Automata (MCA)
This document was generated using the LaTeX2HTML translator Version 95.1 (Fri Jan 20 1995) Copyright © 1993, 1994, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
l2h -dir test ali.tex.
The translation was initiated by Pam Milliken on Fri Aug 16 15:06:21 EST 1996
