Registered: May 2005
Posts: 3

Hi again,

I might have found the answer, yet I need some clarification.

It said in the book (around page 250-270, I forget where), that class 3 has small scaled structured yet they are randomized through out the CA, and class 4 has this randomization yet some structures repeat in a periodic way.

is this definition correct for ALL CAs of those classes, or is it just a generalization based solely on observations? meaning, all CA's of class 3 will exhibit randomly placed structured, and not disguise as a class 4?

Thanks a lot to those who are willing to answer,

Jackee

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

The 3-4 distinction is between localized structures that persist on relatively simple periodic backgrounds, and thoroughly mixed or chaotic patterns. A typical 4 has a few possible stable background patterns allowed under the rule, with most of the pattern evolving rapidly to such a background as an "attractor" sub-state. In rule 54, for instance, a pattern of 3-1-3-1 white black, that alternates step to step, is a stable background. There are different offsets possible, but only a handful. In rule 110, the most common background is a pattern 14 cells wide that repeats every 7 steps, composed of small 3-2-1 white patterns with 1-2-long black separators, several of which "tile" a region.

But 4s then support a variety of "exceptions" to their backgrounds, or offsets between regions of different backgrounds, which are locally preserved with some definite subcycle, move about at different speeds through the backkground, and disrupt each other or interact with different background regions when they collide.

In contrast, little or none of this localised regularity is typically seen in the class 3s - although they may have some regular regions, e.g. the left border of rule 30 from a simple initial (where effectively the pattern is "isolated" from "input" from the left, by limited interaction range). Most of the true 3 pattern looks like well mixed randomness. By which I mean, if you ask about the frequency of various possible blocks, you find they occur at about the rate you'd expect if all of them happen somewhere. So a run of white n cells long is rare because a single white is roughly half the time, falling off like (1/2)^n.

There are some local structures visible, like triangles in rule 30, that have to arise from sub-cases of the rule. A line of white stays white and can only shrink by 1 cell per step from each edge, for example. There may also be some directional correlations - the line "right and down" in rule 30 alternates colors more than expected by pure chance (which your visual system can pick up as a slight tendency to connected black and white stripes running upper right to lower left, looking a bit like a dendritic drainage system).

But those minor effects, deviating from nearly perfect randomness, are not anything like the regular backgrounds seen in the class 4s. In most regions of a 4, if you tell me the local pattern I can predict a large region below (perhaps moving right or left, it is true), without an elaborate logical calculation, unless a rare "particle" enters the region in the meantime. Some period will let me do so, using some modded number of steps in between e.g. The overall unpredictability of a 4, then, stems from the complex interaction of particle-like deviations from periodicity. Whereas the overall unpredictability of a 3 crops up immediately over most of the pattern - the local areas look random.

Another way to say the same thing is, if you take a block frequency spectrum of 2D areas in a class 4 rule (so and so many instances of this 5x3 pattern, and this one, and this one, etc) - or better yet over a number of different initials - you will see large spikes and many zeros. Those are the stable background pattern subcases (in different "phases" to your pattern "block" edges), and patterns ruled out by them. In a class 3, the spectrum will be largely flat, with many completely dissimilar blocks of cells represented.

I hope this helps.

Report this post to a moderator | IP: Logged