A New Kind of Science: The NKS Forum > Applied NKS > Numbering scheme on page 173
Author
Ayhan

Registered: Dec 2004
Posts: 4

Numbering scheme on page 173

Hi at all,

i don't understand the numbering scheme on page 173:

http://www.wolframscience.com/nksonline/page-173

on the page 171 are two pictures with the code 1022 and code 942

http://www.wolframscience.com/nksonline/page-171

and on page 177 is another picture

http://www.wolframscience.com/nksonline/page-177

can somebody explain this to me.

I am very thankful for every help.

Ayhan

Report this post to a moderator | IP: Logged

12-15-2004 10:42 AM
Jason Cawley
Wolfram Science Group
Phoenix, AZ USA

Registered: Aug 2003
Posts: 712

When you want to refer to a page in the NKS book, you don't need to provide the whole URL. We have a shortcut set of tags for that, since it is a common thing to want to do. Just enclose the page number in "pg" --- "/pg" tags, inside square brackets. So for example, to give you a link to page 927, I just write -

927

Next, when you have a question about implimentation details or code referred to by the book, the first place to check is in the notes to the page you are on. In this case, there are notes on page 927 - that is why I picked that one, above. Implimentation of 2D Cellular Automaton explains the code used to generate those pictures. It explains the numbering scheme, as based on IntegerDigits[rule,2,10]. Another note on that page explains the total number of rules of various types.

All of that is general stuff; it may not answer your specific question.

The rules on the pages you refer to are what are called "outer totalistic" rules. That means the surrounding cells only effect the next color of the center cell, after being totaled - their exact pattern aka configuration does not matter, only how many are black and how many are white (for the 2 color case, that is). The center cell matters independently; it is not totaled with the others. That is what makes them "outer totalistic", rather than just "totalistic", rules. Totalistic rules, simply, means the center cell is tossed into the totaling along with the rest.

So, how many cases are there, if the neighborhood is the four adjacent cells? Well, none of the outer cells might be black - then the total would be 0. Or all of them might be black - then the total would be 4. Or anything in between. So there are 5 possible values for the outer total - {0,1,2,3,4}. Then the center cell could be black or it could be white - independent of the above. That means the possible combinations are any of 0-4 with 1, or any of 0-4 with 0, for a total of 10 possible cases. The center cell then updates to either a 1 or a 0, depending on the rule for the case that applies at that position. So, there are 2^10 = 1024 possible outer totalistic, 2 color rules, with a 4 neighbor neighborhood.

What is the numbering scheme for those rules? Effectively, you want the cases "paired up", outer total 4 with center cell 1, outer total 4 with center cell 0, outer total 3 with center cell 1, outer total 3 with center cell 0, etc, all the way to outer total 0 with center cell 0. That gives 10 cases, and we give each a digit, in that order. Then the value of that digit - 1 or 0 - says what the center cell is to become if that case applies.

So let's look at the digits for the rules in the examples on those pages. Rule 1022 tells us -

IntegerDigits[1022,2,10]

{1,1,1,1,1,1,1,1,1,0}

Meaning, the only way the center cell can become white, is if it and all its neighbors were white on the previous step (0 outer total, and 0 center cell). That yields uniform growth - anything next to any number of black cells becomes black and stays that way.

If we look instead at Rule 942, we see -

IntegerDigits[942,2,10]

{1,1,1,0,1,0,1,1,1,0}

To make that a little easier to read, let's apply a little trick to break it up into pairs -

Partition[IntegerDigits[942,2,10],2]

{1,1},{1,0},{1,0},{1,1},{1,0}

The first part is always 1, and that is telling us what to do if the center cell is black. Answer, it stays black. The second part tells us what to do if the center cell is white. That stays white (0) in the outer total cases 3, 2, and 0. So the center cell only changes - and only from white to black - if it is white to start with, and the outer total is exactly 4 or is exactly 1.

Part of your confusion may stem from the later use of a much higher number, employing the same scheme. On page 177, the rule shown is Rule 175850. How did we get a number larger than 1024? This is showing a 9 neighbor rule, including diagonals as neighbors. So now the number of possible totals is 0 through 8. To cover all the cases, we now need 18 binary digits rather than 10 - any of {0,1,2,3,4,5,6,7,8} for the outer count, and 1 or 0 for the center cell. Our digit representation of the rule therefore becomes outer total 8 and center cell 1, outer total 8 and center cell 0, outer total 7 and center cell 1, etc. And there are -

2^18 = 262144

possible rules of this type. The particular rule shown on page 177 has rule number 175850. Let's look at its digits -

IntegerDigits[175850,2,18]

{1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,0}

Partition[%,2]

{{1,0},{1,0},{1,0},{1,1},{1,0},{1,1},{1,0},{1,0},{1,0}}

So that is {1,0} for most possible outer totals, which just means the center cell stays 1 or 0 when it is 1 or 0. The exceptions are outer totals 5 or 3, when the center cell becomes 1 (black) even if it is 0 (white) beforehand. That gives nearly circular growth, from the right sort of seed.

These days we can evolve these CAs in Mathematica using the built-in CellularAutomaton function. You just need to know the right rule form to give it, to specify an outer totalistic rule with a given neighborhood. The help file entry for CellularAutomaton explains that. But for convenience, an outer totalistic 2 color rule is specified by e.g. -

{942, {2, {{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}}, {1, 1}}

- as the first argument of the CellularAutomaton function. The first bit is the rule number in the same scheme as in the book. The last bit is giving the range and dimensions - range 1 in each of 2 dimensions, thus {1,1}. The first part of the middle bit "2," is just specifying the number of colors. The center portion has a small 3 by 3 matrix, which is a "kernel" of cell "weights". The 0s say to ignore the diagonals. The 1 in the middle specifies the center cell as the least significant "bit" in the rule. The "2"s put all the others into the same second "bit", thus making an outer totalistic rule. You can do a lot with the kernel options in the built in CellularAutomaton function, but that is an advanced topic.

From what has already been said you should be able to see what you do to make it a 9 neighbor outer totalistic rule instead. Just fill in the 0s in the kernel with more 2s -

{175850,{2,{{2,2,2},{2,1,2},{2,2,2}}},{1,1}

You also have to specify an initial condition of the proper form. For a 2-D, 2 color CA, that is any array of 1s and 0s. (You can build those easily with "Table", sometimes using "ReplacePart" in addition). Also, to see just the pattern on the final step, you take "last" of the series of arrays the CellularAutomaton function will hand you back. So for example, to make something like the pictures on those pages, you would use -

ArrayPlot[Last[
CellularAutomaton[{942, {2, {{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}}, {1, 1}},
ReplacePart[Table[0, {100}, {100}], 1, {50, 50}], 22] ]]

ArrayPlot[Last[
CellularAutomaton[{175850, {2, {{2, 2, 2}, {2, 1, 2}, {2, 2, 2}}}, {1, 1}},
ReplacePart[Table[0, {300}, {300}]
1, {{150, 147}, {150, 148}, {150, 149}, {150, 150}, {150, 151}, {150,
152}, {150, 153}}], 200 ]]]

I hope this helps.

Report this post to a moderator | IP: Logged

12-15-2004 03:46 PM
Ayhan

Registered: Dec 2004
Posts: 4

You helped me very much, I still wish you a beautiful day.

Report this post to a moderator | IP: Logged

12-16-2004 09:26 AM
Jesse Nochella
WRI

Registered: Mar 2004
Posts: 132

other codes?

Hello,

A question that I should of asked before your reply, Jason. It was in regard to a scheme for all possible 2 dimensional rules of a certain range and color, including 4 and 8 neighbor ones.

I'm not sure of what the convention is. There are multiple schemes for classifying diffirent kinds of rules in a great little program I play around with called "Merik's Cellebration". The particular one that I'm interested in is just the raw unrestricted "Neumann binary" one that involves all possible 2-dimensional rules to be set up. They can be quite long. I have a rule that I've set up in MCell but it is not totalistic and I want to implement it into Mathematica

Is the convention like standard Wolfram codes where the states are just converted into numbers and sorted by value in a right to left fashion? Would 3-d rules then be just partitioned into a matricies like say:

.......{110011101,1}.... would be in a rule where

110
011 -> 1
101

I guess I'm just a little confused about whether the CellularAutomaton function is by default set up to only read totalistic 2-d codes or not. Is there a quick way to set up CellularAutomaton to read these Neumann codes? What about other codes?

You can just point towards a resource if I've missed something thats already out there. NKS doesn't seem to go into much depth about non-toatlistic 2-dimensional codes. I guess thats because presumeably there is nothing captured by them that any 1-dimensional rule rule captures better. I dont know about that, there's a lot of rules out there.

Thanks.

Report this post to a moderator | IP: Logged

12-16-2004 09:24 PM

wolframscience.com  |  wolfram atlas  |  NKS online  |  Wolfram|Alpha  |  Wolfram Science Summer School  |  web resources  |  contact us