The notion of cellular automata was put forward
in the 1940s by Stanislaw Ulam, a colleague of John von Neumann. Ulam suggested to Neumann to consider a digital
programmable universe, in which 'time' is imagined as defined by the
ticking of a cosmic digital clock, and 'space' is a discrete lattice of
cells, each cell occupied by an abstractly defined very simple computer
called a finite automaton. Very
simple local rules determine the state of any cell at any discrete point of
time. There are only a finite number of states available to a cell or an
automaton. These states could be, say, a few colours, or a few integers, or
just 'dead' or 'alive', etc. At each tick of the digital clock, every automaton
changes over to a new state determined by its present state and the present
states of the neighbouring cellular automata (CA). The rules by which the state
of any automaton changes at a given instant of digital time are the equivalent
of the physical laws of our actual universe.
The subject of cellular automata has got a big boost from
the work of Stephen Wolfram. He established that CA have a truly wide-ranging
applicability and, in particular, have features of nonlinear dynamical
systems. He emphasized that the complex phenomena we see in the
real universe can be usually thought of as the running of 'simple programs'.
The best and often the only way to understand these phenomena is by modelling
them on a computer with the help of CA, rather than by working out the
consequences of idealized and approximate mathematical models
based on a set of equations. Approximations are generally not a good idea for
modelling complex systems: No approximation may be a good enough one when
things are really complex.
Wolfram's idea of a 'simple program'
typically has the following ingredients:
- A set of transformation or operation rules (usually 'local' rules).
- Data to operate on.
- An engine that applies the rules to the data.
In a cellular automaton, the data enter
only at the beginning of the computation ('initial conditions'), and the engine
keeps applying the same deterministic rules to the outputs of its previous
application of the rules. Wolfram investigated a large number of simple
programs, and demonstrated that extremely complex-looking patterns can be
generated by many of them. The figure below illustrates the point.
Shown here is
a 1-dimensional cellular automaton. It consists of a row of squares, and each
square can be either black or white. Starting from just one such row of squares
(the top row in the upper figure), each time the system is updated, a new row
of squares is created just below the previous row, following a simple rule. The
simple transformation rule operative in this figure says that a square in the
new row should be black only if one or the other, but not both, of its
vertically-above predecessor's neighbours is black.
Shown in a
separate figure at the bottom is a graphical depiction of this rule, in which 8
block are drawn, corresponding to the 8 possible configurations of three
neighbouring cells, each configuration determining the colour of the cell in
the next row. Starting with a single black square in the top row of squares,
this rule produces a complex pattern of nested triangles.
Shown at the
bottom, below the graphical depiction of the operating rule for this CA, are
the numbers 0, 1, 0, 1, 1, 0, 1, 0, where 0 corresponds to a white cell, and 1
to a black cell. Treating this sequence of digits as a binary number, we get
01011010, which is the number 90 in the decimal system. Wolfram therefore calls
this cellular automaton as generated by Rule 90. The sequence of the
eight blocks for depicting this rule has been so chosen as to generate the
smallest possible number for labelling or classifying the rule.
A particularly popular example of CA is the Game of Life (GOL), invented (around 1970) by John Conway. It provides
a graphic demonstration of artificial evolution; the evolving structures can be seen on a computer
screen. One starts with a 2-dimensional lattice of square cells, each cell
randomly taken to be either black or white. Let black mean that the 'creature'
denoted by a black cell is 'alive', and let white mean that the corresponding
creature is 'dead'. Very simple local rules are introduced
for how the cells are to change from one time step to the next.
For example, if a cell has two or three neighbours which
are alive (i.e. black), then the cell becomes alive if it was dead to start
with, or remains alive if it was already so. If the number of neighbours is
less than two, the cell dies of 'loneliness'. And if the number of neighbours
is more than three, again the cell dies, this time due to 'overcrowding'.
Remarkable patterns emerge on the computer screen when this program is run.
Every run is different, and it is not possible to exhaust all possibilities. Often the 'live'
cells organize themselves into coherent and ever-changing patterns. The figure below shows the so-called 'Gosper glider
gun'.
A 'gun' is a configuration of the GOL which repeatedly
and endlessly shoots out moving objects such as 'gliders'.
An unlimited variety of patterns, including bizarre-looking
'creatures' or manmade contraptions, can emerge as the CA evolve. Here is a
'spaceship':
Will you like a demo? Please click here: http://activeden.net/item/game-of-life/136281
Here is another excellent website for having fun with
the GOL:
A CA applet is available at http://www.gmilburn.ca/2008/12/02/elementary-cellular-automata/.
For more on what one can do with CA, watch this video
called the 'Amazing Game of Life Demo':
This post should give you a feel for how life arose out of nonlife. It was just a matter of relentless evolution of complexity. Very simple local rules of interaction were in operation, and one thing led to another. Such evolution has been going on all the time, and will continue to do so.
No comments:
Post a Comment