Cellular
automata (CA) are a powerful tool for understanding natural phenomena, so I
shall dwell on them some more, carrying on from where I left in Part 68.
The Rule 90
cellular automaton I discussed in Part 68 is a special case of the general
class of 1-dimensional CA. For the general case, a site i on a row of
cells at time t can carry any of the values ai from
the set 0, 1, ... , k-1. We can, for example, associate a specified
colour with each member of the set. The value ai of the site
for each i is updated in discrete time steps according to a specified
deterministic rule which depends on the neighbourhood of the site:
ai(t+1) = φ[ai-r(t),
ai-r+1(t), ..., ai+r(t)].
For Rule 90
CA, k = 2 and r = 1; i.e., there are just two colours (black and
white), and only nearest neighbours of the previous time step decide the colour
of a cell.
An extensive
empirical analysis of all 1-dimensional CA by Wolfram showed that the CA rules
and the patterns generated by them (even when we start from random or
disordered initial conditions) can be generally divided into just four universality classes:
In Class 1 CA,
evolution from almost any initial state leads finally to a unique homogeneous
state. This is like the occurrence of a limit point or a point attractor in the phase space of a nonlinear dynamical
system. Patterns in Class 1 CA are static or repetitive, after
the initial few time steps.
Class 2 CA
In Class 2 CA,
there is ultimately a sequence of simple stable or periodic structures. This
corresponds to the occurrence of limit cycles or periodic attractors in phase space. Class 2
patterns are nested.
Both Class 1
and Class 2 CA are predictable after their static (repetitive or nested)
nature has been discerned, and are therefore computationally reducible. Rule 90 CA
are Class 2 CA.
Class 3 CA
Compared to
Class 1 or Class 2 CA, Class 3 CA go to the opposite extreme. They generally
exhibit chaotic or aperiodic long-time behaviour. Such CA grow indefinitely.
Their patterns are often self-similar or scale-invariant. They are
characterized by a fractal dimension, with
or ~1.59 as the most common value. They correspond to strange attractors in phase space.
Class 4 CA
Class 4 CA are
the most relevant from the point of view of complex behaviour. For them the
patterns grow and contract irregularly. The long-time behaviour is neither
fully predictable nor totally chaotic.
There are complicated localized structures, some of which propagate with
time. There are regions of coherent structures that propagate, grow, split
apart, disappear, or recombine in all sorts of ways. The pattern is changing
all the time; it never settles down. The long-time behaviour is undecidable
(typical of a complex system).
The simplest
possible rules for 1-dimensional CA are those for k = 2 and r = 1.
Detailed analysis by Wolfram has shown that there are 256 distinct types of
them. Each type corresponds to a specific local rule for generating a row of
cells from the previous row. Thus there are 256 rules in all, Rule 90 being an
example.
The picture
below is an interesting example of the possible operation of Rule 30 in Nature,
in this case in the pigmentation-pattern mechanism.
It is a textile cone snail ('Conus textile') shell,
similar in appearance to Rule 30 CA (see figure
below).
Rule 30 for going from one row of a cellular automaton
to the next is as follows:
Current
pattern: 111 110 101 100 011 010 001 000
New state for
centre cell: 0 0 0 1 1 1 1 0
In the late 1940s, John von Neumann got interested
in the question:
Can a machine be programmed to make a copy of itself
which can make a copy of itself? That is, can there be self-reproducing
machines which can generate self-reproducing machines?
To bring out the essence of self-reproduction, Neumann
imagined a thought experiment. Consider a machine moving around on the surface
of a pond. The pond contains all sorts of machine parts. Our machine is a 'universal constructor'; i.e., given a recipe for constructing any machine,
it can search the pond for the right parts and construct the desired machine.
In particular, it can construct a copy of itself if the requisite description
is known to it.
But it is
still not a successively self-reproducing
machine, because the copy it has constructed of itself has no information about
its own description for constructing another copy of itself. Neumann argued
that for this to be possible, the original machine must have a 'description
copier'; i.e. a mechanism for duplicating the original description and for
attaching this duplicate description to the new copy it is constructing of
itself. The offspring will now have the wherewithal for a sustainable
self-reproduction in this so-called Neumann
universe.
Thus any self-reproducing system must play two
roles:
- It should serve as an algorithm that can be executed during the copying and constructing process.
- It should serve as a data bank that can be duplicated and attached to the offspring.
These two predictions were confirmed for real-life
systems in 1953 when Watson and Crick determined the structure of the DNA
molecule. The DNA molecule not only serves as a data base for synthesizing
various proteins etc., but it also unwinds and makes a copy of itself when the
biological cell divides into two.
For testing his thought experiment, Neumann used cellular automata. He proved that there existed at least one
cellular-automaton pattern which could reproduce itself. The pattern he found
involved a large lattice of cells, with 29 possible states for each cell. This
was an important result because it meant that self-reproduction was possible in
machines, and was not confined to the so-called living beings only.
Or, you may well say that 'living beings' are nothing
more than self-replicating machines; only their level of complexity is a bit too much for
us to comprehend fully.
No comments:
Post a Comment