GoL Patterns with Eventful Histories

2005/07/21

GoL Patterns with Eventful Histories

This blog is about some investigations of small GoL patterns (primarily small in terms of number of cells rather than size of bounding box) with "interesting" or "eventful" histories. One of the aims of this work has been to find patterns that will go on producing novelty forever. The other is to explore the "second-order" patterns you get by placing two finite patterns on an infinite array in all the possible relative positions that can be produced by translating one of them relative to the other (as Gencols does). I won't go into a lot of detail about either of these themes and what I've learned at present, but will concentrate on specific patterns, and aspects of their histories. Before doing so, I'd like to thank Tom Rokicki, not only for producing hlife (http://tomas.rokicki.com/hlife/), the program with which most of the work was done, but also for giving me access to Loft, a machine with 3.6Gb memory, for running hlife on some of these patterns. Without hlife very little of what is described here would have been possible, and without the loan of Loft, I couldn't have taken the most interesting patterns as far as I have. For the patterns for which I provide pictures (drawn with hdraw, the companion program to hlife), a link in the text takes you to the page with those pictures on. For patterns without such a link, the effects I discuss occur soon enough to be seen conveniently using GoL programs such as Life32, Xlife or similar. At some point, I may add pictures using Life32.

All the patterns discussed here have names which are composed of three parts, separated by hyphens. The first two parts identify the two sub-patterns used, while the last part specifies the spatial relationship between them. Thus "nhaa-blilr-e48n30" consists of the pattern "nhaa", which is my name for a specific "ark" (switch-engine pair), and the pattern "blilr" (a blinker in horizontal orientation); the blinker's most "western" (leftmost) cell is 48 cells "east" of the ark's leftmost cell, and the blinkers northernmost cells (i.e., all of them) is 30 cells "south" of the ark's northernmost cell. An alternative way of describing this is to locate the "northwest corner cell" of each subpattern - the cell that is just as far west as its westernmost cells, and just as far north as its northernmost - and describe how they are related.

The lines of apparent gobbledegook following each pattern name are its description in RLE, which can be read by most GoL programs.


(A) Combining an ark (with at least one backward stream of gliders) with a blinker or pre-block.

In these 19-cell patterns, the first member of a backward stream of gliders hits a block or blinker, and subsequent members of the stream hit the resulting debris. Clearly, this depends on the blonk being on the right diagonal - otherwise the stream will miss, or quickly eliminate the blonk. If this does not happen, there is typically a prolonged period during which the strem repeatedly reactivates the "junk" into
which it is directed, throwing off gliders and sometimes *WSSs. So far, all the examples of this type of pattern investigated have eventually stabilised, but there are several different ways in which this can happen, and this range of
possibilities is what is illustrated here. Incidentally, I have also experimented with an ark and a single switch engine going in opposite directions, with the ark's stream of gliders hitting the switch engine's trail, but no fundamentally different outcomes have emerged.

The following outcomes have been observed:

1. The stream(s) eventually break(s) through, and thereafter the ark behaves exactly as it would have without the interaction with the blonk. An example is ohhs-blilr-e1340s1146:

x = 1343, y = 1147, rule = S23/B3
31bo$31boo$31bobbo$$32bobo$33bo13$o3bo$bobo$bbobbo$5bo$5bo1124$1340b3o!

