Roger Eugene Hill
The life, career, scientific and spiritual insights of a physicist plus a few excursions into Complexity Science and Art.


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           6             5           4                3           2            1           0 .

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 1D CA.

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.

CA90 CA110
        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 is:




n=17    16      15     14     13     12     11    10      

   9       8         7       6       5      4      3    2       

    1      0.

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= 256+128+64+32+8+2+1=491. So, 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^17+2^15+2^13+2^11+2^10^2^9+2^7+2^6+
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.
Copyright © 2009 - 2020 Roger E. Hill. All rights reserved.      Contact: