80. Adaptive Computation

I described Neumann’s self-reproducing cellular automata (CA) in Part 69. Langton (1989) extended the CA approach to his work on artificial life (AL) by introducing evolution into the Neumann universe.

In the self-reproducing CA created by Langton, a set of rules (the so-called GTYPE) specified how each cell interacted with its neighbours, and the overall pattern that resulted was called the PTYPE. The local rules could evolve with time, rather than remaining fixed. His pioneering work was a fine example of evolutionary computation or adaptive computation.

 

http://www0.cs.ucl.ac.uk/staff/ucacpjb/wc3paper.html

Langton also correlated his work on AL with Wolfram’s four classes of CA (cf. Part 69). We saw in Part 35 on chaos how the dynamics described by the equations for modelling weather phenomena by Lorenz changes drastically with the values assigned to the three adjustable or 'control' parameters. In particular, the dynamics is chaotic only for a certain range of values of the control parameters, and nonchaotic or not fully chaotic for other values. Small values of control parameters give nonchaotic behaviour, similar to the dynamics described by Wolfram’s Class 1 and Class 2 CA. And sufficiently large values of the control parameters result in totally chaotic dynamics, which corresponds to Class 3 CA.

Langton investigated the introduction of a similar (only one) parameter into the rules controlling CA behaviour to check the above analogy more clearly, and particularly to investigate the connection between Class 4 CA on one hand, and partially chaotic systems on the other. After a number of trials, he came upon a parameter (λ) for the CA rules to correspond to the control parameter in an equation governing chaotic behaviour.

This λ was defined as the probability that any cell in the CA will be ‘alive’ after the next time step: In Part 68 I chose the colours black and white for distinguishing the two states of a CA cell, which we can now relate to ‘alive’ and ‘dead’; just like what was done for the Game of Life. For example, if λ = 0 in the rule governing the evolution of a particular set of CA, all cells would be white or dead after one time step. The same would be true if λ = 1. In fact, the CA dynamics is symmetrical about the value λ = 0.5, except for the fact that the colours black and white get interchanged.

In his computer experiments, Langton found that, as expected, λ = 0 corresponds to Wolfram's Class 1 rules. The same was true for very small nonzero vales of λ.

As this control parameter was increased gradually, Class 2 features started appearing at some stage, with characteristic oscillating behaviour. With increasing values of the control parameter, the oscillating pattern took longer and longer to settle down.

Taking λ = 0.5 resulted in totally chaotic behaviour, typical of the Wolfram Class 3.

Langton found that clustered around the critical value λ ≈ 0.273 were Class 4 CA.

Thus, as the control parameter increases from zero onwards, we see a transition from ‘order’ to ‘complexity’ to ‘chaos'.

http://www.noyzelab.com/research/ulamizer2.html

In Part 6 I discussed how the variation of a control parameter like temperature can cause phase transitions to occur in a system such as water (from steam to liquid water to ice, on cooling). Langton realized that his control parameter λ plays a similar role in determining the dynamics of CA. It is like temperature. At low temperatures a material (such as H₂O) is solid, in a crystalline state, which is an ordered state. At high temperatures we have a fluid state (liquid or vapour), which signifies chaos or disorder. Langton drew the analogy with such phase transitions for describing the Class 4 behaviour in CA which sets in for values of λ around 0.273.

The solid-fluid transition in water is actually a first-order or discontinuous phase transition. But a crystal can also undergo one or more solid-to-solid phase transitions. Such transitions may be of first order or second order. As Langton pointed out, a second-order phase transition is actually better for drawing the analogy with Class 4 CA.

A second-order phase transition is characterized by the occurrence of 'premonitory phenomena' (cf. Wadhawan 2000). That is, even before the phase-transition temperature T_c is reached, the material exhibits 'critical phenomena', and regions of the new phase start appearing and disappearing in the old phase. This is unlike a first-order phase transition, which occurs sharply (e.g. at the melting point of ice), and there are generally no critical fluctuations or premonitory phenomena (even though there is a range of temperatures in which the parent phase and the daughter phase coexist).

Langton’s control parameter λ for CA gives Class 4 behaviour not only for the value 0.273, but for a certain range of values around that number. And even for a specific value of the control parameter in this range, coherent structures may exist indefinitely, or over an arbitrarily large number of cells of the cellular automaton.

Langton gave this phase boundary in the Neumann universe the name edge of chaos.

We should remember, however, that the edge is not a sharp one. It is more like a thin or thick membrane in phase space, with chaotic behaviour on one side, and ordered behaviour on the other. Complex behaviour is at its most creative within the membrane. There is a gradation from chaos to complexity to order across the membrane.

More on this next time.