Geoscience Reference
In-Depth Information
dominant land use. We have said little about time, but similar problems emerge where different
temporal processes requiring synchronisation in complex ways characterise the automata.
2.3 ORIGINS OF CA
CA date back to the very beginnings of digital computation. Alan Turing and John von Neumann,
who pioneered the notion that digital computation provided the basis for the universal machine,
both argued, albeit in somewhat different ways, that digital computation held out a promise for a
theory of machines that would be self-reproducible, that computers through their software could
embody rules that would enable them to reproduce their structure, thus laying open the possibility
that digital computation might form the basis of life itself. This was a bold and daring speculation
but it followed quite naturally from the philosophy of computation established in the 1920s and
1930s. von Neumann perhaps did most to establish the field in that up until his death in 1956, he
was working on the notion that a set of rules or instructions could be found which would provide
the software for reproducibility. The idea of automata flowed quite easily from this conception, and
the notion that the elements of reproducibility might be in terms of
cells
was an appeal more to the
possibility
of using computers as analogues to create life than any actual embodiment of such func-
tions through computer hardware.
von Neumann worked on many projects, CA being only one. His work was published posthu-
mously by his student and colleague Arthur Burks who carried on this work at the University of
Michigan in the 1960s and 1970s (Burks, 1970) where, through his Logic of Computers Group,
he kept the field alive until the glory years began. These years were fallow in that although von
Neumann's insights marked his usual genius, computer hardware and software had not reached the
point where much could be done with CA. In fact, progress came from a much simpler, more visual
approach to automata. von Neumann had drawn some of his inspiration from Stanislaw Ulam, the
mathematician who worked with him on the Manhattan project. Ulam had suggested to him as early
as 1950 that simple CA could be found in sets of local rules that generated mathematical patterns in
2- and 3D space where global order could be produced from local action (Ulam, 1962, 1976). It was
this line of thinking that was drawn out, as much because in 1970, John Conway, a mathematician
in Cambridge, England, suggested a parlour game called
Life
which combined all the notions of CA
into a model which simulated the key elements of reproduction in the simplest possible way.
Life
has become the exemplar
par excellence
of CA, but its popularity rests on the fact that a generation
of hackers took up Conway's idea and explored in countless ways the kinds of complexity which
emerge from such simplicity.
It is probably worth stating the elements of
Life
for it is a more general embodiment of the key
elements of CA than our examples so far. In essence,
Life
can be played out on any set of cells which
exist in any space, but it is most convenient to think of this space as being a regular tessellation of
the 2D plane such as the usual cellular grid. Any cell can be
alive
or
dead
,
on
or
off
, and there are
two rules for cells becoming alive/giving birth or dying/not surviving. The rules are simplicity itself.
A cell which is not alive becomes alive if there are exactly three live cells immediately adjacent to
it in its Moore neighbourhood. A cell remains alive if there are two or three live cells adjacent to it,
otherwise it dies. Less than two adjacent cells implies the cell dies from isolation, more than three
from overcrowding. The event that set the field humming in 1970 was John Conway's challenge
reported by Gardner (1970) in his recreational mathematics column in
Scientific American
that he,
Conway, would give a prize of $50 to the first person who could unequivocally demonstrate that cer-
tain configurations of
Life
could be self-perpetuating. The challenge was won by Bill Gosper and his
group at MIT within the year who showed that a particular configuration of cells and their dynamics
called a
glider gun
would, under these rules, spawn live cells indefinitely (Poundstone, 1985).
However suggestive the game of
Life
might be, the original logic of automata eventually
came to fruition. Burk's group produced some of the basic ideas which now serve to underpin
complexity theory. Work on genetic algorithms associated with Holland (1975 [1992]) and with
