Geoscience Reference
In-Depth Information
around any cell is composed of cells which are geometrically contiguous. It is entirely possible
to consider neighbourhoods where the concept of locality does not mean physical contiguity,
that the cells comprising the neighbourhood are scattered within the space, especially if the
cells of the CA are not spatial in the Euclidean sense. But such examples stretch the concept of
GeoComputation and we will avoid them here. In Figure 2.2a through c, the cells comprising
each neighbourhood are symmetrically arranged, whereas in Figure 2.2d, there is no symmetry,
although the property of uniformity, which means that every cell in the system has the same form
of neighbourhood, imposes a meta-regularity on the automata. The neighbourhood in Figure 2.2a
is called the Moore neighbourhood, in contrast to the reduced 3 × 3 cell space (CS) in Figure 2.2b
which is the von Neumann/Moore neighbourhood. The Moore neighbourhood is in fact the most
usual and the most general. The pattern in Figure 2.2c is a symmetrically displaced/extended
version of the von Neumann neighbourhood, whereas that in Figure 2.2d is more randomly con-
figured, although its form must have meaning to the problem in hand. Within the complete 3 × 3
cellular space, there are a total of
n
∑
combinations or forms (where the summa-
tion over
n
is taken from 1 to 9). This gives 512 possible neighbourhoods whose cells are contigu-
ous to one another within the 3 × 3 space, and this admits an enormous variety of patterns that
might be generated by such CA. In this context, however, we will largely deal with the Moore
neighbourhood.
If we turn to patterns within the neighbourhood which generate different transition rules, the
number of possibilities is even greater. Let us assume that each cell is either on or off, the two-
state characterisation that we will use for most of the examples in this chapter. Then for the von
Neumann neighbourhood in Figure 2.2b which consists of 5 cells, there are 2
5
or 32 different
configurations of on-off cell patterns that affect the transition rule. If the transition rule is one of
switching the central neighbourhood cell on or off if a certain set of patterns occurs, then there
are 2
32
possible automata that might result. In the case of the Moore neighbourhood which has
9 cells, then the number of possible automata is 2
512
, which is an astronomical number, twice as
large as the number of elementary particles in the universe (Toffoli and Margolus, 1987)! There
are of course not two possible neighbourhoods - the von Neumann and Moore - but 512 for which
these computations can be envisaged.
Patterns inside neighbourhoods interact with the shape of neighbourhoods themselves, and this
complicates the concatenation of neighbourhoods with patterns. But the point is that this shows
that enormous variety can be generated by thinking in these terms about the kinds of patterns that
might be computed using CA. Our discussion is devoid, however, of any meaning to the pattern of
cells, but it does illustrate the possibility that any conceivable pattern might be computed using CA.
Readers will have to think a little about these implications, and if they find difficulty in envisaging
these possibilities, first, think of all the possible neighbourhoods one might construct based on a
3 × 3 grid - begin to write them out to convince yourself that there are 512 possibilities or 511 if the
neighbourhood with no cells is excluded. Then think about the number of different on-off configu-
rations within the 3 × 3 space which might trigger some action or transition. Start to write these out
too. You will give up quite soon but at least this will demonstrate the enormous array of possible
structures that can be built from these simple bits using the CA approach.
There are three distinct sets of initial conditions which are associated with different types
of growth model and different characterizations of states. The simplest condition involves an
automaton which begins to operate on a single cell which is switched on in a two-state (on/off
developed/non-developed) system. The best example is the one we noted earlier which gives rise
to the diffusion from a single seed, often placed at the centre of the cellular space. The second
condition is a straightforward generalisation of this to more than one seed. These two types of
condition might be thought of as invoking growth processes within a single city or system of
cities, for example. The third condition involves a system that is already complete in that every
(!/[(
99−
nn
)! !])
