A New Kind of Science: The NKS Forum (http://forum.wolframscience.com/index.php)
- Pure NKS (http://forum.wolframscience.com/forumdisplay.php?forumid=3)

Posted by Jeff Patterson on 01-12-2005 04:40 PM:

Why all the triangles?

Does anyone other than I wonder why the inverted triangles show up in so many, many of the patterns produced by cellular automata (and the other mechanisms Wolfram uses to generate patterns)? This is enough to pique any researcher's interest--finding very similar phenomena in widely divergent domains. Yet unless I've missed something, Wolfram never discusses it.

Posted by Tommaso Bolognesi on 01-12-2005 05:43 PM:

Jeff,
I guess your question is equivalent to
asking why, by trowing random bits on a line, you end up having all those black and white segments.
The triangles are segments that shrink in time (depending on the CA rule) at no faster speed than two bits/step.

__________________
========================================================================
Tommaso Bolognesi
Formal Methods && Tools Lab.
CNR - ISTI - Pisa - Italy
e-mail: t.bolognesi@iei.pi.cnr.it
web: http://matrix.iei.pi.cnr.it/FMT/

Posted by Jason Cawley on 01-12-2005 06:19 PM:

If a given rule leaves a white background unchanged, then whenever a line of white cells n steps long occurs in that rule's evolution, a triangle will be formed. The rule is local with a maximum range, therefore it has a sort of "light speed", or fastest rate of information spread within the pattern. In the case of the ECAs with their range 1 neighborhood, that speed is one cell to the left or right at each step.

So, if a line of white cells 11 wide occurs and the rule leaves a white background unchanged, the next step must leave a line of white cells at least 9 wide. And after that, one at least 7 wide. Etc. So any fluctuation that produces a long white string will also produce below it a triangle, as that white string "evaporates" from its "edges", as new information flows into the "gap". (See 947 for some analysis of the frequency of triangles of various sizes in various ECAs, from random initial conditions).

Note, there is nothing special about "white" in this analysis - the colors could be reversed and it could be a black triangle doing the "evaporating". The key thing is that the local neighborhood for all the cells in a triangle below a constant line, are the same. They are all the white-white-white rule case, or the black-black-black one. As the rule is the same and is deterministic, it must produce the same result, throughout that region.

Now, if the rule does not leave a white background unchanged, a completely empty triangle need not arise from such a solid line of cells. But you will still detect a triangle of sorts. In this case, the background of the rule must cycle. To see this, imagine the whole array is one color. Then every cell has the same local neighbors and own value on the preceding step. Ergo, they must all go to the same color. It need not be the same as the color on the previous step, but they all make the same change.

The whole array thus acts as a single state, and the rule just evolves like a finite state machine with only as many states as the rule has colors. The possible transition graphs for a small FSM then determine the possible cycles. For a 2 color, there are only 3 - stay white, stay black, or alternate. There can be a short transient, but those are the only possible long run behaviors. With 3 colors there are a few more - you can cycle through all the colors or a subset of them, e.g.

So what you see in those cases is triangles with alternating stripes inside them. The uniformity of neighbor works the same way as with a pure white "gap" triangle. The background just isn't entirely dormant. To produce a variety of behaviors, the same rule needs a variety of neighbor combinations - right center left for one of the cells must be different from right center left for the other. When there is such a difference, you see it as something besides the uniformity within the triangle pattern.

It is a fine question and must have occurred to lots of people. I hope this helps explain why it occurs.

Posted by Jeff Patterson on 01-13-2005 04:24 PM:

Perhaps I didn't ask my question very well or, more likely, you're going to have to dumb down your answer a little bit. I'm only on my second reading of NKS and, while I have a background in research, I'm very new to this way of thinking.

With the very simple CAs Wolfram describes early in the book one can (with a little thought and examination of the rules) correctly predict the occurrence of triangles, and under what sets of rules and under what circumstances they will occur. But when it comes to much more complex rules (e.g., p. 120, p. 150) and means of presenting/analyzing the results I think that it is, for all practical purposes, impossible to predict, in advance, anything about what will happen. Indeed, this is one of Wolfram's primary themes: You just have to run the program and see what happens.

Consider the types of complex rules I note above and all their possible variants (different seed conditions, different constants, etc.). If I handed you one of these picked at random and asked you to predict the result, your answer would almost certainly be "Damned if I know. We'll just have to run it through Mathematica and find out."

If I then said, "Well, sometimes this rule produces a relatively long horizontal sequence of white (or black) cells. Can you tell me anything about what will happen next?", your answer would again almost certainly be "Nope, still gotta run it and see what happens."

*But* if I then told you that sprinkled more or less densely throughout the output were local structures of very simple form and asked you what shape you thought they might be, I'm guessing the dialog would go pretty much like this:

"Almost certainly those local structures will be triangles."

"Pointing up or down?"

"Down"

"Right triangle?"

"Possibly, but probably not."

Your answer to my original question (Why all the triangles?) seems to indicate that one should be able to predict the occurrence of triangles, their orientation, and details a priori. If so, please explain. Otherwise, again, Why all the triangles? What commonality is there among such different rules that makes triangles the local structure which appears almost exclusively? Or, more precisely: What commonality is there among the different rule variants that do produce triangles?

Posted by Jason Cawley on 01-13-2005 05:30 PM:

Locality, that is the thing they all have in common. There is some upper limit on the speed information can move about the pattern. As a result, locally uniform areas persist, with definite outlines set by the system's internal "light speed".

If you look at all of those patterns, you will notice that nearly all the time, the orientation of the triangles is the right-left and up-down "flipped" shape of the overall pattern, on a smaller scale. The reason is, the overall pattern grows according to its light speeds (maximum rates of information transfer) in the various directions. Areas of local uniformity can only disappear, at the same rates.

Rule 110 grows only on the left and down; its internal triangles are right angled with 90 degree angle to the upper left. Rule 30 grows in an isosceles triangle pattern; its internal triangles are isosceles but upside down. In the digit sequence cases, carry digits propagate to the left, not to the right, but division is an inverse operation in that respect, etc.

Occasionally you will see internal structures that are different from the overall shape of the pattern. This arises when one or the other does not grow or shrink, as fast as is possible within the rule.

For example, the branchings within rule 2049 (see p.68) travel at speed 1/2 compared to the maximum growth of the pattern. And most of the black triangle regions - which notably aren't perfect - follow a similar stretched shape. But if you look carefully you will see a few small completely white triangles that do have the inverse shape of the entire pattern. The reason for the difference is this rule grows at light speed on a white background, but white structures move only half that fast on a black background.

If a system were a fully and immediately connected network, all nodes linked to each other, with information at any point able to alter the behavior at any other point on a single step, you would not see this. But most systems with internal components or substates do not have that character. Most exhibit some form of locality and "between-ness" or ordering, such that information or changes at A can alter outcomes at Z only (1) with some lag and (2) after altering intermediary outcomes G, M, T etc along the way.

If you are more familiar with OKS, you can think of this phenomenon as related to wave motion. That a poke of any kind sends out ripples gradually, at rates that are bounded above, is quite general. And as these purely formal examples show, it arises due to locality alone. (Even just typical locality, with occasional exceptions. In digit based cases, for example, carries can sometimes propagate far to the left on a single step, but typically do not).

Posted by Philip Ronald Dutton on 01-14-2005 02:50 AM:

sink / source

In reference mainly to the rule 30 triangles:

I sometimes liken the triangles as sinks or sources. Like a drain in which all the water (or the surrounding cells) gets sucked in....

What about the areas that are not obvious triangles ? Well.. maybe those are areas of interference- areas where sinks are trying to establish their presence but in which there exists the influence of sources which are also interested in that area (or space).

I say "water" but I could have said "force" or "gravity" or whatever....

Since we look at a "progression" of steps.. then you have to really think of these "triangles" as 1-D sinks and sources and not 2-D. So maybe you could see them as representing a (for example) node in the universal (possibly connected) electron graph (as in graph theory). The triangles (while they last in the progression of CA) could model one of the nodes (in the electron universal graph) which has some particular case of stability (or existence without direct interference).

Eventually, *poof*... that node ceases to exist... and, hence the sink has flushed itself and its influences....

And now I flush my possibly unscientific discourse....

__________________
P h i l i p . R . D u t t o n

Posted by Jeff Patterson on 01-14-2005 03:11 PM:

Ok, I think I'm starting to get it. If I'm understanding what's being said, a single-row sequence of all black (or white) cells is a local structure which degrades at light speed back to randomness (or whatever the background soup is). But that leads to two more questions.

First, it would seem to me that any specific sequence of cells can be viewed as a single-row local structure. Surely there's nothing magic about a row of monocolored cells. For example, a series of alternating black and white cells would seem to me as much of a single-row local structure as a series of white ones. If so, we should see checkerboard triangles degrading into the background soup at light speed. But we don't. So apparently there *is* something magic about a series of monocolored cells. What is it?

Second, if the local structure degrading to entropy explanation is correct we should see a) *only* inverted triangles of one orientation and shape or another and, b) we should always see the degradation limited in rate by light speed. However, there is at least one exception to both of these predictions: page 166. There we see local structures, a sequence of monocolored "cells" which pops into existence and, rather than degrading, persists while shifting to the left to produce a parallelogram. Then the local structure, rather than gradually degrading at light speed, abruptly vanishes. Why doesn't the degradation to entropy explanation apply here?

Posted by Jason Cawley on 01-14-2005 08:35 PM:

What is special about a uniform block is simply that it is guareenteed to have the same effect on a whole range of cells below.

Suppose we take the ECA case, as the simplest. The rule is local and of range 1. Any uniform region larger than 3 cells wide, will therefore apply the same case from its rule table to multiple cells below that uniform region. The same case from the rule table means the same outcome, since these are deterministic rules. Nothing else can vary.

Now suppose instead that the pattern in question is not uniform, but instead is 0-1-0-1 etc, repeated across a long region. What does this do below? The leftmost cell uses the portion of the rule table for the entry "0-1-0". But the next cell to the right uses the portion of the rule table for the entry "1-0-1". They are not in general the same. Therefore, the cells below will not in general remain as they were.

If they happened to be exactly {0,1,0}->1 and {1,0,1}->0, then you would get a stable structure that did nothing as it went down the page - except perhaps erode from the edges. If they happened to be exactly {0,1,0}->0 and {1,0,1}->1, then the whole line of cells would cycle. You'd see a region of preserved diagonal stripes, again perhaps eroding at light speed from one side or the other. But in any other case, the outcome is going to go to other combinations than those set by the original 0-1-0-1... initial condition. It will then hit additional cases in the rule table. Mixing, entropy.

