[About Rule chosen] - A New Kind of Science: The NKS ForumA New Kind of Science: The NKS Forum
Pages:1
About Rule chosen
(Click here to view the original thread with full colors/images)
Posted by: Stephane
I have probalbly a naive question.
If there is only 255 rules in NKS.
When I look on the NKS summer school
I see scientist'project - saying >
Favorite Outer Totalistic 3-Color Rule Rule chosen: 10667314
Where comes from this rules and how I choose them ? 10667314
Thank you in advance
stephane
www.mem-son-mem-image.com
Posted by: Jason Cawley
There are 256 elementary CA rules, numbered 0 to 255, because there are 2 possible colors for the center cell on the next step, the one being updated, and 8 possible patterns of the cells above, from each of 3 cells being one of two colors. That is, the elementary 256 comes from 2 ^ 2 ^ 3.
If we increase the number of colors, we increase both of those 2s to 3s. So a general 3 color, range 1, 1 dimensional cellular automaton can be any of 3^3^3 possible rules, which is 7.6 trillion possible rules. As you can see, increasing the base number of colors has a huge impact on the size of the rule space.
That is for general rules, meaning the value of the center cell on the next step depends on the exact combination of colors above. If the cells above are 2-1-0, that is a different pattern from 0-1-2, for instance (in the general rule case). Because the whole space gets so large, we can consider special, smaller rule spaces that don't depend on every detail of the prior arrangement. That gives us the idea of totalistic and outer totalistic rules.
With a totalistic rule, we don't care about the exact pattern on the previous line. Instead we just add the previous cell values up - so 2-1-0 and 0-1-2, as well as 2-0-1 and 1-1-1, will all have the same updated value for the cell below - because they all have a total cell value above, of 3.
How many 3 color totalistic 1D range 1 rules are there? Well, if you add up 3 numbers, each of which is 0, 1 or 2, the total can be anything between 0 and 6. That makes 7 possible cases. The next cell can be any of 3 things (0, 1, or 2), so we have 3^7 possible totalistic 3 color rules (staying range 1 and 1 dimensional). 3^7 is 2187. Notice, much fewer than the general rule space, because we have only one power, not 2. Or otherwise put, because we are raising the base number of colors (the first 3) to a power of only the 7 possible totals as rule cases, instead of 27.
Now, outer totalistic means we do the totaling thing for the left and right neighbor cells (or in general, the neighborhood other than the cell being updated, itself), but let the center cell still matter "independently". That is, we have the follow distinguished patterns -
Outer total is 4 and the center cell is 2
Outer total is 4 and the center cell is 1
Outer total is 4 and the center cell is 0
Outer total is 3 and the center cell is 2
Outer total is 3 and the center cell is 1
Outer total is 3 and the center cell is 0
Outer total is 2 and the center cell is 2
Outer total is 2 and the center cell is 1
Outer total is 2 and the center cell is 0
Outer total is 1 and the center cell is 2
Outer total is 1 and the center cell is 1
Outer total is 1 and the center cell is 0
Outer total is 0 and the center cell is 2
Outer total is 0 and the center cell is 1
Outer total is 0 and the center cell is 0
Since there are five possible outer totals - 0 through 4 from adding up 2 numbers each 0 through 2 - there are 15 cases all told. Each of which could tell the center cell to become a 0, or a 1, or a 2. So the rule space for outer totalistic 3 color rules (still range 1 and 1 dimensional) is 3^15, which is 14,348,907 possible rules.
That was the rule space we asked students to pick their personal favorite from (that year - different years we have used different rule spaces). We deliberately picked a space large enough that there would be essentially no chance anyone's favorite was also someone else's, but also moderate enough that computer search within it works.
The distinctions between general, totalistic, and outer totalistic rules frequently raise questions like this. You aren't the only one who asks it. Notice that the totalistic rules are a proper subset of the outer totalistic ones, which in turn are a proper subset of the general rules, for the same number of colors and size of neighborhood. Also notice that the totalistic and outer totalistic rules are forced to have more symmetry than the general rules, because they can't treat right and left neighbors differently.
I hope this helps.
Posted by: Stephane
Thank you for your answer, Jason, your answer are always very completed and are very usefull for a person that are not a scientist.
I will appreciate if you have the time to describe this in detail :
ArrayPlot[
CellularAutomaton[{13723198,
{3, {3, 1, 3}}},
{{1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1}, 1},
{1000, All}]]
(I pick up this exemple from Tommaso Bolognesi mix with Doron Bergman Students study)
ArrayPlot[CellularAutomaton[{455 ,
{3, {3, 1, 3}}},
{{1, 0, 2, 2, 2, 1, 2, 0, 1}, 0}, 1,
(why this part is shorter)
{100, All}]]
Maybe you have already answer it before ?
I'm aware of my ignorance
Thanks
stephane
www.mem-son-mem-image.com
Posted by: Jason Cawley
Not a problem, it is why we are here.
OK, I'll take Tomasso's favorite rule first, it is one I like.
ArrayPlot is a built in Mathematica function that accepts a data array and returns a color shaded plot (by default, in grey level colors). It is wrapped around the CellularAutomaton evolution to display the results, and plays no further part here. I might, incidentally, add my favorite color scheme for 3 color CAs at the end, between the last two closing braces -
, ColorRules -> {0 -> Yellow, 1 -> Red, 2 -> Black}
But that is purely aesthetic.
The CellularAutomaton function call has 3 major parts, each can have subparts (and in this case does). The first is the rule specification - which CA from which family to run. The second is the initial condition - what pattern of colors or site values appears on the first row, that the rule operates on for the rest of the evolution. The third is a generalized number of steps to run the rule for - where by generalized, I mean it can also include options about what part of the result to return.
The rule specification in Tomasso's favorite rule is this part -
{13723198, {3, {3, 1, 3}}},
The first piece is the rule number, and specifies exactly which rule to use out of the whole family. The second piece gives the rule family, here an outer totalistic, 3 color, 1 dimensional, range 1 rule. How does {3, {3,1,3}} say all that?
The first 3 is the number of colors. The next bit, the list {3,1,3} is called the kernel, and gives the weights to be assigned to each cell in the rule's neighborhood. Since the kernel is a 1 dimensional list, it is a one dimensional rule. A 2D rule would have a matrix there instead. Since the kernel is 3 elements long, the rule is range 1 - the middle one is the center cell weight, and the others are 1 away on each side. If it were a range 2 rule, the list would need to be 5 elements long.
OK, but why are the elements themselves {3,1,3}? That pattern, where the outside elements are the same value as the number of colors, and the center cell is a 1, is the pattern that gives an outer totalistic rule. It is saying, take the left element and multiple it by 3, the center element and multiple it by 1, the right element multiplied by 3, add them all up. That number is the case of the rule table to use. Well, since both sides are 3, they are interchangable - a 2 on the right or on the left has to act the same, since each will add 6 to the case to use. The middle cell will matter independently, because the "outer total" will always be divisible by 3 - 0, or 3, or 6, or 9, or 12. The case being used "mod 3", will always be the value of the center cell.
If you wanted a totalistic rule, you would have a kernel of {1,1,1} instead. Or if you wanted a general rule, with all possible arrangements treated differently, you could use {9,3,1} (with each entry the number of colors raised to a different integer power - the "1" being 3^0).
That is a lot of internal minutae about how that rule specification manages to say "this is an outer totalistic 3 color range 1 rule". Doron's rule is the same pattern, just a smaller rule number.
OK, now on to the next bit, the initial condition. That is the part that in Tomasso's favorite case reads -
{{1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1}, 1},
It has two parts - first a list with (in this case) 0s and 1s in it - it could have 2s as well, since this is a 3 color rule, but his specific initial condition doesn't happen to start with any 2s in it. And then that ", 1}" at the end. That says, "embed the previous list in a sea of "1"s, repeated. In other words, the initial condition is all 1s outside of the specified list, and is a mix of 1s and 0s inside.
In Doron's initial condition, there are 2s as well, but it is a shorter list. That just means he starts from a narrower pattern. You can go as short as the simplest possible "seed" - {{1},0} means a single "1" surrounded by 0s. You can also have a repeating pattern rather than a single color as a background e.g. you could put Tomasso's list on a background of {0,1,2,1,0} repeating "blocks" instead of a background of 1s, by having the initial condition read -
{{1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1}, 0,1,2,1,0},
OK, last bit. It is the part that reads {100, All}. That means "run this rule from the specified initial condition for 100 time steps, and show me every cell that could have been affected by the evolution, whether it was or not."
So, the part you specifically asked about - why is Tomasso's initial condition wider than Doron's - is just, he picked that one. Any list will work there; each possible list you'd put in would be the same rule, but started off from a different pattern.
I hope this helps.
Posted by: Stephane
Hi Jason,
Thank you again for this clear explanation.
I wish you could explain the all NKS book like that. :)
May I dare a suggestion ?
In this forum there is Artistic NKS where there is not so many post like in 'pure NKS', as you know.
I think one of the reason is that for most artists the mathematical level or programming level are not very developped.(it's my case) but I'm crazy interessted about it and i see the amazing potential.
As I see your post, with your kind and clear explanation. The idea come's up :
Why the NKS staff (if they have some time to spare) will not make a tutorial "special for artist".. or beginners.
We can imagine some goals, for example to create a demonstration applet like "the tractable shape of Maurice Martel" or other tools that I saw on the demonstrations.wolfram.com, I think with some focused tutorials. it will lovely for the artistic communauty and we will have some exploration to do. This wish is also true for the fantastic Michael Trott's books.
Thank you for your attention.
Stephane
Ps. About "demonstration" is it possible to customize the button and layout ?
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