Pictures of the result after 2^24 steps are shown as ohhs-blilr-e1340s1146.out-24a (the whole pattern - note the dot on the far right, which is an LWSS), and ohhs-blilr-e1340s1146.out-24b (a member of the glider stream emerging from the ark's tail).

2. The stream(s) eventually create eater(s) (standard or non-standard) which thenceforth consume them. An example is nhaa-blilr-e31n47:

x = 34, y = 63, rule = S23/B3 31b3o47$12bo$12boo$12bobbo$$13bobo$14bo7$3o$bobbo$5bo$bbobo!

Pictures of the result after 2^26 steps (this way of stabilising seems to take rather longer than breakthrough) are shown as nhaa-blilr-e31n47.out-26a (the whole pattern), nhaa-blilr-e31n47.out-26b and nhaa-blilr-e31n47.out-26c (the two eaters, with gliders approaching them).

3. A glider from the stream-junk reaction catches the head of the ark and interferes with it in a way that halts the production of the glider-stream. So far I have only one example of this: nhaa-blilr-e48n30:

x = 52, y = 45, rule = S23/B3
49b3o29$12bo$12boo$12bobbo$$13bobo$14bo7$3o$bobbo$5bo$bbobo!

Pictures of the result are shown as nhaa-blilr-e48n30.out-23a (the whole pattern) and nhaa-blilr-e48n30.out-23b (the point at which the head of the ark was hit, destroying one of the two switch engines.

4. The glider stream builds up a regular, ever-growing addition to the body of the ark (by which I mean the regular, repetitious stuff the ark produces, between the growing head and the irregular tail), growing in the same direction as the head of the ark is moving. In the only example I have, ohhs-bliud-w1n188, this addition takes the form of slightly modified glider-crystal:

x = 36, y = 211, rule = S23/B3
o$o$o186$32bo$32boo$32bobbo$$33bobo$34bo13$bo3bo$bbobo$3bobbo$6bo$6bo!

Pictures showing the pattern after 2^22 steps are ohhs-bliud-w1n188.out-22a (the whole thing), and ohhs-bliud-w1n188.out-22b and ohhs-bliud-w1n188.out-22c ( the additional structure at two different scales).


(B) A pair of modified Gosper-type puffers diverging at right angles.

By a "modified Gosper-type puffer" I mean one the original c/2 orthogonal "puffer train" found by Bill Gosper, modified by adding a blinker or block in such a way that it shifts from a period of 140 to a period of 100, and produces a backward wave of gliders. There are a number of different blonk placements that produce this change, but all the patterns described here use two copies of one I call "gosblor4c2", one
of which is the mirror image of the other, as well as being perpendicular to it. The two puffers travel east and south, and are oriented so that the backward wave of gliders from each travels toward the body of the other.

Some of these 50-cell patterns rapidly settle into a simple repetitive type of growth, others show "Morse-Thue" type characteristics (see below), and others again appear to get more and more complicated as far as I have been able to follow them.

In this type of DPP, it is convenient to specify the spatial relationship of the two puffers in terms of how far "north" or "south", and how far "south-west" or "north-east" the northwest corner cell of the second is from that of the first. This is because shifting one puffer relative to the other along a north-east / south-west line leaves the relationship between the diagonals along which members of the glider waves travel unchanged (although the collision produced by each meeting pair may differ according to whether the north-east / south-west distance is odd or even), while shifting along a north / south line, unless by a multiple of 50 cells, does not.

I now describe some examples, roughly in order of increasing complexity.

(1) In some cases, the members of the backward waves meet along a diagonal line bisecting the angle between the puffers' bodies. An example is gosblor4c2-gosblor4c2f-s1sw13:

x = 25, y = 25, rule = S23/B3
21b4o$20bo3bo$24bo$23bo3$21bo$22bo$22bo$21boo$15bo4bo$14boo3$11bo9b4o$
10boo8bo3bo$24bo$23bo3$bo8bo4bo$o5bobbo4bo$o6b3o4bo$obbo10bobbo$3o11b
3o!

Here, each colliding pair (after some initial complications) produces four beehives and two traffic lights. In none of the cases where members of the two waves meet does anything very interesting occur.

(2) When the two waves pass through each other, both may cause minor changes to the body of the other puffer, with no further interactions, as in gosblor4c2-gosblor4c2f-s8sw13:

x = 24, y = 32, rule = S23/B3
20b4o$19bo3bo$23bo$22bo3$20bo$21bo$21bo$20boo$14bo4bo$13boo3$20b4o$19b
o3bo$23bo$22bo4$11bo$10boo5$bo8bo4bo$o5bobbo4bo$o6b3o4bo$obbo10bobbo$
3o11b3o!

(3) Alternatively, one of the two waves may produce a secondary wave, by "bouncing" off the body of the other puffer, as in gosblor4c2-gosblor4c2f-s15sw13:

x = 24, y = 39, rule = S23/B3
20b4o$19bo3bo$23bo$22bo3$20bo$21bo$21bo$20boo$14bo4bo$13boo3$20b4o$19b
o3bo$23bo$22bo11$11bo$10boo5$bo8bo4bo$o5bobbo4bo$o6b3o4bo$obbo10bobbo$
3o11b3o!

(4) However, a relative shift of the two puffers along a north-east / south-west puffer from the previous example causes the secondary wave to interfere with the non-bouncing primary wave, as in gosblor4c2-gosblor4c2f-s15sw27:

x = 38, y = 53, rule = S23/B3
34b4o$33bo3bo$37bo$36bo3$34bo$35bo$35bo$34boo$28bo4bo$27boo3$34b4o$33b
o3bo$37bo$36bo25$11bo$10boo5$bo8bo4bo$o5bobbo4bo$o6b3o4bo$obbo10bobbo$
3o11b3o!

If, as in this case, the resulting collisions leave behind debris that interferes with later gliders from the bouncing primary wave, we get what I call an "expanding feedback loop" (run the pattern and it will be quite clear why), and typically Morse-Thue type sequences appear. Such sequences are non-repeating, but can be generated by simple recurrence relations. The "classic" Morse-Thue binary sequence starts with "0" and uses the recurrence relations "0->01" and "1->10" to generate each successive partial sequence: the fifth of these is "0110100110010110". In the current example, a similar sequence can be seen in the line of debris that forms from collisions between the secondary wave and the non-bouncing primary wave.

(5) Going up a notch in complexity, we can get two or more such loops interacting. I have not worked out exactly what is going on in
gosblor4c2-gosblor4c2f-s17sw51:

x = 62, y = 79, rule = S23/B3
58b4o$57bo3bo$61bo$60bo3$58bo$59bo$59bo$58boo$52bo4bo$51boo3$58b4o$57b
o3bo$61bo$60bo51$11bo$10boo5$bo8bo4bo$o5bobbo4bo$o6b3o4bo$obbo10bobbo$
3o11b3o!

However, it does seem to settle down eventually, although some process is switching the production of traffic lights on and off at ever-increasing intervals. After 2^24 steps, the overall pattern is shown as gosblor4c2-gosblor4c2f-s17sw51.out-24a (the traffic lights are in the line of successively longer dashes shown more clearly in gosblor4c2-gosblor4c2f-s17sw51.out-24b).

(6) In one family of patterns, however, there are many which have not settled down as far as I have been able to track them. Instead, more and more waves of gliders, lines of debris, and as time goes on, waves of *WSSs appear, without apparent end. Here is one that produces a wave of HWSSs: gosblor4c2-gosblor4c2f-s24sw47:

x = 58, y = 82, rule = S23/B3
54b4o$53bo3bo$57bo$56bo3$54bo$55bo$55bo$54boo$48bo4bo$47boo3$54b4o$53b
o3bo$57bo$56bo54$11bo$10boo5$bo8bo4bo$o5bobbo4bo$o6b3o4bo$obbo10bobbo$
3o11b3o!

This is shown after exactly 1538469 steps: gosblor4c2-gosblor4c2f-s24sw47.1538469a shows the whole pattern, while gosblor4c2-gosblor4c2f-s24sw47.1538469b shows one of the HWSSs (the third), at the moment of formation. These HWSSs move east, just above the glider wave from the eastward puffer. Of course, they never catch the puffer, nor do they interact with the wave, but they suggest the question: in such cases, will the puffers continue producing their glider waves forever, or could something stop them? For one of the puffers itself to be destroyed, a disturbance in the body of the puffer would have to move at >c/2, or (even more unlikely), something would have to travel "up" the glider wave with an orthogonal velocity >c/2. The first of these can't be ruled out altogether, as we know there are c/2 puffers that produce a fuse that can burn at >c/2. Perhaps more likely, an MWSS or HWSS could be generated close to the wave in a position that would allow it to consume the wave, or transform it into something else. I do not yet have any examples of this.

(7) However, I do have one subfamily of patterns that produce block-laying switch engines. Two members are shown here. The first,
gosblor4c2-gosblor4c2f-s24sw72:

x = 83, y = 107, rule = S23/B3
79b4o$78bo3bo$82bo$81bo3$79bo$80bo$80bo$79boo$73bo4bo$72boo3$79b4o$78b
o3bo$82bo$81bo79$11bo$10boo5$bo8bo4bo$o5bobbo4bo$o6b3o4bo$obbo10bobbo$
3o11b3o!

Produces its first switch engine after somewhat more than 2^26 steps, the fastest found so far. The pictures show it almost at the moment the switch engine comes into being, first the whole pattern (gosblor4c2-gosblor4c2f-s24sw72.out-26-21-19-15-14-10-9a), then a closeup of the site where it is produced (gosblor4c2-gosblor4c2f-s24sw72.out-26-21-19-15-14-10-9b). The most prolific yet investigated,
gosblor4c2-gosblor4c2f-s24sw672, has produced five switch-engines after 2^32 steps: gosblor4c2-gosblor4c2f-s24sw672.out-32a shows the whole pattern, while gosblor4c2-gosblor4c2f-s24sw672.out-32b shows all five switch engines. By this point, the upper three have already stopped growing: gosblor4c2-gosblor4c2f-s24sw672.out-32bse1end shows the end of the uppermost. Once created, these switch engines bodies get hit by stray gliders, which in some cases produce "tumours", several of which can be seen in gosblor4c2-gosblor4c2f-s24sw672.out-32bse1end, and sometimes new gliders. Gliders which go in the direction the switch engine is growing will overtake it, and if they later collide with something, may send gliders back which can halt switch engine growth. (Clearly, the switch engine could also crash into pre-existing debris.) Sometimes glider-crystal can build up, as shown for the same pattern (and the same switch engine) after 2^31 steps in gosblor4c2-gosblor4c2f-s24sw672.out-31bse1crys.

All the switch engines I have so far found in this subfamily (members of which are related by 50 cell relative shifts of the two puffers either north / south or north-east / south-west) are apparently produced by the same sequence of collisions (their roots all look like the one shown in gosblor4c2-gosblor4c2f-s24sw72.out-25-24-23-21-19-15-14-10-9b). I have not yet reconstructed that sequence, but that should be a fairly straightforward, if tedious matter. I do know that the glider which actually produces the switch engine comes from the south-east. More difficult questions I'm considering are:

* Does the number of active switch engines increase over time? If so, and if no other process intervenes, these patterns would show an indefinitely (though perhaps irregularly) increasing growth rate.

* As more and more gliders hit a switch engine (if indeed, this goes on indefinitely), what happens to it? Does it act (a) as a site of a form of catalysis and/or (b) as a semi-permeable membrane? (we can ask the same of the lines of debris formed by multiple separate collisions, but these are generally much sparser, and do not run in semi-cardinal directions, so gliders cannot run alongside them).


(C) A pair of arks diverging at right angles.

I actually started investigating these before the two classes of pattern described above, but they are more easily discussed last, as they seem to be the most complex of all. So far, I have only looked at 16-cell arks, so these are 32-cell patterns. The ark-pair I have looked at in most detail consists of two "nikk" arks, one being one step behind the other. An nikk ark is symmetric about its axis of growth, producing two waves of gliders to each side. Waves from the two arks approach each other at right angles.

(1) The first thing to consider here (supposing the two arks are far enough apart not to interfere with each other before they get going properly) is the collision produced between members of the waves. In the case of nikk-nikkm1r90-w4s67:

x = 38, y = 101, rule = S23/B3
6bo$5bobo$$4bobbo$4boo$4bo25$34bobo$37bo$33bobbo$32b3o34$28bo3bo$29bob
o$30bobbo$33bo$33bo24$o$bo$bbo$bo$o$bb3o!

the gliders annihilate in pairs.

(2) In the remaining examples here, the collision produced is always the same, and would if not interfered with produce gliders going back towards both arks. However, the two waves are close enough that there is interference between them, so only alternate collisions between members of the front waves produce such gliders, at least initially. When the north-west headed glider produced by such a collision hits the north-east headed ark, it produces in turn a glider that goes north-east, alongside the ark. It is these gliders that produce the complexity among some members of this class of pattern.

In nikk-nikkm1r90-w4s66, these gliders escape to infinity, and the central east-west line of debris quickly settles down to an alternation between two types of debris, produced by local interactions.

(3) If these gliders interact with the initial glider waves, however, the result is, once again, an expanding feedback loop - but of a rather different type to that explored above, as one side of the loop consists of a glider stream rather than a wave. In simple cases, like nikk-nikkm1r90-w4s78, the outcome is a swift settling into a regular pattern with (in this case) every 8th member of the front wave being removed. There is a periodicity of 64 in the north-south relationship between the two arks (and for that matter the east-west relationship), resulting from the type of interaction (if any) produced.

(4) In other cases, it takes longer to establish a stable and repetitive growth pattern. for example, nikk-nikkm1r90-w4s162:

x = 38, y = 196, rule = S23/B3
6bo$5bobo$$4bobbo$4boo$4bo25$34bobo$37bo$33bobbo$32b3o129$28bo3bo$29bo
bo$30bobbo$33bo$33bo24$o$bo$bbo$bo$o$bb3o!

takes about 2^22 steps to do so. The picture nikk-nikkm1r90-w4s162.out-22a shows the whole pattern after 2^22 steps, while nikk-nikkm1r90-w4s162.out-22b shows the head of the north-east heading ark (every 12th member of the front wave is removed), and nikk-nikkm1r90-w4s162.out-22c shows the eastern end of the east-west debris line and the multiple waves of gliders being produced.

(5) Morse-Thue type sequences are also possible, but I have only found one example, nikk-nikkm1r90-w4s546:

x = 38, y = 580, rule = S23/B3
6bo$5bobo$$4bobbo$4boo$4bo25$34bobo$37bo$33bobbo$32b3o513$28bo3bo$29bo
bo$30bobbo$33bo$33bo24$o$bo$bbo$bo$o$bb3o!

This has previously been circulated to a small group under another name (dnikk13g513, I think). The picture nikk-nikkm1r90-w4s546.out-20a shows the western end of the east-west debris line.

(6) A considerable number of the patterns examined have not settled down as far as I have tracked them. Quite a number of these have produced switch engines, growing out of the upper ark at right angles. All but one of these have gone south-east, and all but one have been block-layers. The pattern nikk-nikkm1r90-w4s906:

x = 38, y = 940, rule = S23/B3
6bo$5bobo$$4bobbo$4boo$4bo25$34bobo$37bo$33bobbo$32b3o873$28bo3bo$29bo
bo$30bobbo$33bo$33bo24$o$bo$bbo$bo$o$bb3o!

is the only one to have produced a switch engine going north-west from the upper ark. After 2^40 steps, it has also produced three going south-east, but all these have been halted. The picture nikk-nikkm1r90-w4s906.out-40a shows the entire pattern at this point, nikk-nikkm1r90-w4s906.out-40b shows most of the pattern, nikk-nikkm1r90-w4s906.out-40c is at the largest scale that allows all four switch engines produced to be seen (of the three going south-east, two have crashed into the central line of debris, while the third is the short line parallel to these two and just above the higher of them).

(7) Finally, we can ask whether these diverging ark pairs will continue their growth for ever. I believe that, unless they stabilise, they will not do so. This is because arks grow relatively slowly, and it is possible for *WSSs to be created in such a way that they pass in front of an ark. Since gliders created close to an ark and travelling in the same direction overtake the ark's head, there is the possibility of a collision, which could block the ark's path, or send a glider back to collide destructively with its head. I have not yet seen an example, but do have an example of an LWSS passing in front of an ark, in the case of nikk-nikkm1r90-w4s164:

x = 38, y = 198, rule = S23/B3
6bo$5bobo$$4bobbo$4boo$4bo25$34bobo$37bo$33bobbo$32b3o131$28bo3bo$29bo
bo$30bobbo$33bo$33bo24$o$bo$bbo$bo$o$bb3o!

The picture nikk-nikkm1r90-w4s164.out-35-33-32-31a shows (almost) the entire pattern after 2^35 + 2^33 + 2^32 + 2^31 steps, while nikk-nikkm1r90-w4s164.out-35-33-32-31b shows the eastward end of the central debris line. The diagonal cross near the end of this line consists of large numbers of gliders, and the dot between the upper arms of this cross is an LWSS. The picture nikk-nikkm1r90-w4s164.out-36a shows the upper half of the pattern after 2^36 steps. The head of the upper ark is near the centre of the picture, and the dot above it and near the top of the picture is the same LWSS, 2^34 + 2^31 steps later.