Registered: May 2006
Posts: 9

If one has an 1D CA with two states, k=1 and periodic boundary conditions what class is rule 90?

A. Suppose, we start from random initial conditions. According to p. 265 (NKS) ... rule 90 does manage to produce random behavior of the kind expected in class3.

B. Suppose, we start from cells with a low density of black cells (see p. 265, NKS). In this case the behavior of rule 90 is not random, because the density of black cells will always be low.

Given explanation for the behavior of rule 90: randomness comes from the initial conditions and is not generated intrinsically. (p. 265, NKS).

Unfortunately, no classification is provided.


Classification:

case B.: the behavior of rule 90 is not random => it can not be in class 3 (in what class is it??)

case A.: the behavior of rule 90 is random => it is in class 3

That means, it is not possible to classify CA rules without taking the initial condtion into account.


I would be grateful to get some comments on this.

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 103

The classification's current status is that it serves as a rough guide to typical behavior, but is not really a central theme in thinking about behavior.

One says that a particular evolution is cyclic, nested, complex or has local structures. So it depends on the rule and initial condition, but really the same evolution can be emulated by many pairs of rules and initial conditions.

A consequence of the principle of computational equivalence is that any universal rule is capable of emulating any evolution. So, in some sense, every universal rule can do evolutions which are any of the above.

One particularly flexible rule is rule 94. On p.951 there are evolutions from simple initial conditions which are cyclic, nested and complex, starting from {1},{1,1},{1,0,0,1,0,0,1} respectively.

As far as I know, nobody has yet found any localized structures for rule 94 which persist.

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

Todd Rowland wrote:

“So, in some sense, every universal rule can do evolutions which are any of the above.”

If a three color rule emulates elementary class 4 rule 110, is the three color rule “more” universal than rule 110?

Is there structure to universality or is everything flat?

I am thinking in an analogous way of Cantor’s infinite and his Grundlagen.

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

Registered: May 2006
Posts: 9

Todd Rowland wrote:

"The classification's current status is that it serves as a rough guide to typical behavior, but is not really a central theme in thinking about behavior."

I see! In this case I would like to know in what class you would classify rule 90 (see above for the context and distinguish different inititial conditions) if you had to do that nevertheless?

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

There is a better if more involved answer. Wolfram's original classification is based on the behavior seen from random initial conditions. From random initial conditions, rule 90 gives random looking behavior. It was therefore classified as a class 3 rule.

Later, investigating the various mechanisms for generating randomness, Wolfram thought the dividing line between systems that simply transmit randomness already present in their initial conditions to their later outputs, and those that intrinsically generate randomness even from simple inputs, was more fundamental.

The simple behavior of rule 90 from simple inputs is one sign - not yet a sufficient one, however - that it does not intrinsically generate the randomness seen. It is also an additive rule, meaning we can find the behavior from a complicated initial condition, from additive superposition of the behaviors from simpler ones.

One might want to argue that additive superposition might in some sense be thought of as adding apparent randomness or complexity. But basically, rule 90 from random initials looks random because the initials are, and it faithfully preserves the randomness already present in them.

Later, Wolfram took to calling all simple forms of behavior "class 2 behaviors". Nesting is one of those. It seemed more intricate and complex back in the early 1980s than it seems now, after it has been much more thoroughly studied. Rules that produce nesting from simple initials are quite common in a whole variety of simple program types. But NKS currently considers those simple behaviors, and calls them class 2. They are generally reducible - meaning, short cut formulas can typically be found to give the value at a later time step, at some location within the pattern, without performing all the intermediate steps the rule itself goes through to arrive at that outcome for that bit.

In current usage, rule 90 from simple initials is clearly class 2, and rule 90 from complicated initials *looks* complicated, but can be analyzed and "reduced". I call those "cracks" - as in cracking a code - apparent complexity for which a short, reducing formula can be found. Rule 90 is the paradigmatic case of a "crack".

Another case with its own issues but some similarities is the apparent complexity of the digits of successive powers of 3 in base 2 (see page 121). Or consider extended fraction representations of square roots, which have a simple form, whereas their digit representations do not (see e.g. page 914). These are all cases in which our immediate impression is of considerable complexity - and in some of them that is certainly real on some level - combined with formulas or representations that find some simplicity in them.

An open question in NKS that I call the "crackables" question is, how far do "cracks" extend into the space of apparently random, class 3 looking behavior? Wolfram thinks they are an exceptional case on the border, that reducibility "gives out" rapidly in class 3s, most of which are expected to be computationally irreducible. But one might instead wonder whether there are lots of "cracks" for various cases of apparent complexity, that simply have not been found yet. Perhaps we aren't looking at the right representation to see them, or haven't noticed the key idea needed to perform a reduction.

Wolfram's belief that it is the former rather than the latter is an empirical induction on partial evidence, rather than a deduction. We look at lots of 3s, we try to find ways to crack them. Throw a half dozen people and significant formal and computing power at the problem, looking for regularities. With some you find cracks, but it is rare. With some you can see a few elements from which you might start. With many, you can't, and no standard method of analysis seems able to reduce the complexity seen.

