dvgrn

15 is probably not the minimum. There are some ideas floating around for getting down to 14, and some wilder ideas that might get to 13 or 12.

Below that we'd need some significantly different mechanism that nobody has thought of yet. It doesn't seem likely that anyone will be able to prove that universal construction is impossible with a single-digit number of gliders -- but if a solution exists it might take an omniscient being to find it.

... Or maybe some clever hacker will figure it out tomorrow! That's what happened to get us to the current minimum. We were stuck at a minimum of 32 for quite a while, until Daniel Vargas (MathAndCode) suddenly showed up with a new idea.

Heh, oddly enough, the RCT can probably be better thought of as a way of explosively _decompressing_ a glider construction recipe. There are lots and lots of reasonable-sized recipes for constructing different patterns. When you apply the RCT trick to any of them, the cost in gliders always shrinks to 15, but the pattern's bounding box always expands to something gargantuan.

The Life pattern that most evokes DNA and self-replication is another megapattern from several years ago, the 0E0P metacell, which even has a visible "nucleus" for its "DNA":

  https://conwaylife.com/wiki/0E0P_metacell

That's definitely completely true. We can specify the relative positions of the initial gliders at each of the three corners of the RCT pattern in just a few dozen bytes.

But the number that says how far apart those corners are from each other has very roughly half a million digits. The exact number depends on exactly what pattern is being encoded by the RCT pattern -- I think the example construction of Alan Hensel's decimal counter pattern needs somewhere around a 450,000-digit number.

There are some optimizations underway to decrease that number by a few percentage points, but it's always going to be a very big number!

I think that was just saying "more space between initial gliders implies a longer time needed to complete construction". There's no Einsteinian relativity to be found here.

(A Doppler effect does show up in Conway's Life sometimes, but that's about as far as we get with analogies to the physical universe...!)

It's a bit hard to see how this RCT trick could be useful for reducing anything besides the number of gliders.

RCT is basically one very unreasonable end of a wide spectrum: you can use a very small number of gliders to build something, as long as you're content to have the construction take a ridiculously long time. Conversely, you can build that same thing in a lot less time, but it will take a lot more gliders.

I think the biggest prerequisite for getting good at "advanced GoL" is just an unreasonable amount of patience.

Probably I'm a good case in point. I'm definitely not a particularly clever mathematician, but it seems like it's possible to understand any new Life technology just by tinkering with the pieces for long enough.

