7 Celluar Automata
Cellular automata are discrete dynamical systems.
Their space is represented by a uniform grid, with each cell containing a value;
time advances in discrete steps and the rules of change of each cell is determined by the states of its closest neighbour cells.
Different celluar automata are implemented an can be simulated
- Conway’s Life
- Wofram Universe
- Disease Spread
- three implementations of Per Bak’s sand piles
- two Circular rooms
- Spreading Bugs
- Diffusion
- three advections automats
- two diffusion based automats to generate leopard skins
The automat can be selected by the pull down menu. The active one is diplayed.
7.1 Life
Life was devised in 1970 by John Horton Conway.
The automat knows two states: dead (0, off) or alive (1, on).
The neighbourhood of a cell is defined by the eight surrounding cells.
The rules
- if, for a given cell, the number of neighbours is exactly two, the cell maintains its status quo into the next generation. If the cell is on, it stays on, if it is off, it stays off.
- if the number of on neighbours is exactly three, the cell will be on in the next generation.
This is regardless of the cell’s current state.
- if the number of on neighbours is smaller than or equal to 1 or greater than or equal to 4 the cell will be off in the next generation.
7.2 Universe according to Stephan Wolfram
To understand the principle, we will first look at Stephen Wolfram’s one-dimensional model.
Stephen Wolfram (*1959) is a British physicist. He is the developer of Mathematica and the search engine Wolfram Alpha.
His book ”A New Kind of Science (2002)” describes many applications of cellular automata.
A simple example is the following automaton: We divide the space into a number of cells (e.g. 150).
Each cell can assume the state dead or alive (0 or 1). Now you can start with a live cell in the centre.
The constellation in the next step results from the following rules
- A cell receives the new state 1 if there were one or two living cells in the block of three consisting of itself and its two neighbours.
- A cell receives the new state 0 if there were zero or 3 living cells in the block of three consisting of itself and its two neighbours.
If the last cell is reattached to the first (ring), the border cells also have 2 neighbours. You can then calculate more generations without getting edge effects.
The meaning of the headline is just the situation of the cell under regard (in the center of the triplet).
So 1 1 0 means: the left neighbor is alive (1), the cell itself is alive (1) and the right neigbor dead (0).
The rules are defined through the transistion of all eight triplets to their results.
In this case we see the rule 0 1 1 1 1 1 1 0, meaning that 1 1 1 results in 0 and 1 0 1 results in 1.
The complete transitions are:
| 1 1 1 | 1 1 0 | 1 0 1 | 1 0 0 | 0 1 1 | 0 1 0 | 0 0 1 | 0 0 0 |
|---|---|---|---|---|---|---|---|
| ↓ | ↓ | ↓ | ↓ | ↓ | ↓ | ↓ | ↓ |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
Finally the number of rules is the span that can be addressed by eight digits or bits wich results in a binary number (represented by the bottom line of the above table). There are therefore 256 rule sets in total.
Wolfram used tha principle and interpreted the eight-digit binary number as a decimal number.
This allowed him to simply ”name” all possible rules from 0 to 255.
The above rule is then number 126 (binary 0 1 1 1 1 1 1 0).
7.3 Disease
This automat simulates the spread of a disease.
A cell can either be susceptiple (0), infected (1), ill (2) or immune (3).
The automat is not fully deterministic !!
The rules
- if a cell is susceptible it will be infected with a certain probability depending on the number of infected neighbours.
The cell will be infected if the number of neighbours multiplied with a random number between 0 and 1 exceeds 0.9.
- infected cells become ill with a probability of 60%
- ill cells stay ill (50% probability), become immune (25% probability) or susceptible (25% probability)
- immune cell become susceptible with a probability of 5% to represent deaths and births
7.4 Per Bak’s sandpile model
Per Bak’s sandpile model is an example of self-organized criticality.
It is a cellular automat whose configuration is determined by the number of sandgrains on a cell.
The rules
- a grain of sand is added at a randomly selected cell
- a cell with more than 3 sand grains becomes unstable and topples by distributing one grain of sand to each of it’s four neighbours.
This may cause unstable cells in the neighbourhood. An avalanche is born.
- if any avalanche dies out, another grain of sand is added to a randomly selected cell.
There are two models implemented:
- 4 neighbours. A cell with more than 3 sand grains becomes unstable and topples by distributing one grain of sand to each of it’s four (left, right, up and down) neighbours.
- the same model but with 8 neighbours. A cell with more than 7 sand grains becomes unstable and topples by distributing one grain of sand to each of it’s eight neighbours.
7.5 Circular Room
The circular room is a nice automat to demonstrate self organization.
It is most impressive to start from a randomized initial state.
The rules
- The N states are circulary arranged: The state N is identified with state 0. Each cell has 4 neighbours.
- The state of a cell is increased by one if at least one neighbour has the state of the cell plus 1.
The Circular Room is implemented for 6 and 20 states.
7.6 Bug Spread
This is an example of an automat combined with a differential equation model. The are two state variables, the number of bugs B within the part of the forest (cell) and the mean age A of the trees in this part of the forest. The differential equations for the bug growth, the aging of the forest and the bug spread are given by
\[\begin{eqnarray*} \frac{\partial B}{\partial t} &=& r \cdot A \cdot \left ( 1 - \frac{B}{K} \right ) \cdot B - \mu \cdot \frac{B^2}{B^2+M^2} + D_a \frac{\partial^2 B}{\partial x^2} \\ \frac{\partial A}{\partial t} &=& \alpha \cdot \left (1-A \right) - \beta \cdot \left (\frac{B}{K} \right )^3 \cdot A \end{eqnarray*}\]
The diffusive spread is realized by an automat scheme with an additional wind direction from west to east.
\[\begin{eqnarray*} \Delta B(i,j) &= & -4 \; \varepsilon_0 \cdot B(i,j)\cdot \Delta t \\ \Delta B(i-1,j) &= & \varepsilon_0\cdot(1-\varepsilon_r) \cdot B(i,j) \cdot \Delta t \\ \Delta B(i+1,j) &= & \varepsilon_0\cdot(1+\varepsilon_r) \cdot B(i,j) \cdot \Delta t \\ \Delta B(i,j-1) &= & \varepsilon_0 \cdot B(i,j) \cdot \Delta t \\ \Delta B(i,j+1) &= & \varepsilon_0 \cdot B(i,j) \cdot \Delta t \end{eqnarray*}\]
\((i, j)\) denotes the cell in the \(i\)-th row and \(j\)-th column. The differential equations are solved with Euler’s scheme. The time step \(\Delta t\) for the calculations is \(0.01\).
Parameters
| Parameter | Value | Unit | Meaning |
|---|---|---|---|
| r | 54.75 | 1/y | growth in old forest |
| K | 5000 | bugs/cell | capacity of bugs |
| \(\mu\) | 36500 | bugs/cell/y | predation by birds |
| M | 500 | bugs/cell | bug density controlling predation |
| \(\alpha\) | 0.15 | 1/y | aging factor of forest |
| \(\beta\) | 1.7 | 1/y | damage of forest |
| \(\varepsilon_0\) | 1.0 | 1/y | maximum part of bugs to diffuse |
| \(\varepsilon_r\) | 0.9 | - | parameter for direction (wind force) |
The simulation shows the number of bugs per cell.
It takes several hundred generations until the dynamical state of the system appears.
Unfortunately this example is very slow due to the numerical solver of the differential equations.
7.7 Diffusion
Demonstration of diffusion.
The simulation should be started with a random filling or a small filled area (circle or square).
The color table is fixed to white&black. Filling can be done by a left mouse click.
7.8 Advection
Demonstration of advective transport.
The simulation should be started with a small filled area (circle or square).
The color table is fixed to white&black. Filling can be done by a left mouse click.
Three scenarios are implemented:
- 1D advection (1 cell per time step): simulation of advection without numerical diffusion.
The advection velocity is set to one cell per time step in x direction
- 1D advection (0.1 cell per time step): simulation of advection demonstrating the effect of numerical diffusion.
The advection velocity is set to 0.1 cell per time step in x direction.
- 2D advection (0.1 cell per time step): simulation of advection demonstrating the effect of numerical diffusion.
The advection velocity is set to 0.1 cell per time step in north-east direction.
7.9 Leopard
The model describes a mechanism that can describe how the coat pattern of a leopard can develop through diffusion processes. The model considers two substances with different properties.
The Activator: Substance that produces the expression of a characteristic (pigment production) with the following characteristics:
- autocatalytic (self-reinforcing)
- generates inhibitor
- diffuses slowly (localized)
The Inhibitor: Substance that suppresses expression of the characteristic
- suppresses activator production
- diffuses quickly (long-range)
Equations
\[\begin{eqnarray*} \frac{\partial a}{\partial t} &=& \frac{a^2}{b} \;-\; \mu_ a \cdot a \;+\; \varepsilon_a \;+\; D_a \, \frac{\partial^2 a}{\partial x^2} \qquad Activator\\[2ex] \frac{\partial b}{\partial t} &=& a^2 \;-\; \mu_b \cdot b \;+\; \varepsilon_b \;+ \;D_b \, \frac{\partial^2 b}{\partial x^2} \qquad Inhibitor \end{eqnarray*}\]
Parameters
| Parameter | Meaning |
|---|---|
| \(μ_a = 1.0\) | Decay rate of the Activator |
| \(μ_b = 1.0\) | Decay rate of the Inhibitor |
| \(ε_a = 0.01\) | Basic production rate of the Activator |
| \(ε_b = 0.01\) | Basic production rate of the Inhibitor |
| \(D_a = D_b/8.0\) | Diffusion constant of the Activator (fixed ratio) |
| \(D_b = 4.0\) or \(8.0\) | Diffusion constant of the Inhibitor |
There are two models selectable with \(D_b\) = 4.0 and \(D_b\) = 8.0.
7.10 Common Settings
7.10.1 Color Table
The different automata look nicest with their default color table, but the colortable can be changed for some automata and is displayed in the color bar. The automata with discrete states are best visualized by the discrete color table. The number of colors displayed in the color bar corre- sponds to the number of states of the active automat.
7.10.2 Cells per row
The number of cells per row can be selected. The automat field is then built quadratic. The higher the number the slower the simulation runs.
7.10.3 View of the world
The world can either be assumed as closed (Torus) in this case the first row is neighbour of the last one and the first column is neighbour of the last column. If the case of a plain world boundary cells have less neighbours.
7.11 Common Functions
7.11.1 Show
If Show is switched on, every generation is shown, if switched off the picture is not actualized until Show is switched on again.
This is useful if only higher generation numbers are of interest because the simulation becomes quite faster without displaying.
7.11.2 Run
Run starts the simulation. The generation is displayed in the info window.
The simulation can be stopped by Interrupt .
7.11.3 Step
Step calculates the next generation
7.11.4 Interrupt
Interrupt stops the simulation.
7.11.5 Clear
Clear sets all cells to zero.
7.12 Setting the initial states
7.12.1 Single Cells
The initial state of the automat can either be set by mouse within the automat field.
Depending on the number of states the following settings are possible
- left mouse click sets cell to 1
- <Shift>+ left mouse click sets the cell to 2
- <ctrl>+ left mouse click sets the cell to 3
- middle or right mouse click resets the cell to 0
7.12.2 Randomfill
Randomfill fills the field with random values depending on the number of possible states.
7.12.3 Fill
All cells are filled with the selected fill value.
7.13 Load & Save
It is possible to save a configuration by [Save] in a file.
These files get automatically the extension .lif and are stored normally in <Path to Mathtools>/mftfiles.
The configuration can be loaded by [Load]
7.14 PS print/Print
A Postscript output is generated and stored in <Path to Store Directory>/plots.
The PS-files are named automatically.