Hacker News Reader

Comment by npinsker | Hacker News Reader

What are the coolest problems that have been recently solved?

What are the coolest open problems you'd like to see solved?

It's hard to choose one these days -- a whole pile of open problems actually got solved in the last few years, like omniperiodicity, glider syntheses of really complicated things like spacefillers, fixed-cost universal construction (it only takes fifteen gliders to build anything buildable) and still lifes and oscillators that solve the "unique father problem" (i.e., there are groups of cells that, if they're found in the Life universe at any point, they must have been there from the beginning of time.) So now I don't know what to wish for next!

I suppose if I get a free wish for anything I want, I'd love to see a glider synthesis for Sir Robin, which a big oblique spaceship discovered in 2018. It's currently way beyond our ability to figure out how to build it out of gliders -- but twenty years ago the same was true of just about every Life spaceship, and now we have recipes for dozens of them.

What would that investigation look like, just large amount of trial and error?

It's going to have to be the opposite of trial and error, I would think -- though maybe in some sense some of the underlying searches for useful predecessors of patterns like Sir Robin could count as "directed super-high-speed trial and error".

The problem at the moment is that nobody can see how to direct those searches toward a predecessor that's made entirely out of gliders -- it's clear that the Sun will burn out long before a trial-and-error search would be at all likely to return a result.

We can easily make a huge number of non-Sir-Robin predecessor patterns that will evolve into Sir Robin -- and we can find ancestor patterns for most of those predecessors, too -- but each step backward always produces something that's a little bigger, a little blobbier, and a little more random and chaotic looking than Sir Robin was... so ultimately all we're doing is making the problem more difficult with each step.

> fixed-cost universal construction (it only takes fifteen gliders to build anything buildable)

Here’s the Hacker News discussion from when this was discovered: https://news.ycombinator.com/item?id=33797799

Dave, I’m still regularly blown away by this discovery. I don’t know what else there is to be said, but do you have any other comments regarding this?

Definitely I have lots more to say about 15-glider universal construction! It was a really exceptionally interesting collaboration, where several people working together were able to complete something that would have taken any one person a ridiculously long time to sort out.

Development of the RCT has slowed down a bit, though there's a hyper-optimized version in the works that will build a spacefiller instead of a Hensel decimal counter as its example pattern:

https://conwaylife.com/forums/viewtopic.php?p=180134#p180134

There's also another long-awaited project in the works, that will use quite a bit of the same technology along with some new ideas -- a unidimensional (one cell thick) spaceship:

https://conwaylife.com/forums/viewtopic.php?f=2&t=2040

It's improbably complex and awkward, of course, just like an RCT pattern, and it's huge though nowhere near as huge as an RCT pattern -- but there will be one phase of the spaceship that fits in a 1xN bounding box.

Reply on news.ycombinator.com