NetLogo User Community Models
by Nigel Gilbert (Submitted: 9/15/2002 )
WHAT IS IT?
This program is an example of a two-dimensional cellular automaton. A cellular automaton is a computational machine that performs actions based on certain rules. It can be thought of as a board which is divided into cells (such as square cells of a checkerboard). Each cell can be either on or off. This is called the "state" of the cell. According to specified rules, each cell will be on (black) or off (white) at the next time step.
This particular cellular automaton is called the Parity Model. It is one of the simplest, yet the effects it produces are astonishingly complex. There is only one rule, which all the cells follow. The rule is that each cell looks at its four neighbours (the ones immediately to its left, right, above and below) and if an odd number of them (that is, 1 or 3) of them are 'on', it switches itself 'on'. If there are an even number 'on' (2 or 4), it switches itself off. [Spelling note: 'neighbour' is one of those words that is spelled differently in British and American English. Since I'm English, I'm using the British spelling].
The rule is applied to all the cells in the grid during one time step. Then the same rule is applied again (but some of the neighbour cells may have changed from on to off or off to on since last time, so the rule may not yield the same result). This is repeated indefinitely.
The grid of cells is made endless by connecting the lefthand edge to the righthand edge and the top to the bottom. This means that the cells 'below' the bottom row of cells are the cells on the top row, and the cells to the left of the left hand column are the right hand column of cells.
HOW TO USE IT
Press the SETUP button to clear the grid - all the cells turn white (off).
Next you need to seed the grid with a few cells that are on. There are three possibilities:
a. Press the "Add central patch" button to turn one patch in the middle of the grid black, or
b. Press the "Add central block" button to turn a 7 by 7 square set of patches black, or
c. Press the "Add 'On' cells" button and then 'draw' the patches you want turned black by dragging the mouse over the grid.
Then press GO and watch what happens.
THINGS TO NOTICE
Notice that an initially very simple pattern (for example, with seed (a), one black patch in the middle) becomes a more and more complicated pattern and then suddenly reverts to multiple copies of the initial simple pattern.
After the pattern has reached the edge of the grid, it 'wraps' round to the opposite edge and starts advancing through the pattern that is being generated from the centre. The consequence is that you get interference patterns (like the waves reflected off the end of a bath tub when you make a splash at the other end). What is remarkable is that, despite the complexity of these interference patterns, they still resolve to very simple ones every now and again.
This is because the Parity rule has an important property. The regularity of the patterns you see is because the rule is an example of a linear rule: if two starting patterns are run in separate grids for a number of time steps and the resulting patterns are superimposed, this will be the same pattern as one gets if the starting patterns are run together on the same grid.
THINGS TO TRY
Try drawing your own starting patterns (seeds) with the "Add 'on' cells" button and see if you can find a seed that generates interesting patterns.
Starting from a regular pattern such as the "central patch" or "central block", see how many steps it takes before you get to a multiple of the starting pattern. Is this number the same for all seeds?
EXTENDING THE MODEL
1. the model defines the neighbourhood of a cell as the four cells above, below, to the left and to the right. This is called the 'von Neumann' neighbourhood, after an early pioneer of computers. It is also possible to define the neighbourhood of a cell as consisting of the eight cells surrounding a cell - the Moore neighbourhood. You can try the model using the Moorre neighbourhood (as before, the cell becomes 'on' if an odd number of the 8 surrounding cells are 'on') by making a very small change to the code:
For each cell:
Can you prediict what kind of patterns you will see?
3. [Hard] Rewrite the program so that the grid, instead of wrapping round at the edges, extends to infinity (of course, your computer will not accommodate a grid of infinite size, so you will have to find some way to simulate such a grid).
REFERENCES AND CREDITS
There is a large literature on cellular automata.
A recent and critically acclaimed book by one of the pioneers of cellular automata is: Stephen Wolfram (2002) A new kind of science. Wolfram Media Incorporated.
A clear account of some simple but important Cellular Automata can be found in T. Toffoli and N. Margolus (1987) Cellular Automata Machines. MIT Press.
The parity model is used as an illustration in Chapter 7 of Nigel Gilbert and Klaus G. Troitzsch (1999) Simulation for the Social Scientist. Open University Press.
This version of the Partity Model was written by Nigel Gilbert (based on the Life model by Uri Wilensky) for the annual ZUMA summer school of Simulation for the Social Sciences, 2002.
Nigel Gilbert, University of Surrey, UK; firstname.lastname@example.org
(back to the NetLogo User Community Models)