Launch the Interactive Tutorial via Java Web Start
Cellular
Automata in one dimension: A Simple Dynamical System
Interactive Tutorial by Sam Reid
Dynamical systems model time-dependent phenomena in which the next state is computable from the current state. Dynamical systems may be discrete or continuous, depending on the nature of the time coordinate. Many physical systems can be modeled as dynamical systems.
In this tutorial, we examine the Cellular Automaton, a dynamical system which is not only temporally discrete, but spatially discrete as well. Furthermore, the rule that governs the update of the system is spatially localized. These assumptions do not hinder the system's emergent behavior-on the contrary, even 1-Dimensional Cellular Automata exhibit emergent behavior including fractals, chaos, randomness, complexity and particles. In fact, it was recently proved that any computable function can be implemented in terms of an infinite 1-Dimensional Cellular Automaton [5].
In this tutorial, we study this simple form of Cellular Automata and depict its complex emergent behavior. We hope an exploration of this powerful dynamical system will confer insight into many forms of dynamical systems.
This page is meant to accompany the interactive tutorial powered by Java.
In a Cellular Automaton, all cells behave identically, and have the same connectivity.
Characteristics of a Cellular Automata
1. States, the number of distinct states a cell can be in.
2. Neighborhood, the description of how cells are connected to other cells.
3. Update Rule, the decision of how a cell's state should change based on the states of its neighbors.
Runtime of a Cellular Automata
1. Initialize all cells with specified initial conditions.
2. For each cell, determine what it should become in the next time step, based on the states of its neighbors.
3. Update all cells simultaneously.
4. Go to step 2.
The Tutorial
The tutorial is parceled into three main sections:
1. Introduction
The basic ideas of a cellular automata are introduced.
2. Types
The four main classes of behavior are introduced.
3. Emergent Properties
Fractals, sensitivity to initial conditions, particles, phase locking, the 'Edge of Chaos', dynamical parameters.
4. The Explorer
A main application for exploring cellular automata.
In order to advance in the tutorial, you must proceed through all stages. Once you have completed a main section, you will receive a shortcut (password) past it for future sessions. This is to encourage the user to pay attention to detail, to help ensure that some degree of understanding has been reached.
The Explorer
Basic Features:
1. Choose a rule visually or numerically, or from thumbnails.
2. Set initial conditions by hand (or randomly).
3. Set boundary conditions (circular or fixed).
4. Set the lattice size.
5. Zoom in/out.
6. Panning left, right and forward and back in time.
Advanced Features:
1. Create/Edit patterns.
2. Pattern identification/highlighting.
3. Set up and run experiments.
Alternatives to Web Start
Java Web Start is the recommended mechanism for launching this interactive tutorial.
However, if you are having troubles with Web Start, you may try the following:
The Executable Jar:
In Windows, double click to run
Or from a command line, execute java -jar ca1d-reid.jar
Download the Tutorial as a Jar File
Or
Applet:
The Tutorial as an Applet
The Web Start version of this tutorial has been tested under Windows XP and Mac OS X, under Java 1.4.2_05.
References
[1] C. G. Langton. Computation at the edge of chaos: Phase transitions and emergent computation. Physica D, 42:12 37, 1990.
[2] P Tisseur 2000 Nonlinearity 13 1547-1560 Cellular automata and Lyapunov exponents
Interactive Tutorial by Sam Reid
Dynamical systems model time-dependent phenomena in which the next state is computable from the current state. Dynamical systems may be discrete or continuous, depending on the nature of the time coordinate. Many physical systems can be modeled as dynamical systems.
In this tutorial, we examine the Cellular Automaton, a dynamical system which is not only temporally discrete, but spatially discrete as well. Furthermore, the rule that governs the update of the system is spatially localized. These assumptions do not hinder the system's emergent behavior-on the contrary, even 1-Dimensional Cellular Automata exhibit emergent behavior including fractals, chaos, randomness, complexity and particles. In fact, it was recently proved that any computable function can be implemented in terms of an infinite 1-Dimensional Cellular Automaton [5].
In this tutorial, we study this simple form of Cellular Automata and depict its complex emergent behavior. We hope an exploration of this powerful dynamical system will confer insight into many forms of dynamical systems.
This interactive tutorial
requires Java version 1.4 and up:
Once you have verified your Java 1.4+ installation:
Launch the interactive tutorial now via Web Start!
Once you have verified your Java 1.4+ installation:
Launch the interactive tutorial now via Web Start!
This page is meant to accompany the interactive tutorial powered by Java.
In a Cellular Automaton, all cells behave identically, and have the same connectivity.
Characteristics of a Cellular Automata
1. States, the number of distinct states a cell can be in.
2. Neighborhood, the description of how cells are connected to other cells.
3. Update Rule, the decision of how a cell's state should change based on the states of its neighbors.
Runtime of a Cellular Automata
1. Initialize all cells with specified initial conditions.
2. For each cell, determine what it should become in the next time step, based on the states of its neighbors.
3. Update all cells simultaneously.
4. Go to step 2.
The Tutorial
The tutorial is parceled into three main sections:
1. Introduction
The basic ideas of a cellular automata are introduced.
2. Types
The four main classes of behavior are introduced.
3. Emergent Properties
Fractals, sensitivity to initial conditions, particles, phase locking, the 'Edge of Chaos', dynamical parameters.
4. The Explorer
A main application for exploring cellular automata.
In order to advance in the tutorial, you must proceed through all stages. Once you have completed a main section, you will receive a shortcut (password) past it for future sessions. This is to encourage the user to pay attention to detail, to help ensure that some degree of understanding has been reached.
The Explorer
Basic Features:
1. Choose a rule visually or numerically, or from thumbnails.
2. Set initial conditions by hand (or randomly).
3. Set boundary conditions (circular or fixed).
4. Set the lattice size.
5. Zoom in/out.
6. Panning left, right and forward and back in time.
Advanced Features:
1. Create/Edit patterns.
2. Pattern identification/highlighting.
3. Set up and run experiments.
Screenshots
If you still haven't installed Java,
you are free to browse non-interactive screenshots of the tutorial:
Screenshots
If you still haven't installed Java,
you are free to browse non-interactive screenshots of the tutorial:
Screenshots
Alternatives to Web Start
Java Web Start is the recommended mechanism for launching this interactive tutorial.
However, if you are having troubles with Web Start, you may try the following:
The Executable Jar:
In Windows, double click to run
Or from a command line, execute java -jar ca1d-reid.jar
Download the Tutorial as a Jar File
Or
Applet:
The Tutorial as an Applet
The Web Start version of this tutorial has been tested under Windows XP and Mac OS X, under Java 1.4.2_05.
References
[1] C. G. Langton. Computation at the edge of chaos: Phase transitions and emergent computation. Physica D, 42:12 37, 1990.
[2] P Tisseur 2000 Nonlinearity 13 1547-1560 Cellular automata and Lyapunov exponents
[3] Langton, C., "Studying artificial life with cellular automata," Physica D 22 (1986), 120-149.
[4] Wolfram, S. A New Kind of Science.
[5] Cook, M. "Universality in Elementary Cellular Automata." Complex Systems 15, 1-40, 2004.
[6] The Attractor-Basin Portrait of a Cellular Automaton, James E. Hanson and James P. Crutchfield, J. Statistical Physics 66:1415-1462 (1992).
[7] Melanie Mitchell, Peter T. Hraber, and James P. Crutchfield, Revisiting the Edge of Chaos: Evolving Cellular Automata to Perform Computations, Complex Systems, 7:89-130, 1993
[8] R. Das, M. Mitchell and J. P. Crutchfield. A genetic algorithm discovers particle-based computation in cellular automata. In Y. Davidor and R. Manner (editors) Parallel Problem Solving from Nature Conference (PPSN-III), Jerusalem, Israel, 1994.
[9] Digital Philosophy, Ed Fredkin, http://www.digitalphilosophy.org/, 2001