A New Kind of Science: The NKS Forum > Pure NKS > Enumeration of 2D CAs
Author
Jamie Raymond
Northeastern University
Boston, MA

Registered: Feb 2004
Posts: 2

Enumeration of 2D CAs

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

02-25-2004 05:28 PM
Richard Phillips
Wolfram Science Group
Boston, USA

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.

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

02-26-2004 04:40 AM
Jamie Raymond
Northeastern University
Boston, MA

Registered: Feb 2004
Posts: 2

Report this post to a moderator | IP: Logged

02-27-2004 10:18 PM
Richard Phillips
Wolfram Science Group
Boston, USA

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

03-01-2004 02:11 AM
mohammed1

France

Registered: Apr 2006
Posts: 17

3-D cellular Automata

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

04-26-2006 09:59 PM
Chris Smeenk

Registered: Feb 2006
Posts: 8

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

Hello Richard Phillips,

I too have been struggling with these 2D automata, and your post is helpful. I am trying to validate a program I wrote for the 2D automata by replicating the output on page 173. Based on the caption on this page it seems like the rules are a hybrid of totalistic and non-totalistic: the output depends on the value of the center cell in particular and also on the the sum of the values in its neighbours.

Let the cells be labelled:

a b c
d e f
g h i

I think one way to capture the description given is to index the rule using

1 + 9 - e - e*(a + b + c + d + f + g + h + i)

this way when the central cell (e) is off, the process returns the value of the last bit; when it is on, the process returns the totalistic value. This index is used to get the value of the central cell at the next step. Unfortunately, I have been unable to duplicate the figures on page 173.

Any suggestions or comments are much appreciated. Also, if you wouldn't mind avoiding the use of Mathematica code in your response, I will be happy. thank you.

Report this post to a moderator | IP: Logged

05-18-2006 03:05 PM
Jason Cawley
Wolfram Science Group
Phoenix, AZ USA

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

05-18-2006 03:30 PM
Chris Smeenk

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

05-18-2006 04:45 PM
Jesse Nochella
WRI

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

05-18-2006 10:51 PM
Alessandro

Registered: Apr 2007
Posts: 5

a little clarification

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

so the pattern:
0 0 0
0 0 0
0 0 0

has identifier 1, while the pattern;

1 1 1
1 1 1
1 1 1

has identifier 111111112, right?

What is not clear to me is how to identify the rule: given e.g. the pattern 111111112, the rule could be to translate the central '1' to either '0' or '1': how do I enumerate the rules themselves, not the patterns?

thanks for any help...

Alessandro

Report this post to a moderator | IP: Logged

05-02-2007 12:35 PM

wolframscience.com  |  wolfram atlas  |  NKS online  |  web resources  |  contact us