Registered: Feb 2009
Posts: 1

In NKS, on page 173, there is a description of 2-d CA programs and a statement about the conventions for naming these rules. As I understand things, the code 454 (for instance) corresponds to binary 111000110, which is a tally of all the on/off states for a table of different cell configurations. What I'm not sure about is what this table looks like, because as I try to work this out on paper, I'm not sure where to go with the author's directions and the range of possible on/off cell configurations would seem to require another binary digit. What am I missing? I'm seeking the kind of rule table/explanation for these 2-d code rules that the author charts out on pg. 25 for 1-d CA. So how to go about unpacking the codes? I'd also appreciate knowing the table configuration for Moore neighborhoods.

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

Those are outer totalistic rules with 4 neighbors, no diagonal connection.

Totalistic is a kind of symmetry - it means the behavior is not sensitive to the exact arrangement of surround values, but only to the total count of those values added together. Since that total is a many-to-one mapping, there are several configurations that will have the same output. For example, if there are 2 1s in the exterior 4 cells, it doesn't matter which 2.

The "outer" in "outer totalistic" means only the cells other than the center cell itself, are treated in that manner. The center cell still matters independently. This is in contrast to a full blown "totalistic" rule (totalistic "simply"), which lumps the center cell in with all of the others in a single total.

So, for an outer totalistic CA with nearest neighbors and 4 of them, how many possible distinct configurations are there? Suppose with 2 colors, to start.

Not 2^5, the number of configurations of 0s or 1s in each of the five cells, because that would have all the values matter independently. That is the right number of rule cases for a *general* 2 color, 5 neighborhood CA. But not for an outer totalistic one.

Instead, there are 4 cells in the outer total. Each can be a 0 or a 1. The sum of 4 numbers each of 0 or 1, will lie within the range 0 to 4. There are 5 possibilities for the outer total, therefore.

And there are 2 possibilities for the center cell, itself.

So there are 5 x 2 = 10 overall possibilities, that are distinct up to outer totalistic symmetry.

That means the rule table needs 10 individual rules in it, to specify what happens to the center cell on the next step, to be fully filled out.

Each individual rule can send the center cell to a 0, or to a 1. Independently.

So the total number of rules of this kind is 2^10 = 1024.

They are ordered as follows -

IntegerDigits[rule, 2, 10]

gives the right hand side values to be filled out - the values for the center cell in each of the 10 distinct "clauses" of the rule table. Those clauses themselves are -

Tuples[{{4,3,2,1,0},{1,0}}]

In English rather than Mathematica, that means the cases are -

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

With the first of those cases effectively counting as the "largest digit" in the rule number, and the 0 with 0 case counting as the "smallest digit" of the rule number.

So, rule number 0 sends all 10 of those cases to 0.
Rule number 1 sends the very last case to 1, all others to 0.
Rule number 2 sends the 2nd to last case to 1, all others to 0.
Rule number 3 sends the last 2 cases to 1, all others to 0.

Etc. Counting up to the 2^10-1 th rule, which sends all 10 cases to 1.

Now for a general CA rule with 9 neighbors (Moore), there is no outer total or total business going on. There are 9 neighbors and (with 2 colors) 2^9 rule cases to fill out (instead of 10), and 2 possibilities for each. Making for 2^(2^9) = 2^512 possible rules. Way too many to look at them all, though they can be sampled.

A table in the notes on page 927 gives the number of possible rules with various 2D CAs with different neighborhoods, symmetries, and totalistic schemes.

How are the general ones numbered, though?

The convention is that the upper left corner is the highest digit, the upper center is the next highest digit, the upper right the next highest, then the left center-row, then the center cell, then the right center-row, then the bottom left, then the bottom middle, then the bottom right. As though a 9 digit number were written with its first 3 digits on the top line, the next 3 on the middle line, and the smallest 3 digits on the bottom line. The upper left is the "256's place", the upper center is the "128's place", the upper right is the "64's place", etc.

I hope this helps.

Report this post to a moderator | IP: Logged

Registered: May 2011
Posts: 1

Hello - I am having a similar problem but enough different that the response doesn't solve my problem. Not only on P.173, but on P.928 there is a further discussion of symmetry rules, equivalence classes, and a statement that there are 12 bits and 4096 rules. All this in-turn references P.941 where the 32 possible configurations of a 5-cell neighorhood are discussed.

The twelve classes, deduced from the correlation of the info on P.928 with that on P.941, in the order listed on P.928 are:

11 - 5 black - all black
10 - 4 black - 3 outers and center
9 - 3 black - 2 adjacent outers and center
8 - 4 black - 4 outers
7 - 3 black - 3 outers
6 - 2 black - 2 adjacent outers
5 - 3 black - 2 opposite outers and center
4 - 2 black - 1 outer and center
3 - 2 black - 2 opposite outers
2 - 1 black - 1 outer
1 - 1 black - 1 center
0 - 0 black - all white

I assumed that this would be the bit order of the code from high to low and left to right. Upon implementing a program in this manner, I get the appropriate figures but against the wrong codes. Given the large number of codes, I am not keen on trying to ennumerate all the possibilities and pictures. I can only surmise that my assumption was incorrect. I have not been able to find a definitive statement as to the proper order. Your clarification is eagerly awaited.

Report this post to a moderator | IP: Logged