Site Info

Authors
  • H.Koenig
  • Adam Goucher
  • Dave Greene

Main

2011 January 07

Transcendental Objects
Sprouts and parasites

Mitchell Riley was investigating interactions between a perpendicular p20 backrake and dirty Schickoidal puffer. One particular arrangement initially seems rather inconspicuous, but actually harbours an incredible surprise after approximately 1.6 million generations. Shown below is a snapshot after 2 097 152 generations:

image

What is that unusual oblique protrusion? Mitchell initially thought that it may be a switch engine, but it is clear from the angle that it is not: switch engines travel diagonally, not obliquely. It is, in fact, something that seldom occurs naturally. The gliders from the east-directed Schickoidal puffer have partially annihilated the glider stream from the north-directed backrake. A northeast-directed glider has collided with this stream, causing a messy reaction. It just so happens that the reaction generates another glider, which hits the stream of gliders again, triggering the reaction again, ad infinitum. (In this case, though, outside influence causes the 'parasite' to be terminated at circa 2 million generations.)

image
Mitchell's parasite on the p8 backrake

He discovered three more parasites, this time on a single p8 backrake. More interestingly, Bill Gosper noticed that two antiparallel backrakes can allow these parasites to reproduce, leading to an entire profusion of parasites on each rake. However, the number of parasites is limited, as they each consume a nonzero proportion of the rake's gliders.

image
A parasite reproduces in the presence of two backrakes

Continue reading "Sprouts and parasites" More

2009 March 24

Unusual Growth Rates
Pi In A Cloudy Sky

Dean Hickerson's 'Life Computes Pi' patternUpdate:Until recently, Dean Hickerson's Life pages have been available only in Web-archive form, with no images available.

Updated versions of these pages have now been moved to a new home on Tomas Rokicki's website, and the images and text files are all available again.

The image at right is from an intriguing family of patterns constructed in mid-2006. The family includes 'Life Computes Pi' and a number of 'Clouds' variants. There's really no substitute for watching these evolve in real time in a high-speed Life simulator, but a few surprising pictures of later stages of their evolution are shown below.

The pattern to the right is the starting configuration for 'Life Computes Pi', which consists of four breeders creating lines of guns that recursively stifle each other's output. The gliders appear to be spiraling outward, but in fact each set of four guns affects only itself, and any finite area around the center of the pattern will eventually repeat an earlier state.

As the number of ticks (t) increases, the population of the entire pattern approximates (pi-2)/720 t^2. At four million ticks, when the images below were captured, this works out to a value of pi correct to two places after the decimal point... so this is not quite the most efficient way to calculate pi.

'Clouds' variant of 'Life Computes Pi' pattern at 4 million ticksThe image to the right shows the large-scale shape generated by this family of objects after several million generations. The variant shown here is known as 'Clouds', because a complex feedback effect between the quadrants creates ever-larger rough-edged clouds of gliders as the pattern grows in size.

Continue reading "Pi In A Cloudy Sky" More

2006 August 12

Transcendental Objects
New Quadratic Growth Puffer

P140Quadratic Growth Puffer Mitchell Riley has found by hand a 40 bit pattern which quickly becomes a Period 140 Quadratic Growth Puffer which produces a Switch Engine every cycle. Also shown is Gen 1540, where the fifth Switch Engine is just starting out.

P140Quadratic Growth Puffer

2006 May 12

Transcendental Objects
Quadratic Population Growth, Revisited

2006-03-11-Gotts-dots.rle
'Gotts Dots': sprouts its nth switchengine at t ~ 2^(24n-6) --
41 ON cells, growth rate O(t ln t)
Bill Gosper, 11 March 2006
Bill Gosper and Nick Gotts set some new records back in March, for patterns exhibiting quadratic growth starting from the smallest initial population. On March 11, Bill Gosper produced the starting configuration shown at right, which is closely related to patterns from his previous Golly experiments.

Golly screenshot of Nick Gotts' 'wedge' /  'GRoW'
26-cell quadratic growth pattern
Nick Gotts, 17 March 2006
A week later, based on this, Nick Gotts produced a 26-cell quadratic-growth pattern: a forward-glider-producing switch engine repeatedly overtakes a crystal formed by collision with sideways gliders produced by a c/12 rake assembly. When the switch engine reaches the crystal, a reaction produces a orthogonal block-laying switch engine and restarts the crystal production at the c/12 rake boundary.

Golly screenshot of 'wedge' /  'GRoW' at ~3.5M ticks
Here is what the 26-cell pattern looks like after ~3.5 million generations:

2005 August 10

Transcendental Objects
New Sawtooth Patterns

David Bell has constructed two new smaller sawtooth patterns. The first one undercut the size of the previous smallest known sawtooth by 6 cells. Sawtooth pattern with minimum repeating population of 269

4-engine Cordership with minimum population of 134 To improve on this new record, Bell constructed a 4-engine Cordership with a minimum population of 134, compared with the 3-engine Cordership's minimum population of 149:

4-engine Cordership with minimum population of 136 There is at least one other variant with a larger population, but which still beats the 3-engine Cordership. This has a minimum population of 136:

The problem with the 3-engine Cordership is that the 2-engine "wing" component swings wildly in population from small to large, and in the 3-engine Cordership the two (overlapping) wing components are locked together in a non-optimal relative phase, so that whenever one half has a small population, the other half has a large population.

By adding another switch engine in the middle to create two independent wing components, the relative phases can be adjusted in an optimal manner to reduce the population, even taking the extra switch engine into account.

Note: these new Corderships have a smaller minimum population, but the 3-engine Cordership still has a smaller average population. The average population of the 3-engine Cordership is 193.125, whereas the average population of the 134-cell-minimum Cordership is 217.854.

Sawtooth pattern with minimum repeating population of 262 David Bell constructed a sawtooth with a minimum repeating population of 262 based on the 136-cell-minimum Cordership:

Moving sawtooth with repeating minimum population of 1239 Bell has also created a revised moving-sawtooth pattern using the small c/3 period 27 rakes discovered since they were constructed. Further optimization is probably still possible.

The pattern works in the same way as Bell's previous moving sawtooths, by using the output of c/3 rakes to ignite the blinkers from a c/2 blinker puffer, with the number of blinkers to be consumed growing on each cycle.

Another possible sawtooth design using 'lineship' technology, which Bell has not been able to complete as yet, is presented here.

2005 May 05

Transcendental Objects
New Transcendental Patterns

Dean Hickerson has presented a pair of new transcendental patterns he's created. These consist of puffers and guns, which grow in what appear to be unpredictable ways.


Ruler @ 850 Ruler The first is a "Ruler" generator:

This produces groups of LWSSs headed west, with gaps of fixed size between them. The lengths of the groups form the 'ruler' sequence, 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 ... (Sloane's A001511). The first group of length n is emitted about generation 96*2^n. The pattern uses a Corderman eater puffer found by Paul Tooke (Jan 2004), a p48 glider gun by Noam Elkies (Jun 1997), a p8 glider reflector by Noam Elkies (Sep 1998), and a p24 LWSS puffer (source unknown).

Shown are the starting pattern at Gen 0 and later at Gen 850, after 1-2-1-3-1 as been emitted. (Note: They've been rotated 90° to better fit the page.)


Jagged Lines @ 850 Jagged Lines The second object is "Jagged Lines":

Jagged lines of gliders, formed by a drifting collision of two Lightweight Spaceships (LWSS) streams, crash to form an approximately vertical jagged line of pairs of blocks. I don't know if the line stays within a bounded distance of the center line, or extends infinitely far to the left, or to the right, or both.

Shown are the starting pattern at Gen 0 and later at Gen 850, shortly after the second block pair has been created. (Note: They've been rotated 90° to better fit the page.) Hickerson also simulated the placement of the block pairs and presented a plot showing the first 11,426,769 Twin Blocks produced by Gen 4,113,636,213. (The horizontal:vertical scale is 488:1 to emphasize the shifting locations.) The dimensions of the jagged line of Twin Blocks are cells 140,480 wide with a tail 685,605,960 cells long.

Hickerson says that he doesn't think it's a random walk:

There are some large portions of it that are almost symmetric across horizontal lines. Also, the transitions between successive minimal and maximal x-coordinates are rather brief. I.e. it spends a long time far to the left of the center line, then moves quickly to a point far to the right, spends a long time there, etc. I think there's an approximate scale-invariance; if you expand the picture by appropriate factors horizontally and vertically it'll look almost the same. But I don't understand it well enough to say what those factors are.

Jagged Lines @ 4.1 Billion

Gabriel Nivasch points out that if the Pre-Block (shown in red), which is responsible for the asymmetry of the pattern, is removed, then the pattern generated is one generated by a growing sequence which starts out with zero and adds four new items at the end while sequentially reading the digits already laid out. The additions are

0 -> 1 0 1 0
1 -> 1 0 1 1

which gives the initial sequence of "0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1".