The rules for 1D CA.
An elementary CA 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 7 cells in
the center and running for 100 steps.
CA Pattern Maker allows for there to be multiple adjacent starting cells. This is done by appending to the input rule number "_n" where n is the number of starting cells.
CA175850_7_100 (the_7 means that there were 7 adjacent initial center cells and the_100 means that the pattern was run for 100 steps. )
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.