Wolfram Science Group
Phoenix, AZ USA
Registered: Aug 2003
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 -
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