ACSE – 1 Assessment 1
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
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
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.
3 Problem specication
You must create a single python module le called automata.py, which when imported exposes
functions called rule_thirty and life (plus life_periodic, lifehex and life_generic if you
attempt the extension exercises) with the following signatures:
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: [email protected] 微信:itcsdx