[2D CA Rules (regular and totalistic) help] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


2D CA Rules (regular and totalistic) help

(Click here to view the original thread with full colors/images)


Posted by: Guy Israeli

Hello all

can anyone direct me or explain in how 2D CA rules work?

I've seen in other posts that for 9 neigh rule it goes something like that (example)

0 0 0
0 0 0 -> 1
0 0 0

but where is that 1 placed? How do I determine the 9 rules?

I know (probably so do you) that for 1D CA that 0 0 0 will result in a 1 or a 0 directly below the middle digit.

How does it work with 2D? Also, if possible a short explaination for 1D but a bigger radius..

I know I've asked a lot of questions, any answer will be greatly appreciated.

Thank you very much,

Guy


Posted by: Jason Cawley

The right hand side is the new value of the center cell, the middle of that left hand side pattern. The rule scans over the whole array with a moving "window" or partition. Each center cell has a slightly different local pattern, but shares cells with the pattern for the ones next to it. For instance, if I number 12 cells 1-9, A for 10, B for 11, C for 12, just to ID the locations (not saying anything about the cell value there) -

1234
5678
9ABC

Then the neighborhood for updating cell 6 is

123
567
9AB

The neighborhood for updating cell 7 is

234
678
ABC

Then the rule needs cases for all the patterns that can happen. There are 2^9 two color patterns, starting with -

000
000
000

And ending with

111
111
111

The first few are

000
000
000

000
000
001

000
000
010

000
000
011

Where effectively I am counting in binary, with lower right the least significant digit, and upper left the most significant digit. Those are the cases for the rule. Each one goes to a 0 or to a 1.

Notice, a single 9 neighbor, 2 color rule has 2^9 = 512 different cases. The whole rule looks something like this -

If {{0,0,0},{0,0,0},{0,0,0}} then replace center cell with 1
If {{0,0,0},{0,0,0},{0,0,1}} then replace center cell with 0
If {{0,0,0},{0,0,0},{0,1,0}} then replace center cell with 1
If {{0,0,0},{0,0,0},{0,1,1}} then replace center cell with 1
...
If {{1,1,1},{1,1,1},{1,1,1}} then replace center cell with 0

For 512 cases, each a different "If". The rule number is then the sequence of 512 binary digits - those right hand side 1,0,1,1... numbers strung together into one big binary number. We say, the rule number encodes what to do in each of the cases that can arise for that type of rule. Each digit of the rule number tells us what to do in a different case.

In execution, I scan through the array with a partition, getting a 3 by 3 block. I compare the block I have to the cases of the rule, to "look up" the right case. For instance, if I see the pattern -

001
010
001

what case of the rule should I use? I have a 1 in the least significant digit aka the 2^0 digit, another in the 2^4 digit, and another in the 2^6 digit. So I need case 1 + 16 + 64 = 81. If case 81 is a 0, the center cell goes from 1 to 0. If case 81 is a 1, the new center cell stays 1. Then I move to the next bit of the array and do it all over again.

For every cell in the array, I have to find its neighborhood, look up that pattern as a left hand side to find the right "If" in the rule, read out the result that case is supposed to go to, and make the new value of that cell, that right hand side.

All of which can be optimized by Mathematica functions like Partition to get neighborhoods, and looking at just the needed digits to get the result. Or just use the further optimized built in function CellularAutomaton to do it for you.

All the executions are effectively done simultaneously, or in other words the old array values are used for all the partitions, to get all the new array values.

Now, consider instead a 1D case with a larger neighborhood. Say range 2. Now I need a partition into blocks 5 cells wide to settle what each new center cell will become. But the rest of the scheme is the same. There is some neighborhood of cells overall, thus some overall number of possible combinations of them, going up as color ^ total size of neighborhood. A rule needs that many cases in its rule table. Each one can go to any of the k colors (here, 0,1 to keep it simple). So the number of (general) rules goes as colors ^ (colors^neighborhood size).

For the ECAs, that is 2^(2^3) = 2^8 = 256. 2 colors, 3 neighbors, 8 cases, 256 possible ways of treating each of the different combinations of cases. A specific rule (like e.g. rule 30) is a particular combination of ways of treating all of the different cases that might arise. In case 1, do this, in case 2, do that, through all the possible cases. We say, it is a complete dispatch table.

With large neighborhoods, there are lots of possible rules. So people have come up with some simpler schemes, which are subsets of all the possible rules, but not quite as many. For instance, you can consider only those general rules that treat all of the cells around the center one in the same way, depending only on the number of them that are 1 or 0, not which way. These are called "outer totalistic" rules. All that means is that a pattern like this -

110
101
100

Has to have the same right hand side as a pattern like this -

101
001
011

Because both of them have 5 1s around a 0. All the other patterns = cases with a central 0 and 5 1s would also have to go to the same thing as these two.

But such schemes are deliberate simplifications of the more general case, where every distinct possible local pattern can have a different right hand side. They can be confusing, if one thinks they are somehow the essence of 2D CAs or the only way to set them up - they aren't. They are a "slice" through general 2D CAs of that number of colors, that happen to have various symmetries in them.

I hope this helps. If there is another aspect of the subject that remains unclear, be more specific about where, and I'll try to explain.


Posted by: Guy Israeli

thank you very very very much for that lucid explanation

exactly what I need




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