One dimensional cellular automata. (Back) (Root)

0013100132

0123000001

1113202133

3002311232

One-dimensional Cellular Automata

Cellular automata are not fractals. Some cellular automata generate fractals. The four pictures above are depictions of time histories of one dimensional cellular automata.

A cellular automata has four parts:

Let's go through the proccess used to generate a time history of a one-dimensional cellular automata.

The set of cells

The examples above use a one-dimensional array of cells with the first and last cell defined to be adjacent so that the automata wraps.

The neighborhoods

The neighborhood of a cell is the cell itself and the two cells next to it in the array.

States

The states are the numbers 0, 1, 2, 3 which are depicted as white, blue, green, and red respectively.

Rules

We add up the values in the neighborhood of a cell C, which gives us a number from 0-9. The rule for a given automata is specified by an array of ten numbers, in the range 0-3, which we use as a lookup table to find the new state for C. These rules are given beneath the automata for each of the examples. Let's trace the automata given by 0100000000.
TimeCells
0

0

0

0

0

1

0

0

0

0

1

0

0

0

1

1

1

0

0

0

2

0

0

1

0

0

0

1

0

0

3

0

1

1

1

0

1

1

1

0

4

1

0

0

0

0

0

0

0

1

5

0

1

0

0

0

0

0

1

0

6

1

1

1

0

0

0

1

1

1

7

0

0

0

1

0

1

0

0

0

This method of specifying a rule is cammed a sum automata. If we have 5 cell states we would need to specify an array of 13 numbers, for the possible sums 0+0+0 to 4+4+4 (0-12) with the numbers in the range 0-4 (the five states).

The numerical rule could be summarized "be blue if there is one blue cell in your neighborhood, otherwise be white." If we run the example above for a longer time we can see it generates another version of the Sierpinski triangle, at least until it hits itself because of the cell space wrap-around. This shows that some cellular automata do generate fractals.

An important point is that the next value for each cell is computed simultaneously and they are all updated together. It is also possible to update cellular automata in other ways, e.g. pick a cell at random and update only it. These two types of updating are call synchronous and asynchronous updating. The examples in this article were all generated with synchronous updating.

The sum automata rule is simple and convenient, but there are actually an enormous number of number of different ways to specify automata rules. Sum automata are symmetric (they don't care about the order of the cells in their neighborhood at all) and so are easier to get symmetric pictures from.