[Second Order Rules] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1

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

Posted by: Joseph Raschack

Introduction

I'm new here and I haven't read the book yet (I only found out about it yesterday) so I'll start by apologizing if this post is a repeat of someone else's proposal. I'd also like to explain my terminology, incase I misuse anything.

Rules

A Rule is a set of I/O listings for a blackbox (the theoretical blackbox, not the cellular one). The total listings are, sensibly enough, pow(base,input_terms) in number. (e.g., pow(2,3)==8) Therefor, Rule 110 is a Rule containing 8 possible input arrangements and their corresponding outputs.

First Order Rules

Rule sets are fine, if we want static, predictable growth patterns which, given time, can be modeled mathematically. But, by what mechanism are rules chosen?

First Order Rules determine the boolean output Y3 of a function taking 3 boolean arguments, X1,X2,X3. (Yea, I know people debate this, but every mathematical system is in some way interchangeable, so I consider the ease of switching terminology to be a good thing.)

Second Order Rules

Same game, but instead of bits, we use First Order Rules as our data type.

Any block inherits a combination of its 3 parents' rule sets. For example,

X1 X2 X3 X4 X5
X1 Y2 Y3 Y4 Y5

The determining rule set for Yn is Xn. The state of X(n+1) and X(n-1) are both used in determining if Y2 is set or clear, but their rules aren't used. Y2 is set if X2's rule says it is. (X1 and X3 don't have rules covering Y2.) So Y2 inherits a combination of rules X1,X2,X3, while Y3 would inherit X2,X3,X4.

We can think of it kinda like X2 is Y2's mother whereas X1 and X3 go on Jerry Springer to fight for a paternity test.

Rule Sets

All First Order Rules (all 256 of them) are a Rule Set, covering all permutations of 3:1 boolean I/O.

If we still assume 3:1 I/O, we get alot of Second Order Rules in our Second Order Rule Set.

As I said above, the number of ouput values is pow(base,input_terms). Since we have 256 different First Order Rules, we have a base of 256: pow(256,3) is the total number of possible input combinations (which means that there are also pow(256,3) corresponding ouput values). (pow(256,3)==16777216)

The total number of First Order Rules is 256, which is pow(base,output_values) (pow(2,8)==256).

So the total number of Second Order Rules is pow(256,16777216).

(As a sidebar, to determine the total number of possible Rules in a given ruleset: pow(base,pow(base,input_terms)) where base is the total number of values the data can take, i.e., each box is a digit.)

Ten Long Years

In other words, we might want some EXTREMELY simple mechanism for determining the new First Order Rule.

A simplified function for determining Y2 of a First Order Rule is:

rule(RuleN,x1,x2,x3) {
return bitof(RuleN, (x1<<2)|(x2<<1)|(x3));
}

(Note to the purist: the menu is not the territory, the map is not the meal, the implementation is not the equation.)

So a simple mechanism for determining the new rule set would be, if we have Second Order notation be similar to First Order:

rule(RuleN,x1,x2,x3) {
return RuleN[ (x1<<16)|(x2<<8)|(x3) ];
}

where RuleN is an array of pow(256,3) bytes, each holding the value of the new First Order Rule, and X1,X2,X3 are all bytes holding the current rules.

Someone else may be able to simplify it further, using a less data-heavy approach to having a 16 MB array to cover each Second Order Rule. (Dude, exponential growth sucks!)

Caveats

Second Order Rules are not just First Order Rules with a base-256 value system. Regardless of I/O type, a First Order Rule is static; all blocks are permuted in the same way. A Second Order Rule determines the permutation of the permutation system. Whereas First Order is DNA, Second Order is inheritance, mutation, and evolution.

PS: Don't no one go into seclusion over this. I'm sure a quick post on Slashdot will have us an implementation in no time fnord.

Posted by: Jon Awbrey

Joseph,

This sounds interesting, but is a little
hard to follow. I feel that there must
be some definitions and/or explanations
missing that it might help your reader --
me, anyway -- to know. Would you be
able to expand and fill a bit?

Thanks In Prospect,

Jon Awbrey

Posted by: Joseph Raschack

In a cellular automata, there is a grid of blocks. Each block has a property: color. The global rule is applied iteratively to the entire grid to determine the colors of the blocks.

In my version, each block has two properties: color and rule. The global rule tells how to combine the rule properties while each block uses its rule to determine the color of the next block.

The CA is set up as follows:

X1 X2 X3
-- Y2 --

For each block Y2, determine its color by applying some rule to the colors of X1, X2, and X3. (For example, Rule 110.)

In a First Order system, the only rule is the global rule, which is the same for the entire grid.

In a Second Order system, the global rule is not the only rule.

So for each block Y2, determine its color by applying the rule of X2 to the colors of X1, X2, and X3. Then determine Y2's rule by applying the global rule to the rules of X1, X2, and X3.

X2's rule is simply one of the 256 rules discussed in the book. So if X2 has rule 255, Y2 will be black but Y2's rule will be some function of (X1.rule,X2.rule,X3.rule). So if X1 has rule 25 (and determined Y1's color using this rule) and X3 has rule 55 (which likewise determined Y3's color), then Y2's rule will be Y2.rule=GlobalRule(25,255,55);

And Y2's rule (possibly rule 17) will be used to determine Z2's color.

Any First Order system (the kind commonly used) can be described as a Second Order system:

Each block has rule N. The global rule says: For any three rule sets (N1,N2,N3), return N.

Thus, the rule property of the blocks never change, since N1=N2=N3=N. (This would be analogous to applying Rule 0 or Rule 255 to a First Order system: the color would never change.)

Am I still confusing? Here's some pseudo-code:

for (j = 0; j < GridHeight; j++) {

CurrentRow = Grid[j];
PreviousRow = Grid[j-1];

for (i = 0; i < RowLength; i++) {

Y2 = CurrentRow[i];
X1 = PreviousRow[i-1];
X2 = PreviousRow[i];
X3 = PreviousRow[i+1];

Y2.color = getColorByRule(X2.rule, X1.color, X2.color, X3.color);

Y2.rule = getRuleByRule(GlobalRule, X1.rule, X2.rule, X3.rule);

}
}

Hope this helps.

Posted by: Jason Cawley

The idea is clear enough - thanks for the additional explanation. But it seems to me it is rather too much all at once. Instead of allowing the rule used at each cell to vary over the entire elementary rule space, why not instead restrict it to a small set, starting with just 2, and then treat the number of possible rules across the lattice and through time as a parameter, like the number of colors?

When you allow a number of rules but use the same one on each step, depending on some global parameter, that is the GCA set up. If instead the rule to use is fed in as an additional global input at that step, you get the ICA set up. Some have also already looked at changing the rule across the lattice on individual steps, for example using the identity rule at some locations and any single rule at others, to model updates that don't all have to happen at the same time.

So the obvious simpler way to do what you are talking about, would be to have the rule at each location picked from a rule list, with the integer value (like a second color) giving the position in that list to use. The full blown second order case you are talking about would then be a special case of this class, with the parameter value for "number of rules" set to 256. But you'd have all the simpler ones, with only 2 rules or 3 rules, to look at first - a much more tractable space size to explore.

I hope this is helpful.

Posted by: Joseph Raschack

"The full blown second order case you are talking about would then be a special case of this class,"

Actually, quite the opposite.

Consider Rule 0 and Rule 255. Only one of two possible colors is ever outputted. I'm certain there are similar rules in multi-colored CAs where only 2 or 3 of n possible colors are ever outputted.

So what you're talking about is a subset of Second Order rules where any given input produces only one or two outputs, for example, the Second Order system which produces only rule N that I described earlier. Such systems can be simplified by removing from the input combinations any rule which is not produced as output, so that a First Order system can be reduced to: (RuleN,RuleN,RuleN)=RuleN, since any other combination of input would include rules which are not produced.

I agree, though, that such simplified systems would be a much easier starting point for study, especially since I'm still just starting my studies. :)

Posted by: Jason Cawley

Both are true. The set up I describe with the parameter value for number of rules set to 256, would be the space you are discussing. The space you are discussing, sliced to include only those subcases with 2 rules ("colors" in the meta sense), would be the set up I am describing with the parameter value set to 2. Since there are already 65536 of those with only 2 underlying colors, 17 million with 3 rules, 6x10^25 with 2 rules with 3 underlying colors, and 4x10^38 with 3 rules each with 3 colors - there is little point in going further before investigating those.

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