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

REH ORCID Research Gate

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           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 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.

Copyright © 2009 - 2022 Roger E. Hill. All rights reserved.      Contact: