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*a*from the set 0, 1, ... ,_{i}*k*-1. We can, for example, associate a specified colour with each member of the set. The value*a*of the site for each_{i}*i*is updated in discrete time steps according to a specified deterministic rule which depends on the neighbourhood of the site:*a*

_{i}

^{(t+1)}=

*φ*[

*a*

_{i-r}^{(t)},

*a*

_{i-r}_{+1}

^{(t)}, ...,

*a*

_{i}_{+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.