| current pattern | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| new state for center cell | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
[Rule 90 starting with a single nonzero cell.]
[Rule 90 starting with a single nonzero cell.]
Although most laws of nature are local (short range), nature generates order and patterns on a large scale. How does this happen? Some of the simplest models that incorporate both space and time (spatiotemporal models) and that generate complexity involve an array of cells interacting with a small number of neighbors by simple rules. These models are referred to as cellular automata models.
Cellular automata were first investigated by John von Neumann and Stanislaw Ulam while studying self replicating systems. A cellular automaton is a spatial lattice which can have any one of a finite number of states and which are updated synchronously in discrete time steps according to a local (nearby neighbor) rule. Although a complete theory of cellular automata has not yet been developed, Stephen Wolfram developed a complete classification of one dimensional automata in the 1980s. The Rule 90 Model is an implementation of one such rule.
Imagine a circular coral reef divided into cells that supports some type of life form. Each each cell can be alive or dead and the entire reef evolves from one year to the next as follows:
How does life evolve on the reef?
To make the study of one dimensional cellular automata more straightforward, we abandon the life on a reef analogy and refer to a one-dimensional lattice with cells (array elements) that can take on the value of zero or one. Each cell in a one dimensional lattice has two neighbors forming a neighborhood of 3 cells. Each neighborhood has eight (8) possible patters and there are 28=256 possible rules because each pattern can produce either a zero or a one. The rule which governs the next state of the Rule 90 automaton is:
| current pattern | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| new state for center cell | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
Wolfram named 1D automata using the decimal numbers that are obtained by regarding the sequence of center cell states as a binary number. For example, the 1D Rule 90 automaton is: 90 = 64+16+8+2 = 010110102. This rule produces a Pascal triangle mod 2 (Sierpinski gasket) if there is a single initial cell with a value of one.
The following EJS models show examples of cellular automata. These models are listed in order of EJS programming complexity.
The core idea that very simple rules can generate great complexity is now an established idea in science. For example, many millions of organic compounds having an immense range of physical properties can be constructed from carbon, oxygen, and hydrogen and can be understood using the Schrödinger equation. Although the stronger conjecture that simple automata rules may underlie physical laws predates Steven Wolfram's book A New Kind of Science, this book provides an overview and many examples of the applicability of this idea.
Cellular automata models are also import in the social sciences. See, for example, the following books.
Cellular automata are often discussed in books on chaos and nonlinear dynamics. The following books connect the mathematics with physical systems.
This implementation of the Rule 80 Model was created by Wolfgang Christian and Francisco Esquembre using the Easy Java Simulations (EJS) authoring and modeling tool. You can examine and modify a compiled EJS model if you run the model (double click on the model's jar file). Right-click within this running model and select "Open Ejs Model" from the pop-up menu to copy the model's XML description into EJS. You must, of course, have EJS installed on your computer.
Information about Ejs is available at: <http://www.um.es/fem/Ejs/> and in the OSP ComPADRE collection <http://www.compadre.org/OSP/>.