Lawrence J. Thaden
Registered: Jan 2004
Posts: 350 |
More on those closed sets of initial conditions
I got to thinking about using initial conditions which are digit expansions of a set of three color rule numbers that are closed with respect to the map function.
If using such initial conditions has validity in three-color rules, how about exploring the ECAs with such initial conditions?
The first one I tried was rule 110. Interestingly, it requires all 256 ECA rules to form a closed set. (More details about this at the end of the post.) This makes for a string of digit expansions 2048 digits long. So the processing is a little inconvenient on a desktop computer. But if the process is done piecewise, it is possible to discover rule 110’s behavior in this way.
The results are striking. Of course there is no overall triangular shape since the initial conditions are not a single black cell embedded in a background of white cells. Rather, things are cyclic. That is, with periodic boundaries. Figure 1a shows the big picture, the first 32768 time steps in two columns, each 16384 steps in length.
This figure shows the main features of the foreground, but details of the background are not discernible because of the resolution. What is clear is that most of the intersections are complete by the end of the first column of the figure. As for the characteristics of the different kinds of intersections, they are what you can find described in the literature on rule 110. However our focus here will be on the way the behavior ends rather than on the many types of intersections that occur at the outset.
Figure 1b is a continuation of 1a. It takes the cellular automaton out to step 65536. These files are large and so they are zipped together using PKWARE software. If you are not able to unzip them PKWARE has a free reader available at www.zipreader.com.
Figure 2 is a close up view of the upper left corner of the output. Its magnification brings out the background. The point to note is that the background generally appears as parallel objects spiraling tightly from right to left down the time steps. And this general parallel structure is sometimes interrupted when a foreground line passes in front of it. What appears to happen is that the background gets a “kick” forward in time through part of a step. However, this could be an illusion, and I have not analyzed the actual content of these rows. But it is clear that, once things quiet down, there is no “kick” forward in time to be observed.
Figure 3 shows the left and right halves of the first 1024 steps. This shows the full range of different types of intersections. Some outputs seem to be a decomposition of complex inputs. For example, the grid like objects and the thick black shunt bars. Other times the output can become more complex than the input. One instance is at the right side of figure 3b, after the grid like object enters on a diagonal collision with an elaborate, almost vertically line. (To locate this look for the relatively large white triangle.) But then additional collisions occur before vestiges of the grid like object finally vanish. And occasionally a collision results in which there are two inputs but appear to be three outputs. Actually, it may be that the third output comes off one of the other outputs. An example of this is the thin white line breaking off to the left at the lower center of figure 1a column 2. A close-up of this is shown in figure 4.
Figure 5 shows the point at which rule 110 begins to cycle. It is at step 62168. And what an enormous cycle it has, 485036032 steps. What appears to be playing out in the foreground is one elaborate diagonal line spiraling at a much faster rate than the background while another stationary vertical line proceeds at a rate much closer to the background rate. And while the vertical line is made of stationary objects, the diagonal line is made of objects that are offset by four columns to the left of each previous object.
But whenever the diagonal catches up so as to collide with the vertical line, the intersection seems to cause both inputs to change into each other on the output. And they get “kicked” in the exchange, so that the stationary vertical line now appears 13 cells farther to the right than before, and the diagonal appears to continue on a track 19 columns to the left of where it was before the collision.
The objects that make up the series in these two lines are comparable to what are referred to in Tag Systems terminology as the set of production rules. The elaborate diagonal line moving from right to left is the faster of the two, and the stationary vertical line moving from left to right shows what is comparable in Tag Systems to the position of the clock. Each time the two lines collide, the position of the clock moves 13 cells to the right. This clock pulse is synonymous with the “kick” to the right mentioned in the previous paragraph.
To break it down we can speak of the cycle as having sub-cycles, each with one collision. These sub-cycles start at rows 62168, 80386, 98604, 116822, and so on. The collisions occur at columns 1006, 1019, 1032, 1045, and so on. And since we are using cyclic or periodic boundary conditions, the shifting wraps around to the left end of the row when it reaches the right boarder. It takes 18218 rows before the next collision.
For convenience, and somewhat arbitrarily, the row at which the stationary vertical series of objects exits the collision has been chosen to mark where the collision occurs. Actually it occurs over a number of rows.
The way we compute the cycle length is as follows.
Initial conditions have 2048 cells and each collision is displaced by 13 cells. But since the LCM for 13 and 2048 is their product, 26624, the collision marking the beginning of a cycle will occur on the same column after 26624 right-shifted sub-cycles. And we know that the sub-cycles begin every 18218 rows. So the cycle length is 26624 x 18218 = 485036032.
You can imagine the geometry of this cycle as a torus with a cross section having a circumference of 18218 rows. On this torus there are 26624 arcs each displaced from the other by 13 cells and fitting the circumference. These arcs mark the position of the clock. But since there are only 2048 cells around the torus, which is not an even multiple of 13, the clock ticks around the torus many times before reaching its starting point. The diagonal series of objects is a solenoid that wraps round and round the torus intersecting each time with the beginning of one of the arcs until it finally meets up with its starting point. By this time it has traveled through 485036032 rows. And the collisions have occurred once per column, but not contiguously.
This is demonstrable with the following Mathematica code:
Mod[FoldList[Plus,1006,Table[13,{2048}]],2048]
The result is a list of the columns in order of the collisions that take place as the diagonal series wraps around and around meeting the clock each time. The list has 13 sections, each with 157 or 158 members starting with the columns on the left and ending with those on the right. These sections alternate in size from 158 to 157 with the exception of section 11 and 12. They both have 158 members.
If we select those columns from all of the sections nearest the starting point, (not of these sections but of the cycle; namely column 1006), this is the list of columns:
{1012, 1018, 1011, 1017, 1010, 1016, 1009, 1015, 1008, 1014, 1007, 1013, 1006},
where the last number indicates the point at which the cycle starts again.
Begin Deletion: 10/30/2008
Reason for deletion: These differences are all 13 modulo 2048 as of the correction made for where the cycle begins. The second set of differences are all 0.
Now the differences between these starting points in each section is analogous to the derivative of a two dimensional curve. It is also a list:
{6, -7, 6, -7, 6, -7, 6, -7, 6, -7, 6, -7}.
And the differences between members in this latest list is analogous to the second derivative of a two dimensional curve. It is the alternating minus and plus values of the clock pulse:
{-13, 13, -13, 13, -13, 13, -13, 13, -13, 13}.
End Deletion: 10/30/2008
I suppose that with access to a supercomputer it would be a trivial problem to verify that the above computation is correct and that there is a cycle that starts with row 62168 and has 485036032 steps. However, my desktop computer balks at doing much more than 250K steps at a time. This means that I would have to make slightly over 1900 runs to check it out. I’ll leave it to someone else.
One final note: Emil Post required a halt for his Tag System. Comparably, we can consider the cycle coming to its end as the halt.
Figure 6 shows the collision that is repeated in each sub-cycle. Even though it gets right-shifted 13 columns, it never changes its shape. This figure also includes the two types of objects that make up the stationary vertical series and the diagonal series. And, of course, the background objects.
Begin Editing 10/29/2008
Well, the starting row for the cycle is not 62168. Rather, it is row 43988. In fact, the starting row for the cycle and all the subcycles occurs, not at a collision, but after a collision. So while it is true that row 62168 marks the first collision within the cycle, the starting row for the second subcycle is 38 rows later at 62206.
However, this does not change the subcycle length, 18218, nor the shift right amount of 13 cells every 18218 rows. It just means that the shift right occurs during the collision which happens 38 cells before the end of a subcycle.
And the first collision occurs outside the cycle during startup. So the clock position at the beginning of the cycle is at cell 991, not at cell 1006.
So the clock positions for the first 26 subcycles are:
{991, 1004, 1017, 1030, 1043, 1056, 1069, 1082, 1095, 1108, 1121, 1134, 1147, 1160, 1173, 1186, 1199, 1212, 1225, 1238, 1251, 1264, 1277, 1290, 1303, 1316}.
And all of the clock positions within a cycle are found with:
Mod[FoldList[Plus, 991, Table[13, {2048}]], 2048]
The result is a list of the columns in order of the collisions that take place as the diagonal series wraps around and around meeting the clock each time. The list has 12 sections, each with 157 or 158 members thus:
{157, 158, 157, 158, 157, 158, 158, 157, 158, 157, 158, 157}
The last clock position in this list, number 2048, is 991, which is the first clock position in the cycle.
So when the cycle starts over, the first collision will cause a shift of the clock from 991 to 1004, 13 cells to the right, just as happened in the first cycle.
As the clock positions progress from left to right in increments of 13 cells, they finally approach the right boarder. Since we are using periodic boundary conditions, this means that the next clock position will sometimes be in the neighborhood of the left boarder. It is still 13 cells to the right of the previous clock position but wrapped around to a lower cell number. This happens 13 times in a cycle at clock pulses:
{82, 239, 397, 554, 712, 869, 1027, 1185, 1342, 1500, 1657, 1815, 1972}.
Remember, there are 18218 rows between each adjacent pair of clock pulses. These 18218 rows make up a subcycle. But the entire cycle has 485036032 rows.
End Editing 10/29/2008
Begin Editing 10/30/2008
Here is a correction to the total number of rows per cycle. It is compelled by the fact that each cell gets hit exactly once per sub-cycle by a collision during the overlapping right shifts.
I had said:
“But since the LCM for 13 and 2048 is their product, 26624, the collision marking the beginning of a cycle will occur on the same column after 26624 right-shifted sub-cycles. And we know that the sub-cycles begin every 18218 rows. So the cycle length is 26624 x 18218 = 485036032. ”
However, since we use periodic boundary conditions, there is no need to bring in LCM. So the computation is simply 2048 collision locations x 18218 rows per sub-cycle = 37310464 rows per cycle.
The geometry is the same. It is a torus with the dimensions of the sub-cycle dynamically shifting clock position 2048 times while the series of objects making the solenoid wraps around and around the torus colliding with the clock position as it advances 13 cells to the right 2048 times.
End Editing 10/30/2008
Initial Conditions
Here is the code that generates the initial conditions:
inits = Flatten[Table[IntegerDigits[i, 2, 8], {i, 255, 0, -1}]];
Demonstrating that these are sufficient and necessary is achieved with the map function.
First, the algebraic expression for rule 110 is examined to determine its components and their associated rules. Thus we find 110: XOR[AND[(NOT[x], y, z)], y, z]. Here are the rule numbers: 15: NOT[x], 204: y, 170: z, 128: AND, 150: XOR. This list of rules is called the seed.
Next, the seed is used as the p[[i]], q[[i]], and r[[i]] operands input to the map function, again with each rule taken in turn as operator. The results are filtered to remove duplicates.
The result is that the list has grown to 37 rules from the original 5. The process is repeated with the expanded list and it produces all 256 rules listed on page 884 of the NKS book.
The conclusion is that the smallest possible set sufficient for closure with rule 110 is all 256 rules.
Then comes the tedious part, establishing that this set necessarily contains all possible rules. There must be no possibility that any other rule can be generated by the map function using these 256 rules as operators and operands.
The task can be accomplished on a desktop computer if it is done in batches of 32 rules as operators. This is a valid procedure since each operator is independent of the others.
It turns out that each batch has the 256 ECA rules, once duplicates have been removed. So the set of 256 rules is necessarily the smallest closed set with respect to the map function and rule 110.
 Attachment: figs 1 pkzipped.zip
This has been downloaded 1101 time(s).
__________________
L. J. Thaden
Last edited by Lawrence J. Thaden on 10-30-2008 at 11:50 PM
Report this post to a moderator | IP: Logged
|
09-22-2008 12:55 PM
