Conway's Life: Work in Progress

Geminoid Research

2010-12-21T21:16:00.006-05:00

Since Andrew Wade built his amazing Gemini spaceship out of miscellaneous scraps from the Conway's Life junkyard (a feat somewhat equivalent to assembling a jet airplane out of Model T parts) I've been looking at possible ways to simplify the design. With a lot of help from Paul Chapman this summer, I think I'm finally making some progress.

Here's a diagram of a possible Geminoid replicator unit. The original Gemini's base units are about 3750x4700, with about 16,000 live cells. This version fits into 580x540, with less than two thousand ON cells. In place of the Gemini spaceship's twelve input channels, there is now just a single stream of gliders. Four channels are encoded in the stream, two channels for each construction arm. Click on the image to the right to see how multiple copies of this unit will fit together.

There is no destruction arm in this design, and that's definitely its biggest weakness; I have quite a bit of programming left to do to produce a search utility that can "seed" the empty spaces between the signal channels with still lifes that will cause a chain reaction that destroys the entire replicator unit. The reaction will be triggered by a single glider coming from the construction site at the intersection of the two arms. It's easy enough to come up with a collection of still lifes that will do this; the trick is to find a set that's reasonably close to minimal. My current goal is to find SODs (Seeds Of Destruction) that no more than double the original population.

The other item that needs special explanation is the encoding of four channels into one, and the special limitations placed on the construction-arm salvos by that architecture.

The original Gemini had twelve parallel channels corresponding to the four glider lanes that were used to construct the various salvo combinations that acted on the elbow to produce INC and DEC movements and fire EVEN and ODD gliders. The four-glider-lane shoulder architecture was taken from Paul Chapman's prototype universal constructor -- but the prototype was "the first thing that worked" and pretty far from optimal.

It turns out to be very easy to find sets of three lanes where combination salvos (one or more sets of one, two, or three synchronized gliders) will produce all the necessary INC/DEC/ODD/EVEN operations. Once you allow multiple "cycles" -- two or three sets of synchronized gliders, not just one set -- it's even possible to cut the number of lanes down to two, or even just one (!)

It seems amazing that there's a universal set of operations at all using a single glider lane. But with pairs of synchronized gliders on a the same lane there are dozens of operations available. Many of them need five cycles instead of three or four, but considering the minimal highway width that's not much of a handicap.

The lane set I chose for a redesigned Geminoid spaceship -- pairs of gliders on lanes -5 and 4, separated by 9 cells -- has the advantage of being completely symmetrical, meaning that LEFT and RIGHT gliders can be fired equally well just by using a mirror-image salvo. This will come in handy when it's time to trigger the destruction of the old copy of the Geminoid... Also, glider inserters are available that leave the lane nine cells away completely unaffected when placing a glider, so all possible glider sets are trivially constructible.

Run the pattern in the "Geminoid replicator unit" link, and advance or delay some of the gliders in the first cycle (set of four). The corresponding output gliders will be advanced or delayed by the same amount with no ill effects -- unless the distance between any two adjacent gliders drops below 497 ticks.

The unusual feature of this operation set is that gliders are required on both lanes for each cycle of each operation. The single channel is decoded into four channels with a simple set of parallel period quadruplers, which allows the decoder to be completely asynchronous -- but it means that leaving out a glider would have disastrous consequences for the decoding process. Thus there will have to be extensive use of NOP operations (in this case, four pairs of gliders that have no net effect on the construction-arm elbow). It's also quite likely that all the operations the Geminoid uses will be exactly four cycles in length, but this isn't quite necessary for all cases.

First complete glider-to-Cordership converter

2009-02-07T07:06:00.004-05:00

For years now I've been fruitlessly plotting to put together a Herschel layout utility for Golly, to help design multi-glider shotguns and other large-scale Herschel signal circuitry. One of my first uses for the utility will be to design a (relatively) compact Cordership gun that can be triggered by a single input glider.

It seems Calcyman has finally gotten tired of waiting for this wondrous device to appear, so he has built one himself: the world's very first complete glider-to-Cordership converter! (The link goes to the RLE pattern file; here's the MCell version.)

Input gliders at the lower left are converted into clean 3-engine Paul Tooke Corderships in 13,311 ticks -- as long as no two gliders are closer together than 708 ticks. The signal is split into three main parts. The one in the center triggers an improved Herschel-to-swimmer converter using a new 5-glider recipe (see my last post for the old 6-glider solution.)

The new reaction [RLE / MCL] uses the usual four gliders to create a switch engine, but a modified Fx119 Herschel circuit allows a single glider to suppress all the extra junk the switch engine creates, until it has moved far enough forward to pick up the swimmer track.

The other two signals trigger two mirror-symmetric Cordership-wing constructors. Each of these builds a new switch engine next to the original swimmer, which then replaces the swimmer-lane support structure on that side. Once both wings are in place, the swimmer becomes the central engine of a free-flying Cordership.

I'm working on tightening up this pattern somewhat; Calcyman's new suppression reaction disposes of glider #1 from the old H-to-S, but the embarrassing #6b is still in there. The wing constructors use parts from an old universal shotgun-building toolkit, which tends to produce fairly large and sprawling patterns -- so it may make sense to adjust these at the same time.

[Further bulletins as events warrant.]

A New Kind of Signal (though not a useful one yet)

2007-06-17T15:02:00.000-05:00

This is a speculative project that has been in the works for a long time: an odd-period Herschel loop that includes a switch-engine stage. I wanted to see what David Bell's "swimmers" looked like when incorporated into a stable Herschel track. The current version isn't exactly pretty, but it does work. Here's the RLE pattern file.

What Went Wrong This Time?

The center of this circuit is an extensible Herschel fanout device based on paired F171 conduits. Theoretically adding another synchronized signal is simply a matter of adding another pair of F171s to the beginning of the series, and running a Hersrch search to produce an appropriately-timed output. F171 is a relatively slow conduit, so you do get a little extra time for adjustments with each new pair.

But it turned out not to be enough; it gets increasingly hard to reach around the edges of the conduits that have already been placed. After using the last four outputs (circuits 6, 5, 4, and 3, working backwards -- the two ends of the F171 chains, and the two extensible tandem-glider outputs) it was impossible to route the previous tandem-glider signal around to get it where I wanted it fast enough. The signal could be hurried into the general neighborhood, but it didn't quite hit any of the spacetime locations I needed. I tried most if not all of the likely Herschel-to-glider converters that could produce either of the two gliders coming in from the southwest.

I should probably have tried simply skipping the output of one F171-pair and checking to see if 342 ticks was enough extra time to allow a connection from one link further back. Something to try next time around --

In this case, the failure of the extensible fanout meant that other types of Herschel fanout devices (circuits 1 and 2 in the labeled MCell "envelope" diagram at right) had to be bolted on instead, before the split that feeds the two F171 chains. This allowed plenty of time to route two signals around to feed the SW shotgun, though the design uses up a lot more space and the conversion takes longer.

As usual, the layout was done from the inside out, so to speak, with the H-to-G converters in the deepest part of the fanout tree "solved" first. Also as usual, toward the outer edges expert Herschel plumbers may detect hints of increasing impatience with high-level architectural issues...

Not Good Enough Yet

Unfortunately I'm going to have to rebuild the whole thing eventually, because of a mistake I made in the layout very early on. Basically I thought I had a clean way to get a Herschel to the northeasternmost H-to-G converter (circuit #6) in the right number of ticks, but there was a flaw in the only conduit that fit there: it worked only half the time (i.e., it needed a blinker as one of its suppressing catalysts, to keep the Herschel signal from interfering with other catalysts later on; otherwise it produced an extra blinker).

So to make this odd-period loop work, there's a huge extra Herschel conduit bolted on to the top of the converter (circuit 6b) to suppress the extra blinker. 6b is a large slow glider-to-Herschel converter -- this was the easiest way to get a spare Herschel out without changing the rest of the circuits.

The repeat rate of the full circuit was going to be up in the 600-tick range in any case, because of the boojum-transmitter adjustment I used in circuit #2... and because the swimmer-to-Herschel stage at the other end of the channel uses basically the same slow glider-to-Herschel mechanism, except it reflects an extra glider back to clean up a junk block.

In any case, two Herschels are doing the job of delivering the last glider to the northeast in the switch-engine recipe, where one Herschel should really be plenty... kind of spoils the whole construction. I'm not sure the idea of "elegance" really applies to these extended Herschel-track experiments -- but anyway it isn't quite up to my arbitrary standards for these things.

General notes on multi-Herschel constructions

Laying out these things is a balancing act between ridiculously large solutions and ridiculous amounts of time spent working out the bugs in more compact circuitry. It's easy to produce any glider timings you want, for example, if you leave enough space for a boojum-reflector timing adjustment on every signal path; known Herschel conduits can give you output gliders with any timing mod 8, relatively quickly (usually three or four conduits, sometimes two -- assuming the output lane is an reasonable distance ahead of the input Herschel.)

But when adjustments are necessary, it tends to affect the compression of the circuitry: if the adjusted boojum-reflected glider is sent into a tandem-glider transceiver, the repeat time will get worse the more the reflector is moved back. If the glider goes into a standard G-to-H, then you're immediately stuck with the repeat time of the G-to-H (currently I think this is still at least 497 ticks). Thus a "good" circuit design should probably try to avoid adjustable components -- ideally the signal-splitter outputs should be routed fairly directly toward their goals. Too bad it never actually seems to work that way...

Another Approach (that doesn't seem to work)

I'd also like to have one more look at the idea of using junk still-lifes or oscillators to keep the switch engine going in its early cycles, on the way from the construction site into the diagonal track. Currently two of the six gliders in the recipe just suppress the switch engine's exhaust, doing the same job that the boats do in the permanent track. A simple block, blinker, or beehive can do the same job, and get cleanly destroyed in the process; they can be placed any time after the initial construction gliders go by but before the switch engine hits the key spot with its exhaust.

#C Four gliders plus two blocks produce a 'swimmer'
#C -- the blocks must be placed after the gliders go past.
#C Theoretically Herschel-to-block converters might make this
#C as efficient as the six-glider version, but Herschel tracks
#C close to the swimmer lane tend to get in the way of
#C the incoming gliders; an all-glider solution was much easier.
x = 69, y = 71, rule = B3/S23
19bo$17b3o$16bo5boo$16boo4boo3$25bobo$25boo$26bo$$15bobo$16boo$16bo$oo
$oo3$29bo5boo$28bo6boo$28b3o$5boo$5boo$$20boo21boo$19bobo20bobo$21bo
21bo4$15boo$15boo$51boo$50bobo$51bo3$22bo$21bobo$21boo$59boo$58bobo$
59bo3$30bo$29bobo$29boo$67boo$66bobo$67bo3$38bo$37bobo$37boo6$46bo$45b
obo$45boo$$67boo$67boo3$54bo$53bobo$53boo!

I spent a lot of time fiddling around with Herschel-to-junk converters a few months back, but discovered as usual that being able to adjust the timing of the suppressing signal -- i.e., building the suppressing junk at any of a moderate range of times during the construction -- wasn't worth losing the wider range of adjustability in the delivery location: when you're placing stationary junk you have to hit the right location exactly and you have to worry about the converter catalysts getting in the way, where with a glider you can place the H-to-G converter anywhere along the input diagonal.

Five Types of Interchangeable Signals

It seems a little odd that there aren't more kinds of asynchronous signal tracks by now. For tracks where converters to and from other signal types have been explictly constructed, we've got gliders, *WSSes, Herschels, 2c/3 diagonal wires, and now switch engines. How many have I left out? Even if we say that the tracks can contain low-period oscillators, I don't think there are very many more types (?)

I'd say that things like Caterpillar blinker trails and telegraph wires don't count (yet) because they move each time they're used, and nobody has bothered to set up a way to send a signal through only when an input comes in. Theoretically a telegraph could transmit information asynchronously, but not if it's being powered by high-period guns as in the current model (a signal is sent every cycle, but it's modified slightly depending on the input.)

I do have a rough design for an asynchronous telegraph that avoids sending ten pulses per signal (or a reverse signal) to reset the wire. But it would end up similar in size and latency to the current model, and at this rate it will be several years to never before that sees the light of day. Converters using Corderships or 2c/5 spaceships as signals would be at a similar order of size and level of effort.

Maybe someone can supply p15 converters to get a signal out of an orthogonal pi-heptomino track made of pentadecathlons --

#C pi-heptomino conduits: Dean Hickerson, 17 February 1997
#C Herschel-to-pi stage by Paul Callahan (part of Fx176)
x = 151, y = 75, rule = B3/S23
124bo3bo$123boo3boo6$104boo6boo25boo6boo$103bobbo4bobbo23bobbo4bobbo$
102b6obb6o21b6obb6o$103bobbo4bobbo23bobbo4bobbo$104boo6boo25boo6boo6$
107b4o$106b6o$105b8o$104boo6boo$105b8o$35bo17bo17bo17bo16b6o$34bobo15b
obo15bobo15bobo16b4o$135b3o$134bo3bo$34b3o15b3o15b3o15b3o43bo3bo$34b3o
15b3o15b3o15b3o44b3o$35bo17bo17bo17bo$95boo$95boo$35bo17bo17bo17bo$34b
3o15b3o15b3o15b3o44b3o$34b3o15b3o15b3o15b3o43bo3bo$134bo3bo$135b3o$34b
obo15bobo15bobo15bobo$11boo8boo12bo17bo17bo17bo$12bo8boo$12bobo$13boo
$$126boo$7boo117boo$8bo$8bobo$9boo$$116bobboboobobbo$116b4oboob4o$116b
obboboobobbo3$9bo$9bobo$9b3o$11bo$$21boo$21boobboo8bo17bo17bo17bo$25bo
bo6bobo15bobo15bobo15bobo17boo$bboo23bo80boo$3bo23boo$3o31b3o15b3o15b
3o15b3o$o33b3o15b3o15b3o15b3o$35bo17bo17bo17bo3$35bo17bo17bo17bo$34b3o
15b3o15b3o15b3o$34b3o15b3o15b3o15b3o3$34bobo15bobo15bobo15bobo$35bo17b
o17bo17bo!

Getting the signal started is no problem, using a stable Herschel-to-pi stage, but I don't think anyone has found a good converter for the end yet. Should be possible to engineer a multi-stage one, at least, where some useful junk is destroyed and re-created. Obviously it would be p15 or p30, not stable, but it would still be fun to see a really big pi orbital working.

A Small Direct Converter (if wishes were horses)

When Brice Due was working on a revision of ptbsearch last year, I held out some hopes that a compact H-to-S (Herschel-to-swimmer) converter might happen show up, once the search code started keeping an eye out for "tamable" switch engines along with other more likely transients (Herschels, B-heptominos, R-pentominoes, and so forth.)

Come to think of it, one could also keep an eye out for transient patterns that could trigger a 2c/3 signal -- a direct H-to-2c/3 would save even more spaghetti wiring than an H-to-S would... though a direct 2c/3-to-H is probably a harder problem, maybe more something for a 'dr'-type search on a new supercomputer, or a distributed computing system.

Distributed Searches?

Periodically I try to work on finding a way to usefully distribute an exhaustive ptbsearch search (or dr or wls -- pick your poison). But so far I've more or less hit a wall and bounced off, every time. The most promising line of research seems to be finding a way to short-circuit repeated searches in one area, probably using hash tables and lots of RAM.

To make this a little less vague: you often notice that a search problem splits into separate sub-searches, where you end up going through all the permutations of Solution A | B | C ..., say in one corner of the search area, and Solution Z | Y | X ... in another corner. Since the local conditions are identical and [A|B|C...][Z|Y|X...] works equally well in any combination, it might really only be necessary to go through A, B, C... once and Z, Y, X... once, and record the results of the search in a hash table somehow.

Might work even better to short-circuit searches that _don't_ produce solutions; how much of a WLS search involves going over the same ground over and over, for example? My perception is that a majority of WLS's time is wasted chasing its tail in this way -- but quite possibly that's just an artifact of my relative inability to set up successful WLS searches!

Anyway, maybe one of these days we'll get there. A non-engineered "Conway-space" H-to-S would go a long way toward allowing Herschel circuitry to be packed into tighter spaces: at the moment, the new F171 is the best diagonal conduit available. Oherwise, parallel circuits that run diagonally tend to have to travel Manhattan-style, with a lot of 90-degree turns and sharp corners that get in each others' way -- or they have to convert signals to tandem gliders and back, which is also fairly awkward (mostly because of chirality limitations in the standard transmitter).

Hex Counter and Cells Within Cells

2007-04-27T08:56:00.000-05:00

Some incredible patterns have been included with the latest version of Golly, a cross-platform editor and player that can display huge CA patterns, and often run them at unheard-of speeds. Golly 1.2 came out in mid-April on SourceForge; one of the new patterns is a two-digit hexadecimal counter implemented as a Conway's Life pattern. It's a modernization of sorts of Alan Hensel's 1994 "Decimal Counter" pattern -- an animated Java version of which is now available on the Web [collidoscope.com].

Another set of patterns by the same author, using some of the same components, are composed of huge grids of metapixels -- regions thousands of cells square that are designed to mimic the behavior of the underlying cellular automaton, or that can be "reprogrammed" to simulate other rules.

The Golly engine is based on hashlife (see the Dr. Dobb's Journal link for details on how the algorithm works).

The hex counter can be found in the Hashing-Examples folder in Golly's pattern collection, along with three metapixel samples. This series of screenshots shows the counter in action at various scales.

The first screenshot shows individual cells in the underlying grid, making up two still lifes (a block and a fishhook eater) and two spaceships (lightweight and middleweight).

The two spaceships are part of a high-period salvo that either creates a block or 'pulls' it along a row of memory bits that encode each pixel of the 'hex counter' movie.

The two blockers in the lower left corner both suppress the creation of blocks. The one on the left ends the block-pull cycle and allows the movie to cycle back to the beginning. The one on the right cleans up the extra block in an identical reaction triggered by the salvo-suppression glider coming in from the upper left, instead of by a block.

The suppressing glider is itself suppressed by a glider from a high-period Herschel-based gun that ends just to the right of this image. It is made from a long series of Herschel period-doublers plus a Herschel-to-glider converter.

This is the first subpixel zoom in the series, so individual cells can no longer be seen and shapes may become somewhat distorted. For example, the two seven-bit eaters at center left, which are part of the row of 'memory bits' that tell the movie pixel when to toggle ON and OFF, are reduced to four-bit polyominoes in this view.

The rows of lightweight spaceships (LWSSs) that form the ON state of each movie pixel can now be seen clearly at the top. No LWSSs can be seen at the bottom edge because that pixel is currently turned OFF.

Here an entire edge of a single movie metapixel can be seen; in the center can be seen the row of memory bits that encode half of the metapixel's contribution to the movie. For compactness, the even and odd bits of the movie are stored along separate edges of the metapixels.

The other half of the movie's frames are encoded in a column along the left edge of the movie metapixel, on a diagonal mirror-image from the row along the bottom. At this zoom, two entire metapixels are visible, and the memory-bit columns are visible only as thin vertical lines at the far left. It can be seen that different metapixels contain different coded sequences.

Here several metapixels can be seen at once. The differential shading between the two halves of the pixels at this scale is an artifact of the LWSSs' rectangular shape, and the fact that they are not spaced a power-of-two distance from each other.

At this scale the pixels appear solid and almost all of the details of the control mechanisms are too small to be seen.

At this scale the entire 'movie screen' can be seen. The movie's frame rate will vary widely depending on the memory and CPU speed, but with a step size of 8^4 or 8^5 it may reach several frames per second once Golly's hash tables have been populated.

A final view of the movie screen with all the construction details lost in the distance.

Stable pseudo-Heisenburp device and other P1 wiring projects

2007-01-22T16:23:00.000-05:00

I've been experimenting recently with what might be called "staged-recovery" Herschel conduit constructions. Reactions using only stable (P1) catalysts are often imperfect -- that is, there's no known way to accomplish many signal-processing tasks without either

(a) temporarily destroying some still life, and going back and replacing it later, or

(b) creating an unwanted still life as a byproduct of a useful reaction, and going back and removing it later.

Generally (b) is easier than (a), since most simple still lifes can be annihilated by a single glider on the correct lane -- maybe with the help of a catalyst, but with few or no timing constraints. If a period-2 byproduct (most commonly a blinker) has to be modified or removed, this usually cuts in half the allowable spacetime locations for cleanup gliders, but still leaves a very wide search space.

So this kind of repair just means routing a Herschel to any one of twenty-plus known Herschel-to-glider converters, anywhere along the target glider lane, with a wide range of timings (usually the quicker the better). With this many degrees of freedom, a Hersrch search can generally find a fairly compact solution.

-- Compact as these things go, that is! With a choice of 17 conduits in the basic set, a string of (say) three to five conduits will often be enough to put a glider on the correct lane, without having to wander off too far in the wrong direction -- unless the glider lane is too close to the input Herschel. A target area at least fifty cells away from the input Herschel should usually allow a clean connection to be made. I'll work on some rough coverage graphs for a separate posting.

The basic idea behind a staged-recovery construction is that it's often possible to quickly make a repair, even a difficult repair -- say, rebuilding a loaf used to reflect an incoming glider, as shown below -- at the cost of some minor damage to the repairing circuitry. If the damage itself can be repaired relatively quickly and easily, the result is a somewhat more complex circuit that can recover more quickly overall -- if the initial part of the circuit is triggered again, the damaged area can often be repaired before the next signal reaches it.

Highway robber without a staged-recovery mechanism -- recovery time is 2381 ticks.

As an example of a staged-recovery construction, here's a "highway robber" that absorbs gliders on a given lane and produces optional output gliders or Herschels, while letting gliders on all lanes beyond the key lane pass unharmed. This version takes the straightforward route of first producing Herschel signals from the initial glider, then using the Herschels to rebuild the original loaf. (The loaf is dangled in the key glider lane as "bait", and is destroyed while reflecting the input glider.)

Highway robber with staged-recovery mechanism --
recovery time is 1696 ticks, but the pattern does not become
stable again for 2234 ticks.

Here's the same basic reaction using two stages, where the stage 2 circuit removes two extra beehives from the stage 1 circuit, and as a result allows the highway robber to recover more quickly overall, and also to produce an output signal much more quickly:

stable pseudo-Heisenburp device -- recovery time is 1847 ticks.

And here's the same idea taken a little further -- attaching the highway robber to a revised 2c/3 transceiver produces a stable pseudo-Heisenburp device, which "borrows" a glider from the edge of a fleet of gliders, and later (thanks to the magic of stable 2c/3 signal wires) puts it back in exactly the right location relative to the other gliders in the fleet:

The primary use of the staged-recovery idea in the transmitter is in the northeast circuit, which asynchronously rebuilds a beehive and sends in a glider to reset the beginning of the 2c/3 wire after the signal is sent. The pattern could be rearranged to trigger this circuit considerably faster -- or even *before* the main trigger signal arrives (in which case the quiescent state of the transmitter would not include a beehive).

Here's a Python script that builds a complete P1 Heisenburp device from its component parts. The above screenshot shows what it looks like in Golly 1.1. It can also take advantage of the new multi-layer functionality in Golly 1.2. In multi-layer mode, the script produces a screen something like this:

tiled views of the Heisenburp device: screenshot from Golly 1.2 beta

Update: The latest version of this script is now included as Scripts/heisenburp.py in the Golly 1.2 release distribution.

Xlife #I format for Golly? Sort of...

2006-11-02T20:16:00.000-05:00

I've added a couple of Python scripts, breeder.py and breeder-display.py, to a subsidiary folder in the Golly CVS system. These are by way of being translations of the original Xlife breeder.life -- one is short and fast, and the other is a slower on-screen walkthrough showing the breeder being incrementally constructed from smaller pieces.

I was hoping to be able to use breeder.life as a test case for code that would take *.life as input and produce one of these two types of .py script as output... but it's only _almost_ that simple.

The breeder.py script is a direct translation -- the numbers after each #I line show up pretty much unchanged in the Python script, and there's an easy glife conversion for the rotation and reflection specs:


0, 1 -> identity
1, 1 -> rcw
2, 1 -> flip
3, 1 -> rccw
0,-1 -> flip_y
1,-1 -> swap_xy
2,-1 -> flip_x
3,-1 -> swap_xy_flip

The only problem is that four subpatterns in breeder.life are defined with an 18-step time offset, like this:


#B ./breederrake.11
#I :breederpuffer 71 37 0 1 0
#I :ss.s 75 14 0 1 18
#I :ss.m 60 6 0 1 18
#I :ss.m 60 -8 0 -1 18
#E

Translated into English: "To make a breederrake11, put a breederpuffer at (71,37), run it for 18 generations, and then drop an LWSS at (75,14), an MWSS at (60,6), and a reflected MWSS at (60,-8)" [where breederpuffer, LWSS (ss.s), and MWSS (ss.m) are defined later in the file.]

This would all be very well and good, but here's the rub: the resulting breederrake11 subpattern is _not_ the 'flat' pattern resulting from running breederpuffer for 18 generations and adding the *WSSs. It's a true recursive definition -- which means that to get the right results in the final pattern, you have to rebuild each and every instance of breederrake11 by dropping a breederpuffer at the right relative location, waiting 18 ticks, and then adding the spaceships!

The glife system, on the other hand, generally deals with 'flat' subpatterns: if you give the above recipe for a breederrake11 and drop a copy of it into the Golly universe, what you'll see at t=0 in your final pattern is *generation 18* of breederpuffer!

The only safe way around this appears to be to "unpack" every definition that has a nonzero time value -- flatten out the nested definitions... and end up with a significantly longer recipe.

So in the end I cheated. In this specific case, it was easy enough to move the spaceships forward 9 cells to produce an equivalent breederrake11 that was all defined at t=0 -- no 18-tick time offset. The revised subpatterns were safe to use for the next level of definitions (this is not necessarily true, but it happened to be true in this case.)

The only remaining ugliness was the way that Xlife drops subpatterns into the universe, then runs the universe until it's time to drop in the next pattern -- instead of running each subpattern in isolation, then dropping it in when it has reached the right phase. Doing this in Python and storing the subpatterns in variables can require a lot of nested parentheses [or a long series of assignments to intermediate variables]:


flotilla = (((((((breederrake11(314,242)[4]
                  + breederrake11(312,201,flip_y))[101]
                 + breederrake00(368,286))[33]
                + breederrake10(359,158,flip_y))[306]
               + breederrake10(406,137,flip_y))[129]
              + breederrake01(349,273))[141]
             + breederrake10(428,336) + breederrake10(426,107,flip_y))[223]
            + breederrake00(473,371))[1]
           + breederrake00(472,71,flip_y)

The final result is a Python variable containing a complete breeder pattern.

--------------------------------------

The other way to build a breeder using the Xlife recipe is to use Golly's visible universe -- actually drop subpatterns in and run them. The second Python script, breeder-display.py, does this, in a way that lets you see the breeder pattern coming together:


breederrake11.put(314,242)
run(4)
breederrake11.put(312,201,flip_y)
run(101)
breederrake00.put(368,286)
run(33)
breederrake10.put(359,158,flip_y)
run(306)
breederrake10.put(406,137,flip_y)
run(129)
breederrake01.put(349,273)
run(141)
breederrake10.put(428,336)
breederrake10.put(426,107,flip_y)
run(223)
breederrake00.put(473,371)
run(1)
breederrake00.put(472,71,flip_y)

[if you look at what the script is actually doing, it's actually a bit more complicated than that, because it highlights the location of the next paste operation ahead of time -- but the above is the basic idea.]

--------------------------------------

In either case, the Xlife model doesn't seem to be the most efficient way of describing patterns compactly _or_ building them quickly -- my final target here is still a structured-format Caterpillar. The Xlife system essentially requires rebuilding every single copy of every single component pattern! It's possible to take shortcuts some of the time, but they're dangerous -- a pattern that Xlife can successfully load may blow up catastrophically if shortcuts are used.

Golly's normal method of defining new patterns in terms of transformed and rephased subpatterns, and then re-using the 'flat' results, seems to be more generally useful for recursive pattern definitions.

Brice Due's Game-of-Life Metapixel -- Sample Patterns

2006-09-09T14:55:00.000-05:00

Here are a few sample screenshots showing "metapatterns" created using Brice Due's new Conway's Life metacell and displayed with Golly 1.0. Click on the images to see them at full size:
Download this file

Download this file

A metacell is a large pattern that "simulates" a single cell in Conway's Game of Life or another similar CA rule; that is, when a grid of metacells is run for the right number of ticks -- one "metatick", so to speak -- a metacell will turn ON or OFF according to the rules it's programmed to follow, just as a single cell does.

David Bell's original unitcell was the first example of a metacell, followed by Jared Prince's modification which allowed multiple independent cell states in a single "Deep Cell". Both of these unitcells were hard-coded to simulate only the Conway's Life rule (which is also the only rule that allows the patterns to function.)

One of these days, Brice Due will probably get around to finishing the work of documenting his recent OTCAMP [Outer Totalistic Cellular Automaton Meta-Pixel] construction, which showed up as a star feature of the Golly 1.0 pattern collection. This new 2048-cell-square pattern is capable of acting like a single CA cell following any "outer totalistic" rule -- i.e., birth and survival can be programmed to depend on any combination of number of ON neighbors, from zero to eight, in the metacell's immediate neighborhood. The official OTCAMP weblog describes the new signal-processing technology (mostly period 46) included in the construction.

But the most impressive feature is the "metapixel" behavior: where Bell's and Prince's designs relied on a single glider in a particular spacetime location to signal an ON or OFF state for the metacell, Brice's metapixel quickly switches rows and columns of LWSSs on and off across a large area -- so the state of a metacell can be seen even when a viewer is zoomed out so far that it's impossible to distinguish individual circuit elements, let alone single cells.

The effect is that Golly can run a large metapixel pattern at surprisingly high speeds (after some initial warmup time to build up the hash table) -- and if the zoom level is high enough to show the whole metapattern, the effect is fairly similar to watching a regular pattern in a conventional Life player. When I started zooming in for the first time, the effect was thoroughly jaw-dropping -- it takes several successive magnifications before the individual components become visible.

The OTCAMP weblog is currently [as of 2/5/2007] a work in progress, and since Brice is also working on another very interesting Game-of-Life project (reworking Paul Callahan's 'ptbsearch' signal-conduit search program) I don't want to distract him... so I figured I'd make the ON and OFF metapixel patterns available here, along with a few pictures and sample metapatterns -- just in case anyone wanted to look at some of the metapatterns that didn't make it into the Golly "top-100" collection.

A full archive of the metapatterns Brice sent me, plus one or two that I generated myself with a Golly Python script (metafier.py, now included in the Golly 1.1 Scripts folder), can be downloaded from http://cranemtn.com/life/weblog/metablog.tar.gz. And here are the base patterns from which any metapattern in any outer totalistic rule can be composed -- a single OFF cell and a single ON cell. Notes on programming these metacells to simulate any rule of the form B??/S?? [each cell's birth and survival depending on the number of ON cells in its eight-cell neighborhood] can be found in the comments of the OFF and ON cells; I've also reproduced the header at the bottom of this posting.

Here's a detail from a metapattern made out of copies of Jason Summers' p156 gun:

Download this file or click on it to see a full-sized image.

Here's a detail of one particularly interesting phase of the p156 tiling:

Here's a sample metapattern showing what happens when the tiles are programmed to run the B1/S1234568 rule instead of B3/S23:
Download this file to open it in Golly, or click on the image to see a full-sized screenshot. Detail after the pattern runs several metacycles:

Here are a couple of simple B3/S23 patterns, generated with the Golly 'metafier' script (left) and Brice's original Perl script (right), showing what metapixels look like at various scales. The Perl script works on HistoricalLife three-state rule patterns from MCell 4.20, so the presence or absence of a metapixel cell can be used to denote the third state -- a "history" state that is used for cells that are currently OFF but have been ON in the past:

Download this file

Here's an MWSS -- a middle-weight spaceship from Conway's Life, B3/S23 -- made out of metapixel tiles. However, the tiles are programmed to simulate a completely different rule, B3-S12345, which uses the MWSS as a seed for an expanding maze pattern:
Download this file

Here's the same pattern after it has run for a few hundred meta-generations:

Header (slightly modified) for metapixel ON and OFF base tiles:

------------------------------------------------------------------ OTCAmetapixel unit cell by Brice Due (fall 2005 - spring 2006). For info, base patterns, and a perl script to automate tilings, see b3s23life.blogspot.com/2006/09/brice-dues-game-of-life-metapixel.html Both ON and OFF tiles must be programmed identically before tiling a model pattern. See below for programming instructions. ------------------------------------------------------------------ OTCAmetapixel tilings require Golly hashlife to run. Get Golly at http://golly.sourceforge.net USAGE: Speed steps 8^3 - 8^6 are good. Be patient after changing the speed step; the hashlife cache needs time to warm up. Try increasing the maximum hash memory setting if the meta-pattern continues to run haltingly. ------------------------------------------------------------------ OTCAmetapixel = Outer Totalistic Cellular Automata Meta Pixel = OTCAMP Period: p35328 = 2^9 * 3 * 23 Dimensions: 2048x2048 but physically 2058x2058 (see TILING below) Pixel Area: 1720x1720 = 70% of the tile area Duty Cycle: 90% (1720 / lwss c/2 = 3440 gens to transition pixel display) TILING: To tile by hand, place tiles so that the cornermost blocks overlap. The tiles will physically overlap by 5 cells in every direction. The overlap will place tubs inside cross-corner neighbors. When tiling by script the tiles can be trimmed to 2048x2048 and the corner blocks and tubs removed. But the script MUST place the tubs inside cross-corner neighbor tiles. PROGRAMMING: There are three different programmings. Two must be done explicitly by the user while the third is done implicitly during tiling. B/S RULE: Any outer totalistic rule can be programmed. The lookup tables in the SW corner of the tile are in the familiar B/S format. The presence of an eater denotes membership of {B,S}n within the active rule set. To aid programming by hand, defective eaters have been placed at all 18 positions. These defective eaters burn cleanly. Thus, programming a rule is as simple as completing the eaters at the desired positions within the lookup tables. The lookup tables have been graphically annotated to make things clear. (Note: to study a single tile, program the rule B0/S = B0/Snone.) CONNECTIVITY: There are eight glider output channels {NW, N, NE, E, SE, S, SW, W}. These channels are initially closed by eaters. The physical presence of a neighbor tile will trigger the appropriate proximity fuses and open the necessary glider channels. This programming is done automatically when tiles are placed. NEIGHBORHOOD: Any subset of a Moore neighbrhood can be programmed. Initially there are 8 active proximity fuses {NW, N, NE, E, SE, S, SW, W}. Disabling a fuse results in that glider *output* channel remaining permanently closed. To disable the corner fuses, remove the lwss for that corner. To disable edge fuses, remove the block in the middle of that edge. Do not remove the eater near the block. For example, a von Neumann neighborhood is programmed by disabling the four corner fuses, leaving the four edge fuses active.

The Last Few Years of Life News

2006-06-06T05:44:00.002-05:00

For the past few years, Heinrich Koenig has been making available an ongoing catalog of new Game of Life results and current open problems. [I've been helping out some, but it's his server, so he ends up doing most of the work...]

Some randomly selected highlights:

Based on a recent 41-cell construction by Bill Gosper that exhibits O(t ln t) growth, Nick Gotts produced a pattern with only 26 ON cells with O(t^2) growth. [Update based on Nick Gotts' comment: Gosper's 41-cell construction remains the smallest pattern with a growth rate that is not an integral power of t.]

Hartmut Holzwart spent a little time recently constructing strange some patterns that look like inside-out spaceships. They're actually signals that travel through a half-ON, half-OFF striped agar -- the pattern that serves as the center of most of Holzwart's recent extensible "greyship" spaceships. The new signals move at 2c/3, two thirds of the "speed of light", and at right angles to previously-known lightspeed signals in the same medium.

Speaking of 2c/3, a while back Noam Elkies and I put together a 2c/3 diagonal signal transceiver based on a "wire" designed by Dean Hickerson. A transceiver is a device capable of transmitting information along a variable-length "wire"; in this case, the signal travels diagonally at two thirds of the speed of light, faster than any possible spaceship-based signal.

For diagonal signalling, this can even beat Jason Summers' telegraph from February 2003, which can communicate along an orthogonal "wire" at the speed of light (see Gabriel Nivasch's discussion of lightspeed signals -- a pair of telegraphs at right angles can only manage c/2 diagonally.)

Nicolay Beluchenko, in addition to producing several incredible collections of new Game-of-Life spaceships with a variety of new shapes and speeds -- and has also modified a known 'Garden of Eden', or 'orphan' pattern to fit it into a 12x12 bounding box. [Update: Achim Flammenkamp had previously discovered a 12x11 Garden of Eden with only 72 ON cells.]

Along with his extended explorations of c/12 Cordership technology, David Bell created a series of new sawtooth patterns. Definition of 'sawtooth' from Stephen Silver's Life Lexicon: "Any finite pattern whose population grows without bound but does not tend to infinity. (In other words, the population reaches new heights infinitely often, but also infinitely often returns to some fixed value.)".

Dean Hickerson invented some new "transcendental patterns" consisting of puffers and guns, which grow in what appear to be unpredictable ways.

A little farther back (December of 2004) Gabriel Nivasch, in an incredible feat of Life engineering, put the finishing touches on a Caterpillar -- a spaceship that travels at the previously unknown speed of 17c/45.

Many of the above patterns are much easier to study now that Andrew Trevorrow and Tomas Rokicki have made available their new cross-platform Life simulator, "Golly". It works on Macintosh, Windows, and Linux boxes, and makes clever use of hash tables to display the evolution of patterns with interesting large-scale behavior to a previously unheard-of number of generations.

Before the Caterpillar appeared on the scene, Karel Suhajda, Scot Ellison, David Eppstein, Paul Chapman, and others collaborated on the project of completing Jason Summers' sub-1000 gun collection [download link] -- an impressive conglomeration of the smallest known patterns that produce one output glider every p generations, for each period p=14 to 999.

This "gun collection" showcases a surprising variety of Life patterns, since as a general rule most new primes or prime factors require different mechanisms! (Some patterns have adjustable periods, but adjusting them tends to increase their size... and quite soon a custom-designed alternative with a smaller bounding box can generally edge them out of the running.)

Most of the higher-period guns were produced with Karel Suhajda's search program 'Hersrch' [download link], which given a target period can automatically generate a minimal Herschel loop (standard period-independent signal-guiding Life technology, originated by David Buckingham and extended by Paul Callahan). But the gun collection is an apparently inexhaustible source of optimization problems: as new Life technology is discovered, it can be incorporated into new guns with smaller bounding boxes, as in the case of this new piece of Herschel technology.

Back in 2004, Paul Tooke discovered an amazing new Cordership with only three engines, much easier to construct with gliders than any of its predecessors -- see '/jslife/guns/gun-corder-p690.lif' in Jason Summers' patttern collection.

Mark Niemiec's incredible collection of glider constructions is always worth mentioning. He's been steadily adding to the collection with syntheses of new discoveries.

Also in 2004, Jared Prince made an ingenious modification to David Bell's old Unit Life Cell. His new "Deep Cell" can process two independent states in parallel, opening up the possibility of running an infinite number of infinite Life configurations simultaneously in a single infinite universe (it's just that most of the configurations are simulated very, very, very slowly...) But of course for this kind of proof-by-example, execution speed isn't really the point: the pudding is in the proof, not in the practical details -- or however one should phrase that.

---------------------------------------------

Number-theory curiosities of various kinds have been showing up in of Game of Life patterns for a long time, of course. Many Game of Life engineering efforts involve infinitely-expanding patterns -- ranging from mathematically simple ones like Hartmut Holzwart's MAX pattern, which expands at the maximum sustainable speed in all directions, to much more complex engineering efforts like Dean Hickerson's prime-number generator -- or Jason Summers' modification of Hickerson's pattern, which expands forever unless it discovers a new Fermat prime (!). In August 2003 Jason Summers constructed a pattern that expands at O(log n) -- and logic circuitry that can store and manipulate integer values in O(log n) space is also within reach now.

New results from Glue 2

2006-02-24T06:55:00.000-05:00

Paul Chapman's Glue project is producing some interesting results these days. Glue (or rather Glue 2) is a search program that finds "natural" constructions of singlets (indivisible p1 and p2 patterns) by starting with a target object -- usually a block -- and bombarding it with a p2 slow salvo of gliders.

'salvo' means that all the gliders come from the same direction; 'slow' means that glider #n+1 must not arrive until the reaction from glider #n's collision has settled down into stability or a p2 oscillation, and 'p2' means that the only timing constraint on the gliders is that an even or odd phase may be specified. (Many intermediate collision results contain blinkers, beacons, toads, or other p2 patterns, and a glider on a given input lane can interact with a p2 target in two possible ways.)

You can also download the RLE, or have a look at a larger image. Here are the actual recipes in text format, and the MCell file used to create the above picture.

This is an example of a clever new MCell rule by Brice Due -- it shows not only the Smear but also the starting locations of the gliders and block, without changing anything about how Life actually evolves. Potentially a fairly useful trick for displaying this stuff. His notes also taught me a new way to do cell-state substitutions, with an MCell command I hadn't noticed (or at least realized the potential of). I had been doing the same task much more painfully by setting up whole new rules to do state conversions.

After the pattern is run, the full cell history is visible, just as in MCell's 'HistoricalLife' rule: all cells that were ON at any point during the reaction are blue instead of black --

Here's another take on the same display problem: Koenig's annotation format allows for multiple layers in different colors, in a format that's backwards compatible with standard RLE (at least for most Life editors.) Click on the image to see the RLE:

Finally, here's a screenshot of the current version of the Glue 2 search program used to generate these recipes:

Holiday Greyships -- Grey No Longer!

2005-12-10T10:55:00.000-05:00

Over the last several months, Hartmut Holzwart (with some help and suggestions from Jason Summers and others) has been building a wide variety of "greyships": extensible orthogonal spaceships with a wide variety of sizes and shapes, where the expandable central area is made up of stripes -- half ON and half OFF cells, either parallel or perpendicular to the spaceship's direction of travel.

Running these ships in MCell with the Rainbow024 palette and 17 alive states (see the Colors menu for both settings) gave some nice Yuletide colors -- figured I'd post the results here:

trial pattern showing a slipping-stripe reaction sent in
by Gabriel Nivasch: Hartmut Holzwart, 21 November 2005

alternate mirror-symmetric pattern showing Gabriel Nivasch's
slipping-stripe reaction: Hartmut Holzwart, 28 November 2005

hybrid 2c/4 greyship: Hartmut Holzwart, 16 November 2005

alternate hybrid 2c/4 greyship
Hartmut Holzwart, 16 November 2005

sample asymmetric hybrid greyship
Hartmut Holzwart, 18 November 2005

hybrid greyship: Hartmut Holzwart, 18 November 2005

symmetric hybrid greyship: Hartmut Holzwart, 18 November 2005

triangular hybrid greyship:
Hartmut Holzwart, 23 Nov 2005

greyship showing new components: Hartmut Holzwart, 25 Nov 2005

hybrid greyship with a crooked internal boundary
Hartmut Holzwart, 8 December 2005

asymmetrical c/3 greyship
Hartmut Holzwart, 11 November 2005

long and short c/3 ships w/ central p14 wick,
based on a ship from Jason Summers' raw c/3 collection:
Hartmut Holzwart, 14 Nov 2005

c/3 ship with central p15/5 wick: Hartmut Holzwart, 7 Decenber 2005

perpendicular-to-the-grain greyship with new back slope
Hartmut Holzwart, 29 November 2005

new greyship component shown on right side
Hartmut Holzwart, 29 November 2005

mirror-symmetric against-the-grain greyship with new back slopes
Hartmut Holzwart, 2005-11-30

perpendicular greyship with -1/4 back slope
Hartmut Holzwart, 1 Dec 2005

pentagonal perpendicular greyship with -1/4 back slope
Hartmut Holzwart, 1 Dec 2005

sample greyship-based puffer:
Hartmut Holzwart, 2 Dec 2005

perpendicular greyship with even symmetry --
new back slope, front end from a spacefiller:
Hartmut Holzwart, 5 December 2005

two even-symmetry perpendicular
greyships chained together, with
small tagalongs at back end:
Hartmut Holzwart, 5 December 2005

new perpendicular greyship with central
wick from an old unfinished spacefiller:
Hartmut Holzwart, 6 December 2005

perpendicular greyship with -1/2 back slope
Hartmut Holzwart, 7 December 2005

greyships suggested by Gabriel Nivasch,
with stripes offset by one down the middle:
Hartmut Holzwart, 7 December 2005

Some ideas for a p8 or pure-stable Unit Life Cell

2005-09-20T04:18:00.000-05:00

I've been looking a little bit at rebuilding David Bell's Unit Life Cell using p4/p8 glider and Herschel technology. The point would be to produce a unitcell with a period that's a power of two, to work more efficiently with hashlife/qlife algorithms. The p30 mechanisms in the current unitcell mean that hashlife has to add 15 different phases to its hash table before it has them all (I think). Also, I was wondering if it might not be possible to squash the necessary p8 circuitry into a 256x256 area -- or [much more likely!] into a 256x512 area, which hashlife could handle just about as well. The idea is to optimize the design for simulation by the new hashlife-based player/editor, Golly:

http://golly.sourceforge.net

I think the Life-logic circuitry can be simplified considerably if the neighbor-count chute is modified a bit; in particular, if the stream of gliders that reads the contents of the chute is slowed down to (let's say) p64, then it's possible to check that either the #2 or the #3 neighbor-count glider is the first one out of the chute -- and then suppress the #2 neighbor-count glider with a negated cell-is-ON signal.

With a long-enough gap between gliders, Herschel-based switches can allow just the first glider of a stream to get through, then automatically reset itself afterwards. Here's one such circuit that works at p64:

Okay, now imagine a Unit Life Cell with no moving parts. An infinite grid of OFF unitcells will just sit there; it takes three appropriately-timed gliders from neighboring unitcells to activate a given cell, and then it stays activated only as long as two or three gliders keep coming in to sustain it.

A glider at some critical spot still means the unitcell is ON, and the lack of that glider means that it's OFF.

As in the p8 case, the fanout device is simple to construct with Herschel circuitry -- it could be a standard G->H converter (fairly compact at p8, but not too bad even at p1) followed by a string of glider-producing conduits:

Then the trouble starts. If the unitcell can't have any moving parts, there can't be a "timing gun" in it saying when to look for gliders from neighboring cells. So we have to always produce a "timing" signal at exactly the same time no matter which gliders come in from neighboring cells -- one glider, two gliders, eight gliders.

I have the feeling that I'm not being clever enough, but the best design I can think of at the moment is a string of eight circuits like the following sample pattern, each hooked up to an input glider from a neighboring cell:

Then you also have to actually count the number of signals from neighboring cells. Luckily the above pattern has a spare output glider for each input signal, and these could be collected into a single lane with standard stable reflectors and sent through a counting mechanism. Here's one possibility:

#C ladder from programmable constructor --
#C could be used as a configurable neighbor-counting mechanism
x = 424, y = 465, rule = B3/S23
207bo$207b3o$210bo$191bo17boo$179bo11b3o$177b3o14bo$161bo14bo16boo$
161b3o12boo$164bo$163boo3$164boo$164boo17boo$183boo$$221boo$221boo3$
180boo$180bo19boo$181b3o15bobo$183bo15bo$177boo19boo$177bo$178b3o$180b
o6$186boo$186bo$167boo15bobo$167boo15boo$155boo$154bobo$154bo$153boo$
47bo9bo$47b3o5b3o27bo$37boo11bo3bo30b3o$16bo19bobo10boo3boo32bo14bo$
17bo18bo50boo12b3o$15b3o17boo63bo$100boo$166boo$165bobo$99boo64bo$80b
oo17boo63boo$32boo46boo$bboo28boo$3bo$3o$o$$83boo$63boo19bo$43bo6boo
11bobo15b3o92boo$41b3o6boo13bo15bo94boo$40bo24boo19boo$40boo45bo$84b3o
$84bo$$165boo107bo$166bo19boo86b3o$102boo62bobo17bo90bo$78bo23bobo62b
oo15bobo71bo17boo$78b3o23bo74bo4boo60bo11b3o$81bo22boo72bobo63b3o14bo$
80boo14boo80bobo47bo14bo16boo$96boo69boo10bo48b3o12boo$166bobo62bo$
166bo63boo$165boo$180boo$180bo50boo$181b3o47boo17boo$183bo66boo$$288b
oo$288boo$$97boo$97bobo147boo$99bo147bo19boo$99boo147b3o15bobo$250bo
15bo$244boo19boo$244bo$245b3o$247bo4$87boo$87boo$253boo$253bo$96boo
136boo15bobo$96boo136boo15boo$222boo$221bobo$221bo$220boo$95boo17bo9bo
$95bo18b3o5b3o27bo$91boo3b3o5boo11bo3bo30b3o$91bobo4bo4bobo10boo3boo
32bo14bo$93bo9bo50boo12b3o$62boo29boo7boo63bo$61bobo103boo$61bo4boo
165boo$60boo5bo164bobo$64b3o99boo64bo$64bo82boo17boo63boo$99boo46boo$
69boo28boo$70bo$67b3o$67bo$$150boo$130boo19bo$110bo6boo11bobo15b3o92b
oo$108b3o6boo13bo15bo94boo$107bo24boo19boo$107boo45bo$151b3o$151bo$$
232boo$233bo19boo90boo$169boo62bobo17bo91boo$145bo23bobo62boo15bobo71b
o$145b3o23bo74bo4boo60bo11b3o$148bo22boo72bobo63b3o14bo$147boo14boo80b
obo47bo14bo16boo$163boo69boo10bo48b3o12boo$233bobo62bo$233bo63boo$232b
oo$247boo$247bo50boo$248b3o47boo17boo$250bo66boo$$355boo$355boo$$164b
oo$164bobo147boo$166bo147bo19boo$166boo147b3o15bobo$317bo15bo$311boo
19boo$311bo$312b3o$314bo4$154boo$154boo$320boo$320bo$163boo136boo15bob
o$163boo136boo15boo$289boo$288bobo$288bo$287boo$162boo17bo9bo$162bo18b
3o5b3o27bo$158boo3b3o5boo11bo3bo30b3o$158bobo4bo4bobo10boo3boo32bo14bo
$160bo9bo50boo12b3o$129boo29boo7boo63bo$128bobo103boo$128bo4boo165boo$
127boo5bo164bobo$131b3o99boo64bo$131bo82boo17boo63boo$166boo46boo$136b
oo28boo$137bo$134b3o$134bo$$217boo$197boo19bo$177bo6boo11bobo15b3o92b
oo$175b3o6boo13bo15bo94boo$174bo24boo19boo$174boo45bo$218b3o$218bo$$
299boo107bo$300bo19boo86b3o$236boo62bobo17bo90bo$212bo23bobo62boo15bob
o71bo17boo$212b3o23bo74bo4boo60bo11b3o$215bo22boo72bobo63b3o14bo$214b
oo14boo80bobo47bo14bo16boo$230boo69boo10bo48b3o12boo$300bobo62bo$300bo
63boo$299boo$314boo$314bo50boo$315b3o47boo17boo$317bo66boo$$422boo$
422boo$$231boo$231bobo147boo$233bo147bo19boo$233boo147b3o15bobo$384bo
15bo$378boo19boo$378bo$379b3o$381bo4$221boo$221boo$387boo$387bo$230boo
136boo15bobo$230boo136boo15boo$356boo$355bobo$355bo$354boo$229boo17bo
9bo$229bo18b3o5b3o27bo$225boo3b3o5boo11bo3bo30b3o$225bobo4bo4bobo10boo
3boo32bo14bo$227bo9bo50boo12b3o$196boo29boo7boo63bo$195bobo103boo$195b
o4boo165boo$194boo5bo164bobo$198b3o99boo64bo$198bo82boo17boo63boo$233b
oo46boo$203boo28boo$204bo$201b3o$201bo$$284boo$264boo19bo$244bo6boo11b
obo15b3o92boo$242b3o6boo13bo15bo94boo$241bo24boo19boo$241boo45bo$285b
3o$285bo$$366boo$367bo19boo$303boo62bobo17bo$279bo23bobo62boo15bobo$
279b3o23bo74bo4boo$282bo22boo72bobo$281boo14boo80bobo$297boo69boo10bo$
367bobo$367bo$366boo$381boo$381bo$382b3o$384bo5$298boo$298bobo$300bo$
300boo9$288boo$288boo3$297boo$297boo5$296boo17bo9bo$296bo18b3o5b3o27bo
$292boo3b3o5boo11bo3bo30b3o$292bobo4bo4bobo10boo3boo32bo14bo$294bo9bo
50boo12b3o$263boo29boo7boo63bo$262bobo103boo$262bo4boo$261boo5bo$265b
3o99boo$265bo82boo17boo$300boo46boo$270boo28boo$271bo$268b3o$268bo$$
351boo$331boo19bo$311bo6boo11bobo15b3o$309b3o6boo13bo15bo$308bo24boo
19boo$308boo45bo$352b3o$352bo4$370boo$346bo23bobo$346b3o23bo$349bo22b
oo$348boo14boo$364boo12$365boo$365bobo$367bo$367boo9$355boo$355boo3$
364boo$364boo5$363boo$363bo$359boo3b3o$359bobo4bo$361bo$330boo29boo$
329bobo$329bo4boo$287bo40boo5bo$285b3o44b3o$284bo47bo25boo$284boo53boo
17bobo$269boo67bobo19bo$270bo67bo21boo$270bobo6bo57boo$271boo4bobo3bo$
278boobbobo$282bobo$283bo4boo$271boo15bobo$270bobo17bo65boo$270bo19boo
64bo$269boo86b3o$359bo$294boo$294bo$292bobo$292boo46boo$280boo57bobo$
280boo57bo$338boo7$348boo$268boo78boo$269bo$269bobo83bo$270boo83b3o$
358bo$357boo$337boo$338bo$338bobo$339boo3$353boo$353bobo$355bo$271boo
15boo65boo$271boo15bobo$263boo25bo$264bo25boo$264bobo$265boo$$350boo$
350bo$284bo66b3o$282b3o68bo$281bo$281boo20bo$287bo15b3o$285b3o18bo$
284bo20boo11boo$284boo32boo6$287boo37boo21boo$268boo17boo36bobo21boo$
268boo55bo17boo$324boo17boo$$267boo$268bo76boo$265b3o12boo56boo5boo$
265bo14bo16boo39boo$281b3o14bo$283bo11b3o20boo$295bo22bo$319b3o$321bo!

Because there's a separate output for each possible neighbor count (if the ladder were extended to eight "rungs") it's possible to add eaters to block off outputs corresponding to any standard Bnnn.../Snnn... rule. The remaining outputs would be collected into a single lane with standard stable reflectors, as before -- the ladder would be set up so that there's at most one output glider for any neighbor-count (and either an ON or OFF cell-state signal, which suppresses either the S or B part of the ladder's output signal.)

The size of the ladder means that 512^2 is probably too small to hold the entire stable pattern -- but the next larger power of two, 1024^2, should be plenty big enough. And it should be relatively easy to adjust the period of the cell to a power of two, as well: probably p8192.

David Bell's Unit Life Cell adjusted to 512^2

2005-09-19T20:43:00.000-05:00

There's a new cross-platform open-source Life editor in the works -- and an insurmountable opportunity came up recently in the "golly-test" discussion list. Brice Due had constructed several patterns made up of "unit Life cells", which are large Life logic circuit configurations that mimic the behavior of single Life cells. Thus a single infinite Life universe can support an infinite regress of unitcells simulating unitcells simulating unitcells, at exponentially slower speeds. (See also Jared Prince's "Deep Cell".)

As it turns out, the timing guns in David Bell's original 500x500 Unit Life Cell are a good bit slower than they need to be, so there's still plenty of time for signals to arrive from neighboring 512-size cells, even though they have a little farther to travel. So the biggest headache was resynchronizing a lot of p30 circuitry; stretching each unitcell by 12 cells added multiples of 48 ticks to the glider paths. [If only the magic number had been 515 instead of 512, I would hardly have had to resynchronize anything at all...]

The "circuit diagram" for the original Unit Life Cell is shown at right: the area is 499^2 cells (and you need a one-cell-wide space between adjacent cells).

I didn't include a trail for the reaction for an OFF cell with two neighbors, which makes use of the isolated pentadecathlon at the left -- the #2 neighbor-count glider bounces back and annihilates what would otherwise be the ON output glider generated by the #3 neighbor-count glider. (I think.)

I had to make surprisingly few changes to expand the above to a 511^2 cell -- basically, just a gun and a few reflectors in the lower left corner had to be moved southwest, and then the gun, the counting chute, and all the reflectors leading to it needed to be rephased to match the new timing of the gliders from neighboring cells.

Here's the RLE for a single 511^2 Unit Life Cell.

-- And here's the RLE for a 3x3 test grid representing a blinker, with the Xlife version here.

Coincidentally, I had to switch to RLE in the unitcell #B definition -- it looks like the current version of Xlife can't quite handle picture-format subpatterns at width 512, so my 3x3 grid was getting corrupted. I included the #M prefix in the RLE header, so Achim's Xlife 3.6 should be able to handle the above pattern. I have a private build (3.5.2. going on 3.5.3) that can handle RLE subpatterns with or without the non-standard Xlife-style #M tags, but that change hasn't spread very far yet...

------------------------------------

It wouldn't be an impossibly difficult task to adjust the unitcell period to be a power of 2 as well: after David Bell designed and built the original Unit Life Cell, a p8N glider reflector was discovered, comparable in size to the p30N reflector used in the current unitcell. (Unlike p30, p8 would be compatible with power-of-two step sizes between generations, which would match the way Golly's underlying 'hlife' algorithm works with Life patterns.]

However, so far I am successfully resisting that project: since the fanout device and the glider-to-block converters (and the rest of the neighbor-counting logic) are irrecoverably p30, they'd all have to be replaced with p8 equivalents -- and offhand I don't know of a p8 glider-to-block converter or a small alternate glider reflector equivalent to the two-p30-gun reflector used to get gliders onto the other square color. Easy enough to arrange a new Herschel-based fanout device so no alternate reflectors are needed, though --

Rather than work on a p8-reflector-based version, I'd be tempted to find a pure-stable solution: the advantage would be that any cells that are not ON have no moving parts whatsoever! Which would probably increase the simulation speed, and might also make it easier to see the active cells in a large pattern of unitcells. I think I have all the pieces for a pure-stable Unit Life Cell worked out in my head now (see the next posting)... and they are even easy to reconfigure for any standard rule. Well, any non-B0 rule at least -- otherwise I need a clock gun in each cell.

Sawtooth pattern needs tuneup

2005-08-16T20:20:00.000-05:00

[thumbnail at .5 sub-pixel zoom -- click on image to expand]

attempted sawtooth pattern with incorrect timing --
runs for three cycles and then blows up.
The generations where the line burns out to
create a block are 3648, 9952, 20896, and 39800.
Their remainders modulo 192 are 0, 160, 160, and 56.
The growth in the generation numbers is
approximately a factor of 1.72.

David Bell, 18 July 2005

Adapted from notes by David Bell:

For the sawtooth to be made functional, the remainders of the generation numbers where the line burns out (modulo 192) must either be constant or else oscillate only over a few "safe" values.

The sawtooth can be easily modified by shifting the glider reflectors forwards or backwards along the path and by adjusting when the beehive is turned into the backward glider. But simply bouncing the gliders back using the glider reflectors might not be good enough; it might be necessary to hold onto them until the right generation numbers before releasing them.

Alternative sawtooth mechanism

David Bell, 18 July 2005

Another sawtooth mechanism: a pair of gliders can arrive from the end of the line to cleanly ignite it while sending a glider back to the source direction. Perhaps the timings involved in this alternative mechanism would be easier:

Update: 16 August 2005

another attempted sawtooth with incorrect timing --
runs for about 342,000 ticks and then blows up.
A p1056 gun is attached to a p8 regulator
in place of the original simple reflectors.
Dave Greene, 16 August 2005

Notes by Dave Greene:
I tried replacing the reflectors at the stationary end of the pattern with a p8 universal regulator, and ended up with an almost-sawtooth that works nicely for 342,000 generations -- and then blows up. Apparently my math is still wrong somewhere...

My one useful result was that a line-igniting glider can be delayed by any multiple of 176 generations, and the burning fuse will still arrive at the active site at the same phase of the p192 lineship. [After 192 generations the fuse is longer by 16 cells, so it takes 16 ticks longer to burn. So to keep the burning fuse from arriving late at the active site, you have to subtract 16 ticks from 192].

-- So I attached a p1056 gun (6 x 176) to the universal regulator, and found a configuration that survives for quite a few cycles... apparently by sheer luck, since there's something wrong with the underlying theory. The problem seems to be that the ever-increasing return time of the glider also extends the length of the fuse by a variable amount -- and the fuse burns four times as fast as a glider travels, so it's easy for the feedback effect to result in several possible arrival times. The burning-out reaction is versatile enough to handle any amount of lateness up to 80 ticks or so after the phase used for the first couple of cycles -- but eventually a phase always seems to come along that is off by more than that.

I also tried p880 and p2112 drive guns [I thought I had accounted for the variable fuse lengths with p2112, which is LCM(176,192) -- but no such luck.] It seems possible that delaying one of these drive guns by some number of generations would get the pattern into a stable cycle -- I just haven't figured out how to predict this in advance yet, and brute-force searching is fairly tedious in this case. Anyway, it wouldn't be quite as interesting to get the right answer by accident!

I tried writing equations to predict the length of later cycles, given the glider travel time and fuse burning time and the phase of the burning fuse's arrival at the active site... but so far I've always ended up with wrong answers after a cycle or two. Haven't given up yet, but would be happy if someone else wanted to figure it out!

Perpendicular greyship update

2005-08-12T12:07:00.000-05:00

Update: 22 July 2005 07:22

Hartmut Holzwart has produced some new partial results related to perpendicular greyships -- i.e., spaceships whose central section is made up of alternating lines of ON and OFF cells, and whose direction of travel is perpendicular to these lines. Several completed spaceships of this type are shown in an upcoming weblog posting.

Connection of 1/10 slope to 1/2 slope
Hartmut Holzwart, 14 July 2005

A 1/10-slope edge can be connected to a 1/2-slope edge:

Connection from side of perpendicular 
greyship to 1/4-slope back edge

Hartmut Holzwart, 22 July 2005

Jason Summers' side component can be connected to the 1/4 back edge component; however, Holzwart reports that his attempts to connect the side component to a known front component have not been successful.

Greyship details

2005-07-09T15:48:00.000-05:00

Jul 1:


#C diamond-shaped greyship  Hartmut Holzwart  1 Jul 2005
x = 88, y = 83, rule = B3/S23
50bobo$49bobbo$48boo$47bo3bo$46b3obo$45bo$44b7o$5bobo35bo9boboo$4bobbo
34b12ob3o$3boo36bo16bo$bbo37b17obbo$b4o34bo19boo$o4bo32b23o$obbo33bo
21bo$obbo32b23o$bo33bo25boboo$bb4obo26b28ob3o$3bo3bo25bo32bo$4bo27b33o
bbo$4bobo24bo35boo$30b39o$3b3o23bo37bo$3boo23b39o$3b3o21bo41boboo$26b
44ob3o$4bobo18bo48bo$4bo19b49obbo$3bo3bo15bo51boo$bb4obo14b55o$bo19bo
53bo$obbo16b55o$obbo15bo57boboo$o4bo12b60ob3o$b4o12bo64bo$bbo13b65obbo
$3boo10bo67boo$4bobbobo4b71o$5bobobbobbo69bo$8bo3b71o$9bo75bobo$10b76o
bo$$10b76obo$9bo75bobo$8bo3b71o$5bobobbobbo69bo$4bobbobo4b71o$3boo10bo
67boo$bbo13b65obbo$b4o12bo64bo$o4bo12b60ob3o$obbo15bo57boboo$obbo16b
55o$bo19bo53bo$bb4obo14b55o$3bo3bo15bo51boo$4bo19b49obbo$4bobo18bo48bo
$26b44ob3o$3b3o21bo41boboo$3boo23b39o$3b3o23bo37bo$30b39o$4bobo24bo35b
oo$4bo27b33obbo$3bo3bo25bo32bo$bb4obo26b28ob3o$bo33bo25boboo$obbo32b
23o$obbo33bo21bo$o4bo32b23o$b4o34bo19boo$bbo37b17obbo$3boo36bo16bo$4bo
bbo34b12ob3o$5bobo35bo9boboo$44b7o$45bo$46b3obo$47bo3bo$48boo$49bobbo$
50bobo!

July 2:


#C front and sides for square greyship  Jason Summers 2 Jul 2005
x = 46, y = 63, rule = B3/S23
10bo$$10bo$$10bo4$8bo3bo$8bo3b27o$9bo$10b29o$$10b29o$9bo$8bo3b27o$8bo
3bo$8bo3b27o$9bo$10b29o$$10b29o$9bo$8bo3b27o$8bo3bo$8bo3b27o$9bo$10b
29o$$10b29o$9bo$8bo3b5obobb5obobob5obo$5bobobbobbo4bobobo3boobobbo4bo$
4bobbobo4boo8boo3bo3boo6bobobo$3boo10bobbo5b4o6bobbo$bbo13bobo8bobo5bo
bo$b4o15bo8bo$o4bo14bo8boo$obbo16boobo6b3o$obbo19bo8bo$bo$bb4obo$3bo3b
o$4bo$4bobo$$3b3o$3boo$3b3o$$4bobo$4bo$3bo3bo$bb4obo$bo$obbo$obbo$o4bo
$b4o$bbo$3boo$4bobbo$5bobo!

July 4:


#C 2c/4 45-90-45 triangle greyship  Hartmut Holzwart  4 Jul 2005
x = 100, y = 59, rule = S23/B3
48bobo$47bobbo$46boo$45bo3bo$44b3obo$7bo35bo$4b4o35b6o$4boo35bo9boboo$
bbo38b11ob3o$bb4o33bo16bo$bo37b16obbo$3obbo31bo19boo$b3o33b22o$bbo32bo
21bo$3b3obo27b22o$3bobboo25bo25boboo$4b3o26b27ob3o$6bo24bo32bo$4bo26b
32obbo$4bobo22bo35boo$3bo25b38o$4bobo20bo37bo$4bo22b38o$6bo18bo41boboo
$4b3o18b43ob3o$3bobboo15bo48bo$3b3obo15b48obbo$bbo18bo51boo$b3o17b54o$
3obbo13bo53bo$bo17b54o$bb4o11bo57boboo$bbo14b59ob3o$4boo9bo64bo$4b4obo
5b64obbo$7boobobbo67boo$9boobb70o$10boo69bo$11b70o10b3o3bo$83booboobb
7obbo$9b75o10bobboo$8boo78b3o6boo$7boobb3obb4obb4obb4obb4obb4obb4obb4o
bb4obb4obb4obb4obboobbobbo$6b3obb3obobboobobboobobboobobboobobboobobb
oobobboobobboobobboobobboobobboobobboo$7bobo7bo5bo5bo5bo5bo5bo5bo5bo5b
o5bo5bo5bo7b4o$8b3o80bo3bo$7bobboo79bo$10b3obbo76bobbo$10b3obbo$4boo7b
o$3boob5oboo$4b6ob3obo$5b3o3bobb3oboboo$13booboboo$11bo9boo$9boobbob3o
bobboboo$9bo4bobbobobooboo$9bo3boo5b3obo$10b3o7boo!


#C 45-90-45-triangle greyship with p2 technology except on backslope
#C Hartmut Holzwart  4 Jul 2005
x = 85, y = 74, rule = B3/S23
48bobo$47bobbo$46boo$45bo3bo$44b3obo$7bo35bo$4b4o35b6o$4boo35bo9boboo$
bbo38b11ob3o$bb4o33bo16bo$bo37b16obbo$3obbo31bo19boo$b3o33b22o$bbo32bo
21bo$3b3obo27b22o$3bobboo25bo25boboo$4b3o26b27ob3o$6bo24bo32bo$4bo26b
32obbo$4bobo22bo35boo$3bo25b38o$4bobo20bo37bo$4bo22b38o$6bo18bo41boboo
$4b3o18b43ob3o$3bobboo15bo48bo$3b3obo15b48obbo$bbo18bo51boo$b3o17b54o$
3obbo13bo53bo$bo17b54o$bb4o11bo57boboo$bbo14b59ob3o$4boo9bo64bo$4b4obo
5b64obbo$7boobobbo67boo$9boobb70o$10boo69bo$11b70o$$13b70obo$12boo69b
oo$11boobb4obobob5obobb5obobob5obobb5obobob5obobb5obobob3o$9boobobbo3b
oobobbo4bobobo3boobobbo4bobobo3boobobbo4bobobo3boobobboo$6b4obo5boo3bo
3boo8boo3bo3boo8boo3bo3boo8boo3bo$6boo9b4o6bobbo5b4o6bobbo5b4o6bobbo5b
4o$4bo15bobo5bobo8bobo5bobo8bobo5bobo8bobo$4b4o14bo9bo8bo9bo8bo9bo8bo$
3bo18boo8bo8boo8bo8boo8bo8boo$bb3obbo15b3o6boobo6b3o6boobo6b3o6boobo6b
3o$3b3o19bo9bo8bo9bo8bo9bo8bo$4bo$5b3obo$5bobboo$6b3o$8bo$6bo$6bobo$5b
o$6bobo$6bo$8bo$6b3o$5bobboo$5b3obo$4bo$3b3o$bb3obbo$3bo$4b4o$4bo$6boo
$6b4o$9bo!


#C greyship w/ back at limit slope ~1/4  Hartmut Holzwart  4 Jul 2005
x = 95, y = 120, rule = B3/S23
50bobo$49bobbo$48boo$47bo4bo$46b4obbo$45bo$45b3obobboo$7bo35bo6bobo$4b
4o35b8obbo$4boo35bo10bobo$bbo38b11obbo$bb4o33bo14boboo$bo37b14obobo$3o
bbo31bo16bobo$b3o33b18obo$bbo32bo18boboboo$3b3obo27b19obbo$3bobboo25bo
20boboboo$4b3o26b21obbobo$6bo24bo24boboo$4bo26b24obobo$4bobo22bo26bobo
$3bo25b28obo$4bobo20bo28boboboo$4bo22b29obbo$6bo18bo30boboboo$4b3o18b
31obbobo$3bobboo15bo34boboo$3b3obo15b34obobo$bbo18bo36bobo$b3o17b38obo
$3obbo13bo38boboboo$bo17b39obbo$bb4o11bo40boboboo$bbo14b41obbobo$4boo
9bo44boboo$4b4obo5b44obobo$7boobobbo46bobo$9boobb48obo$10boo48boboboo$
11b49obbo$60boboboo$11b49obbobo$10boo50boboo$9boobb48obobo$7boobobbo
48bobo$4b4obo5b48obo$4boo9bo46boboboo$bbo14b45obbo$bb4o11bo44boboboo$b
o17b43obbobo$3obbo13bo44boboo$b3o17b42obobo$bbo18bo42bobo$3b3obo15b42o
bo$3bobboo15bo40boboboo$4b3o18b39obbo$6bo18bo38boboboo$4bo22b37obbobo$
4bobo20bo38boboo$3bo25b36obobo$4bobo22bo36bobo$4bo26b36obo$6bo24bo34bo
boboo$4b3o26b33obbo$3bobboo25bo32boboboo$3b3obo27b31obbobo$bbo32bo32bo
boo$b3o33b30obobo$3obbo31bo30bobo$bo37b30obo$bb4o33bo28boboboo$bbo38b
27obbo$4boo35bo26boboboo$4b4o35b25obbobo$7bo35bo26boboo$45b24obobo$45b
o24bobo$47b24obo$47bo22boboboo$49b21obbo$49bo20boboboo$51b19obbobo$51b
o20boboo$53b18obobo$53bo18bobo$55b18obo$55bo16boboboo$57b15obbo$57bo
14boboboo$59b13obbobo$59bo14boboo$61b12obobo$61bo12bobo$63b12obo$63bo
10boboboo$65b9obbo$65bo8boboboo$67b7obbobo$67bo8boboo$69b6obobo$69bo6b
obo$71b6obo$71bo4bobobobo$73b3obbo3bo$73bobbo5boo$75bo4boob3obbo$74bo
3bobo3b3obo$74b3o6bobo$72boobo6boobo$71boboboo4boobooboobobo$71bobb3o
5bo4bo$71booboo7b4o3bobbo$73boo10bo4boobo$$91boo$89bo4bo$88bo$88bo5bo$
88b6o!

Jul 5:


#C junctions to construct arbitrary greyship front-edge slopes, 0-90
#C Jason Summers  5 Jul 2005
x = 95, y = 66, rule = B3/S23
9bobo17b30o$8bobbo18bo$7boo22b28o$6bo3bo21bo$5b3obo23b26o$bboo30bo$bo
3b5o25b24o$o3bo31bo$o5boo29b22o$3o3b4o28bo$bo7bo29b20o$boo37bo$bobo23b
obo4bobo4b18o$boobboobo8bobo6bobboboobobbo4bo$bbob3obo3bob4obobo3boo8b
o7b16o$9booboboobbobbobbo4bo6bobboobbo$4b6oboo3b4obob5obo7b4obboobb12o
$5bo4b3o6bo11boo10boobo$6boo5boobboobbob5obo7b4obboobb12o$7bobbo5b4obo
bbo4bo6bobboobbo$8boboboo5bobo3boo8bo7b16o$26bobboboobobbo4bo$27bobo4b
obo4b18o$40bo$39b20o$38bo$37b22o$36bo$35b24o$34bo$33b26o$32bo$31b28o$
30bo$29b30o$26boo$25bo3b30o$24bo3bo$24bo5b29o$24b3o3bo$25bobo4b63o$25b
oobbobbo$23bo3boo4b62o$22boo10bo$23b6o6b60o$24bo4bo6bo$25b3o9b58o$25bo
3bo8bo$27b3o9b56o$27b4o9bo$30bo10b54o$42bo$43b5obobb5obobob5obobb5obob
ob14o$44bo4bobobo3boobobbo4bobobo3boobobbo$45boo8boo3bo3boo8boo3bo3b
12o$46bobbo5b4o6bobbo5b4o6bo$47bobo8bobo5bobo8bobo5b10o$51bo8bo9bo8bo
6bo$51bo8boo8bo8boo6b8o$51boobo6b3o6boobo6b3o5bo$54bo8bo9bo8bo6b6o$90b
o$91b4o$92bo$93boo$94bo!


#C shift a greyship left or right edge in by one stripe
#C Jason Summers  5 Jul 2005
x = 77, y = 55, rule = B3/S23
77o$$77o$$77o$$77o$$56obobob5obobb5obo$56boobobbo4bobobo3boo$bb5obobob
5obobb5obobob3ob3obbooboboboboo3boo3bo3boo8boo$bobo3boobobbo4bobobo3b
oobobboobboobboo3bobbo4booboo6bobbo5b4o$5boo3bo3boo8boo3bo3bo3bo8bobb
3o3bobobo5bobo8bo$5b4o6bobbo5b4o5boobb6obo14bo9bo$8bobo5bobo8bobo3bobo
8bo4b3o7boo8bo$bo8bo9bo8bo3booboobboo7bo3bo6b3o6boobo$bo8boo8bo8boo3b
3o3bo3boboobbo3bo7bo9bo$boobo6b3o6boobo5boo7bobboobo6boobo$4bo8bo9bo5b
o5b3o$27bobo3boo$25b3o4boobo$24boobbo5bo$26bo5bo$24bobo5bobo$24bo6bo$
21b4o7bobo$21boo9bo$19bo14bo4bobo$19b4o9b3o3bobbo$18bo12b3o3boo$17b3o
bbo9boo$18b3o12b8o$19bo14bobo4bo$20b3obo12b3o$20bobboo12bo3bo$21b3o15b
3o$23bo15b4o$21bo20bo$21bobo$20bo$21bobo$21bo$23bo$21b3o$20bobboo$20b
3obo$19bo$18b3o$17b3obbo$18bo$19b4o$19bo$21boo$21b4o$24bo!


#C  Greyship with slope of 5/9  Hartmut Holzwart  5 Jul 2005
x = 140, y = 115, rule = B3/S23
68bo$65b4o$65b3o$63bo3bo$63b3o10boo$61bo5bo7booboo$61b6o6bob5o$59bo10b
obobooboo$59b12oboboo$57bo16boo$57b18o9b4o$55bo19bo7bo4bo$55b20o7bo$
53bo23bobobo6bo$53b27o$51bo42boo$51b32o10b4o$49bo34bo7b5o$49b35o7bo$
47bo38boboo$47b40oboo$45bo44bo11bobbo$45b46o10bo$7bo35bo57bo3bo$4b4o
35b50o8b4o$4boo35bo53bob3o$bbo38b55obobo$bb4o33bo59bo$bo37b61o10boo$3o
bbo31bo71booboo$b3o33b64o6bob5o$bbo32bo68bobobooboo$3b3obo27b70oboboo$
3bobboo25bo74boo$4b3o26b76o9b4o$6bo24bo77bo7bo4bo$4bo26b78o7bo$4bobo
22bo81bobobo6bo$3bo25b85o$4bobo20bo100boo$4bo22b90o10b4o$6bo18bo92bo7b
5o$4b3o18b93o7bo$3bobboo15bo96boboo$3b3obo15b98oboo$bbo18bo102bo11bobb
o$b3o17b104o10bo$3obbo13bo115bo3bo$bo17b108o8b4o$bb4o11bo111bob3o$bbo
14b113obobo$4boo9bo117bo$4b4obo5b119o$7boobobbo$9boobb122o$10boo126bo$
11b128o$$11b128o$10boo126bo$9boobb122o$7boobobbo$4b4obo5b119o$4boo9bo
117bo$bbo14b113obobo$bb4o11bo111bob3o$bo17b108o8b4o$3obbo13bo115bo3bo$
b3o17b104o10bo$bbo18bo102bo11bobbo$3b3obo15b98oboo$3bobboo15bo96boboo$
4b3o18b93o7bo$6bo18bo92bo7b5o$4bo22b90o10b4o$4bobo20bo100boo$3bo25b85o
$4bobo22bo81bobobo6bo$4bo26b78o7bo$6bo24bo77bo7bo4bo$4b3o26b76o9b4o$3b
obboo25bo74boo$3b3obo27b70oboboo$bbo32bo68bobobooboo$b3o33b64o6bob5o$
3obbo31bo71booboo$bo37b61o10boo$bb4o33bo59bo$bbo38b55obobo$4boo35bo53b
ob3o$4b4o35b50o8b4o$7bo35bo57bo3bo$45b46o10bo$45bo44bo11bobbo$47b40ob
oo$47bo38boboo$49b35o7bo$49bo34bo7b5o$51b32o10b4o$51bo42boo$53b27o$53b
o23bobobo6bo$55b20o7bo$55bo19bo7bo4bo$57b18o9b4o$57bo16boo$59b12oboboo
$59bo10bobobooboo$61b6o6bob5o$61bo5bo7booboo$63b3o10boo$63bo3bo$65b3o$
65b4o$68bo!


#C some components for a possible p4 greyship traveling perpendicular
#C  to its stripes, instead of parallel  Jason Summers  5 July 2005
x = 209, y = 93, rule = B3/S23
186b3o3b3o$186bobbobobbo$186bo7bo$186bo7bo$73b3o3b3o5b3o3b3o91bobobobo
$59bo5bo6bobbo3bobbo3bobbo3bobbo6bo5bo77bobobobo$58b3o3b3o5bo3bobo3bo
3bo3bobo3bo5b3o3b3o77bo3bo$43b3o3b3o5bobbooboobbo3bobbobobobo3bo3bobob
obobbo3bobbooboobbo5b3o3b3o61b3ob3o$29bo5bo7bobbobobbo4b3obbobobbobob
5obobbob7obobbob5obobobbobobb3o4bobbobobbo7bo5bo50bo$28b3o3b3o4bo4bobo
3bobbo3bobobobo3bo29bo3bobobobo3bobbo3bobo4bo4b3o3b3o45b9o$13b3o3b3o5b
oobbobobboo3b4obobob10obbob41obobb10obobob4o3boobbobobboo5b3o3b3o29bo
9bo$12bobbo3bobbo3bobbobobobo8bobobo71bobobo8bobobobobbo3bobbo3bobbo
27b13o$12bo3bobo3bo3b4obobobb10ob75ob10obbobob4o3bo3bobo3bo26bo13bo$
11bobbobobobo3bo6bo105bo6bo3bobobobobbo24b17o$10b5obobbob127obobbob5o
22bo17bo$9bo149bo20b21o$9b151o19bo21bo$178b25o$9b151o17bo25bo$176b29o$
9b151o15bo29bo$174b33o$9b151o13bo33bo$172b37o11$8bo3b8o$3bo3b5o8bo$bb
3obbo4b8o$bobboobobboo$boo4bobobb8o$4boobooboo8bo$3b4oboobb8o$oobboobo
3bo$9boob8o$11bo8bo$9bobb8o$9b3o$8bo3b8o$3bo3b5o8bo$bb3obbo4b8o$bobboo
bobboo$boo4bobobb8o$4boobooboo8bo$3b4oboobb8o$oobboobo3bo$9boob8o$11bo
8bo$9bobb8o$9b3o$8bo3b8o$3bo3b5o8bo$bb3obbo4b8o$bobboobobboo$boo4bobo
bb8o$4boobooboo8bo$3b4oboobb8o$oobboobo3bo$9boob8o$11bo8bo$9bobb8o$9b
3o$8bo3b8o$3bo3b5o8bo$bb3obbo4b8o$bobboobobboo$boo4bobobb8o$4boobooboo
8bo19b73o$3b4oboobb8o$oobboobo3bo28b73o$9boob8o$11bo8bo19b73o$9bobb8o$
9b3o28b73o$8bo3b8o$3bo3b5o8bo19b35obob35o$bb3obbo4b8o52bobobobobo$bobb
oobobboo28b27obo15bob27o$boo4bobobb8o44bobobo15bobobo$4boobooboo8bo19b
19obo31bob19o$3b4oboobb8o36bobobo31bobobo$oobboobo3bo28b11obo47bob11o$
9boob8o28bobobo47bobobo$11bo8bo19b3obo63bob3o$9bobb8o20bobobo63bobobo!

A structured pattern for a Caterpillar

2005-06-09T08:20:00.000-05:00

Structured patterns

Something I've been wanting to do for a while now is to produce a structured description of Gabriel Nivasch's Caterpillar.

In the context of the Game of Life, a "structured pattern" would be a description in terms of the smaller subpatterns that are repeated many times in the full pattern, such as the "shish-ke-babs" or the various rakes that make up the Caterpillar. The subpatterns in turn may be composed of smaller sub-subpatterns like pi climbers, blinkers, gliders, etc. A structured format makes a much better "blueprint" of a large pattern than a standard RLE encoding or picture-format file, and it's also very compact -- probably better compression than any standard binary-archive tool could manage.

Xlife 3.5/3.6 provides a good pattern format for describing this kind of structured pattern. Unfortunately it isn't quite versatile enough for this purpose. The big problem is that when you're dealing with periodic subpatterns, you often want to be able to include copies of them at several different phases. Xlife's approach is to define one phase of each periodic pattern as its "base" pattern; to paste multiple copies in, you paste the first base pattern, run the entire universe some number of generations to get the first pattern to the right phase relative to the second; then paste the second base pattern -- and if necessary run N more generations and paste a third base pattern, and so forth.

For stable patterns, or patterns that don't interact too closely, that's fine. But unfortunately this approach doesn't work very well for large numbers of subpatterns or higher periods -- sometimes Xlife's format doesn't support a "natural" compact definition based on subpatterns, because (for example) two of the subpatterns interfere with each other before the correct phase of the third subpattern can be placed to stabilize the whole conglomeration.

Ideas for an extension of Xlife #I format:

First, for reference, here is a summary of current Xlife syntax.

An extension of the format would fix the problem described above -- you'd have to be able to say, "run just this pattern in isolation for N generations, then paste it at (x,y)." This seems like a more natural way to compose patterns from subpatterns.

-- In fact, that's how Xlife's GUI does it! To register subpatterns in a "load script", you specify subpatterns' locations, transformations, and number of ticks forward in time from the base pattern. It's actually quite a surprise to look in an #I-format file for the first time and find out that Xlife has translated your registered subpatterns into this alternate format that is only sometimes equivalent.

I think Eugene Langvagen's PLife project has the necessary versatility to describe this kind of run-N-ticks-then-paste operation, but I haven't done enough benchmarking yet to know whether PLife can handle Caterpillar-sized structured patterns.

The main problem that I see is that a PLife script can easily become much too syntactically complex to be read directly by other Life software. You could create a structured pattern using a PLife script, but you'd have to convert it back to RLE to communicate it to anyone who doesn't have Python and PLife available. Xlife format is much more straightforward to write a parser for.

2c/3 transceiver, large size

2005-06-02T00:34:00.000-05:00

The new 2c/3 receiver accepts diagonal signals from the track and uses a repeatable reaction to convert these signals into output gliders. (In the pattern as shown below, all the output gliders are blocked, but one or more of them could easily be allowed to escape by removing the appropriate eaters.)

This version of the receiver can process signals separated by 2175 or more generations. The incoming signal interacts with a small constellation of still lifes at the receiver end of the 2c/3 track (two blocks and an eater, shown in light green in the picture). With the assistance of a few catalysts, the constellation collapses cleanly into an R-pentomino, which is then guided onto a Herschel track.

The path of the active signal is shown in gray the image below; the direction of travel is indicated by the red arrows. Gliders from the output Herschel (short blue arrows) are used to create two more Herschels; the Herschels are then routed to various Herschel-to-glider converters, which produce five gliders in two salvos (long blue arrows). Four of these gliders collide to rebuild the original constellation. (The first glider just removes an extra block left by the conversion of the receiver's initial output R-pentomino to a Herschel.)

2c/3 signal receiver: Dave Greene, 6 February 2005

2c/3 details

2005-06-02T00:29:00.000-05:00

2c/3 is a respectable speed in the Life universe; by comparison, a glider travels at only one-fourth of the speed of light, and it was proven many years ago that this is the fastest that any finite diagonal spaceship can travel through empty space. There is a similar limit of half of the speed of light for orthogonal spaceships.

However, disturbances in pre-existing structures can travel much faster than these limits -- there is no theoretical limit lower than lightspeed, either diagonally or orthogonally. See Gabriel Nivasch's lightspeed article for details and examples.

A signal in a 2c/3 track will quickly overtake a glider travelling in the same direction. If a sufficiently long track can be made to turn a corner, a 2c/3 signal in it will even overtake an orthogonal c/2 spaceship.

2c/3 transceiver, Mark Minus One

2005-05-29T05:28:00.000-05:00

What follows is the first draft of a Game-of-Life circuit with a new, faster type of signal -- two-thirds of the speed of light diagonally! This is a big improvement in signal speed. Even Jason Summers' light-speed 'telegraph' can theoretically approach only half the speed of light diagonally, and it is considerably more unwieldy even than this pattern, and harder to re-use. Besides the telegraph, the fastest repeatable diagonal signal was a simple glider, at c/4.

Input is a Herschel, output is a glider. For comparison purposes, an extra reference glider has been added near the input Herschel. Despite the horrific and unnecessary inefficiency of the Herchel-to-2c/3 converter, and the fact that the output glider is produced from a 'backward' part of the 2c/3-to-glider converter, the output signal still manages to catch up to the reference glider!

Nothing about this pattern is properly optimized. For example, there's no good reason for the input Herschel ever to travel north; the conduit delivering the sacrificial beehive to the key point of the 2c/3 transmitter is ridiculously long; and the four boojum reflectors had to be moved embarrassingly far to the northwest to get the timings to work out.

The stair-step diagonal Herschel conduit at the left edge of the pattern is an artifact of an old toolkit I put together a year or two ago, which allows a shotgun for a synchronized glider salvo (like the three closely-spaced gliders traveling northeast from this area) to be constructed relatively quickly, though at considerable cost in efficiency. This part of the pattern took me less than an hour to put together, but it should be possible to fit a shotgun that fires twice as quickly into less than half the space.

After some optimization on the transmitter, it will be possible to use this technology to build the world's first period-independent pseudo-Heisenburp device, which can absorb a glider and produce as many output signals as needed -- including a new glider with exactly the same path and timing as the original!

[Previous Heisenburp devices all require the input glider to be aligned to some particular period, or they fail catastrophically. On the other hand, these periodic patterns can be "true" rather than "pseudo" Heisenburp devices: they produce output signals without destroying, or even temporarily affecting, the input glider.]

The 2c/3 signal track was discovered by Dean Hickerson in March 1997; Noam Elkies came up with several ingenious recipes for getting a repeatable signal started in a 2c/3 track, early this year, after I came up with a convoluted way of getting a signal out of a 2c/3 track. Further optimization is no doubt possible at both ends...

Update: May 1, 2007 -- Finally got around to doing the optimization work; the results can be seen in the latest version of the Golly project, Golly 1.2. Run heisenburp.py in the Scripts folder (you need to have Python installed, but it will take you all of maybe five minutes, and it's worth it.)

Glider-proof patterns

2005-02-14T00:35:00.000-05:00

Copied from my postings to newsgroup: comp.theory.cell-automata
Date: 13 Feb 2005
Subject: Re: exist glider gun able of reconstruction in Life?

Ilmari Karonen wrote:

> This line of thought suggests another possibly interesting
>  question:  are there any known patterns that are fully
>  "glider-proof", in the sense that they can withstand a
>  collision with a single glider from any direction and in
>  any phase?

Among existing eater patterns in B3/S23 Life, I think the successful-defense record is still held by the eater2, which can absorb any number of gliders on any of four adjacent paths and emerge undamaged:
#Life 1.05 ..* *.* .** ......* ....*.* .....** ..........* ........*.* .........** ..............* ............*.* .............** . ...............**.* ...............**.*** .....................* ...............**.*** ................*.* ................*.* .................*
-- For many stable patterns, by the way, there are other input glider lanes where the gliders are caught and turned into boats, which are then cleanly deleted by another glider coming in on the same lane. I'm not sure how to count those, though; if another glider then comes in on a different "glider-proof" lane, a boat would sometimes get in the way and cause an explosion.

So I suppose that's a different metric: any object will have a glider-pair-invulnerability percentage (!) higher or equal to the single-glider-invulnerability percentage. (Percentages could be calculated from the number of input glider lanes that allow a complete recovery, divided by the total number of input lanes that affect the object in any way.)

There's a double-sided version of the eater2 which I thought at first would have the highest known glider-invulnerability. By the above metric, if my quick counts are right, the double-sided eater2 is exactly 10% single-glider-proof, and 12.5% glider-pair-proof -- whereas the single-sided eater2 above is only 6% glider-proof -- 1/17 of the lanes are safe.

By comparison, a double-ended fishhook eater has a rating of 1/28 (3.6%) and a standard eater is down around 1/52 -- though the slow-glider-pair-proof ratings go up to 1/14 and 3/52, respectively...

However, it appears that one can string together double-sided eater2 patterns and increase the percentage rating indefinitely: each new eater2 added to the chain means that 18 more glider lanes will affect the object, of which 8 lanes are safe. So the glider-proof rating of these eater2 chains asymptotically approaches 4/9. Here's a 22% glider-proof eater2 chain, for example:
#Life 1.05 ........................** .........................* ....................**.* ....................**.** . ....................**.** ...............**.*..*.** ...............**.** . ...............**.** ................*.** ...........**.* ...........**.** . ...........**.** ......**.*..*.** ......**.** . ......**.** .......*.** ..**.* ..**.** . ..**.** *..*.** **
It takes one or two more eater2s to reach 25% (depending on whether glider-pair invulnerability is good enough) and further improvement gets slower and slower.

So it looks like maybe the first challenge would be to find something that breaks the 50% barrier. There might possibly be some clever way of getting those absorbing blocks one step closer together, but it doesn't look too likely to me...

-----------------------------

One more related topic:

Ilmari Karonen wrote:

>...  There are known CA's with indestructible patterns, but I'd be
>  surprised if Life had any.  However, the weaker condition of
>  "glider-proofness" doesn't intuitively seem quite as impossible
>  to me.

There's an even weaker form of the question which has the virtue of having a positive answer: it is technically possible to build an eater (of sorts) that can safely handle a wider "glider highway" than the eater2's four adjacent lanes. In fact, it can be shown that any given width of highway can be made single-glider-proof with a stable pattern -- or even multiple-glider-proof, as long as there's enough space between the gliders.

Last March I cobbled together a miscellaneous collection of stable Herschel conduits into a pattern that I called a "highway robber": it can absorb a glider coming in on one particular path -- let's call it "lane 0" -- and recover its initial configuration (very slowly!). It can also send out one or more output gliders to signal a capture from the highway. But in this case the important thing is that it allows gliders on adjacent lanes 1, 2, 3, ... of the highway to pass by
unharmed.

[Conventional small eaters based on boats or tub-with-tails (tubs-with-tail?) can almost manage this last trick --
#C 7x9 boat-based eater .....* ......* ....*** . . **...* *...*.* .*...** ..* *.***** **....* ...*** **.* *.*

-- they can absorb a glider on lane 0 and leave lanes 2, 3, 4 ... unaffected. As it happens, they also usually work on gliders coming in at 90 degrees from lane 0, that strike the eater at the same point. But they reliably blow up if a glider comes in on lane 1.]

A row of highway robbers watching adjacent lanes of a glider highway can absorb any slow glider salvo traveling along that highway. And setting several highway robbers to watch the same lane could reduce the minimum time between gliders by quite a bit.

But guarding a wide highway this way is hideously expensive -- the current highway-robber pattern is close to 400x400, though it could be made a good bit smaller. And it can only watch for gliders coming from one direction, of course -- if gliders can travel in both directions on the highway, you have to double the number of robbers so they can watch each others' backs.

Basically, every glider lane that you have to guard with this method just makes a pattern that much bigger and adds more unguarded lanes somewhere else. Figuring out how to build a complete glider-proof perimeter is very much an unsolved problem.

-------------------------------

So to return briefly to the original question: my instinct is that a stable pattern will never be 100% glider-proof -- there are too many possible lanes of attack -- and that even with an active pattern, it's going to be very hard to avoid having an Achilles' heel somewhere, at least during the detect-and-repair process. But it might at least be possible to design an active defense system with a reasonably high probability (above 99.99%, let's say) of recovering from a single random glider impact.

-- Just don't throw any orthogonal spaceships at it, or all bets are off!

HTML version of Oscichem articles

2004-09-14T12:20:00.000-05:00

Testing the email-to-blogger function:

Here are links to Nicolay Beluchenko's Oscichem articles, in HTML format, with Paul Callahan's Java applet displaying the associated Life patterns:

Oscichem #1
OsciChem #2

[Update: Have only completed editing on two out of three so far. Waiting for Nicolay's approval of the third article -- see text draft of OsciChem #3.]

Glue's slow-salvo block-move table

2004-09-11T08:13:00.000-05:00

-- Starting out this weblog with a small experiment. I'm posting a few intermediate results from Paul Chapman's 'Glue' project, which involves a recursive enumeration of still lifes and constellations that can be produced from a single block in B3/S23 Life by a salvo of slow gliders.

[In the unlikely event that most of this terminology is still unfamiliar to you, but you're still interested for some reason: a salvo is a fleet of gliders all traveling in the same direction; a slow glider salvo is one in which the phase and spacing of the incoming gliders doesn't matter, as long as they are sufficiently far apart. For definitions of those terms, see Stephen Silver's Life Lexicon.]

Here is a table of the number of gliders needed to move a block by a given X, Y distance:

The actual recipes can be found here, in an only slightly mysterious format.

Update 2005-12-28: A new version of Glue is currently in progress, which allows for p2 intermediate patterns as well as stable patterns to be considered. Will post more data when it's available...