SWEN90004
Modelling Complex Software Systems
Lecture Cx.05
Cellular Automata I: 1D and 2D CAs
Artem Polyvyanyy, Nic Geard
artem.polyvyanyy@unimelb.edu.au;
nicholas.geard@unimelb.edu.au
Semester 1, 2021
1 / 42
Objectives
understand the limits of mathematical models
introduce cellular automata – a bottom-up approach to
modelling complex systems
explore the behaviour of 1- and 2-dimensional CAs.
2 / 42
Outline
Motivation
1D Cellular Automata
2D Cellular Automata
3 / 42
From macro to micro. . .
Complex systems are systems whose behaviour emerges from inter- actions between many individual parts:
Lotka-Volterra model–
parts = animals (predator and prey)
interaction = predation (eating of prey by predator)
SIR disease model–
parts = people (susceptible, infectious and recovered)
interaction = disease transmission (from infectious to
susceptible people)
4 / 42
From macro to micro. . .
The ODE models of these systems required us to represent their state in terms of global (or macro) variables, and to define update rules in terms of how these global variables changed over time:
Lotka-Volterra model:–
variables = predator/prey population size
update = in terms of rates of birth, death and predation
SIR disease model:–
variables = proportion of the population in each disease state update = in terms of rates of infection and recovery
5 / 42
From macro to micro. . .
However, in order to build these ODE models, we had to make assumptions about our systems. Both models required us to assume that all individuals in our subpopulations (eg, predators, or suscepti- bles) were identical, and that all individuals in our population had an equal chance of interacting with each other.
6 / 42
From macro to micro. . .
In discussing possible problems with these models, these assumptions kept coming up as limitations:
Lotka-Volterra model:–
some predators/prey might be stronger/weaker than others
some predators/prey might be faster/slower than others
predaotrs/prey populations might have non-uniform spatial
distribution
SIR disease model:–
some age groups (eg, children) might be more susceptible/infectious
populations might have non-uniform spatial distribution (eg, 90% of our population might be vaccinated, but if the 10% who are not all live in the same suburb, that is a high-risk subpopulation)
We could extend our ODE models to reflect this heterogeneity (vari- ation between individuals), but the number of equations and param- eters required would explode rapidly.
7 / 42
From macro to micro. . .
For the next few weeks, we are going to explore approaches to modelling that are capable of representing this heterogeneity in populations:
cellular automata models agent based models
network models
These models will be computational rather than mathematical
8 / 42
Implementing a spatial model
Consider an SIR model, in which each person in our population has a fixed location on a square lattice (grid):
what is the most appropriate data structure?
how could you represent states?
how do you determine who interacts with who? how are states updated?
9 / 42
Outline
Motivation
1D Cellular Automata
2D Cellular Automata
10 / 42
Cellular Automata
Cellular Automata (CA) are a type of discrete dynamical system that exhibit complex behaviour based on simple, local rules.
Developed in the 1940s by John von Neumann and Stanisłav Ulam at Los Alamos National Laboratory, who were interested in self-replicating robots (von Neumann) and crystal growth (Ulam).
FigureJohn von Neumann, Richard Feynmann & Stanisłav Ulam, Los Alamos, 1940s
11 / 42
Cellular Automata
automaton: a theoretical machine that updates its internal state based on external inputs and its own previous state
Figure
cellular automaton: an array of automata (cells), where the inputs to one cell are the current states of nearby cells
Figure
12 / 42
Cellular Automata
InaCA:
time is discrete (like the logistic map)
space is discrete: typically a 1D or 2D grid (3D also possible)
system state is discrete: each component of a system is in one
of a finite set of states (eg, ON or OFF); therefore the entire
system has a finite, countable number of states
update rules are defined in terms of local interactions between
components
13 / 42
Cellular Automata – applications
14 / 42
1D Cellular Automata—the simplest case!
Figurespace: a one-dimensional grid of cells
Figurestate: each cell takes one of two states
Figureneighbourhood: the cell itself and its two adjacent neighbours (K = 3)
15 / 42
1D Cellular Automata—the simplest case!
Figuretime: discrete generations (time steps)
Figureupdate: use the state of the neighbourhood in the previous generation
16 / 42
1D Cellular Automata—the simplest case!
Figurethere are 2K possible combinations of neighbourhood states
Figureeach of these combinations determines the state of the target (centre) cell in the next generation
17 / 42
1D Cellular Automata—the simplest case!
Figurewe have a lookup table to determine the next state of each of the cells
What about the edges?
18 / 42
1D Cellular Automata—behaviour
We will use NetLogo to explore the behaviour of some different rules
19 / 42
More formally
Each finite automata consists of a finite set of cell states Σ, a finite input alphabet α and a transition function ∆, which is a mapping from the set of neighbourhood states to the set of cell states:
∆ = ΣN → N
The state of a neighbourhood is a function (eg. cross product) of the states of the automata covered by the neighbourhood template. Thus, the input alphabet α for each automaton consists of the set of possible neighbourhood states.
Let K =| Σ | (the number of cell states).
The size of α is equal to the number of possible neighbourhood states:
|α| = |∆| = |ΣN| =KN
20 / 42
More formally
To define a transfer function ∆, a unique next state in Σ must be associated with a possible neighbourhood state.
Since there are K =| Σ | choices of states to assign as the next state for each of the | ΣN | possible neighbour states, there are KKN possible transitions functions ∆ that can be defined.
DNK is the set of all possible transitions functions ∆ which can be defined using N neighbours and K states.
21 / 42
More formally
For example
Consider a 2-dimensional cellular automata using 8 states per cell; a regular lattice with a five cell local neighbourhood (north, south, east, west).
Here, K = 8 and N = 5, so there are:
| ∆ |= KN = 85 = 32768 possible neighbourhood states.
For all of these neighbouhood states, there is a choice of 8 different states for the next cell state under ∆, so there are:
DNK = K K N = 885 ≈ 1030000 possible transitions functions.
22 / 42
Naming CA rules
There are KKN = 223 possible rules for updating the canonical 1D CA (K = 2; N = 3).
We can interpret the sequence of 8 output values as base-2 number:
0×27+1×26+0×25+1×24+1×23+0×22+1×21+0×20 = 90 ie, this is Rule 90
23 / 42
Exploring CA rules
Many of the 256 rules are trivially equivalent to each other: simple transformation of the underlying geometry:
mirror: reflection through a vertical axis.
complement: exchange the roles of 0 and 1 in the definition
Some of the 256 elementary rules are identical – simply by renaming the states or reversing right and left – so the number of essentially different elementary rules is smaller (only 88).
24 / 42
Rule 30
Rule 30 displays aperiodic, chaotic behaviour. . .
Figure
25 / 42
Rule 30
. . . that bears similarity to patterns found in nature
FigureA Textile Cone Snail (Conus textile), Cod Hole, Great Barrier Reef, Australia Photographer: Richard Ling richard@research.canon.com.au
26 / 42
Rule 110
Rule 110 is Turing complete; ie, capable of universal computation
Figure
http://nicolas.brodu.net/en/programmation/mesincom/index.html
27 / 42
Discrete time dynamics
Many of our concepts from last week’s ODE models also apply here. . .
We are interested in the long term behaviour of the system: what happens as t → ∞?
Our state space (the set of all possible states in the system) is discrete and finite, and our trajectories are sequences of states We can observe transients, fixed point and limit cycle attractors
the states that lead to each attractor constitute its basin of attraction
Figure
28 / 42
Wolfram classes
“. . . many (perhaps all) CA fall into four basic behaviour classes”
Stephen Wolfram, 1984
Figure
29 / 42
Outline
Motivation
1D Cellular Automata
2D Cellular Automata
30 / 42
2D Cellular Automata
A 2D CA is similar to a 1D CA, except that we have to choose how to define our neighbourhood and our update rules.
Two common neighbourhoods are:
the Von Neumann neighbourhood (left):
{(0, 0), (±1, 0), (0, ±1)}
the Moore neighbourhood (right): {−1, 0, 1} × {−1, 0, 1}
Figure
31 / 42
Conway’s Game of Life
Invented by British mathematician, John Conway in 1970, inspired von Neumann’s earlier attempts to construct a self-replicating machine
Like Rule 110, the Game of Life is Turing complete
32 / 42
Conway’s Game of Life
The rules of Life:
each cell can be alive (black) or dead (white)
if an alive cell has fewer than 2 living neighbours, it
dies—loneliness
if an alive cell has more than 3 living neighbours, it
dies—overcrowding
if an alive cell has either 2 or 3 living neighbours, it stays
alive—survival
if a dead cell has exactly 3 living neighbours, it comes
alive—reproduction
The initial pattern of living cells constitutes the first generation of the system. The rules are then applied simultaneously to every cell in the system to produce the second generation, and so on.
What is the long term behaviour of the system?
33 / 42
The rules of Life
Loneliness
If an alive cell has fewer than 2 living neighbours, it dies
34 / 42
The rules of Life
Overcrowding
If an alive cell has more than 3 living neighbours, it dies
35 / 42
The rules of Life
Survival
If an alive cell has either 2 or 3 living neighbours, it stays alive
36 / 42
The rules of Life
Reproduction
If a dead cell has exactly 3 living neighbours, it comes alive
37 / 42
Conway’s Game of Life
We will use NetLogo to explore the behaviour of some different initial conditions
38 / 42
Conway’s Game of Life
over time, organised patterns emerge:
Figure
39 / 42
Conway’s Game of Life
can be used to implement information-carrying signals and logical operations on those signals
Figure
40 / 42
Conway’s Game of Life
The Game of Life (and CA more generally) is a ‘classic’ example of a complex system:
many components
local interactions
decentralised control
parallel processing
emergent global behaviour self-organisation
They still make some strong assumptions that may limit their applicability as models of real systems however. . .
all updates happen synchronously all updates are deterministic
Next lecture we will discuss how we could create CA models of more realistic scenarios: predator-prey interactions and the spread of an infectious disease.
41 / 42
Additional references
Gardner, M (1970) Mathematical Games—The fantastic combinations of John Conway’s new solitaire game “life”. Scientific American 223:120–123.
Wolfram, S (1984) Computation theory of cellular automata. Communications in Mathematical Physics 96:15–57
Langton, C (1986) Studying artificial life with cellular automata. Physica D 22:120–149
Flake, GW (1998) The Computational Beauty of Nature. MIT Press, Cambridge MA (chapter 15)
Wolfram, S (2002) A New Kind of Science. Wolfram Media, Champaign IL
Schiff, JL (2008) Cellular Automata: A Discrete View of the World.
Wiley-Interscience, Hoboken NJ
Shiffman, D (2012) The Nature of Code. http://natureofcode.com/ (chapter 7)
42 / 42