The Past and Future of CGOL

[bubblegum]

The problem I ran into was that when I wanted spaceships to make cameo appearances in the correct decade of the timeline, I had to reserve a lot of empty lanes stretching all the way back to T=0

Can't you just set a time to paste in the ship?

Yes, definitely, but the RLE won't reflect these changes. Of course it doesn't really matter generally if it's a LifeViewer script, but I'm not dvgrn.

Also, I'm not dvgrn.

...
Sir Robin is 282 bits. The top of our current game for glider synthesis is something like 70P2H1V0.1. We have a hard time even getting started on anything bigger than 70 bits, partly because the search programs we use to find workable predecessors tend to get exponentially slower with linear increases in the number of bits being searched.
...

Yikes! What are these algorithms behind those programs? I don't particularly care for glider synthesis, but exponential time seems kind of ridiculous to my intuition for CGOL, something so... deterministic.

oh dear

Also, would the advancement of software used to look for patterns be worth a mention on the timeline? I know that GoldenRatio mentioned soup searching programs, but what about others that find ships, oscillators, synthesis etc?

Possibly, if nobody objects to it, I think maybe they could be slotted in with the respective eras of the patterns they discover.

...
However, the omniperiodicity problem is one of the oldest remaining unsolved Holy Grails of the Game of Life, so even if we just get p19+ oscillators out of a signal wire, that will generate plenty of excitement all by itself.
...

I second this.

Thirded.

Of course, there are the Freywa-y types of people but I'm hoping the Lifenthusiasts (how many e's are in this word) that will get excited about a p19+ signal wire loop outnumber the ones that won't.

[dvgrn]

The problem I ran into was that when I wanted spaceships to make cameo appearances in the correct decade of the timeline, I had to reserve a lot of empty lanes stretching all the way back to T=0

Can't you just set a time to paste in the ship?

When I started the project, LifeViewer's PASTET wasn't a thing yet. But anyway using PASTET would have permanently limited the pattern to being run only in LifeViewer animations, and I kind of wanted the timeline to be explorable in Golly as well.

Yikes! What are these algorithms behind those programs? I don't particularly care for glider synthesis, but exponential time seems kind of ridiculous to my intuition for CGOL, something so... deterministic.

Well, lifesrc/WLS/JLS, and LLS and ikpx and other SAT-solver-based searches, all basically share the unavoidable problem that every time you add one single unknown bit to your search area, you double the number of patterns that can theoretically be placed in that area.

The lifesrc family has a clever set of shortcuts to quickly rule out large subsets of those patterns, and LLS outsources its cleverness to the various SAT solvers and ends up with a somewhat different/similar (delete whichever is inapplicable) set of shortcuts. But in the end, the increase in the number of possibilities is still an exponential function, not a linear one. And that's the cause of the huge underlying problem with the idea of aiming for a Sir Robin synthesis, without first proving out a workable method on spaceships that are a third or a half of Sir Robin's size.

Also, would the advancement of software used to look for patterns be worth a mention on the timeline? I know that GoldenRatio mentioned soup searching programs, but what about others that find ships, oscillators, synthesis etc?

The appearance of searchers based on SAT solvers (LLS, ikpx) definitely seems like the beginning of a new Age. Not only was this development responsible for finding Sir Robin, but in the OCA realm it made possible the discovery of really weird and wonderful spaceships with various unlikely properties, which show up primarily on Discord these days:

Code: Select all

x = 27, y = 23, rule = B2c3-cikn4-eijn5-akn6ein7c8/S01e2ei3-cen4-iqy5iknqr6ai7c8
2b24o$2b24o$2b4o2b18o$2b4obob17o$2b4ob2ob16o$2b4obob17o$2b4o2b18o$2b
24o$2b24o$ob6o2b17o$b6obob17o$b5ob2ob17o$b6obob17o$b7o2b17o$b26o$b26o$
b21o2b3o$b20obob3o$b19o4b3o$b20obob3o$b21o2b3o$b26o$b26o!
#C [[ AUTOSTART ZOOM 14 GPS 14 TRACK 3/49 0 ]]

