Lawrence J. Thaden
Registered: Jan 2004
Posts: 350 |
A Third Example Combining Class 2 and 4 Behavior
The two previous examples in this thread both used rule numbers whose progenitors were simple AND-type expressions in the form AND-type[operand1, operand2]. This third example likewise uses a rule number whose progenitors are simple AND-type expressions.
The AND-type expression used is (1+AND). There are other types available. Namely, AND, -AND, 1-AND, -1+AND, and -1-AND. But these come in three pairs:
AND and –AND are additive inverses.
1+AND and 1-AND are negative multiplicative inverses.
-1+AND and -1-AND are positive multiplicative inverses.
These two operand AND-type operations ignore signs. So the results are always the absolute value. For this reason, we only use AND, 1+AND, and -1+AND.
Each AND-type operation has operands that also come in six forms, but we only use the three positive versions for each of the three operands: {p, 1+p, -1+p}, {q, 1+q, -1+q}, and {r, 1+r, -1+r}. The reason is the same: negative versions of these algebraic expressions are meaningless, since they point to the same rule numbers as the equivalent positive expressions. In this sense these binary operators and their respective rules are comparable to absolute valued functions in traditional mathematics.
Review of Forum Comments
Before presenting this third example I want to review some comments from the Forum that have to do with definitions of the four Classes of cellular automata.
My motive in this is to put this third example in context, because, as will be seen, it illustrates behavior from both Class 2 and 4.
In the thread: “Defining the Classes of Elementary Cellular Automata” I wrote:
There are descriptions of the four classes in the NKS book on pages 231 and 235. …
“In class 1, the behavior is very simple, and almost all initial conditions lead to exactly the same uniform final state.” …
“In class 2, there are many different possible final states, but all of them consist just of a certain set of simple structures that either remain the same forever or repeat every few steps.” …
“In class 3, the behavior is more complicated, and seems in many respects random, although triangles and other small-scale structures are essentially always at some level seen.” …
“… class 4 involves a mixture of order and randomness: localized structures are produced which on their own are fairly simple, but these structures move around and interact with each other in very complicated ways.”
Jason Cawley replied with informative comments on the definition of classes 3 and 4.
Among other things he wrote:
“…universality is not part of the definition of class 4. That class 4s are in general probably capable of universal computation in the infinite size limit, is a result, not something that proceeds from a definition. Class 4 is not meant to designate "such algorithms as are capable of universal computation".
“Class 4 means - from typical (not special or measure zero) random initials (not whole ensembles of initials taken as a programmer's degree of freedom, and not simple initials – italics added - ), typically resolves into a number of localized structures that themselves move about and interact, in often complicated ways.
“Class 3 means - from typical random initials, produces random chaotic patterns.”
Unbounded with Infinite Time
Because we are starting from simple initials, we do not intend to use the class number as defining the cellular automaton in the sense that Jason mentions. Rather it is meant to indicate that the cellular automaton manifests behavioral characteristics in common with the classes Jason comments on.
In addition, we are discussing unbounded cellular automata. The foreground of these cellular automata grow horizontally with each time step to infinity, and they do not cycle.
The Third Example
Now I want to introduce this curious cellular automaton that keeps spawning what appear, at the appropriate resolution, to be diagonally parallel lines.
But, at a finer resolution these lines are seen to be made up of identical triangular particles separated by regular intervals of time steps.
The three color rule number that generates this cellular automaton is 3671598304234. This is another rule number that is the set difference of two modulo 3 sums, and those sums are of pairs of basic AND-type statements.
(13817466: 1+AND[1+p, 1+q] ~XOR~
511758: 1+AND[1+p, q] -> 14329224)
~DIFF~
(1514: 1+AND[p, r] ~XOR~
7343167948506: 1+AND[-1+p, -1+q] -> 7343167950020)
-> 3671598304234
Arithmetic Progression
The time steps at which each parallel line begins is defined by an arithmetic progression, which in traditional form has the expression:
an = a1 + (n - 1) d
where a = 1542, d = 3030, n ranges over the natural numbers, and n and 1 are subscripts.
Of course the traditional form does not yield the desired result in Mathematica, but we can use:
Fold[Plus, a, Table[d, {n}]]
where n = 3
to find the fourth term in the arithmetic progression:
10632
Similarly, to list any number (n + 1) terms in the arithmetic progression, we can use:
FoldList[Plus, a, Table[d, {n}]]
{1542, 4572, 7602, 10632}
Considering just this aspect, the cellular automaton manifests Class 2 behavior, a simple pattern repeating periodically.
The pattern is a stream of triangular shaped particles that appear as a line at an appropriate resolution. The repeating period, after 1542 time steps of start-up, is 3030 time steps in length.
Figure 1 shows a portion of the cellular automaton where there are three parallel lines. The origin of the second and third lines is also shown, but the origin of the first line does not show because the image is just a section taken from the full output.
Here is the Mathematica code that I used to produce Figure 1.
CA3Lines =
Take[CellularAutomaton[{3671598304234, 3, {{-1}, {0}, {1}}}, {{1},
0}, 8500], {4580, 8000}];
Dimensions[CA3Lines]
{3421, 8502}
ArrayPlot[Table[Take[CA3Lines[[i]], {2000, 8502}], {i, 3421}],
ColorRules -> {0 -> Black, 1 -> Darker[Yellow], 2 -> White},
PlotLabel ->
Style[{{"(13817466: 1+AND[1+p, 1+q] ~XOR~ "}, {"511758: 1+AND[1+p,
q]" " [Rule] 14329224)"}, {" ~DIFF~ "}, {"(1514: 1+AND[p, r] ~XOR~
"}, {"7343167948506: 1+AND[-1+p, -1+q]" " [Rule] 7343167950020)"},
{" [Rule] 3671598304234"}}, Bold, "SubSection"],
ImageSize -> {1100, 748}]
Class 4 Behavior
But now for the curious aspect of this cellular automaton: the patterns at the left foreground before and between the time steps that spawn parallel lines. (We will be using “descriptive definition” in this discussion rather than “explanatory definition”.)
Figure 2 shows the start-up of the cellular automaton and the spawning of the first parallel line. The resolution makes it possible to see that the parallel line is actually made up of triangular shaped particles separated by regular intervals of time steps.
But we want to focus on the local structures in the detail preceding the spawning of the first parallel line. The structures look as though the cellular automaton is repeatedly attempting to spawn a parallel line. But in the failure to do so, it generates a disordered set of triangular particles. Then each next attempt seems to get closer with more triangular particles aligning nearer to what is required to make them appear as a parallel line. Finally, the first parallel line is spawned. In the figure it is at the bottom fourth emanating from the left foreground and appears as a stream of 14 triangular shaped particles.
Figure 3 shows the interval between the beginning of parallel lines two and three. It starts off with a short burst that appears common to all the intervals. This is followed by three small failed attempts. Then there is a large attempt with a succession of five tries before complete failure. This is followed by another large attempt that has a first and second half. The first half appears to be organizing the particles. The second half appears to be trying to spawn. But this also ends in failure. Finally, it spawns the third stream of triangular particles.
This behavior observed close to the left edge of the foreground before the first parallel line and in the interval between parallel lines resembles Class 4 behavior. It is not entirely regular and it is not entirely random. Nor is it simple.
And when the efforts to spawn a parallel line collapse, there appears to be definite lines of communication connecting the collapsing structure to the right edge of the foreground. (See circled areas in Figure 3.)
Identical Class 4 Behavior Repeated Regularly
What about the intervals taken as a whole? Does the interval between the first and second spawning of the parallel lines manifest the same behavior as in the interval between parallel lines two and three?
Figure 4 shows the interval between the spawning of parallel lines one and two. The local structures are the same as for those between lines two and three shown in Figure 3.
So the overall behavior of this cellular automaton is completely predictable.
First, there is the predictability of the spawning of parallel lines explained by the arithmetic progression, expressed in Mathematica by:
FoldList[Plus, a, Table[d, {n}]]
where a = 1542, d = 3030, and n ranges over the natural numbers.
Second, the predictability of the equivalent structure in the intervals between the spawning of parallel lines is defined by comparing pictures of the intervals and using proof by induction.
Periodic Boundary Conditions
Figure 5 shows the same cellular automaton evolved over 8001 steps with periodic boundary conditions. Only one line gets spawned.
When the left edge of the foreground reaches the left edge of the background of the cellular automaton, it wraps around and proceeds across to the right edge of the foreground where it intersects exactly at the left edge of the foreground just before the second line is about to be spawned. The collision prevents the second line from ever being spawned.
Instead there is a burst of triangular shaped particles from which there comes a composite vertical stream of two sizes of triangular shaped particles that continues on without incident. This stream is on the left.
But also, to the right emanates a stream of smaller disintegrating particles flanked by a heavy double line on the right and a single line on the left.
The disintegrating stream bifurcates, being drawn by the lines flanking it. The part that is on the left forms a composite vertical stream that continues on without incident. The part on the right bursts into two clusters of triangular shaped particles.
The cluster on the right breaks up the heavy double line into a triple line which continues on the same track as the heavy double line that is no more. The cluster on the left disintegrates only to burst again into triangular shaped particles from which emanate on the right another composite vertical stream that continues on without incident, and on the left a heavy double line similar to the previous heavy double line to its right.
The three streams of particles are of course parallel since they are vertical, but they are not evenly spaced apart from each other. But just as it seems like they will go on down through the time steps forever unimpeded, along comes the first and only line spawned that has wrapped around due to boundary conditions.
It slams into the leftmost vertical line knocking it to the right, though not changing its angle.
This causes the formation of a cluster of small triangular shaped particles, and the spawned line has its angle changed slightly as it also changes the shape of its constituent particles. There also emanates from it a heavy line that is headed on a collision course with what happens next.
The modified original spawned line now slams into the second vertical line and knocks it to the right without changing its angle. There is an accompanying burst of triangular shaped particles, and it is with these that the heavy line collides.
Well, all pandemonium now breaks loose. Eventually, eight vertical streams emerge on the left while the majority of the momentum of the collision continues on the right following a slightly altered angle of the original spawned line.
What happens next is outside of the frame of the 8001 time steps through which the cellular automaton evolved.
Conclusion
Quite a ride! The descriptive language used was motivated by associations with subatomic particle collisions. Not very objective, I acknowledge.
However, the behavior is definitely Class 4. It is not predictable. And, yes, the cellular automaton will eventually cycle.
Moreover, the initial conditions, as we ran it, were simple, not random (See Jason Cawley's comments above.)
initialConditions =
Flatten[{Table[0, {1000}], {1}, Table[0, {1000}]}];
In conclusion, the cellular automaton for rule 3671598304234, when evolved without boundary conditions, has an infinite number of time steps and entirely predictable behavior that can be explained by an arithmetic progression.
However, when periodic boundary conditions are prescribed, the same rule number evolves a cellular automaton with Class 4 behavior, even with simple initials, which is not predictable, but which at some point cycles.
Lawrence J. Thaden has attached this image:
Last edited by Lawrence J. Thaden on 05-10-2011 at 01:04 PM
Report this post to a moderator | IP: Logged
|
04-22-2011 03:05 PM
