Cellular Automaton

Imagine a row consisting of many colored boxes (ideally an infinite number; the row has no beginning and no end). Each of these boxes can only be colored in two different ways; let us say blue or orange. Now it is your turn: you can decide which box should have which color at the beginning. So far, so good.

However, this row of boxes (or cells) is only one part of the cellular automaton. We are missing a rule which determines what happens to the automaton in the next time step. Which of the cells will be blue and which orange? Of course this question cannot be answered out of the blue — we need a prescription which defines how each individual cell is to be colored in the next step. Here we are given complete freedom to be creative. However, we want to focus on the simplest (and most widespread) form of cellular automata.

In this case, the color of a particular cell in the next step depends only on the color of the cell itself and its two direct neighbor cells in the previous step. If we consider a cell whose color is to be determined in the next step, the cell to its left can have two different colors. The cell itself can also only be blue or orange. The neighbor on its right also has only two possible colors. This means that there are exactly

possible patterns. A rule is now defined by specifying which color the cell in question should be given in the next step when one of these eight patterns occurs. So we simply assign one of the two colors (blue or orange) to each of the eight patterns. With this choice, the rule is complete and the automaton is fully specified.

Now we can start the automaton. You have already defined the initial pattern as you like, and settled on a rule for the time evolution of cells. The automaton then proceeds as follows:

1. To calculate its next state (step), it considers each of its cells individually and compares the pattern (consisting of the colors of both neighboring cells and the cell itself) with the rule. Since the rule covers all possible patterns, it will find what it is looking for.
2. The rule determines how the cell under consideration will be colored in the next state.
3. The automaton performs this procedure for all cells independently. (The rules are always applied to the unmodified, current state of the cells.). Practically, this process is implemented by copying the current state to a buffer. The actual memory is then successively overwritten with the new colors, whereby the decisive patterns for the rule are read from the buffer (which remains unchanged until the computation of the next state is finished).

In this way, the automaton calculates the time evolution of states step by step. If one records this time evolution (the history of the automaton) as a two-dimensional “spacetime pattern”, one can generate quite complex, chaotic, yet deterministic patterns (depending on the chosen rule and the initial state). Try it yourself:

Even more complex patterns can be generated by higher-dimensional automata — often one considers two-dimensional ones. A two-dimensional cellular automaton consists no longer of a series of cells, but of an entire chessboard-like plane of cells. In this case, the color of a cell in the next step depends on the colors of all eight neighbors and its own color in the current state. The rule therefore must cover many more patterns than in the one-dimensional case. Another difference arises when one attempts to graphically represent the history of the automaton’s states. Whereas in the case of the one-dimensional automaton, a single two-dimensional “spacetime layer” was sufficient to record all previous states, for a two-dimensional automaton a (spatial) cuboid is needed. Since it is difficult to see inside a cuboid “filled” with cells, the history is usually not displayed for two-dimensional automata.