NetLogo Models Library:
Sample Models/Computer Science/Cellular Automata

(back to the library)

CA Stochastic

Run CA Stochastic in your browser uses NetLogo 4.1 requires Java 5 or higher (system requirements) Note: If you download the NetLogo application, every model in the Models Library (besides the Community Models) is included. If you have trouble running this model in your browser, you may wish to download the application instead.

WHAT IS IT?

This is a one-dimensional stochastic cellular automaton. (See the CA 1D Elementary model if you are unfamiliar with cellular automata.) Unlike most cellular automata, whose behavior is deterministic, the behavior of a stochastic cellular automaton is probabilistic. Stochastic cellular automata are models of "noisy" systems in which processes do not function exactly as expected, like most processes found in natural systems.

The behavior of these cellular automata tend to be very rich and complex, often forming self-similar tree-like or chaotic behavior. They are capable of mimicking many phenomena found in nature such as crystal growth, boiling, and turbulence.

HOW IT WORKS

At each time step, every cell in the current row evaluates the state of itself and its immediate neighbors to the right and left. There are 8 possible on/off rule configurations for every 3-cell neighborhood, each with a certain probability of turning on the cell below it at the next time step. The rules are applied accordingly, and the next state of the cellular automaton appears in the row directly below, creating a space vs. time view of the cellular automaton's evolution.

HOW TO USE IT

Set up:
- SETUP RANDOM initializes the model with a percentage of the cells "on". The percentage on is determined by the DENSITY slider.
- SETUP EXAMPLE initializes the rule settings according to the EXAMPLE slider
- AUTO-CONTINUE? automatically wraps to the top once it reaches the last row when the switch is on
- GO begins running the model with the currently set rule. It runs until it reaches the bottom of the world. If GO is pressed after it has completed, it will wrap to the top and continue.
- ON-COLOR & OFF-COLOR set the "on" and "off" cell colors respectively.

