Cellular Automata

What Is It?

Cellular automata (CA) are well known to computer scientists and mathematicians. They have been used under many names and in many different disciplines. Toffoli and Margolus' book, Cellular Automata Machines, gives an excellent summary of the history of the subject. Though CA were first introduced in the late forties by John von Neumann, the field remained largely dormant for nearly thirty years due to lack of communication and differing nomenclature. In 1970 an article in Scientific American by Martin Gardner about a CA model called the game of Life, invented by John Horton Conway, introduced CA to the public and a generation of young scientists. The proceedings from an workshop on CA held at Los Alamos, New Mexico, provides a detailed exposition on previous uses of CA in a number of disciplines.

In general, CA are dynamical systems with the following defining features:

1. Discrete in space: System consists of a discrete grid of spatial cells or sites.

2. Discrete states: Each cell has a finite (usually small) number of possible states.

3. Discrete in time: The state of each cell is updated in a sequence of discrete time steps.

4. Homogeneous: All cells are identical, and are arranged in a regular array.

5. Synchronous updating: All cell states are updated in synchrony, each depending on the previous states of neighboring cells.

6. Deterministic rule: Each cell state is updated according to a fixed, deterministic rule.

7. Spatially local rule: The rule at each site depends only on the current state and the states of a local neighborhood of sites around it.

8. Temporally local rule: The rule for the new state of a site depends only on states for a fixed number of preceeding steps (usually one).

What Is It Usefull For?

Today's scientists and engineers are faced with ever increasing difficulties when trying to simulate complex systems. More often than not a researcher cannot afford to invest the time and resources to construct and directly study a system and many times it is simply impossible to do so. Cellular automata have in recent years be successfully used to model complex dynamic systems.  The cellular automata model is a simple one, which makes it very attractive, yet it provides a surprisingly powerful means of representing dynamic systems. CA have proven to be very useful in studying complex systems of relatively simple locally interacting units. Research done at MIT and the Air Force Research Laboratory have demonstrated the power of CA algorithms in a number of areas:

Physical Simulation

CA have been used to model Ising spin systems, fluid dynamics (Lattice Gases) and polymer systems. In particular CA models of fluid dynamics have promise for fast, exact simulations of complex fluid flows. Researchers in MIT's Earth and Planetary Sciences Department have successfully used CA models to simulate flow through porous media.  At the Air Force Research Laboratory (AFRL) Lattice Gas CA models were developed for mutli-phase liquid/gas systems, microemulsions and multi-species liquid/gas systems.

Image Processing

CA have been used for realtime 3D rendering, realtime edge detection and realtime image enhancement.

Digital Logic Simulation

Students at MIT's Laboratory for Computer Science have developed CA models which can simulate digital circuits. A toolkit was  designed to take circuit designs and convert them for use with the simulation. Full scale processors have been modeled and run at a simulated speed of 1 kHz. This was on par with the best commercial logic simulation packages available at the time (ca. 1996).

The full range of applications that CA models are suited to is unknown. What is needed is a simple to use but robust environment where CA models can continue to be explored. The Information Mechanics Group at the MIT Laboratory for Computer Science developed Cellular Automata Machines to provide researchers with an means to explore CA models. Much of this work is a direct spinoff of the IM group's CAM8 project.

If you are interested you should check out the following:

Web Sites:
Real applications of CA
Some interesting CA models
CA intro
Life
CA and chaos

News Groups:
comp.theory.cell-automata