1D Cellular Automaton

One dimensional, or elementary, cellular automaton.

A cellular automaton can be seen as a set of conditions which evolves through time according to certain rules. Cellular automata, aside from being visually pleasing, exhibit interesting phenomena that have been studied by many mathematicians; for example, starting from very simple initial conditions and using simple rules, some cellular automata yield complex—and often seemingly random—behaviour while others model physical phenomena.

The Macromedia Flash animation presented here is a basic cellular automaton: it is a one dimensional, two colour, nearest neighbour cellular automaton, which is also known as the elementary cellular automaton. This means that each state of the automaton is present in one dimension (a single row), and that each cell in the state has a binary value: either “on” or “off”, represented by black and white in the animation and by 1 and 0 in the program. The evolution of states through time is represented as rows, therefore the row at the top represents the initial conditions, and the subsequent rows are the evolutions of the states through time. The evolution of a particular cell through time depends on its nearest neighbours, therefore a cell will change in value through time depending on what the previous values of its two neighbours and itself were in the previous state, these are the three cells right above it. In this example, there are therefore eight possible values for a cell’s parents, since each of the three parent cells can have two possible values.

To describe this concept of inheritance from eight possible parent states, we use what is known as rules, which explain what the child state becomes depending on the parent state. The following image is a list of all possible parent states, with child states which are all in the “off” (white) state:

Rule 0

Looking at these parent states, we notice that the rightmost state could be seen as a representation of a binary 000, which is 0 in the decimal system. The subsequent parent states are then 001 (1 in decimal), 010 (2 in decimal), 011 (3 in decimal), and so on until 111 (7 in decimal). We therefore now have a way to name the parent state, this is used in the program to calculate the inheritance.

Similarly, the child states can be seen as binary representations of a number with eight binary positions, therefore of a number from 0 to 255 in decimal. The first rules presented here could be called rule 0: no matter what the parent state is, the child state will always be in the “off” or 0 state. This is obviously a pretty uninteresting rule, since any initial condition dies at the second state. Rule 1 would be represented as:

Rule 1

Rules 1 means that the child state will always be 0 unless the parent state is 0, in which case the child state is 1.

There are in all 256 possible rules (from 0 to 255), some of them are uninteresting while others present nice patterns or have pseudo-random properties. In the following Macromedia Flash animation, the user enters in the first box which rule he want to be drawn, and in the second box he enters the number of initial cells that he wants for the initial conditions. The animation will start when the user clicks on the canvas.

Macromedia Flash player required.

Many rules present interesting features, such as rules 30, 45, 57, 73, 90, 101, 102, 105, 110, 124, 135, 150, 169, 193, and 225.

Stephen Wolfram, the creator of Mathematica, explores in much more details the features of cellular automata in his very interesting book A New Kind of Science. In pages 51–60 he explains this particular example of cellular automaton.

Plaintext source of this program, released under the GPL.