Pages

Saturday, March 2, 2013

69. Cellular Automata and von Neumann's Self-Replicating Machines



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














The binary number 00011110 is equal to the decimal number 30. Hence the label 'Rule 30'. Here is what this rule generates:


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.