Rule Setup:
There are 8 sliders, the names of which correspond to cell states. "O" means off, "I" means on. For example, the upper-right slider is called "IIO," corresponding to the state where a cell and its left neighbor is on, and its right neighbor is off. (NOTE: the switch names are composed of the letters "I" and "O", not the numbers zero or one, because NetLogo switches can't have numbers for names.) If this slider is set to 70%, then the following rule is created: when a cell is on, its left neighbor cell is on and its right neighbor cell is off, then there is a 70% chance the cell below it will be set "on" at the next time step, otherwise the cell below it will be set to "off" at the next time step.

Plot:
This plot measures two types of entropy, or disorder in a system. Cellular automata can produce patterns with varying degrees of randomness. If a pattern is perfectly random, each subsequence occurs with an equal probability, and the entropy is 1. The more likely certain subsequences occur, the lower the entropy. If a pattern is perfectly ordered, then the entropy is 0. In this plot, 4-cell subsequences ("correlation length") are used to calculate the entropy. The first type of entropy is the spatial topologic entropy, which measures how many subsequences are present. The second type of entropy, spatial metric entropy, measures the probability that all subsequences occur with the same frequency.

Plot Configuration:
- PLOT? switches plot on or off
- AUTO-CLEAR? if on, the plot is automatically cleared after each complete screen of cellular automata evolution

THINGS TO NOTICE

Why is it a better idea to have a density that isn't too big or too small?

What is the relationship between the cellular automata display and the entropy plot?

How does the size of the black triangles affect the entropy?

What kinds of configurations lead to long lived chaotic behavior?

THINGS TO TRY

You may want to set AUTO-CONTINUE? to 'on' in order to study the long-term behavior of each cellular automaton configuration. Also, if you have a fast enough computer, you may want to increase the size of the world in order to get a better view of the "big picture." If you turn the plot off, it will also increase the speed of your model.

Change the example slider to 1, and click SETUP EXAMPLE. Click GO and experiment with the III slider, running each configuration a couple of times:
- What happens when III is set to 0%?
- - Why do you think the cellular automaton always ends up in the same uniform, or "absorbing" state?
- As you increase III, what happens to the density of the trees that are formed?
- - Does this seem to effect the time it takes to reach an absorbing state?
- What happens when III is set to 100%?
- - It seems very unlikely that this configuration will reach an absorbing state, but is it possible?
- - Why or why not?

Change the example slider to 2, and click SETUP EXAMPLE. Click GO and experiment with the IOO slider, running each configuration a couple of times:
- Why does this configuration want to have either vertical or horizontal stripes?
- What happens when you change IOO to 0% or 100%?
- - Why does it always end up producing a majority of horizontal or vertical stripes?
- How does changing the OOI slider in conjunction with the IOO slider affect the model?

Change the example slider to 3, and click SETUP EXAMPLE. Click GO and experiment with the IOO slider, running each configuration a couple of times:
- As you change IOO, what happens to the outer shape of the cellular automaton?
- - What happens to the shape of the triangles inside?
- - How is the value of the IOO slider related to the spread of on cells?
- - What should IOO be set to if you want perfectly symmetric triangles?
- Set IOO to 100%, and experiment with the OOI slider in a similar fashion.
- What is the relation between the IOO and OOI slider?

Change the example slider to 4, and click SETUP EXAMPLE. Click GO and experiment with the IOO slider, running each configuration a couple of times:
- As you increase IOO, what transition do you see in the structures formed by the cellular automata?
- - Why do you think this transition, or "phase change," happens?
- Once you get to 100%, notice that the triangles aren't very symmetric.
- - Which slider should you move accordingly in order to make the triangles look more symmetric?
- Now try moving both sliders together in order to find the point at which the cellular automaton makes its phase transition.

Change the example slider to 5, and click SETUP EXAMPLE Experiment with the OOI and IOO sliders together.
- What differences do you notice between the this example and the previous one?
- Does either cellular automaton have lower phase transition point with respect to the OOI and IOO sliders?
- - If so, what accounts for this difference?

EXTENDING THE MODEL

Often times one might want to change multiple sliders in parallel, while leaving other sliders unchanged. Try automating this process by creating additional switches and sliders.

Can you measure the entropy more accurately by using subsequences greater than 4?

There are many other ways to measure order in a system besides entropy, can you think of any?

Can you make a stochastic cellular automata with more neighbors? For example, the cellular automata might have two neighbors on each side.

Try making a two-dimensional stochastic cellular automaton. The neighborhood could be the eight cells around it, or just the cardinal cells (the cells to the right, left, above, and below).

NETLOGO FEATURES

The plot-entropy procedure makes extensive use of the MAP and FILTER primitives. First, MAP is used to convert a list containing the number of occurrences of each pattern of ON? values to a list of probabilities of each pattern occurring. This is done by dividing each item in the first list by the total number of possible patterns. Since both entropy calculations involve the use of a logarithm, FILTER is used to remove all elements in the list that are equal to 0 so that no errors occur. For calculating the topological entropy, MAP is used to change all the remaining elements in the probability list to 1. When calculating the metric entropy, MAP is used to multiply each element in the probability list by its logarithm. Using MAP and FILTER allows these complex calculations to be done in a clean, compact manner.

RELATED MODELS

CA 1D Elementary - a widely studied deterministic equivalent to this model
CA 1D Totalistic - a three color 1D cellular automata
Percolation (in Earth Science) - a model demonstrating the percolation of an oil spill using probabilistic rules similar to this model
Turbulence (in Chemistry & Physics) - a continuous cellular automata that exhibits phase change behavior similar to this model
Ising (in Chemistry & Physics) - a microscopic view of a magnetic field which undergoes phase changes with respect to temperature
DLA (in Chemistry & Physics) - a growth model demonstrating how the accumulation of randomly placed particles can lead to complex structures found throughout nature

CREDITS AND REFERENCES

Chate, H. & Manneville, P. (1990). Criticality in cellular automata. Physica D (45), 122-135.
Li, W., Packard, N., & Langton, C. (1990). Transition Phenomena in Cellular Automata Rule Space. Physica D (45), 77-94.
Wolfram, S. (1983). Statistical Mechanics of Cellular Automata. Rev. Mod. Phys. (55), 601.
Wolfram, S. (2002). A New Kind of Science. Champaign, IL: Wolfram Media, Inc.

Thanks to Eytan Bakshy for his work on this model.

HOW TO CITE

If you mention this model in an academic publication, we ask that you include these citations for the model itself and for the NetLogo software:
- Wilensky, U. (2003). NetLogo CA Stochastic model. http://ccl.northwestern.edu/netlogo/models/CAStochastic. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.
- Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.

In other publications, please use:
- Copyright 2003 Uri Wilensky. All rights reserved. See http://ccl.northwestern.edu/netlogo/models/CAStochastic for terms of use.

COPYRIGHT NOTICE

Copyright 2003 Uri Wilensky. All rights reserved.

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.

This model was created as part of the projects: PARTICIPATORY SIMULATIONS: NETWORK-BASED DESIGN FOR SYSTEMS LEARNING IN CLASSROOMS and/or INTEGRATED SIMULATION AND MODELING ENVIRONMENT. The project gratefully acknowledges the support of the National Science Foundation (REPP & ROLE programs) -- grant numbers REC #9814682 and REC-0126227.

(back to the NetLogo Models Library)