[Enumeration of 2D CAs] - A New Kind of Science: The NKS ForumA New Kind of Science: The NKS Forum
Pages:1
Enumeration of 2D CAs
(Click here to view the original thread with full colors/images)
Posted by: Jamie Raymond
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.
Posted by: Richard Phillips
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}]
Posted by: Jamie Raymond
Ok, that's helpful for totalistic rules, but what about non-totalistic ones?
Posted by: Richard Phillips
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}]
Posted by: mohammed1
How do we describe 3-D cellular automata, the author, stephen wolfram, does not describe the system so that i can understand it.
Posted by: Chris Smeenk
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.
Posted by: Jason Cawley
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.
Posted by: Chris Smeenk
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.
Posted by: Jesse Nochella
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?
Posted by: Alessandro
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
Forum Sponsored by Wolfram Research
© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. |
Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings