On Tue Mar 28, 2000 11:14am, Nick Gotts wrote:
Subject: 65-cell patterns with quadratic growth
I like
Dean's new kind of crystal growth!
This message reports an improvement on the minimum size pattern (in terms of number of cells) required to generate quadratic growth, and some associated investigations.
Some on the list will remember my first attempt in this direction, the `jaws' pattern, which used eight pairs of switch engines to generate a growing row of further switch engines. Some of the pairs were the `Noah's ark' pattern discovered around 1971 by (I think) Charles Corderman, others were a similar pair I found. I'll call patterns of this type, where two bare switch engines stabilise each other, `arks'. (I've found quite a few of these, all starting from 16 cells, but as I haven't been systematic about this, won't post them until I get round to a systematic search, unless anyone specifically wants them --- in which case it might take me a bit of time to collect them together.) Jaws initially had 150 cells, cut to 130 after Paul Callahan found some previously unknown 8- and 9-cell predecessors of the bare switch engine. Paul also found numerous ways of generating stabilised switch engines from small patches of cells, and from these I developed some four-glider collisions which produce infinite (linear) growth by constructing a single, stabilised switch engine. One of these:
Code: Select all
x = 151, y = 67, rule = B3/S23
bo$2bo$3o25$48bobo$49b2o$49bo32$150bo$148b2o$149b2o$141bo$142bo$140b3o!
has three gliders coming from one direction and the fourth at right angles to it, suggesting the possibility that four glider-wave producing arks might be able to produce a line of switch engines. However, the switch engines produced would travel back in the direction three of the gliders came from, and so would run into one of the arks. It was only quite recently I realised this would not necessarily prevent quadratic growth.
The following patterns all use one of two closely related four-glider collisions, different from the one above. (I've found a few others, but again have not been very systematic, apart from a subclass described at the end of this message.)
This is the first definite 65-cell quadratic growth pattern found, ousting the previous record holder, the 71-cell `mosquito 5':
Code: Select all
x = 646, y = 127, rule = B3/S23
640b3o$641bobbo$645bo$642bobo22$612bo$612boo$612bobbo$$613bobo$614bo5$
241boo$240bo$240bo$236b4o8$252boo$253bo$253boo$253bo$$250b3o45$3b3o$bo
bbo$o$bobo$438b3o$439bobbo$443bo$440bobo14$413boo$415bo$415bo$416b4o$
33bo$32boo$30bobbo$$30bobo$31bo!
This is the 65-cell quadratic growth pattern with the smallest bounding box yet found, produced by pushing the left and right halves of the pattern above 174 cells closer. I call this one `teeth':
Code: Select all
x = 472, y = 127, rule = B3/S23
466b3o$467bobbo$471bo$468bobo22$438bo$438boo$438bobbo$$439bobo$440bo5$
241boo$240bo$240bo$236b4o8$252boo$253bo$253boo$253bo$$250b3o45$3b3o$bo
bbo$o$bobo$264b3o$265bobbo$269bo$266bobo14$239boo$241bo$241bo$242b4o$
33bo$32boo$30bobbo$$30bobo$31bo!
The next three are not definitely quadratic growth patterns (my guess is that they all are quadratic, but their switch-engine production might eventually cease, or just possibly and more interestingly, slow down in such a way as to make them superlinear but subquadratic). The first is produced by pushing the left and right halves of the first pattern above 170 cells closer: in this case, when each constructed switch engine hits the nearest ark, it generates a glider which travels parallel to the ark, and collides with a glider that would otherwise help to produce a later switch engine. This leads to some of the expected teeth being absent:
Code: Select all
x = 476, y = 127, rule = B3/S23
470b3o$471bobbo$475bo$472bobo22$442bo$442boo$442bobbo$$443bobo$444bo5$
241boo$240bo$240bo$236b4o8$252boo$253bo$253boo$253bo$$250b3o45$3b3o$bo
bbo$o$bobo$268b3o$269bobbo$273bo$270bobo14$243boo$245bo$245bo$246b4o$
33bo$32boo$30bobbo$$30bobo$31bo!
All the above patterns produce block-laying switch engines. The remaining two, from a slightly different four-glider collision, produce glider-stream-switch engines. In both cases, the glider-streams interact in complicated ways with the arks. In both cases, also, different effects can be produced by shifting the left and right halves of the pattern relative to each other.
This one uses the same set of arks as the patterns above:
Code: Select all
x = 474, y = 129, rule = B3/S23
468b3o$469bobbo$473bo$470bobo22$440bo$440boo$440bobbo$$441bobo$442bo5$
241boo$240bo$240bo$236b4o8$252boo$253bo$253boo$253bo$$250b3o47$3b3o$bo
bbo$o$bobo$264b3o$265bobbo$269bo$266bobo14$239boo$241bo$241bo$242b4o$
33bo$32boo$30bobbo$$30bobo$31bo!
This one, actually the first of the five discovered, uses a slightly different set (which can't be used to produce the collision that makes a block-laying switch engine, so far as I can see):
Code: Select all
x = 764, y = 234, rule = B3/S23
3bo$3bo754b3o$boo756bobbo$o762bo$o759bobo$o$o6$30bo$29boo$27bobbo$$27b
obo$28bo9$730bo$730boo$730bobbo$$731bobo$732bo72$554b3o$555bobbo$559bo
$556bobo14$529boo$531bo$531bo$532b4o77$299bo3bo$300bobo$298bobbo$298bo
$298bo25$329bo$328b4o$326bo4bo$326bo$326bo!
The kind of feedback shown in the last three patterns can also be produced with just two arks (although I haven't found any quadratic growth patterns with fewer than four). The one below, found some time ago, produces an interesting sequence of subpatterns along its midline. Looking at the result after several hundred thou[s]and steps, at the samllest possible scale in Life32, a series of groups of birds-head-like shapes appears. Ignoring initial irregularities, the first group contains 3 heads, the second 4, the third 4, the fourth 3. As far as I was able to trace it (the program crashed), and with parentheses added for clarity, the sequence is:
((3 4 4 3)(4 3 4 3)(3 4 4 3)(3 4 4 3))
((3 4 4 3)(4 3 4 3)(3 4 4 3)(4 3 4 3))
((3 4 4 3)(4 3 4 3)(3 4 4 3)(3 4 4 3))
((3 4 4 3)(4 3 4 3)(3 4 4 3)(3 4 4 ?))
Assuming the last group is of 3, this sequence appears to have interesting self-similarities, very like the Morse-Thue sequence. Changing the vertical distance between the two arks gives different, often far more complicated results.
Returning to the four-ark quadratic growth patterns, you'd think there would be a 64-cell one, but so far I haven't found one. I'm currently working with an infinite class of four-glider collisions that produce stabilised switch engines, of which the following is an example:
Code: Select all
x = 195, y = 112, rule = B3/S23
bbo$obo$boo17$65bo$66bo$64b3o84$193bo$192bo$192b3o$$184bo$185bo$183b3o!
Like all the four-glider infinite growth collisions I know of, this uses what I call the "gliding down Herschel's throat" construction (if you run one, you'll see why I call it that), but in the pattern above, the first two gliders collide to form a pi which completes its development, so the remaining pair can be delayed as long as desired. I think this is the only such infinite class of four-glider collisions in which all the gliders come from two perpendicular directions (there are others in which the gliders that produce the pi come from two opposite directions, and these may or may not include the direction from which the remaining gliders come).
By the way, has anyone ever done a complete survey of three-glider collisions? From the recent discovery of the three glider -> pentadecathlon reaction, I'd guess not. There's an infinite number of them, but the ones where the third glider doesn't arrive until the first two have finished reacting should surely fall into a finite number of classes whose members differ only in timing, and in some cases the spacing of final objects.
Nick