Code: Select all

x = 9, y = 9, rule = B2ae3-acir4-aejqw5-acer6-k78/S02e3-aiq4eirz5-ejk6an
obobobobo2$o7bo2$o3b2o2bo2$o7bo2$obobobobo!
#C [[ AUTOSTART ZOOM 10 GPS 10 TRACK 1/10 0 ]]

Code: Select all

x = 11, y = 9, rule = B2cik3-cikn4ackqty5ejknq6-kn8/S012eik3-aik4-enwy5ajq6acn7
11o$o9bo$o9bo$o3bo5bo$o2bo6bo$o3bo5bo$o9bo$o9bo$11o!

Code: Select all

x = 11, y = 13, rule = B1e2cek3eqy4ejrz5ain6ce7e/S12-c3-aiky4jkw5acr6eik7e
3o$o$o$3o5$3o3bob3o$o5bobo$o4bo2b3o$o3bo5bo$3obo3b3o!

Code: Select all

x = 7, y = 21, rule = B2-ck3cenqy4ceiktz5air6ack7e8/S02eik3ckry4-iw5-enqy6i78
4bo$4b2o$7o$4b2o$4bo10$o$bo$2bo3bo$3bob2o$4b3o$3b4o$2b5o!

Code: Select all

x = 5, y = 4, rule = B3/S23-ijn4a
o2bo$4bo$o3bo$b4o!

Code: Select all

x = 7, y = 7, rule = B2k3-ery4ijkqwy5jr6-ae8/S01e2ck3-cjn4-aqr5-jkny6-an
3bob2o$b3ob2o$o$b3ob2o$3bobo$3bobo$4bo!

[wwei23]

Not only was this development responsible for finding Sir Robin, but in the OCA realm it made possible the discovery of really weird and wonderful spaceships with various unlikely properties, which show up primarily on Discord these days:

Can you show me the rest of the ships?

[dvgrn]

Can you show me the rest of the ships?

I've put in a bid for someone to make a good collection of the most amusing and/or impressive ones. There are many hundreds of them by now, scattered all over the #naturalistic channel on the Discord ConwayLife Lounge. Another example is a period "9" spaceship:

Code: Select all

#C https://discord.com/channels/357922255553953794/370571046971244545/755815337651470346
x = 3, y = 5, rule = B3aeikr4ejkqwyz5-cy6ekn7c8/S2ek3-ack4iknqtw5ijnqy6ain7c
3o$obo$3o$2bo$3o!

Other periods are similarly represented, farther back in the same channel.

Hundreds of "novelty oscillators" are also worth making a collection of -- everything from smiley faces to checkerboards to blobs and boxes and yet more eater2s and so on, all doing things you wouldn't expect them to be capable of.

[MathAndCode]

Yikes! What are these algorithms behind those programs? I don't particularly care for glider synthesis, but exponential time seems kind of ridiculous to my intuition for CGOL, something so... deterministic.

I agree. The program should be able to divide the spaceship into different regions and go one region at a time, especially with such an elongated spaceship. It might look exponential for small spaceships that aren't large enough to be divided into different regions, but it should eventually go down to linear or at most quadratic. The problem is probably that the search programs were designed for relatively small spaceships, so new programs that are better-suited for larger spaceships and better reflect increased computing capabilities compared with even a few years ago are probably in order.

Also, this seems to be the list of what multiple people support so far:

• Better universal XWSS construction
• More multi-directional universal construction
• A Sir Robin synthesis
• Signal reflection fast enoug to prove ConwayLife omniperiodic

[dvgrn]

Yikes! What are these algorithms behind those programs? I don't particularly care for glider synthesis, but exponential time seems kind of ridiculous to my intuition for CGOL, something so... deterministic.

I agree. The program should be able to divide the spaceship into different regions and go one region at a time, especially with such an elongated spaceship. It might look exponential for small spaceships that aren't large enough to be divided into different regions, but it should eventually go down to linear or at most quadratic.

Again, this sounds like a fine hand-waving theory, but the devil is in the details. Goldtiger997 goes through some of the details in this post, which makes a good summary of the current state of search technology. Problems like this already do get divided up into regions -- when that works.

Check out the "What's Next?" at the bottom. It's a 77-cell spaceship, very very wide and thin, and not deeply connected -- there are significant gaps between different pieces of it. This is an unusually good candidate for a region-by-region approach -- but even then, you have to constantly be aware of the constraints imposed by adjacent regions and what you'll have to do to construct them.

For most spaceships, like 282-cell Sir Robin, there are relatively few gaps of any size between sections. Trying to do a predecessor analysis one region at a time will cause a painful explosion in the number of constraints you have to worry about. If you cut the regions down to any reasonable size, you end up with almost no space to work with -- to add fuses, get gliders in to affect an ongoing reaction at a critical moment, etc. Managing the constraints between different construction sections very quickly gets to be much more difficult than the original synthesis problem.

For many spaceships, there just doesn't seem to be any better way than just, um, solving the entire problem at once. (But often that can be done on only one day of the year.)

[MathAndCode]

The program should be able to divide the spaceship into different regions and go one region at a time, especially with such an elongated spaceship. It might look exponential for small spaceships that aren't large enough to be divided into different regions, but it should eventually go down to linear or at most quadratic.

Again, this sounds like a fine hand-waving theory, but the devil is in the details. Goldtiger997 goes through some of the details in this post, which makes a good summary of the current state of search technology. Problems like this already do get divided up into regions -- when that works.

Check out the "What's Next?" at the bottom. It's a 77-cell spaceship, very very wide and thin, and not deeply connected -- there are significant gaps between different pieces of it. This is an unusually good candidate for a region-by-region approach -- but even then, you have to constantly be aware of the constraints imposed by adjacent regions and what you'll have to do to construct them.

For most spaceships, like 282-cell Sir Robin, there are relatively few gaps of any size between sections. Trying to do a predecessor analysis one region at a time will cause a painful explosion in the number of constraints you have to worry about. If you cut the regions down to any reasonable size, you end up with almost no space to work with -- to add fuses, get gliders in to affect an ongoing reaction at a critical moment, etc. Managing the constraints between different construction sections very quickly gets to be much more difficult than the original synthesis problem.

For many spaceships, there just doesn't seem to be any better way than just, um, solving the entire problem at once. (But often that can be done on only one day of the year.)

Yes, but Sir Robin is elongated, which makes things like not assembling it all at once more practical. In addition, the program can use a partial-based method for the predecessors, starting at one end and working its way to the other. The idea is that if the activation recipe and/or still lifes on one side do not work, the other side will be intact for a while.
Also, assembling Sir Robin from the back first makes adding still lifes, sparks, and gliders to the construction area easier.

[HartmutHolzwart]

As a proof of concept, could you provide a gliderless loafer gun? Or at least one using less gliders and some oscillators?

[dvgrn]

Yes, but Sir Robin is elongated, which makes things like not assembling it all at once more practical. In addition, the program can use a partial-based method for the predecessors, starting at one end and working its way to the other. The idea is that if the activation recipe and/or still lifes on one side do not work, the other side will be intact for a while.
Also, assembling Sir Robin from the back first makes adding still lifes, sparks, and gliders to the construction area easier.

As far as I'm concerned, I've already addressed those points as far as I'm competent to, which is not really very far. Your relative measures, "more practical" and "easier", are perfectly true ... but only in the same sense that it's more practical/easier to empty a lake with a teacup than with a thimble. It doesn't mean that it's actually either practical or easy.

There is no existing search program for which Sir Robin is anywhere near elongated enough, or subdivisible enough, or small enough, to make it even vaguely plausible that someone might find a glider synthesis any time soon.

People talk about possible designs for better search programs a lot more often than they actually write workable search programs. Someday no doubt someone will come up with a new angle of attack, and will write a search program that makes it easier to solve difficult glider synthesis problems. But if history is any guide, the result will be some kind of incremental improvement over what we can do now -- not a huge leap to make even the most extraordinarily difficult problems suddenly easy.

Hartmut's suggestion is along these same general lines. Right now we can't even put a spaceship as small as a loafer into a search program, and get a valid glider recipe out. Seems like that would be a much better challenge to start out with, than a Sir Robin synthesis.

[MathAndCode]

As a proof of concept, could you provide a gliderless loafer gun? Or at least one using less gliders and some oscillators?

That's a possibility, but I think that I might have a couple of better candidates.

I think that there's probably a way to shoot four or six gliders at the spark of the twin bees shuttle in a symmetrical way that results in an x66, 44P5H2V0, or some other fairly small spaceship with gutter symmetry, and if someone finds one, then I'll call that clever.

x66 and 44P5H2V0 look promising for synthesis starting with the twin centuries that will destroy a twin bees shuttle unless they're destroyed by a pair of blocks or some other eater. There are several reasons for this:

• The two spaceships are somewhat similar to the starting point
  • They already have gutter symmetry.
  • The leading tips are already six cells apart orthogonally.
  • The twin centuries exhibit both c/2 and c/3 forward movement mechanisms. These are the same forward movement mechanisms used by x66 and 44P5H2V0.
