NetLogo banner

 Home
 Download
 Help
 Resources
 Extensions
 FAQ
 References
 Contact Us
 Donate

 Models:
 Library
 Community
 Modeling Commons

 User Manuals:
 Web
 Printable
 Chinese
 Czech
 Japanese

  Donate

NetLogo User Community Models

(back to the NetLogo User Community Models)

Parity

by Nigel Gilbert (Submitted: 9/15/2002 )

[screen shot]

Download Parity
If clicking does not initiate a download, try right clicking or control clicking and choosing "Save" or "Download".

(You can also run this model in your browser, but we don't recommend it; details here.)

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:
Find the lines in the 'to go' procedure:
ask patches
[ set on-neighbours count neighbors4 with [on?] ]
and change "neighbors4" to "neighbours". The former version counts how many of the 4 neighbours are 'on', and the new version counts how many of the 8 surrounding cells are 'on'. What happens? Compare the patterns before and after making the change. Remebering that the number of neighbours has changed from 4 to 8, is there anything noticeable about the form of the patterns?
2. Experiment with other rules. One interesting rule is the 'majority' rule:

For each cell:
Count the number of neighbouring cells that are 'on' among the eight that surround the cell. If the number is 5 or more, turn the cell on. If 3 or less, turn it off. If exactly 4, choose randomly whether to turn it on or off.

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).

RELATED MODELS

Life
Rumor Mill
Cellular Automata 1D - a model that shows all 256 possible simple 1D cellular automata
CA 1D Totalistic - a model that shows all 2,187 possible 1D 3-color totalistic cellular automata
CA 1D Rule 30 - the basic rule 30 model
CA 1D Rule 30 Turtle - the basic rule 30 model implemented using turtles
CA 1D Rule 90 - the basic rule 90 model
CA 1D Rule 110 - the basic rule 110 model
CA 1D Rule 250 - the basic rule 250 model

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; n.gilbert@soc.surrey.ac.uk

(back to the NetLogo User Community Models)