In this post I’ll describe how a cell in a new generation of an elementary cellular automation is created. I stated before that a rule is applied to a neighborhood of cells of a generation, in the case of elementart cellular automation this is any given cell and it’s neighbor to the left and its neighbor to the right (Fig 1).
Fig. 1 The neighborhood of the filled cell
These three cells determine what the state of the new cell at the came position as the shaded cell in the next generation will be. Each cell in a generation has three parents.
If we look at all the possible combinations of the values of the three cells, we find that there are 2^3 or 8. As proof, here is a printed representation of all possibilities [000, 001, 010, 011,100,101,110,111]. The concept of all cells in a neighborhood creating the next generation is true of all cellular automata, though the neighborhoods themselves can be much more complicated.
[000, 001, 010, 011, 100, 101, 110, 111]
[ 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ]
Since there must be a child cell in each position of a new generation, there must be an outcome for each of the 8 possible states of the parent cells. The list of all possible outcomes is called a rule. Each rule is named by taking the 8 outcomes (either 1 or 0) as binary and then converting it to an integer representation. For example, the simplest and most boring rule is rule 0. Rule 0′s binary is 00000000 and since a rule’s binary representation is the outcome of a new generation, rule 0 does nothing, it just repeats 0′s forever. If you were wondering, yes, since there are 8 bits in each rule there are a total of 2^8 or 256 rules.
As you may have noticed, each generation of a cellular automation has the same number of cells as the previous generation. How, you ask? Well it’s simple really cells in the new generation share parents. Each Cell shares 2 of it’s parents with each of the cells on either side of it. The illustration (fig. 2) below shows the shared parents of the two shaded cells on the bottom row by shading the shared parents in a darker blue. Obviously, all cells in the lower generation share parents as well, the illustration is just to show how 2 adjacent cells cells share the majority of parents.
fig. 2 Shared parents
There you have it, a base understanding of how cells are evolved from their 3 parents to rules and rule spaces, and parent sharing. The evolution of cells IS cellular automation and from these simple concepts we get some pretty interesting stuff.