• x66 and 44P5H2V0 are short and fast enough so that they can fit in a p46 stream without interfering with each other. Their relatively small size compared to some other spaceships should also make creating them easier.
• There are several guns based off of the twin bees shuttle (and more recently, Tanner's p46), so getting gliders at the appropriate period will be relatively easy.
• Twin bees shuttles can be constructed with relatively few gliders.

There is no existing search program for which Sir Robin is anywhere near elongated enough, or subdivisible enough, or small enough, to make it even vaguely plausible that someone might find a glider synthesis any time soon.

People talk about possible designs for better search programs a lot more often than they actually write workable search programs. Someday no doubt someone will come up with a new angle of attack, and will write a search program that makes it easier to solve difficult glider synthesis problems. But if history is any guide, the result will be some kind of incremental improvement over what we can do now -- not a huge leap to make even the most extraordinarily difficult problems suddenly easy.

I think that LazyBoi's suggestion included creating a better program, which I agree with. Part of the point of this thread is to make the future that we agree is best happen, and if we collectively decide that a better search program is worth our efforts and work on it together, then I expect that we will come up with a significantly better search program. Historically, collaborative efforts have achieved more progress than individual ones.

[HartmutHolzwart]

Just for a bit more of handwaving:

the loafer has slightly more appearances in catagolue and a slightly cheaper glider synthesis. This suggests that a gliderless gun might be easier.

Your argument of just creating enough interest and then joint efforts will always get a solution is not exactly what we've seen so far.

[MathAndCode]

the loafer has slightly more appearances in catagolue and a slightly cheaper glider synthesis. This suggests that a gliderless gun might be easier.

While the loafer has more appearances in C1/G1, x66 has more total appearances. Constructing a spaceship with D2 symmetry, especially D2 gutter symmetry (which would mean D2_+1 as opposed to D2_+2), will likely be easier than constructing a spaceship with C1 symmetry for two reasons:

• Patterns with C1 symmetry can have descendants with D2 symmetry, but patterns with D2 symmetry cannot have descendants with C1 symmetry. Likewise, patterns without D2 gutter symmetry can have descendants with D2 gutter symmetry. Thus, reactions tend to accumulate symmetry, so a disproportionately high percentage of reactions of a given size will have higher symmetries.
• Because the two halves are the same, we will only have to worry about figuring out how to build one half.
• We already have a way to repeatedly make a pattern that somewhat resembles those spaceships.

Furthermore, the fact that x66 and 44P5H2V0 are more costly with only gliders means that they need a different, more efficient type of gun more than the loafer needs a more efficient gun.

[wwei23]

Other periods are similarly represented, farther back in the same channel.

I can't access that channel, you'd have to send them over to me.

[HartmutHolzwart]

the loafer has slightly more appearances in catagolue and a slightly cheaper glider synthesis. This suggests that a gliderless gun might be easier.

While the loafer has more appearances in C1/G1, x66 has more total appearances. Constructing a spaceship with D2 symmetry, especially D2 gutter symmetry (which would mean D2_+1 as opposed to D2_+2), will likely be easier than constructing a spaceship with C1 symmetry for two reasons:

• Patterns with C1 symmetry can have descendants with D2 symmetry, but patterns with D2 symmetry cannot have descendants with C1 symmetry. Likewise, patterns without D2 gutter symmetry can have descendants with D2 gutter symmetry. Thus, reactions tend to accumulate symmetry, so a disproportionately high percentage of reactions of a given size will have higher symmetries.
• Because the two halves are the same, we will only have to worry about figuring out how to build one half.
• We already have a way to repeatedly make a pattern that somewhat resembles those spaceships.

Furthermore, the fact that x66 and 44P5H2V0 are more costly with only gliders means that they need a different, more efficient type of gun more than the loafer needs a more efficient gun.

I don‘t think symmetry will help too much except that the two intermediate halves might support each other. Even half of an X66 is as expensive as a loafer. Of course, if one takes a more aggressive target then the learning and benefit will be bigger. I was thinking of the loafer as a better intermediate target, because you already separated that in two parts in earlier posts and because a cheap loafer gun would make loafer synthesis of other patterns more attractive as well. What patterns do we have that somewhat resemble those other patterns?

The other target would be the small c/3 ships. Here we have a 20+ glider synthesis, but already Dave Buckingham was imagining a better method in the early days. He obviously had a near miss that he never shared.

[MathAndCode]

I don‘t think symmetry will help too much except that the two intermediate halves might support each other. Even half of an X66 is as expensive as a loafer. Of course, if one takes a more aggressive target then the learning and benefit will be bigger. I was thinking of the loafer as a better intermediate target, because you already separated that in two parts in earlier posts and because a cheap loafer gun would make loafer synthesis of other patterns more attractive as well. What patterns do we have that somewhat resemble those other patterns?

The twin centuries (the junk emitted by the twin bees shuttle that needs to be destroyed in order to prevent it from destroying the twin bees) strongly resemble the leading edge of x66 and 44P5H2V0. This is the main reason why I proposed those spaceships, as well as any other spaceships that also have a similar leading edge. If we find a good loafer predecessor, then I would encourage an effort to make a clever gun based on that (and I have asked about the possibility that we could use a loaf factory), but natural c/7 forward movement mechanisms, even if they're unstable, don't seem to appear very commonly. As I mentioned here and here, most natural forward movement mechanisms are c/2, c/3, or somewhere in between.

The other target would be the small c/3 ships. Here we have a 20+ glider synthesis, but already Dave Buckingham was imagining a better method in the early days. He obviously had a near miss that he never shared.

If we find out what this is (or a promising alternative), then I would propose or support working on that.

[MathAndCode]

I'm been working on R-conduits recently, and it seems that there is quite a bit of untapped potential there. Shall we devote more resources to this area?

[Extrementhusiast]

• Better universal XWSS construction

Was this referring to the single-channel (or similar)->slow salvo stage, the slow-salvo->object stage, or both?

[MathAndCode]

• Better universal XWSS construction

Was this referring to the single-channel (or similar)->slow salvo stage, the slow-salvo->object stage, or both?

Each is very inefficient, but I suspect that improving single-channel construction would be more useful.

[Roger]

• Better universal XWSS construction

Was this referring to the single-channel (or similar)->slow salvo stage, the slow-salvo->object stage, or both?

Each is very inefficient, but I suspect that improving single-channel construction would be more useful.

Could someone give links to good sources to read up on what current state-of-the-art is on this, what the issues are, what has been tried and what hasn't? If we're going to make a concerted effort around this, we should probably spin off a separate discussion thread and/or a related set of pages on LifeWiki.

[dvgrn]

Could someone give links to good sources to read up on what current state-of-the-art is on this, what the issues are, what has been tried and what hasn't? If we're going to make a concerted effort around this, we should probably spin off a separate discussion thread and/or a related set of pages on LifeWiki.

I think the most recent discussion happened on the ConwayLife Lounge on Discord. The creator of HoneySearch (calcyman/Adam P. Goucher) mentioned the idea of making a version of it that is more spaceship- and rule-agnostic, such that slow salvo searches could be run and databases could be compiled for any desired set of spaceships in a variety of rules.

That definitely seems like the way to go as a next step, but I'm not sure if or when someone will tackle that project. I certainly haven't volunteered to dive into HoneySearch source code yet...!

[MathAndCode]

Could someone give links to good sources to read up on what current state-of-the-art is on this, what the issues are, what has been tried and what hasn't?

This post describes how inefficient the process is.

[dvgrn]

This post describes how inefficient the process is.

But also, to my knowledge nobody has actually ever put together a set of slow unidirectional *WSSes that can perform the 45-degree "slow^2 elbow" universal movement and glider-firing operations mentioned in that link. It's clear that it can be done, but we're still in the very early stages of actual development.

[MathAndCode]

But also, to my knowledge nobody has actually ever put together a set of slow unidirectional *WSSes that can perform the 45-degree "slow^2 elbow" universal movement and glider-firing operations mentioned in that link. It's clear that it can be done, but we're still in the very early stages of actual development.

I can understand that. Once we have better single-channel universal XWSS construction, I'm probably going to work on at least one self-constructing spaceship or puffer using it.

I think the most recent discussion happened on the ConwayLife Lounge on Discord. The creator of HoneySearch (calcyman/Adam P. Goucher) mentioned the idea of making a version of it that is more spaceship- and rule-agnostic, such that slow salvo searches could be run and databases could be compiled for any desired set of spaceships in a variety of rules.

Could HoneySearch be useful for looking into 180° universal construction, or does it only work with 0° universal construction. Also, does it work on Macs?

[dvgrn]

Could HoneySearch be useful for looking into 180° universal construction, or does it only work with 0° universal construction. Also, does it work on Macs?

It's mostly just a big monolithic C++ file (see hs.cpp here, so it should be possible to wrestle with it and make it compile pretty much anywhere.

What it does is to recursively fire one glider at a time at a list of known-constructible objects, and record the outcomes that don't cause uncontrolled explosions -- no emitted gliders allowed, for example. The longer you run it the more constructible objects you'll have in the database.

At some point you hit a point of diminishing returns, where you can already build everything you need to build in the way of self-constructing circuitry, and running things longer mostly just makes the database bigger and harder to store (but very occasionally it will turn up particularly edgy new recipes for difficult-to-build still lifes, like eater2s and so on).

So it's probably much more straightforward to adapt it to finding, say, slow *WSS salvo recipes, than to set it up to find 180-degree recipes. By "180-degree universal construction" do you mean the kind of thing used in the HBK gun, or the period-5603 Cordership gun?

[MathAndCode]

So it's probably much more straightforward to adapt it to finding, say, slow *WSS salvo recipes, than to set it up to find 180-degree recipes. By "180-degree universal construction" do you mean the kind of thing used in the HBK gun, or the period-5603 Cordership gun?

This is for my attempt to lower the cost of universal construction to sixteen gliders. The explanation for how it would work is here. It's more similar to the Cordership gun than the HBK gun in the sense that there would only be one lane from each direction, but there are some differences from either, such that the construction would have to be slow and that the emitted gliders would have to be at a 0°/180° angle from the incoming glider streams instead of 90°.