If anyone wants to follow along with that kind of learning process, just start working through the Life textbook that kryptiskt mentioned. (Full disclosure, I'm one of the authors.)

There have been a lot of GoL variants over the years, but I don't remember running into any attempts to vary the speed of evolution in different locations on the same grid.

The idea that all neighbors move to the next tick simultaneously is a fundamental assumption in cellular automata in general. If you try changing that, the optimizations that allow us to simulate CAs at any kind of reasonable speed ... all stop working, pretty much. It's kind of painful even to think about.

Which means there are probably very interesting rules out there somewhere, where CAs run faster/slower depending on pattern density -- it's just going to be very tricky to explore that particular search space.

Ha -- when was that written?... Let's see, the original form of the statement showed up in 2012: "Some patterns require a very large number (scores, even hundreds) of glider collisions..."

At that time Andrew Wade had already created the self-constructing Gemini spaceship, which needed 173449 gliders to build ( https://conwaylife.com/wiki/Glider_synthesis#Spaceship_synth... ). The recipe could have been reworked to be a little cheaper, but nobody bothered at the time -- and now it can be done in fifteen gliders instead.

If you want to see the construction happening, I'd definitely recommend the old Gemini recipe over an RCT-based one, though! RCT cuts down the cost in gliders to a minimum, but at a terrible cost in the time you have to wait around to see the completed object.

For about twenty years, 1992 through 2012 or so, there was an invite-only "LifeCA" Conway's Life mailing list where a lot of the in-depth research and collaboration tended to happen. That was certainly a good surviving pocket of Life-hacker subculture.

The point of keeping the LifeCA list private was to dodge spammers and keep the signal-to-noise ratio high. This very successfully avoided the terrible drowned-in-spam fate of the Usenet group comp.theory.cell-automata, so that was good -- but it made it quite difficult for newcomers to figure out who to talk to, or what interesting problems had been solved or were still open.

When the conwaylife.com forums showed up in 2009, it turned out that there were much better ways of suppressing spam, and a lot of new energy entered the field.

I think I'd rather have a hand-cranked mechanical design, along the lines of Babbage's Difference Engine -- or maybe something steam-powered. Maybe patch together a few hundred Whac-A-Mole games somehow.

You're most welcome! The project was "in the works" for several years, and it was a very pleasant surprise when it became clear sometime in 2021 that we were actually going to be able to get it completed and out the door by the end of the year.

Naturally that was when people started making discoveries that solved half-century-old open Life problems. In early 2022 we had to fix a few sentences that started with "it is currently unknown whether..." -- but that didn't take too long.

There was also some early discussion of the result by the authors on the ConwayLife Lounge on Discord:

https://discord.com/channels/357922255553953794/370571014654...

I suspect this will get written up in a paper relatively soon, but it's too new for the journal wheels to have turned far enough yet. The original ... publicization, if not publication ... was in a post on the conwaylife.com forums, and there's some more detail there on the general method:

https://conwaylife.com/forums/viewtopic.php?p=140258#p140258

The previous "Grand^N Orphan" result involved a complete enumeration of the relevant 6x3 agars, but this "Unique Father" result was a partial enumeration of 6x6 agars, I think, just until a working example was found.

At least one independent verification has been done:

https://conwaylife.com/forums/viewtopic.php?p=140277#p140277

Right -- this discovery is about identical states extending into the past, not into the future.

A Conway's Life pattern that has to stay the same into the indefinite future would be an impenetrable wall, and we don't know of any such thing in the Life rule. It hasn't exactly been proved impossible, but nobody seriously thinks that such a thing exists.

I think it _can_ easily be proven that a finite stable (period 1) impenetrable wall can't exist. It's trivial to find a way to attack the corners, and almost equally trivial to find something that makes a change at any edge.

The article mentions a couple of new spaceship discoveries from 2020, the Speed Demonoid and the doo-dah spaceship (look them up in the LifeWiki). But it came out just slightly too soon to be able to mention a third one that was discovered only yesterday:

https://conwaylife.com/wiki/Anura

Conway's Life technology has come a long way since it first showed up in Scientific American fifty years ago, when most people were using Go stones or graph paper to explore it.

Now you can run a script in the latest version (4.0) of Golly, to build your own custom Life spaceship. It can move diagonally at any rational speed you want, less than the theoretical maximum of 1/4 lightspeed: https://conwaylife.com/forums/viewtopic.php?p=108786#p108786

The video explanation of the Life metacell is from 7:35 to 13:05.

It's really nice to finally have some good pictures showing how the 0E0P works. Until now it's been kind of a black box, just because the pattern is so impressively huge that even HashLife has a hard time simulating it.

A self-constructing "0E0P" Conway's Life metacell is finally in working order!

The structure behaves like a single cell, obeying the rules of Life or whatever CA rule it's programmed to emulate. Unlike previous metacells, if a new cell has to be born, one of its neighbor metacells has to construct it starting from empty space.

Von Neumann's 29 states were custom designed to make it easy to construct passive configurations, similar to the way a 3D printer builds things -- one layer at a time.

You can't do that in Conway's Life, because stable patterns in Life aren't necessarily stable when you add one cell at a time. But you can do the next best thing, which is to design circuitry that's made out of small stable "Spartan" pieces -- and then build the pieces one at a time.

Related to this, there's an equivalent for building passive structures and then activating them. In Life you can build a static "one-glider seed constellation". Hit the stable constellation with a single glider, and a few ticks later you have a working spaceship. Example:

http://www.conwaylife.com/forums/viewtopic.php?f=&p=57674#p5...

However, there's no reasonable expectation of figuring out how to build a one-glider seed for the Sir Robin knightship any time soon -- the knightship is way too fast, active, and complex. With current techniques a search for such a thing would likely take millions of years.

Does the starting point have to be Javascript?

If so, a good bet might be this HashLife Javascript implementation:

https://copy.sh/life/?gist=31aa52b9430970a28e4c199444e5a873

If not, well, Golly is open-source, cross-platform, supports custom rules via rule tables, and would welcome contributions to its editing-tool department:

http://sf.net/projects/golly

There's even a lifeviewer.lua in the Scripts/Lua folder that duplicates some of LifeViewer's functionality, and is also obviously open source, though it's definitely also a work in progress.

LifeViewer has evolved in a somewhat different direction from the original LifeView, and is still a work in progress -- Chris has been contributing a lot of useful LifeViewer functionality to http://golly.sf.net , and vice versa.

LifeViewer is currently used primarily on the conwaylife forums and the LifeWiki, but it's easy to borrow it to embed in independent Web pages.

The source code is not currently available -- see http://www.conwaylife.com/forums/viewtopic.php?f=&p=35511#p3... . That's also probably the best place to ask any further questions about LifeViewer -- I'm just a beta tester.

Everyone would be completely floored if someone built a gun for the new knightship. It's likely to be several orders of magnitude harder to find a glider synthesis for the knightship, than it was to find the knightship itself.

To build some intuition on the difficulty, check out the list of spaceships for which a glider synthesis is known: http://conwaylife.com/wiki/Glider_synthesis#Spaceship_synthe... .

Except for the macro-spaceships (some of which are pretty trivial to construct because they're self-constructing anyway!) and the Corderships, which aren't elementary and are made out of easily constructible pieces, the biggest spaceships with known constructions are all far smaller than Sir Robin, and most of them are lower period.

Every time you add a few cells to the size of an active pattern like this, you probably double the total difficulty.

"The task of constructing such a spaceship has been likened to building a Formula-1 race car whilst it's on the track and travelling at 200mph." ( http://www.conwaylife.com/forums/viewtopic.php?f=&p=55205#p5... )

There are in fact various 3D rules that can be made to behave exactly like Conway's Life -- starting with some discoveries by Carter Bays involving a two-cell-thick "sandwich" of Life cells that emulated standard Conway's Life. Without the sandwich trick it can do other interesting things:

http://www.complex-systems.com/pdf/04-6-2.pdf

The two problems with 3D life have always been

1) 3D is computationally very expensive compared to 2D, so you tend to get stuck working with much smaller grids; and

2) you need a really good visualization system, otherwise interesting patterns and uninteresting patterns both look like ugly random blobs of cells and you can't tell what's going on.

That said -- not promising anything, and especially not on any definite timeline, but the next version of Golly might have a Lua-based system for experimenting with 3D CAs.

If you have Javascript enabled, then there are several places that should work: the Sir Robin LifeWiki article

http://conwaylife.com/wiki/Sir_Robin

the original link (via the Show in Viewer option), or the Catagolue page

http://catagolue.appspot.com/object/xq6_yyocxukcy6gocs20h0a3...

(click on the knightship in the upper left -- the word "Launch" should appear when you hover over the image).

They all use the same LifeViewer to do the animation, though, so you're out of luck if Javascript isn't available.

Certainly with a good cube you _could_ hold the outside and push to twist a center slice. From www.cube20.org -- "We consider any twist of any face to be one move (this is known as the half-turn metric.)"

Also, "New results: God's Number is 26 in the quarter turn metric!"

Yup, the "c" in spaceship speeds, like "(2,1)c/6", is the same c as in "E=mc^2". It's a good analogy -- one cell per cycle is the maximum possible speed that information can travel in the Life universe.

Yeah, Problem 1 definitely is a (very difficult) open problem, not likely to be solved any time soon.

Problem 2 just looks to me like a known fact, not really a problem... and Problem 3 is only a problem if you don't accept the standard definition of "elementary", and/or if you worry too much about leftover pieces.

As soon as you can see two separate pieces inside a larger spaceship, and each of the pieces in isolation would travel at the same speed as that larger spaceship, then that larger spaceship is not an elementary spaceship.

Once you take out the recognizable pieces, there may well be sparks and other junk left over. But they might just be side effects of the interaction of the recognizable pieces, not anything that can function independently. There are way too many such fading sparks and such for each one to deserve its own name.

Minor side note -- no spaceship of any size will ever contain a Garden of Eden, because every spaceship by definition has at least one predecessor (itself).

The part above about "tape and constructor" is exactly right for the self-constructing Gemini spaceship and its descendants. But it's not quite right for the waterbear. There's no universal constructor in the waterbear, or in its relatives the Centipede and the original Caterpillar.

Large parts of these macro-spaceships never get constructed or destroyed, they just travel along a support structure. That support structure is the only thing that gets constructed, and the construction recipe is encoded not in a simple "tape" glider stream but in the entire body of the spaceship.

Self-supporting spaceships like the waterbear are built with a very limited "toolkit" that only works at one particular speed. In general they're harder to put together successfully, and thus in a way are more impressive than self-constructing spaceships. Once you have a universal constructor, after all, you can build anything that's buildable. The trick is figuring out how to get along without that much power.

That's basically right. Remove any one cell or any subgroup from the knightship, and it's no longer a working spaceship -- at least not one that moves the same speed!

There are "optional extras" that can be added or removed from some spaceships. These are called "tagalongs", and aren't considered to be part of the ship. That can get a little complicated, too, though, like with another recent-ish discovery: http://conwaylife.com/wiki/Fireship .

The "elementary" vs. "engineered" distinction might be clearer with an example of an engineered spaceship, like one of the Corderships: http://conwaylife.com/wiki/13-engine_Cordership .

Inside the 13-engine Cordership are thirteen switch engines, each of which moves at a twelfth of the speed of light, but leaves junk behind. The thirteen pieces basically collaborate on cleaning up each other's junk to make a clean spaceship.

It's very difficult to prove that a large elementary spaceship can't possibly be created by crashing gliders together (for example). Several elementary spaceships do in fact have known glider constructions, but that doesn't stop them from being elementary -- you can't pick those spaceships back apart into their constitutent gliders once they're constructed, and often they're traveling a totally different speed and direction than a glider anyway.