Cellular Automata Cellular Automata
Moreno Marzolla
Dip. di Informatica—Scienza e Ingegneria (DISI) Università di Bologna
http://www.moreno.marzolla.name/
Complex Systems 2
Complex Systems 3
Cellular Automata
● Originally developed in the 1940s by Stanislaw Ulam and John von
Neumann
● Interest in CAs
expanded in 1970 after
Conway's Game of Life John von Neumann (1903—1957) Stanislaw Ulam
(1909—1984)
Complex Systems 4
Cellular Automata (CA)
● A regular grid of cells, each in one of a finite number k of states (e.g., k = 2 for binary states)
● At time t = 0 an initial state for each cell is selected
● A new generation is created (advancing t by 1),
according to some fixed rule that determines the new state of each cell in terms of the current state of the cell and the states of the cells in its neighborhood
– The rule for updating cell states is the same for each cell and does not change over time, though exceptions are known (e.g., stochastic CAs, asynchronous CAs...)
Complex Systems 5
Cellular Automata
● We will generally consider CAs over a linear square grid lattice (i.e., an array or matrix)
● Other topologies can be considered
– Irregular
– Hexagonal
– …
● Example: Game of Life on an hexagonal lattice
Complex Systems 6
Elementary Cellular Automata
Complex Systems 7
1-Dimensional CA
● “Infinite” linear array of cells
● Each cell can be in any of k states
● The neighborhood of each cell in general consists of r cells on the left and on the right
– Usually r = 1, immediate neighbors
– More complex neighborhoods can be considered
Cell
Neighbors (r = 1)
... ...
Complex Systems 8
Finite vs Infinite Grid
● Although the CA grid is logically infinite, it is usually represented using a finite array (or matrix)
● Cells on the edges can be handled in several ways
– Allow the values of the cells on the border to remain constant; or
– Define neighborhoods differently for these cells (e.g., say that they have fewer neighbors), or
– Use a toroidal arrangement
1-D array → Ring
2-D array → Torus
Complex Systems 9
Elementary CA (k = 2, r = 1)
● The binary state ct+1(i) of cell i at time t + 1 is
determined by the states of cells {i - 1, i, i + 1} at time t ct(i - 1), ct(i), ct(i + 1)
i -1 i i+1
Time t i
t + 1
Complex Systems 10
Example
● Rules
● Example (8 cells with wrap-around)
t = 0
t = 1
t = 2
t = 3
t = 4
ct(i-1) ct(i) ct(i+1)
ct+1(i)
Complex Systems 11
Example
● Evolution of the previous CA on a larger array
Complex Systems 12
Wolfram Canonical Enumeration
● With binary state space and r=1, there are 2^8 = 256 possible elementary CAs
● We can encode the rule table with a single 8-bit number by reading the rightmost column top-to- bottom
2
4
8
16
Rule 30 CA
Complex Systems 13
Wolfram Canonical Enumeration
● With binary state space and r=1, there are 2^8 = 256 possible CAs
● We can encode the rule table with a single 8-bit number by reading the rightmost column top-to- bottom
2
4
8
32
Rule 110 CA
64
Complex Systems 14
CAs as Complex Systems:
Wolfram Classification
● Class I
– Always evolve to a homogeneous arrangement, with every cell being in the same state, never to change again
● Class II
– Form periodic structures that endlessly cycle through a fixed number of states
● Class III
– Form aperiodic, random-like patterns similar to the static white noise on a bad (analog) television channel
● Class IV
– Form complex patterns with localized structure that move through space and time. Patterns eventually become
homogeneous, like Class I, or periodic, like Class II
Elementary CA rules 0—49
Elementary CA rules 50—99
Elementary CA rules 100—149
Elementary CA rules 150—199
Elementary CA rules 200—255
Complex Systems 20
Wolfram’s Classification: Class 1
Rule 40 Rule 172 Rule 234
Slide credit: Ozalp Babaoglu
Complex Systems 21
Wolfram’s Classification: Class 2
Slide credit: Ozalp Babaoglu
Complex Systems 22
Wolfram’s Classification: Class 3
Rule 30 Rule 101 Rule 146
Slide credit: Ozalp Babaoglu
23
Wolfram’s Classification: Class 4
Slide credit: Ozalp Babaoglu
Complex Systems 24
Class II CAs
● Class II CAs are repetitive and bear resemblance to programs that execute in an infinite loop
while ( TRUE ) {
for (i=0; i<10; i++) print i;
}
i = 0;
while ( TRUE ) { print i;
i = i + 1;
}
Simple periodicity
Unbounded periodicity: on hypothetical machines with infinite precision this fragment executes forever and is not periodic. In fact, this fragment does repeat when I overflows and starts back at zero; the exact value where this
happens is machine-dependent
Complex Systems 25
Langton's λ metric
● Is defined as the fraction of rules mapping into the non-quiescent state
● For elementary CAs, it is the fraction of rules
mapping to one in the rule table
2
4
8
16
Rule 30 CA, λ = 4/8
Complex Systems 26
Langton's λ metric
● Is defined as the fraction of rules mapping into the non-quiescent state
● For elementary CAs, it is the fraction of rules
mapping to one in the rule table
2
4
8
32
Rule 110 CA, λ = 5/8
64
Complex Systems 27
Langton's λ metric and CA classification
Complex Systems 28
Examples
● NetLogo implements elementary CAs in Sample
Models → Computer Science → CA 1D Elementary
Complex Systems 29
Two-dimensional CAs Game of Life
Complex Systems 30
Two-dimensional CAs
● CAs can be defined over higher-dimensional grids
● For two-dimensional CAs, different types of neighborhoods can be defined
The eight gray cells form the Moore neighborhood for the
red cell
The four dark gray cells form the von Neumann neighborhood for the red cell; the
extended von Neumann neighborhood includes the light gray cells
Complex Systems 31
Conway's Game of Life
● Developed by the British mathematician John Horton Conway in 1970
● Infinite two-dimensional orthogonal grid of square cells, each of which is in two states (alive or dead)
● Moore neighborhood
● Rules:
– Any live cell with fewer than two live neighbours dies
– Any live cell with two or three live neighbours lives on to the next generation
– Any live cell with more than three live neighbours dies
– Any dead cell with exactly three live neighbours becomes a live cell
● The initial pattern constitutes the seed of the system
● Each generation is created by applying the above rules simultaneously to every cell
– The discrete moment at which this happens is sometimes called a tick
John Horton Conway (1937— )
Complex Systems 32
Some notable patterns
Still lifes
Oscillators
Spaceships
Glider Lightweight Spaceship
Source: http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
Complex Systems 33
Some notable patterns
● Conway conjectured that no pattern can grow indefinitely
● A team from the Massachusetts Institute of Technology proved he was wrong
– The "Gosper glider gun" produces its first glider on the 15th generation, and another glider every 30th generation from then on
Source: http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
Complex Systems 34
Logical operations implemented in Life
Logical Not Logical And Logical Or
Complex Systems 35
Universality
● Both CA rule 110 and Life are Turing complete
– M. Cook, Universality in Elementary Cellular Automata, Complex Systems 15: 1-40.
● Below is a Turing machine implemented with a Life pattern in Golly (http://golly.sourceforge.net/), Patterns → Life → Signal Circuitry → Turing-Machine-3-state.rle
36
von Neumann Universal Constructor
Pesavento, Umberto (1995) An implementation of von Neumann's self-reproducing machine. Artificial Life 2(4):337-354; See
http://en.wikipedia.org/wiki/Von_Neumann_universal_constructor for details and links to the golly rule file (requires approximately 6 x 10^10 timesteps for replication)
Complex Systems 37
Another CA that replicates itself
Patterns → JvN → Boustrophedon-replicator.rle
Complex Systems 38
Some practical applications of CAs
Complex Systems 39
Stochastic (Elementary) CA
● In a stochastic elementary CA,
each rule is the probability that the center cell is black
● In general, in a stochastic CA the new cell states may depend on a random outcome
0.0
1.0
0.5
0.2
0.9
0.7
0.7
0.0
Complex Systems 40
Percolation model 1
(site percolation)
● Three states, two-dimensional CA, von Neumann neighborhood
– White: empty cell
– Blue: blocked cell
– Yellow: liquid
● Initial configuration
– Each cell is empty with probability p, blocked with probability 1 - p
– One designated cell (e.g., at the center of the matrix) contains liquid
● One rule
– A white cell with at least one yellow neighbor turns yellow
Complex Systems 41
Percolation model 1
● Suppose we “pour” liquid on the top row. What is the probability that the liquid eventually reaches the
bottom row?
Percolate Does not percolate
Complex Systems 42
Percolation model 1
● It turns out that there is a critical value p* for the
parameter p (the probability that a cell is empty) s.t.
the percolation probability increases sharply for p > p*
– For square lattices, the site percolation threshold is p* ~ 0.59
p Percolation
probability 1
1 p*
Complex Systems 43
Percolation model 2
● Percolation of a viscous liquid in a porous medium
– E.g., oil in sand
● Three states, 1D stochastic CA
– 0: solid, 1: empty, 2: filled
● Solid and empty squares are arranged in a checkerboard configuration
● Liquid percolates top-down through the empty squares with probability p
Empty
Solid
Liquid time
Percolation model 2
● NetLogo Sample Models → Earth Science → Percolation
p = 0.5 p = 0.6 p = 0.7
Complex Systems 45
Percolation model 2
● Note that for percolation model 2 we need to update the cells by row (one row at each time step, moving downwards)
● We have initially said that in a CA all cells must be updated concurrently at each timestep
● It turns out that we can implement the percolation model with global concurrent updates by using a slightly more complex cell state
– Any idea?
Complex Systems 46
Percolation model 2
● Cell state is {soil, empty, newliquid, liquid}
● Initial state:
– Checkerboard pattern of soil, empty
– Empty cells on the first row are set in state newliquid
● Update rule
if ( this.state == newliquid ) then this.state ← liquid;
elseif ( this.state == empty ) then
if ( NE.state == newliquid and NW.state == newliquid ) then this.state ← newliquid with prob. 1-(1-p)^2
elseif ( NE.state == newliquid or NW.state == newliquid ) then this.state ← newliquid with prob. p
endif endif
Complex Systems 47
Percolation model 3 (forest fire)
● A forest is modeled as a rectangular grid
– Each contains a tree with probability P, is empty with probability 1 - P
● Fire starts at the left edge
– Fire propagates along four directions: if a tree catches fire, the fire propagates to adjacent trees on the left, right, top and bottom of the current tree
– Fire does not propagate through empty patches
● There is a critical density P* such that the fire can reach the right edge of the forest
● NetLogo Sample Models → Earth Science → Fire
48
Forest Fire
Density P = 0.57
Density P = 0.60 Density P = 0.59
Density P = 0.58
Complex Systems 49
Morphogenesis
● In 1952 Alan Turing investigated how non-
uniformity (stripes, spots, spirals, etc.) may arise out of a homogeneous initial state
– Reaction–diffusion theory of morphogenesis
– A. M. Turing, The Chemical Basis of Morphogenesis,
Philosophical Transactions of the Royal Society of London.
Series B, Biological Sciences, Vol. 237, No. 641. (Aug. 14, 1952), pp. 37—72
Alan M. Turing (1912—1954)
Complex Systems 50
-validated-60-years-after-his-death
http://www.pnas.org/content/early/2014/03/05/1322005111
Complex Systems 51
Morphogenesis
● The original reaction-diffusion model proposed by Turing resembles a Continuous Spatial Automaton
– Continuum of locations
– The state of a location is any of a finite number of values
– Time can be continuous, and in this case the state evolves according to differential equations
● The model can be approximated by a CA, and yields similar patterns
Complex Systems 52
Morphogenesis
● Two states
– U—undifferentiated (not colorful)
– D—differentiated (colorful)
● Each D-cell secrets inhibitor (I) and activator (A)
● Each cell receives activator
secreted by D-cells in its inner neighborhood, and inhibitor
secreted by D-cells in its outer neighborhood
– The new state is determined by the weighted sum of inhibitor and
activator received
X
Cell X receives the
inhibitors secreted by D cells in this region
Cell X receives the activators secreted by D cells in this region
Complex Systems 53
Morphogenesis
● Netlogo Sample Models → Biology → Fur
Complex Systems 54
Cone Shell Patterns
● The shell grows linearly at its borders
● Pigmentation at a specific point is influenced by the pigmentation around the point of growth
● Is it a 1-D CA?
– Yes, to some extent
– Although pigmentation is not really discrete, but subject to chemical diffusion
Conus textile shell
Slide Credit: prof. Franco Zambonelli Rule 30 CA
Complex Systems 55
B-Z Reaction
● The Belousov-Zhabotinsky (B-Z) reaction is an
unusual chemical reaction: instead of moving towards a single equilibrium state, it oscillates between two
such states
● States are integers in 0..max-state
– 0 = “healthy”, max-state = “sick”, anything else = “infected”
● Rules
– A cell that is sick becomes healthy.
– A cell that is healthy may become infected, if enough of its eight neighbors are infected or sick
– A cell that is infected computes its new state by averaging the states of itself and its eight neighbors
Complex Systems 56
B-Z Reaction
● Netlogo Sample Models → Chemistry & Physics → Chemical Reactions → B-Z Reaction
Complex Systems 57
An interesting book on CA
Tommaso Toffoli and Norman Margolus, Cellular Automata Machines—A new Environment for Modeling, MIT Press, 1987, ISBN 9780262200608.
http://mitpress.mit.edu/books/cellular-automata-machines
