| 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 automaton (CA) 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 EJS Automata Rules Model allows us to investigate these rules.
Each cell in a one dimensional lattice has two neighbors forming a neighborhood of 3 cells. Each neighborhood has eight (8) possible patterns and there are 28=256 possible rules because each pattern can produce either a zero or a one. 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:
| current pattern | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| new state for center cell | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
Whereas Rule 90 produces a Pascal triangle mod 2 (a Sierpinski gasket) if there is a single initial cell with a value of one, Rule 30 produces seemingly random (chaotic) behavior.
| current pattern | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| new state for center cell | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
Rule 110, on the other hand, produces patterns that are neither completely random nor completely repetitive.
| current pattern | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| new state for center cell | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
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 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/>.