Re: Building a reverse caber-tosser
We're exactly 11 times more efficient than the MIT group's bound of 385.
Forums for Conway's Game of Life
Not to worry -- it's not just you, it really is getting painfully confusing! Now is probably a good time for a fresh summary of how to get to a pulsar (or any other constructible object) with these 35 ultra-clever gliders.danny wrote:Wait I'm confused. How does this turn into synthesize a pulsar? Wouldn't there be a heckton of ash at the end? I'm sorry if I'm misunderstanding the thread's contents or anything, I just have lots of questions...
Ooops. Here is the 35 glider synthesis:calcyman wrote:Can you please provide the pattern at generation 0 instead of 5000? Thank you!
Code: Select all
x = 5383, y = 5268, rule = B3/S23 120bo$121b2o$120b2o2$5377bobo$5377b2o$5378bo80$2806bo$2805bo$2805b3o 25$288bo$289b2o$288b2o2$2783bobo$2783b2o$2784bo39$172bo$173b2o$172b2o 206$227bobo$228b2o$228bo21$248bo$249b2o$248b2o2$3123bobo$3123b2o$3124b o11$238bo$239b2o$238b2o1949$123bo$124b2o$123b2o18$2652bobo$2652b2o$ 154bo2498bo$155bo$153b3o39$185bo$183bobo$184b2o17$2714bo$2713bo$2713b 3o$214bo$215b2o$214b2o5$2198bobo$2199b2o$2199bo96$2752bo$2751bo$2751b 3o67$2786b2o$2786bobo$2786bo36$176bo$176b2o$175bobo$2676b2o$2676bobo$ 2676bo18$145b3o$147bo$146bo593$3126b2o$3126bobo$3126bo10$242bo$242b2o$ 241bobo$3124b2o$3124bobo$3124bo1585$150b2o$149bobo$151bo61$211bo$211b 2o$210bobo10$2201b3o$2203bo$2202bo$4697b2o$4697bobo$4697bo25$2179b2o$ 2180b2o$2179bo67$2749b2o$2748b2o$2750bo$253bo$253b2o$252bobo25$2771b2o $2771bobo$2771bo25$3o$2bo$bo158$5380b2o$5380bobo$5380bo!
I was working on my own explanation to this but instead I will go carefully through dvgrn's explanation and see if I can add anything to it.danny wrote: Wait I'm confused. How does this turn into synthesize a pulsar? Wouldn't there be a heckton of ash at the end? I'm sorry if I'm misunderstanding the thread's contents or anything, I just have lots of questions...
I'm glad you did this. I tried for a while but then saw you had already done a better job.dvgrn wrote: Not to worry -- it's not just you, it really is getting painfully confusing! Now is probably a good time for a fresh summary of how to get to a pulsar (or any other constructible object) with these 35 ultra-clever gliders.
I'm hoping I can get close, but someone may need to supply a few corrections.
The triggering of PCSC#1 is something I have a comment on. We would rather not trigger it with a glider from the crystal because it would leave behind a mass of half-honeyfarms that would be difficult to clean. Instead of this it would be better to always leave the crystal in a fully destroyed state. After the last glider has been sent to clear up the last piece of the crystal we could crash the Sakapuffer into a block like this and use the NE glider as the trigger for PCSC#1:dvgrn wrote: Step 8: Now it's time to build Painfully Complicated Seed Constellations #1 and #2. When PCSC#1 is triggered, it will produce several Corderships traveling along the various ash tracks in various directions, cleaning up some part of them, or let's just say all of them (I think that will be doable now)... and then crashing into the messy junk at the various GPSE and Sakapuffer construction locations without releasing any additional gliders -- except for one or two heading back toward PCSC#2.
Code: Select all
x = 716, y = 639, rule = B3/S23 99bo$88b2o8bobo$88b2o8b2o6$107bo$96b2o8bobo$96b2o8b2o6$115bo$104b2o8bo bo$104b2o8b2o6$123bo$112b2o8bobo$112b2o8b2o6$131bo$120b2o8bobo$120b2o 8b2o6$139bo$128b2o8bobo$128b2o8b2o6$147bo$136b2o8bobo$136b2o8b2o6$155b o$144b2o8bobo$144b2o8b2o6$163bo$152b2o8bobo$152b2o8b2o6$171bo$160b2o8b obo$160b2o8b2o4$196b3o$205bo3b2o$179bo23b2ob5o$168b2o8bobo22b2o3bo$ 168b2o8b2o20b2o$199bobob4o$199bo3bo3bo$184bobo20b3o$208b2o$183bo17bo2b 2o11b2o$188bo10b2obob2o11b2o$176b2o7b2obo10bo$176b2o9bo12b4o$201bo4$ 217b2o$216b2o4b3o$184b2o31b2o$184b2o32b3o$219bobo$219bo2bo$222bo$220bo bo$220b3o2$192b2o$192b2o2$219b2o$218bo2bo$206b2o2b3o5b2o$206bobo10b5o$ 206bob2o13b2o$202b2ob2obo11b2o2b2o$201b2o2bo14bo2b2o$205b2o14b3o$222bo 6$202b2o12bo$201b2o13bo$201b3o11bo$209bo6b2obo$203bob2obobo5b2ob2o$ 203bo2bo2bo7bobo$203bobo59$298b2o$298b2o18$271b3o$271bo$272bo88$354b2o $354b2o310$154b2o$153bobo$155bo25$125b2o$2o122bobo$b2o123bo587b2o$o 712b2o$715bo!
Code: Select all
import golly as g n = 64 * int(g.getstring("Enter steps to lengthen or shorten by:")) x, y, w, h = g.getrect() g.select([x, y, w // 4, h]) cells = g.getcells(g.getselrect()) g.clear(0) g.putcells(cells, -n, 0) g.select([x + w - w // 4, y, w // 4, h]) cells = g.getcells(g.getselrect()) g.clear(0) g.putcells(cells, n, 0) g.select([x - n, y, w + 2 * n, h // 4]) cells = g.getcells(g.getselrect()) g.clear(0) g.putcells(cells, 0, -n) g.select([x - n, y + h - h // 4, w + 2 * n, h // 4]) cells = g.getcells(g.getselrect()) g.clear(0) g.putcells(cells, 0, n) g.select() g.fit()
Could you give a link to Elkies' outline?calcyman wrote:If we manage to produce a proof (following Elkies' outline) that every still-life is glider-constructible, then we're left with a finite amount of work to show that every still-life can be constructed in <= 1 glider per cell.
Yes, although apparently it was Mark Niemiec rather than Noam Elkies:Macbi wrote:Could you give a link to Elkies' outline?calcyman wrote:If we manage to produce a proof (following Elkies' outline) that every still-life is glider-constructible, then we're left with a finite amount of work to show that every still-life can be constructed in <= 1 glider per cell.
On 10th August 1994, Mark Niemiec wrote: Mainly to Harold:
Thanks for the papers on de Bruijn diagrams. Now, a lot of stuff
(at least the basic ideas) are starting to make a little bit of sense.
I am currently working on a related task, attempting to prove that
every still-life (finite or infinite) may be cut along an arbitary
horizontal boundary and everything below the line replaced by a small
finite stabilizer. If this can be proven rigorously (and I believe that it
can), we can prove that all infinite still-lifes can be made finite.
This is done by dividing up the universe into regions
where 'a' is the interior of the still-life, is already stable, and has no
effect on the exterior.
'b' is just below the surface, is already stable, and influences row 'c',
'c' is at the surface, and may require stabilization from external row 'd',
'd' consists of cells 'outside' the still-life which we need to add to
stabilize row 'c',
and 'e' consists of anything else we need to stabilize 'd'.
By definition, for every still-life which is cut in this way, for every
'b' and 'c' in that still-life, there must exist at least one sequence 'd'
the row which occurs just below 'c' if the still-life is not cut).
The idea is to prove that for every possible sequence of 'b' and 'c', some
arbitrary 'd' can be chosen which stabilizes 'c', and is also itself
stabilizable by some arbitary 'e'.
The proof is somewhat similar to examining every edge in a de Bruijn
diagram of a (4,2) automata (the states 0,1,2,3 correspond to no cells,
'b' cell, 'c' cell, and 'b+c' cells being on in any specific column.) to
ensure that such edges preserve the 'c' cell. Wherever this is not
possible, any path leading through that edge must be re-routed through
a parallel edge connecting altered versions of the initial states.
We may replace states 0-3 by new states 4-7 as required (like 0-3
but with an additional 'd' cell.). Since 'd' cells may not always be
placed with impunity, finding optimal alternate paths requires some
trial and error.
So far, I have expanded a fair bit of the tree, and it seems like a
quite possible (although fairly tedious task.) I'lll mail the results
when (if?) I get finished.
A slightly more ambitius task which requires the above as a pre-requisite is
to define all such states at the exterior of a partially-constructed
and find all mappings between such states and the corresponding states
in which one more cell is added to the interior:
bbccc -> bbbcc
If cell E is the same as cell D, no translation is needed;
if they differ, a glider construction is required which flips
the state of the single bit (and possibly alters other bits
in 'e'); this will, of course, have no effect on the already-
constructed parts of the still-life 'a', 'b', and 'c'; only
'd' needs to be taken care of by taking care how 'e' is altered.
In the majority of cases in which 'e' is empty, this is not
likely to be a problem. However, if the local area of 'e'
contains a convoluted stabilizer, mucking with an inner cell
could be quite a problem. (On the other hand, such convoluted
stabilizers are usually forced by one obnoxious cell; if
that cell is the one which needs to be flipped, most of
the stabilizer could be removed as well.)
If every such state-transition can be provided with a glider
synthesis, we will have a proof that every still-life can be
constructed from gliders, one bit at a time.
(But don't hold your breath; this could involve thousands of
cases, and even though Dave Buckingham is the best person to
generate the syntheses, I am sure he is not enough of a
masochist to try to find them all!) Perhaps some kind of
automated search will be required here.
Has anyone else researched this area? (or determined that it is
either too trivial or intractible to bother?)
I've just realised that this implies the existence of a 143-cell sawtooth. The smallest explicitly-constructed sawtooth has 177 cells, by comparison.chris_c wrote:Excellent. Thanks for finding that and for clarifying those other issues. The 35 glider synthesis was pretty easy to obtain from the 43 glider version. Just 6 GPSE's now and the minimum population is 143 after 5000 generations:
Seems like it would be a fairly complicated implication, though. Just the fact that a 143-cell pattern eventually constructs, let's say, a 177-cell sawtooth pattern, doesn't mean that the 143-cell pattern actually exhibits sawtooth-ish behavior starting from T=0. It will start acting like a sawtooth after umpteen bajillion ticks, but I'm not sure that counts.calcyman wrote:I've just realised that this implies the existence of a 143-cell sawtooth. The smallest explicitly-constructed sawtooth has 177 cells, by comparison.
It synthesises those 35 gliders, except with greater separation, such that there's a new NOP on the end of the tape each time.dvgrn wrote:Seems like it would be a fairly complicated implication, though. Just the fact that a 143-cell pattern eventually constructs, let's say, a 177-cell sawtooth pattern, doesn't mean that the 143-cell pattern actually exhibits sawtooth-ish behavior starting from T=0. It will start acting like a sawtooth after umpteen bajillion ticks, but I'm not sure that counts.calcyman wrote:I've just realised that this implies the existence of a 143-cell sawtooth. The smallest explicitly-constructed sawtooth has 177 cells, by comparison.
Don't we have predecessors of sawtooth 177 that have fewer than 177 cells, for example (e.g., put a block instead of a boat in the boat-bit positions, and then take a cell out of all the blocks)?
To be a proper sawtooth, doesn't it have to return to 143 cells at ever-increasing intervals? How would that work in an RCT context, exactly?
-- Yeah, that works. Only with a "complex RCT" BABC design, though -- you can't get away with just building a glider synthesis for a sawtooth (which could be a "simple RCT" design), you have to store all the ABC bits from the tape, then have a little subroutine that adds the right additional NOP bits to the B stage.calcyman wrote:It synthesises those 35 gliders, except with greater separation, such that there's a new NOP on the end of the tape each time.dvgrn wrote:To be a proper sawtooth, doesn't it have to return to 143 cells at ever-increasing intervals? How would that work in an RCT context, exactly?
I might start work on converting chris_c's 35-glider synthesis into an equivalent single-glider seed, in a quincunx* shape with seeds in the NW, NE, SW and SE and a single 4-way splitter in the middle. Then, the four 'arms' can be uniformly lengthened to change the value stored in the recipe. This is trivial (compared with anything else we've been discussing) but a good starting point because it's easier to manipulate a p1 seed than 35 live gliders.dvgrn wrote:-- Ouch, this stuff still hurts to think about... maybe mostly because I really like to be able to build working examples of things, and even the simplest "simple RCT" design is just hopeless.
Yup, it's almost as handy as "boustrophedonic", which also hails from the early 17th century. One gets the sense that the English were coming up with all kinds of random abstract ideas around that time, and discovering that they hadn't taken enough French words from the Normans to account for them all... so went on a mostly Latin and Greek borrowing spree to fill in the various gaps.calcyman wrote:quincunx*
* it's so useful this word exists for the 5-spot configuration on the face of a die or domino.
Code: Select all
x = 418, y = 345, rule = LifeHistory 265.2B$265.3B$265.4B$266.4B$267.4B$268.4B$265.B3.4B$265.2B3.4B$265.3B 3.4B$265.4B3.4B$266.4B3.4B$267.4B3.4B$268.4B3.4B$269.4B3.4B$270.4B3. 4B$271.4B3.BABA$272.4B3.B2AB$273.4B3.A3B$274.4B3.4B35.2C$275.4B3.4B 34.2C$276.4B3.4B$277.4B3.4B$278.4B3.4B$279.4B3.4B$280.4B3.4B$281.4B3. 4B$282.4B3.4B$283.4B3.4B$284.4B3.4B$285.4B3.4B$286.4B3.4B$287.4B3.4B$ 288.4B3.4B$289.4B3.4B$290.4B3.4B$291.4B3.4B$292.4B3.4B$293.4B3.4B$ 294.4B3.4B$295.4B3.4B$296.4B3.4B$297.4B3.4B18.2A$298.4B3.4B17.2A16.2A $299.4B3.4B12.2D20.2A$300.4B3.4B12.2D$301.4B3.4B10.D$302.4B3.4B$303. 4B3.BABA6.2AB$304.4B3.B2AB4.B2A2B$305.4B3.A3B3.5B.2B$306.4B3.4B2.9B$ 307.4B3.4B.12B$308.4B3.17B7.2A$309.4B3.17B6.2A$310.4B2.16B$311.19B$ 311.19B5.2A$310.16B2A4B3.2A$310.16B2A6B26.2A$311.23B26.2A$312.23B$ 313.22B19.2A$313.22B19.2A$316.20B$316.20B$317.19B14.2A$317.21B.5B6.2A 16.2A$318.18B2A8B22.2A$318.17BA2BA9B$319.17B2A11B$320.30B$321.11BA18B $322.9BABA18B$323.8BABA19B$324.8BA21B$325.30B$326.19B2A9B7.2A$327.17B A2BA8B7.2A$329.16B2A8B$329.4B.19B$330.3B2.6BA11B5.3B$331.B4.4BABA14B. 3B$336.4BABA18B23.2A$338.3BA17B25.2A$341.19B$344.11B2A3B18.2A$344.10B A2BAB19.2A$345.10B2A4B$346.15B$347.B.2BA9B13.2A$349.BABA9B12.2A16.2A$ 350.ABA9B30.2A$350.BA12B2$364.2A$364.2A5$387.2A$387.2A2$230.2A$231.2A 150.2A$230.A152.2A$408.2A$408.2A2$402.2A$380.2A20.2A$380.2A2$210.2A 186.2A$211.2A185.2A16.2A$210.A205.2A3$388.2A$388.2A5$411.2A$411.2A3$ 407.2A$407.2A5$404.2A$404.2A7$412.2A$412.2A13$201.A$201.2A$200.A.A4$ 167.A$167.2A$166.A.A12$191.A$191.2A$190.A.A8$147.2A$148.2A$147.A8$ 127.2A$128.2A$127.A22$141.2A$142.2A$141.A17$118.A$118.2A$117.A.A4$84. A$84.2A$83.A.A12$108.A$108.2A$107.A.A8$64.2A$65.2A$64.A8$44.2A$45.2A$ 44.A22$58.2A$59.2A$58.A17$35.A$35.2A$34.A.A4$.A$.2A$A.A12$25.A$25.2A$ 24.A.A!
Code: Select all
x = 442, y = 135, rule = LifeHistory 27$46.A119.A119.A119.A$45.A.A117.A.A117.A.A117.A.A$45.A.A117.A.A117.A .A117.A.A$46.A119.A119.A119.A2$41.2A7.2A109.2A7.2A109.2A7.2A109.2A7. 2A$40.A2.A5.A2.A107.A2.A5.A2.A107.A2.A5.A2.A107.A2.A5.A2.A$41.2A7.2A 102.2A5.2A7.2A102.2A5.2A7.2A101.2A6.2A7.2A$35.2A116.A.A117.A.A116.A.A $34.A.A9.A108.A10.A108.A10.A107.A11.A$36.A8.A.A117.A.A117.A.A117.A.A$ 45.A.A117.A.A117.A.A117.A.A$46.A119.A119.A119.A$148.2A118.2A$147.A.A 117.A.A$149.A119.A3$29.2A8.2A$28.A.A7.A.A101.2A$30.A9.A100.A.A$143.A 118.2A$261.A.A$263.A8$20.2A$19.A.A231.2A$21.A230.A.A$254.A4$374.2A$ 373.A.A$375.A4$129.2A$128.A.A$130.A17$339.2A$338.A.A$340.A10$341.2A$ 340.A.A$342.A!
This seems good as a proof, but not so good for making estimates of how many bits will have to be stored in the Sakapuffer position, to complete a construction-with-cleanup along the lines of the 35-glider knightship.calcyman wrote:I don't believe anyone finished off the proof that we can convert monochromatic monophase gliders into arbitrary slow-salvos. Fortunately, we can. Firstly, use the following technique to move a block as far away as necessary... and then coax it into a honeyfarm of the correct parity* to use Chris Cain's 4-glider recipes from the HBK project...
In an email, calcyman wrote:... we don't need a BABC design or sliding-block memory or similar in order to get a record-breaking knightship: we just make the cleanup salvos leave a block at the back of each of the four diagonal arms, and then slow-salvo-manipulate these into the four (fixed!) tips of the quincunx seed.
x = 195, y = 330, rule = B3/S23
x = 35, y = 42, rule = B3/S23
In the current state, if I am not mistaken, there are 6 glider streams from GPSEs:dvgrn wrote:The salvo heading southeast isn't exactly a slow salvo, since the gliders heading northeast depend on their exact timing.
There are two separate ideas of using that reaction:dvgrn wrote:I'm not entirely sure I'm understanding the suggestion correctly, though.