Registered: Feb 2004
Posts: 2

I'm looking for how 2D CAs are enumerated w.r.t the CellularAutomaton function. I've been trying to crack this on my own using the example of rule numer 797, 9-neighbor totalistic, given in the documentation without any success.

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 46

The enumeration of the 2-D 9-neighbor totalistic cellular automata works as follows.

Let's say we have k colors. So the values of individual cells are in the range 0 to k-1.

If you write the rule number in base-k, so for instance your 2 color rule 797 is 1100011101 in base-2, then the digits, read from right to left, give the outputs of the rule when the totals of the 9 cell values are 0 to 9 (k-1) respectively.

So a total of 0 will give an output of 1 (the rightmost digit), a total of 1 an output of 0 (the next digit left), a total of 2 an output of 1, and so on.

Note that 9(k-1) is the maximum possible total value of all 9 cells, and so there are 1+9(k-1) digits in all.

Because we can choose each digit in the rule number independently there are k^(1+9(k-1)) possible rule numbers.

Please say if this does not answer your query in any way.

In Mathematica, to convert from a number to it's digits in base-k you use IntegerDigits[number, k, number of digits], so internally when CellularAutomaton gets a matrix of the 9 cell values it effectively uses the procedure:
Part[IntegerDigits[rule number, k, 1+9(k-1)], -(1+Total[cells, 2])]
to find the new cell color.

To get a list of replacement rules describing the rule explicitly for a given rule number one can use:
 Table[ Partition[IntegerDigits[i, k, 9], 3] -> Part[IntegerDigits[rule number, k, 1+9(k-1)], -(1+Total[IntegerDigits[i, k, 9]])], {i, 0, k^9-1}] 

Report this post to a moderator | IP: Logged

Registered: Feb 2004
Posts: 2

Ok, that's helpful for totalistic rules, but what about non-totalistic ones?

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 46

For general rules, we choose an output color for each of the neighborhood patterns.

So for example:

0 0 0
0 0 0 -> 1
0 0 0

0 0 0
0 0 0 -> 0
0 0 1

... and so on for all the other cases (k^9 in all).

The digits on the right of the arrows become the digits of the rule number.

The position of the digits is found in the following way:

a b c
d e f
g h i

has the digit 1+FromDigits[{a,b,c,d,e,f,g,h,i}, k] digits from the right of the rule number.

If the 9 cells are given as a matrix this is just 1+FromDigits[Flatten[cells], k]

For example, the all 0's pattern has the rightmost digit, and the all 1's pattern (for 2 color rules) has the leftmost digit.

Part[IntegerDigits[rule number, k, k^9], -(1+FromDigits[Flatten[cells], k])] gives the ouput for a given 9 cell matrix.

To get a list of replacement rules describing the rule explicitly for a given rule number one can use:
Table[Partition[IntegerDigits[i, k, 9], 3] -> Part[IntegerDigits[rule number, k, k^9], -(1+i)], {i, 0, k^9-1}] 

Report this post to a moderator | IP: Logged

Registered: Apr 2006
Posts: 17

How do we describe 3-D cellular automata, the author, stephen wolfram, does not describe the system so that i can understand it.

Report this post to a moderator | IP: Logged

Registered: Feb 2006
Posts: 8

Originally posted by Richard Phillips
For general rules, we choose an output color for each of the neighborhood patterns...

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

Those are outer totalistic rules. Basically, the totalistic scheme is applied for all cells except the center cell, but then duplicated for the two different cases, center cell = 0 and center cell = 1.

In the case of a 5 neighbor 2 color rule, that makes for 10 possible cases in the rule table.

outer total 4 and center cell 1
outer total 4 and center cell 0
outer total 3 and center cell 1
outer total 3 and center cell 0
outer total 2 and center cell 1
outer total 2 and center cell 0
outer total 1 and center cell 1
outer total 1 and center cell 0
outer total 0 and center cell 1
outer total 0 and center cell 0

Where "outer total" means the sum of the site values you have labeled b, d, f, and h.

The idea is to treat the rule number as having a "mixed base", with the "last digit" based on the center cell value and ranging from 0 to the number of colors minus 1, and the preceeding "digit" - of weight, number of colors, just as the second digit in standard arab numerals has weight 10 - based on the outer total, with a value ranging from 0 to (neighborsize without center cell) * (colors -1).

When you use a full 9 neighbors, there are 18 cases in the rule table, from 9 possible outer totals (0-8) and 2 center cell values (0,1).

In Mathematica, the CellularAutomaton function takes a "kernel" argument in the rule portion, that specifies "weights" at different offsets. An outer totalistic rule can be specified by using a weight of 1 for the center cell, and a weight of k (number of colors) for all the others meant to be in the neighborhood. Thus -

{{0,2,0},{2,1,2},{0,2,0}} - as a table of weights, gives an outer totalistic 5 neighbor rule for 2 colors.

{{3,3,3},{3,1,3},{3,3,3}} - would give the weights for an outer totalistic 9 neighbor rule with 3 colors.

I hope this helps.

Report this post to a moderator | IP: Logged

Registered: Feb 2006
Posts: 8

hi Jason,

Thanks very much for your reply. In case anyone else reads this page, I want to add that the figures on page 173 are 5 neighbour rules and the correct expression for indexing the digits of the 5 neighbor outer-totalistic rule is:

k*(1 + (k-1)*5) - e - k*(b + d + f + h)

where k is the number of colors and (b, d, e, f, h) are the values given at cell locations from my first post.

Report this post to a moderator | IP: Logged

Registered: Mar 2004
Posts: 132

2-D cellular automaton rules that are up-down reflections, left-right reflections, and rotations of 90, 180 and 270 degrees are all essentially the same rule and therefore exhibit the same behavior. For 3-D cellular automata there are more identical rules. rules that contain symmetries in their construction will not have an 'alter' rule in that degree of symmetry, of which could be either rotational or line type. There might be more? Whats the pattern and how do we enumerate all the essential cases while skipping past the redundant ones?

Report this post to a moderator | IP: Logged

Registered: Apr 2007
Posts: 5

Sorry if I jump so late on this discussion, but I dont' understand a point:

Originally posted by Richard Phillips
...
The digits on the right of the arrows become the digits of the rule number.

The position of the digits is found in the following way:

a b c
d e f
g h i

has the digit 1+FromDigits[{a,b,c,d,e,f,g,h,i}, k] digits from the right of the rule number.

If the 9 cells are given as a matrix this is just 1+FromDigits[Flatten[cells], k]

For example, the all 0's pattern has the rightmost digit, and the all 1's pattern (for 2 color rules) has the leftmost digit.
...

Report this post to a moderator | IP: Logged