Matthew Egbert

m.egbert@auckland.ac.nz

Cellular automata are another classic area of artificial life research.

A CA consists of a regular lattice of cells, where:

• Each cell is in one of a finite number of states (2 or more).
• The state of each cell changes according to a set of rules that specify the next state of a cell, given its current state and the state of its neighbouring cells.

Usually, the rules are the same for all cells in the lattice and all of the cells are updated simultaneously and deterministically.

Some CA use an eight-cell immediate neighbours, called its Moore neighbourhood

Other CAs, can use different neighbourhoods; e.g. the four neighbours of the von Neumann neighbourhood

The best known CA is John Horton Conway's "Game of Life". Invented 1970 in Cambridge.

Objective: To make a 'game' as unpredictable as possible with the simplest possible rules.

Infinite 2-dimensional rectangular grid cells. Each cell is either "dead" (white) or "alive" (black).

t = 0

The best known CA is John Horton Conway's "Game of Life". Invented 1970 in Cambridge.

Objective: To make a 'game' as unpredictable as possible with the simplest possible rules.

Infinite 2-dimensional rectangular grid cells. Each cell is either "dead" (white) or "alive" (black).

t = 1

The best known CA is John Horton Conway's "Game of Life". Invented 1970 in Cambridge.

Objective: To make a 'game' as unpredictable as possible with the simplest possible rules.

Infinite 2-dimensional rectangular grid cells. Each cell is either "dead" (white) or "alive" (black).

t = 2

The best known CA is John Horton Conway's "Game of Life". Invented 1970 in Cambridge.

Objective: To make a 'game' as unpredictable as possible with the simplest possible rules.

Infinite 2-dimensional rectangular grid cells. Each cell is either "dead" (white) or "alive" (black).

t = 3

The best known CA is John Horton Conway's "Game of Life". Invented 1970 in Cambridge.

Objective: To make a 'game' as unpredictable as possible with the simplest possible rules.

Infinite 2-dimensional rectangular grid cells. Each cell is either "dead" (white) or "alive" (black).

t = 4

The best known CA is John Horton Conway's "Game of Life". Invented 1970 in Cambridge.

Objective: To make a 'game' as unpredictable as possible with the simplest possible rules.

Infinite 2-dimensional rectangular grid cells. Each cell is either "dead" (white) or "alive" (black).

t = 5

The best known CA is John Horton Conway's "Game of Life". Invented 1970 in Cambridge.

Objective: To make a 'game' as unpredictable as possible with the simplest possible rules.

Infinite 2-dimensional rectangular grid cells. Each cell is either "dead" (white) or "alive" (black).

t = 6

The best known CA is John Horton Conway's "Game of Life". Invented 1970 in Cambridge.

Objective: To make a 'game' as unpredictable as possible with the simplest possible rules.

Infinite 2-dimensional rectangular grid cells. Each cell is either "dead" (white) or "alive" (black).

t = 7,9,11,13,15...

The best known CA is John Horton Conway's "Game of Life". Invented 1970 in Cambridge.

Objective: To make a 'game' as unpredictable as possible with the simplest possible rules.

Infinite 2-dimensional rectangular grid cells. Each cell is either "dead" (white) or "alive" (black).

t = 8,10,12,14,16...

John von Neumann (1903 - 1957) made major contributions to mathematics, physics, economics, computing, and statistics.

In the 1940's he was interested in self-replication*. How can you build a robot that can replicate itself?

A colleague was working on a model of crystal growth, and this led to the development of cellular automata.

* Note that Watson and Crick's double-helix model of DNA wasn't around until 1953.

Chris Langton invented an 8-state CA that supports creatures called "Langton Loops" that are capable of copying themselves.

• 8 states
• von Neumann neighborhood with rotational symmetry

But Langton's Loops are capable of only limited variety.

von Neumann was interested in open ended evolution and "construction universality."

His UC involves 6,329 cells with 29 states and it was designed by von Neumann in the 1940s without the use of a computer(!)

von Neumann's design included a constructor and a tape of instructions

Again, this predates Watson and Crick's discovery of the double-helix shape of DNA. And I find it an interesting example of a parallel between artificial and natural systems.

"Artificial Life can contribute to theoretical biology by locating life-as-we-know-it within the larger picture of life-as-it-could-be."

Chris Langton 1989 in: Langton ed. Artificial Life. Addison-Wesley. p. 1-47

Glider

Glider

Glider

R-pentomino

Glider

R-pentomino

Predicting these kinds of systems is often impossible (without checking all of the intermediate steps).

A systematic investigation
In 1990s & 2000s, Stephen Wolfram (creator of Mathematica) carried out a systematic investigation of one-dimensional cellular automata.

Stephen Wolfram A New Kind of Science 2002. Publisher: Wolfram Media Place: Champaign, IL ISBN: 1-57955-008-8

Update 1103 of R-pentomino (excluding six gliders) http://www.conwaylife.com/wiki/Methuselah

One spatial dimension.

Two states:

• "on" = black
• "off" = white

Time can be shown on vertical axis.

Neighbourhood is

• current cell
• neighbour on left
• neighbour on right

There are $2^{3} = 8$ possible previous states ("inputs"). And for a given rule set the output for each of those possibilities will be either on or off.

There are 256 possible rule sets (for a 2-state CA with a 3-cell neighbourhood.) To enumerate them, Wolfram constructed a binary number that corresponds to which initial-conditions produce which states.

But of the $2^{8} = 256$ elementary cellular automata, there are only 88 fundamentally inequivalent rules. The others are mirror-images or inversions of other rules (e.g. where all on states are off states and vice-versa).

For example, rule 0 (every input produces a white cell) is structurally equivalent to rule 255 (every input produces a black cell)

Without any complex rules, and without any long-distance communication a fractal is generated.

First 500 steps

Some signs of order on the left-hand side, but chaotic on the right-hand side.

"even continuing for a million steps many aspects of the pattern obtained seem perfectly random according to standard mathematical and statistical tests." (p. 30 Wolfram 2002)

This rule is used as a random-number generator in Mathematica.

...out of simple rules, randomness!

This CA only grows down and to the left.

On the right, we see 150 updates of this rule from a single on cell.

But does it create organized or chaotic dynamics?

Now we see 700 steps.

Is this organized or chaotic?

Now we see 700-1400 steps.

Is this organized or chaotic?

Is it ever going to stop? (Show of hands!)

Now we see 1400-2100 steps.

Is this organized or chaotic?

Is it ever going to stop? (Show of hands!)

Now we see 2100-2800 steps.

Is this organized or chaotic?

Is it ever going to stop? (Show of hands!)

Remember you are effectively seeing the entire system in these images. The stuff to the left is periodic and regular. There is nothing to the right (it only grows to the left).

Now we see 2800-3400 steps.

What has happened?

Is this organized or chaotic?

Now we see 2800-3400 steps.

What has happened?
The single initially on cell produces an extended transient, lasting 2780 steps. At this point, a regular recurring structure emerges. (The part to the left expands forever, but the pattern is now predictable.)

Is this organized or chaotic?

Wolfram calls this class neither chaotic nor ordered, but COMPLEX (more on this in a second).

This particular rule has been proven to be universal, "effectively capable of emulating any other system" (http://mathworld.wolfram.com/Universality.html)

c.f. a Universal Turing Machine is capable of simulating the operation of any Turing machine on any input.

Q: What does a given CA do when started from random initial conditions?

Each initial condition produces a different result, but a given CA ruleset tends to produce dynamics that fall into one of four classes.

Class 1: "Homogenous"
Behavior is very simple and almost all initial conditions lead to exactly the same uniform final state.

paraphrased following Wolfram A New Kind of Science (2002), p 231

Class 2: "Regular"
There are many different possible final states, but all of them consist just of a certain set of simple structures that either remain the same forever or repeat every few steps.

Class 3: "Chaotic"
The behaviour is more complicated and seems in many respects random, although triangles and other small-scale structures are essentially always at some level seen.

Class 4: "Complex"
A mixture of order and randomness; localized structures are produced which on their own are fairly simple, but these structures move around and interact with each other in very complicated ways.

NOTE: Not always possible to easily classify a rule. Sometimes there are "borderline cases" where a given rule set demonstrates, e.g. some Class 2 and some Class 4 behaviour.

NOTE: Wolfram suggests all Class 4 CA are Universal ("effectively capable of emulating any other system")? But this is not proven.

Meinhardt, H. (1995).
The Algorithmic Beauty of Sea Shells.
Springer Verlag. (p. 179, 180)

Simple model of two chemicals, U and V, that diffuse, react and decay.

One chemical reaction: U + 2V → 3V

Parameters: How quickly the reaction takes place compared to diffusion, how quickly U and V decay. etc.

Simple rules can produce complex and life-like collective behaviour!

• Turing, A. M. (1952). The Chemical Basis of Morphogenesis. Philosophical Transactions of the Royal Society of London B 237 (641): 37–72.
• http://mrob.com/pub/comp/xmorphia/

http://www.wired.com/2011/02/turing-patterns/

We can define a value λ that corresponds to the proportion of rules that produce a particular state.

$λ = \frac{(K^{N} - n)}{K^{N}}$

• K = number of states = 2
• N = number of neighbours = 3
• n = number of rules that result in an arbitrarily selected "quiescent" state (we'll pick white)

Christopher G. Langton (1990). Computation at the edge of chaos. Physica D 42. doi:10.1016/0167-2789(90)90064-V.

Most rules produce non-complex results.

Only when the system is "tuned" to have precisely the right set of rules do we see the interesting behaviour.

Self-organized criticality
Could any natural processes "self-tune" or "self-organize" so as to autonomously approach complexity?

It involves the creation of artificial things.

These things serve multiple purposes:

1. They allow us to test hypotheses and explore the implications of theories in contexts that are much more simple than those found in Nature.
2. They also call into question some of the limitations of science as currently practiced. (If we can't predict even the statistics of CA rule 110, Can we expect to be able to formulate some nice theoretical description of how the brain works? Or of how organisms develop?)
3. They provide target systems to try to apply new methods of analysis and description.

Developing and studying artificial systems can be helpful in trying to understand the world around us.

• thought experiments
• sufficiency proof
• intuition pump
• creativity pump