Main  Introduction  Download  Examples  Links  Participants

 

 

 

 

Cellular Automata Basics
Cellular automata are self-generating computer graphics movies. The most important near-term application of cellular automata will be to commercial computer graphics; in five years you won't be able to watch television for an hour without seeing some kind of CA. Three other key applications of cellular automata will be to simulation of biological systems (artificial life), to simulation of physical phenomena (heat-flow and turbulence), and to the design of massively parallel computers.

Capow 98 simulates one and two-dimensional cellular automata. Generally, the computer screen is divided up into "cells" which are colored rectangles or dots. Each cell is repeatedly "updated" by changing its old color to a new color. The net effect of the individual updates is that you see an ever-evolving sequence of screens. A graphics program of this nature is specifically called a cellular automaton when it is 1) parallel, 2) local, and 3) homogeneous.

(1) Parallelism means that the individual cell updates are performed independently of each other. That is, we think of all of the updates being done at once. (Strictly speaking, your computer only updates one cell at a time, but we use a buffer to store the new cell values until a whole screen's worth has been computed to refresh the display.)

(2) Locality means that when a cell is updated, its new color value is based solely on the old color values of the cell and of its nearest neighbors.

(3) Homogeneity means that each cell is updated according to the same rules. Typically the color values of the cell and of its nearest eight neighbors are combined according to some logico-algebraic formula, or are used to locate an entry in a preset lookup table.

Cellular automata can act as good models for physical, biological and sociological phenomena. The reason for this is that each person, or cell, or small region of space "updates" itself independently (parallelism), basing its new state on the appearance of its immediate surroundings (locality) and on some generally shared laws of change (homogeneity).

As a simple example of a physical CA, imagine sitting at the edge of a swimming pool, stirring the water with your feet. How quickly the pool's surface is updated! The "computation" is so fast because it is parallel: all the water molecules are computing at once. And how does a molecule compute? It reacts to forces from its neighbors (locality), in accordance with the laws of physics (homogeneity).

home