So what is special about 0-0-0-0... and 1-1-1-1... is they only apply one entry in the rule table. They will therefore be preserved, either directly, in a cycle, or after a short transient to a fixed point. Whatever happens under the left-but-one 0 also happens under every other cell over to the right-but-one position, exactly. Regardless of what the other entries in the rule table are, no special coincidence required.

It is not necessary to go to a continuous non-CA system to see that other things can happen as well. See 67 for example. Uniform regions are not the only possible persistent structures in a CA, or in any other complicated system. In 1635, black regions persist. Thin stripes of white on a black background persist. Other configurations of white on black can branch in complicated ways, at less than the maximum speed allowed by the underlying rule.

In general, the entire range of types of persistent structures that can occur in some rule, is specific to that rule. There are small recipes for local persistence, besides uniformity. One can ask of a given rule, what uniform backgrounds are possible under that rule, that can tile the whole space and persist? In rule 110, for example, a periodic structure 14 cells wide repeats every 7 steps. But in addition, a totally white background will stay totally white, forever. And regions including black expand into regions of white only on the left. Ergo, when white lines arise, they will persist as white triangle regions until they evaporate from the right.

The uniform behavior of uniform regions is a direct consequence of determinism and locality, in other words. Other special sources of persistence or uniformity are possible in particular rules. But none of them are exempt from the first, general case. A deterministic rule can only change its output if its input changes, and a local rule cannot vary its input within a uniform region. A local rule can vary its input in a periodic region - it can have "phase" with respect to it. But it can't in a completely uniform region.

I hope this helps. Fine questions, by the way.

Posted by Jeff Patterson on 01-14-2005 08:47 PM:

Thanks. I'll have to stew a bit more, but I think I've got it now. Thanks for your patience. I appreciate the careful explanations.