The rules for 1D CA.
A cell can be only in the states of 0 or 1. For a cell C with only 2 neighbors (L and R) we list all the possible combinations of states (configurations) written as <L|C|R> at a particular time step in the following order in n:
<1|1|1> <1|1|0> <1|0|1> <1|0|0> <0|1|1> <0|1|0> <0|0|1> <0|0|0>
where n= 7
4 3 2 1
The rule specifies whether C=1 or 0 in the next time step for each of the 8 possible
preceding configurations. For example, if our rule is that C=1 only when its previous
only neighbor with 1 was on the Left (n=6 and n=4) or its only neighbor with
1 was on the Right (n=3
and n=1) and C =0 for all other configurations, we can write the rule by expressing
the value of C for each value of n in descending order (01011010). The code used
is to treat this pattern as an 8 bit binary number and the code for the rule
is its decimal equivalent. In our example, this would be 2^6+2^4+2^3+2^1=64+16+8+2=90.
So, our example corresponds to rule 90. There are a maximum of 2^8 = 256 rules for
Working backwards, rule 110 would correspond to 2^6+2^5+2^3+2^2+2^1=64+32+8+4+2=110,
or the pattern
(01101110). This means that C will change its state if both L and R =1 (n=7
and 5), keep its state if both L and R =0 (n=2 and 0) or L=1 (n=6 and 4),
and will always be 1 when only R is 1 (n=3 and 1).
Starting from a single C=1 cell at the top and applying the rules as we step down
through the pattern (each line downward corresponds to a new time step) we get the
following patterns for rules 90 and 110 when C=1 is a color and C=0 is white.
1D Rule 90 1D Rule 110
The rules for 2D CA.
The 2D rules don't depend on which neighbor is 0 or 1, as above, but only on how
many of its neighbors are 1. We will use the notation <K|C> where K is the
number of neighbors in state 1 and C is the state of our automaton. Then the order
in n that we will use for the rules when the neighborhood is defined as 8 cells
n=17 16 15 14 13
12 11 10
9 8 7 6
5 4 3 2
For neighborhoods with 4 cells, only n=9 down to 0 are relevant. There are a total
of 2^9 = 512 rules for 4 cell neighborhoods. For the 8 cell neighborhoods there
are a total of 2^17 = 131,072 rules.
Suppose you wanted to impose the rule that C changes state when there are 4 neighbors
(n=9 and n=8), is =1 when there are 3 neighbors (n=7 and n=6), stays the same if
there are 1 or 2 neighbors (n=5 and n=4 and n=3 and n=2), and is =1 if the are no
neighbors (n=1 and n=0). The pattern for this rule would be (0111101011) and the
code would therefore be 2^8+2^7+2^6+2^5+2^3+2^1+2^0=
the rule we want to impose is coded as rule 491.
Working backwards, what would the 8 neighbor code 175,850 mean? Well, 178,850 =
2^5+2^3+2^1(=131,072 + 32,768 + 8,192 + 2,048 + 1,024 + 512 + 128 + 64 + 32 + 8 + 2).
So the pattern would be (101010111011101010) which means that C= 1 whenever there
are 3 or 5 neighbors and remains unchanged in all other cases.
We get the following patterns for rule 491 starting from a single cell in the center
and running for 44 steps, and for rule 178,850 starting from a row of 11 cells in
the center and running for 100 steps.
CA175850_100 (notice that the initial position are the 7 black cells in a row at the center)
One well known rule for an 8 neighbor CA is John Conway's game of Life. This rule
states that: if there are fewer than 2 neighbors, C is dead (from loneliness); if
there are more than 3 neighbors, C is dead (from overcrowding); if there are just
3 neighbors C is alive; and if there are only 2 neighbors, C remains unchanged.
If we equate being dead with C=0 and being alive with C=1, the pattern for the rule
is (000000000011100000). This corresponds to 2^7+2^6+2^5 = 128+64+32 = 224. So,
Conway's Game of Life is rule 224 for 8 neighbors applied to various starting patterns. Playing
the game involves finding starting patterns that evolve into dynamic and persistent
patterns as the number of time steps increases.