Parity

No preview image

1 collaborator

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

CREDITS AND REFERENCES

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

Comments and Questions

Please start the discussion about this model! (You'll first need to log in.)

Click to Run Model

; 2 dimensional Cellular Automata: the parity model
; code based on the NetLogo Life model

globals [
    mouse-x     ;; record last position of mouse (for adding cells by hand)
    mouse-y
    steps       ;; number of steps (cycles/generations) completed
    ]

patches-own [
  on?            ;; indicates if the cell is on (black)
  on-neighbours  ;; counts how many neighboring cells are on
]

to setup         ;; start with all cells off (white)
  ask patches
    [ cell-off ]
  set steps 0
end 

to cell-on
  set on? true
  set pcolor black
end 

to cell-off
  set on? false
  set pcolor white
end 

to go
  if mouse-down?
    [ stop ]  ;; wait for user to stop drawing
  ask patches
    [ set on-neighbours count neighbors4 with [on?] ]
  ask patches
    [ ifelse (on-neighbours mod 2 = 0)    ;; set cell on iff an odd number of neighbours are on
        [ cell-off ]
        [ cell-on ]
    ]
  set steps steps + 1
end 

to add-cells    ;; observer procedure
;; if the patch under the mouse pointer is off, turn it on, and if it is on, turn it off
  if mouse-down? and not (mouse-x = mouse-xcor and mouse-y = mouse-ycor)
      ;; if the mouse button is down and has moved since last time
    [ ask patch mouse-xcor mouse-ycor
        [ ifelse on?
            [ cell-off ]
            [ cell-on ]
        ]
       set mouse-x mouse-xcor
       set mouse-y mouse-ycor
    ]
    wait 0.1
end 

to add-central-patch
;; a one on cell in the middle
    setup
    ask patch 0 0 [ cell-on ]
end 

to add-central-block
;; add a block of on cells in the middle
    setup
    ;; draw a rough circle in the middle
    ask patch 0 0 [
        ask patches in-radius 3
            [ cell-on]
        ]
    ;; remove the points to make a square
    ask patch  0  3 [ cell-off ]
    ask patch  3  0 [ cell-off ]
    ask patch  0 -3 [ cell-off ]
    ask patch -3  0 [ cell-off ]
end 



;; written by Nigel Gilbert (n.gilbert@soc.surrey.ac.uk) July 2002
;; based loosely on a model with the following copyright:

; ***NetLogo Model Copyright Notice***

; This model was created as part of the project: CONNECTED MATHEMATICS:
; MAKING SENSE OF COMPLEX PHENOMENA THROUGH BUILDING OBJECT-BASED PARALLEL
; MODELS (OBPML).  The project gratefully acknowledges the support of the
; National Science Foundation (Applications of Advanced Technologies
; Program) -- grant numbers RED #9552950 and REC #9632612.

; Copyright 1998 by Uri Wilensky. All rights reserved.
; Converted from StarLogoT to NetLogo, 2001.

; Permission to use, modify or redistribute this model is hereby granted,
; provided that both of the following requirements are followed:
; a) this copyright notice is included.
; b) this model will not be redistributed for profit without permission
;    from Uri Wilensky.
; Contact Uri Wilensky for appropriate licenses for redistribution for
; profit.

There is only one version of this model, created almost 13 years ago by Nigel Gilbert.

Attached files

No files

This model does not have any ancestors.

This model does not have any descendants.

NetLogo