Miscellaneous topics in Conway's Game of Life -- unfinished projects of all kinds and conditions

20 September 2005

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

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.

19 September 2005

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

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...]

Unit Life Cell diagramThe "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.