Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
ACSE – 1 Assessment 1
Cellular Automata
Cellular automata are a set of mathematical models consisting of a lattice of cells, each in
a given state, along with a set of rules for how the cell states will change, based on their own
conditions and the conditions of their neighbours. You will implement two well known automata,
Wolfram’s Rule 30 and the Game of Life.
1 Wolfram’s Rule 30
Figure 1: The onset of chaos in Rule 30
Wolfram’s Rule 30 is possibly the most famous one-dimensional cellular automaton. At each
time level the state of a cell depends on its value at the last level and that of its neighbours
according to the following pattern
The gure plots the progression of the state with one cell on initially with time increasing
downward. Note that the table above has the left column ordered by the equivalent binary value,
111, 110, 101 etc. The right hand column then translates to 00011110, or in decimal 30, hence
the choice of name.
Looking at the values of the centre cells, they are hard to predict, indeed Wolfram himself
proposed they could be used in pseudorandom number generators.
Boundaries in a nite lattice can either be dealt with by assuming missing cells are treated
as o, or by treating the lattice as periodic, with the left edge connecting to the right one.
2 Conway’s Game of Life
The Game of Life is an iterative system of rules for the evolution of a 2d cellular automaton
devised by the British mathematician John Horton Conway in 1970. At each step, each cell may take two states, alive or
dead, and may change its state on the subsequent step depending on its own state and that of
its 8 neighbours (including diagonals).
2.1 The rules
Conway’s game is for 0 players. That is to say, it takes an initial state of living and dead cells
on a two-dimensional grid and then works forward in time automatically. The rules are:
For living cells
For each stage:
• A living cell with 0 or 1 neighbours dies of loneliness.
• A living cell with 2 or 3 neighbours survives to the next generation.
• A living cell with 4 or more neighbours dies from overcrowding.
The state of the mesh of cells at time n + 1 thus depends only on their states at time n.
For dead cells
For each stage:
• A dead cell with 3 neighbours becomes live.
• A dead cell with 02 or 48 neighbours stays dead.
You may treat the boundary as if the grid were surrounded by an outer circle of always
dead cells.
2.2 Extension 1: The periodic game of life
One method to extend Life is to apply periodic boundary conditions. Since we have two boundaries, the mesh is doubly periodic, as though the mesh were surrounded on all sides by exact copies
(including in diagonal directions). Otherwise, all rules operate the same as in the non-periodic
case.
2.3 Extension 2: Life on a hexagonal tessellation
Another method to extend Life is to use a mesh pattern which does not map nicely to multidimensional arrays. There are a number of patterns which tessellate to cover a two dimensional
plane, some regular, some irregular. An interesting choice is to use hexagons, along with rules:
• a live cell survives with 3 or 5 neighbours (note it dies with 4),
• a dead cell turns on with 2 neighbours.
Obviously, each cell neighbours only the six other hexagons it touches.
2.4 Extension 3: Generic Life
The Game of Life formula can be abstracted down to four things: (1) a vector of Boolean variables
representing the current state of the cells; (2) a connectivity matrix (also known as an adjancy
matrix) to identify which cells neighbour each other (i.e. a symmetric matrix which has value
1 for element ij if cell number i neighbours cell number j or value 0 otherwise); and a couple
sets of integers: (3) the environment rule, which species the neighbour counts where live cells
survive; and (4) the fertility rule, which species neighbour counts where dead cells come to life.