And this is the typical experience with cases selected as being near "complexity onset", the first few that show up as system resources are "dialed up" (by increasing allowed systems states, colors, ranges, allowed rules, etc). Beyond those, there are combinatorially larger "mountains" of rules (the number of possible rules explodes as you allow more features) with far more going on, where it seems vastly harder to look for "cracks".

That's the idea behind Wolfram's conjecture that almost all 3s are computationally irreducible. But individual cases of apparent class 3 behavior might have some simple cause and yield to the right reductive explanation. So the conjecture can also be seen as a standing invitation to show Wolfram is wrong, by providing thousands of successful "cracks". If someone did so, it would be evidence that "crackables" extend farther into the 3s, than we currently suspect.

Report this post to a moderator | IP: Logged

Registered: May 2006
Posts: 9

Thank you Jason!

I compiled a list of rules (all for 1D CA from random inititial conditions, k=1) that should be in class 2. However, look nevertheless 'complex' or 'random' regarding the actual starting conditions.

Would you agree that all these rules are in class 2?

18,26,41,60,90,102,105,106,120,122,129,146,150,151,153,161,165,169,182,183,195,225

Did I miss some rules from class 2 that look 'complex' or 'random'?


I based my decision on
http://atlas.wolfram.com/01/01/rulelist.html
and references in the literature.

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

Of those, 41 gives short transients to straightforwardly class 2 behavior, but doesn't get there rapidly with a fully random initial and wrapped boundary, because it keeps running onto itself basically. If you put anything on an infinite uniform background it quickly settles into a simple class 2 behavior.

The 225 class (which includes 106, 120, 169, as well as 225) all give a highly shifted form of nesting, which gives complicated stuff if it runs onto itself, again.

The others are all variants on nesting, with {105, 150} arguably the most intricate forms. Outside the areas of regularity those create on any uniform background (eventually), those can look as scrambled as you please, but it is apparent randomness of the "superimposed nesting" type. Just not as straightforwardly so as with rule 90.

You may have missed a few - e.g. the black-white and right-left inversions of rule 41. Testing for the behavior of a single 1 on a background of 0s won't spot all of them - sometimes you want to look at a single 0 on a background of 1s and the like.

Report this post to a moderator | IP: Logged

Registered: Apr 2006
Posts: 10

Building on those rules that Frank has listed as class 2 but appearing as class 3, I have been trying to isolate the rules that do still show particularly interesting behaviour (classes 3 or 4).

I am not sure how to categorise rules 54 and 147 which seem to settle into discrete structures which move around a little bit and interact slightly but not very interestingly.

I also don't know how to categorise rules 73 and 109 which seem to have black lines bounding areas of interest.

Aside from those I have identified the following as being class 3 or 4:

Rules 22, 30, 45, 75, 86, 89, 101, 110, 121, 124, 126, 135, 137, 149 and 193

And of those the following I think are generally class 4:

110, 124, 137 and 193.

The rest I guess are class 3 - does that generally match conventional wisdom? Am I missing any or including any I shouldn't be? Am I on the right track?

Cheers
Ian

Report this post to a moderator | IP: Logged

Registered: May 2006
Posts: 9

I would say 54 and 147 are in class 4. See, e.g., p. 696 in NKS. You can also look at the spectrum at

http://atlas.wolfram.com/01/01/54/

to support this. You will see that all 'complex' rules have a rugged spectra (class 4) whereas random rules have flat spectra (class 3).

Rule 73 and 109 I would say is class 2 (from random initial conditions!)
http://atlas.wolfram.com/01/01/73/

Regarding the list and your classification I would agree to all except rule 121.
From the spectrum

http://atlas.wolfram.com/01/01/121/

you can see that it can not be random, because otherwise the spectrum needs to be flat (all frequencies are present). I would say rule 121 is class 4.

In general, I think the spectrum is of great help to decide which class a rule belongs. For me, class 3 is synonymous with random, class 2 periodic and class 1 constant pattern. Class 3 is not defined, but it contains all rules which can not be in the former classes. This is a pragmatic point of view.

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 167

Largely because I don't think it is sensible to try to constrain classification with conditions like "from random initial conditions".

I have recently looked at both those rules from single digit live percentage average density random seeds, as mentioned for 73 in my recent note in an earlier thread, and generally agree with Wolfram's assessment on NKS p.699 ff.

This leads to the question as to how we should classify rules which exhibit different Classes of outcomes from different categories of initial conditions, and ultimately to whether there are rules which can show both 2 and 3, without being 4?

Wolfram has found signals in 73 but whether there are enough distinct signals and signal interactions to demonstrate universality through the kind of complex constructions used for Conway's Life and 110 is not known.

Ultimately it falls back on the possibility of having a strict definition of Class 4 (and that definition being distinct from universality) for schemes for classification to be as rigorous as some here seem to want them to be. Maybe it is better to just think of the traditional Classes as regions on a landscape with fuzzy boundaries.

__________________
Tony Smith
Complex Systems Analyst
TransForum developer
Local organiser

Report this post to a moderator | IP: Logged

Registered: May 2006
Posts: 9

Tony, what classes would you suggest for rule 73 and 109? If one wants to classify CA rules according to their behavior, rule 73 does not look random

http://liinwww.ira.uka.de/~rahn/ca...._random/73.html

nor complex

http://atlas.wolfram.com/01/01/73/

because the spectrum is too flat.

In general, I think it is important to classify CA rules with resprect to the initital conditions.

Let me give you one example. As discussed earlier CA rule 90 conserves the ratio between black and white cells. If started from random initial conditions the behavior can not be distinguished from a random pattern whereas unbalanced initial condition, e.g., 30% black and 70% white, results in pattern with 30% black and 70% white cells which is clearly different from a random pattern. If I give you now a pattern, generated by me with rule 90 from random initial conditions, and you should classify this PATTERN. The tests you run on the pattern indicate that the pattern is not distinguishable from a random pattern. That means, it is reasonable to conclude that the CA rule ,which produces this pattern, is in class 3.

That fact, that rule 90 does not produce a random behavior if started from unbalanced initial conditions can not have influence on your decision because I did not give you this information.

Now you might say, that based on incomplete information one can not come to the right decision (classification). That is my point! You will always have incomplete information because N cells with 2 states give you 2^N possible initial conditions, hence, you can never be sure if a special initial condition results in a compeltely different behavior compared to the initial conditions you tested so far.

The approach sketched above has the advantage that for a given pattern (or even more, produced by a CA) one can classify the CA rule (or more precisely, make a prediction). In my opinion this is according to the basic idea of Wolfram, because he suggested to classify the behavior of a CA rule. And behavior that is not observed can not be classified.

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

Wolfram discusses intermediate cases on page 240. That there will be ambiguous or borderline cases follows from the simple fact that a potentially astronomical number of rules are being placed into just 4 categories.

In the specific case of rule 73, to get a sense of how varied it is, look at its behavior with unwrapped initial conditions. Try this function -

ArrayPlot[CellularAutomaton[73, {#, 0}, 50]] &


- Mapped over a variety of ics, for example


/@Table[RotateLeft[IntegerDigits[i, 2, 30], 14], {i, 456, 456 + 32}]


Looks pretty class 3, that way. If you doubt it, try extending to 400 steps with the option "PixelConstrained->True" added, and blow up some of the more interesting looking runs. You get a periodic background, diagonal strips at the edges with a different stable periodic pattern, an interior region with class 3 randomness and triangle structures, and sometimes a center-line black strip divider or two. That's an awful lot to see in one pattern of one rule, and suggests to me that this rule is considerably richer than some might have supposed.

From random initials wrapped, what happens is its stable structure of a vertical black stripe 2 cells wide forms with some reasonably high probability from the random initials, so across the whole array you have a number of them. They are stable no matter what happens on either side of them, so they effectively block all information transfer across the pattern. So they slice the evolution up into narrowly segregated "pipes", which are each typically so limited in size that the behavior inside must cycle, relatively quickly (though for some, it can take on the order of 100 steps).

Where the evolution is not forced to behave like a system of limited size, though, the ongoing behavior of the rule is quite complex. And it does not produce more new vertical black stripes from states it hits "naturally". Those are common early in the random ics case, either because they are already present in the ic, or they are hit almost instantly on short transients, from "garden of Eden" initials.

The different possible behaviors from different classes of initials, suggest rule 73 might support programming schemes. One has to be careful with information blockers, however, since details inside a "pipe" closed on two sides cannot affect anything outside that pipe. A 3 color generalization of rule 73 that used the third color to create a way to dissolve one of those "walls", would almost certainly be programmable.

Do not forget that a universal rule is capable of a wide variety of behaviors, not just one characteristic behavior. You can force rule 73 to behave in a class 2 manner from some initials, and get it to behave in a class 3 manner from others. So even rule 73 as it stands can be made to behave in fundamentally different ways, for different types of initial conditions. If not yet rule 73 itself, slight generalizations of it (one more color) can probably be found that could be programmed to do anything an arbitrary computer could do.

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 167

Frank, I've run a few more experiments on Rule 73 and it seems that for initial random seed density outside the 30-70% range, there will be spans between walls with long stabilisation times. Stabilisation is typically quick for spans less than 40 cells wide.

And interesting behaviour keeps coming up, including the attached example where a new wall forms relatively late and the narrower span later settles down into periodic behaviour.

I also remembered after my last post that I had some time ago posted some thoughts about Class determination in a bit more detail than I should repeat here.

Tony Smith has attached this image:

__________________
Tony Smith
Complex Systems Analyst
TransForum developer
Local organiser

Report this post to a moderator | IP: Logged