Unsolved life problems

[hobbyprogrammer77]

What are the biggest unsolved life problems, such as building a replicator or finding an oscillator of every period?

[Freywa]

The two problems you mentioned are in fact THE problems left in Conway's Life. For oscillators of every period, we're missing 19, 23, 34, 38 and 41. Progress on a replicator is going very smoothly on another thread in the Patterns sub-forum.

Besides those biggies, there is a gap in the knowledge of light-speed signals, such as how to turn them around a corner (¡) and the possible outcomes of glider collisions. Right. How am I going to make that 14-cell still life Heinrich Koenig proposed as a stepping stone to a glider-cheap snark?

[velcrorex]

There's also the problem of finding spaceships of different velocities. There is not yet any reasonable hope of finding an example of every combination of period, speed and direction. For periods < 8, the only combinations without a known example are 3c/7 orthogonal ship and a period 6 knightship. EDIT: (As Sokwe noted, there is also no period 7 knightship.)

Also of note, Jason Summers maintains the Game of Life - Status Page.

[Sokwe]

For periods < 8, the only combinations without a known example are 3c/7 orthogonal ship and a period 6 knightship.

There is also no known period-7 knightship.

Another interesting question is the "grandfather problem": Does there exist a finite pattern that has a parent, but no grandparents?

On a related note, this topic is for trying to find solutions to specific incomplete patterns.

[codeholic]

Another interesting question is the "grandfather problem": Does there exist a finite pattern that has a parent, but no grandparents?

A similar one: Does there exist a pattern that has only one parent, and it is the pattern itself?

J. H. Conway will pay 50 bucks for finding such a pattern or proving that no such patterns exist

[Sphenocorona]

codeholic: no, because you can fill in the area around it with stuff that dies in one generation. Or do you mean as if only the area that is considered to be the parent is the area that surrounds the figure out to two cells away?

[codeholic]

codeholic: no, because you can fill in the area around it with stuff that dies in one generation. Or do you mean as if only the area that is considered to be the parent is the area that surrounds the figure out to two cells away?

Yes, probably only the area of influence should be taken into account. There should be an original statement somewhere.

[dvgrn]

Yes, probably only the area of influence should be taken into account. There should be an original statement somewhere.

LifeLine 6:1 says it like this: "Is there a stable configuration whose only father is itself (with some fading junk some distance away not being counted)?"

Found this in an open-problems list from 2008 -- there were several contributions that I never quite finished cleaning up for LifeNews.

Here are the 2008 open problems. I took out a few that I know have been found since then, and put all the specific "complete this pattern" ones on the incomplete-patterns thread. There may be a few more problems here that have already been solved. I'll happily remove them from this post if someone points them out...!

• - Find a stable pattern that cannot be constructed from gliders.
  
  - Prove that, for any stable pattern, there exists a sequence of gliders that interact with it leaving zero live cells.
  
  - Closer to reachable: find p7 and p9 fountains or a p6 superfountain. There are many similar problems of "find an oscillator with this period and a spark that looks like this" that remain unknown.
  
  - A p3 oscillator in which every cell oscillates. (EDIT: found by Jason Summers -- see below.)
  
  - A 2c/6 (c/3) spaceship that's entirely period 6. (EDIT: p6 spaceship with symmetric p3 "wing" sections quoted below.)
  
  - A 3c/6 (c/2) spaceship that's entirely period 6.
  
  - A constructed c/3 rake of around period 144 or less.
  
  - More c/4 orthogonal puffers based on Paul Tooke's p168 puffer.
  
  - Ways to get signals (lightspeed or otherwise) to turn corners, or to convert diagonal to/from orthogonal.
  
  - A period 8 c/4 diagonal glider stream "fuse" that accepts gliders from a p8 backward rake, and emits an equivalent stream. [I've edited this a bit, maybe wrongly, but I think it makes sense...]
  
  - Herschel tracks besides the R64 that consist only of blocks.
  
  - A small color-changing stable reflector.
  
  - How much can the population grow in n generations? I.e. if generation 0 has population P and generation n has population Q, how large can Q/P be? For n=1, Q/P can be arbitrarily close to, but not equal to, 3. Unknown for any larger n.
  
  - Consider a particular cell within a pattern, and look at the sequence of its states in gen 0, gen 1, ... Can every finite sequence of bits occur as such a sequence? (If every finite sequence can occur, then so can every infinite
  sequence.)
  
  - Is there a still-life which is annihilated by any single glider which hits it? How about just every glider from one particular direction? (Such a thing would be useful for protecting a pattern from random glider attacks.)
  
  - Very ambitious: find a termination for a 2c/3 signal wire that emits a glider directly.
  
  - There's also a whole bunch of minimization problems: the "smallest" patterns with particular properties. "Smallest" can be taken to mean initial number of on cells, area of bounding rectangle, diameter..., restrictions can be imposed (symmetries, confinement to a single row/column, consisting only of gliders), and pattern properties include being a spaceship with a specific velocity, growing for ever, growing for ever in various ways (quadratically, sublinearly, with t log(t)...), being a GoE, being grandfatherless... A few of these are solved, but most are not.

[velcrorex]

- A 2c/6 (c/3) spaceship that's entirely period 6.

Does this count?

Code: Select all

x = 27, y = 22
19bo$6bo11boo$5bobo7bob4o$5bo8boobbobo$4bobboboboobb5obo$4boobob4o5boo
3boo$4bobboo16bo$bb3o3bob3o7boobbo$boboo3bob3o7boob3o$o4boobobo9b3obb
oo$o4bobbo11b3ob3o$o4bobbo11b3ob3o$o4boobobo9b3obboo$boboo3bob3o7boob
3o$bb3o3bob3o7boobbo$4bobboo16bo$4boobob4o5boo3boo$4bobboboboobb5obo$
5bo8boobbobo$5bobo7bob4o$6bo11boo$19bo!

It's something of a judgement call whether this is entirely p6.

[skomick]

I believe it was Jason Summers who showed us a p3 oscillator in which every cell oscillates:

Code: Select all

x = 33, y = 26, rule = B3/S23
9b3o5b3ob3o5b3o$12b3o3b2ob2o3b3o$18b2ob2o$12bob4o5b4obo$10bo19bo$10bo
19bo$10bo19bo$8b2o18b2o$8b2o18b2o$7b2o18b2o$7bo19bo$bobo2bob2o11bobo2b
ob2o$o3bo6bo8bo3bo6bo$bo6bo3bo8bo6bo3bo$3b2obo2bobo11b2obo2bobo$5bo19b
o$4b2o18b2o$3b2o18b2o$3b2o18b2o$2bo19bo$2bo19bo$2bo19bo$4bob4o5b4obo$
10b2ob2o$4b3o3b2ob2o3b3o$b3o5b3ob3o5b3o!

[DivusIulius]

I believe it was Jason Summers who showed us a p3 oscillator in which every cell oscillates

*slow clap*

[Tropylium]

- A 3c/6 (c/2) spaceship that's entirely period 6.

I don't think we even have one that would be "entirely" period 4… what's being sought is one that doesn't rely on adding a p6 tagalong or tail component to a p2 ship, I gather?

Glider synthesis of non-standard spaceships is one obvious unsolved problem I didn't see listed.

[dvgrn]

Glider synthesis of non-standard spaceships is one obvious unsolved problem I didn't see listed.

Coming at the idea of "unsolved problems" from another angle, glider syntheses are just one of many categories where the search space seems intractably large. I don't think anyone has written any kind of automated glider-synthesis search utility (though Mark Niemiec might be able to do something like that, given a good multi-year research grant -- Kickstarter, anyone?)

The most useful search programs for this kind of thing right now might be Paul Callahan's 'gencols', and Paul Chapman's 'Glue' for unidirectional slow salvos. These can both sort through all collisions involving N gliders, for small N, to pick out the useful stuff by brute force.

So larger objects have to be glider-constructed incrementally, no doubt using twice as many gliders as necessary. Is there a more direct way to synthesize a Snark, or other medium-sized still lifes or spaceships? Seems like the answer is almost certainly "yes" -- but are there algorithmic shortcuts that might actually allow us to find, say, a 20-glider Snark synthesis?

WLS/JLS/lifesrc backtracking searches tend to produce an exponential explosion of high-energy "space dust" ancestors of objects, so deeply interconnected and active that they're much harder to synthesize than the original object was. Ancestor patterns tend to gradually increase in size, and sooner rather than later they're too large to handle with a brute-force search.

The size increase might not be a bad thing by itself -- a larger search space presumably makes it more likely that there's a solution out there somewhere. If each successive ancestor a is a little bit easier to glider-construct than the last, on average, then we're still getting somewhere!

Of course the hard part is writing an evaluation algorithm that can rate each predecessor for "likely glider-constructibility". Maybe there's a way to backtrack selectively, looking let's say for ancestors that are as close to stable as possible -- or just ancestors that stay as small as possible but contain as many gliders and glider collision products as possible.

Or possibly some memory-intensive hashtable trickery could speed up backtracking searches, somewhat analogous to the way Hashlife can outperform brute-force Quicklife by many orders of magnitude. It certainly seems as if a lot of the time in a WLS/JLS/lifesrc search is spent trying the same things over and over.

Here again the difficulty is to write an algorithm smart enough to recognize, for example, that a search has split into two separate sub-searches and there's no need to try all combinations of Region A solutions with all combinations of Region B solutions (because Region A and Region B can't affect each other). Without a way to find some order in the chaos of a backtracking search, a hashtable-based algorithm is pretty certainly a lost cause...!

[Freywa]

Of course the hard part is writing an evaluation algorithm that can rate each predecessor for "likely glider-constructibility".

Guess what? We don't need an evaluation algorithm. We use our brains. I played a game of Wordfeud and lost. Synthesis of objects using gliders is akin to organic synthesis. There are predetermined reactions that turn subpattern A into subpattern B. These subpatterns show in the target object, and you backtrack from there, working with progressively simpler objects until you arrive at a catalogued still life or oscillator. This is called retrosynthesis, and here humans are always better than hot, hard silicon chips.

[Extrementhusiast]

But we've already synthesized the Snark with around 50 gliders. We're trying to see if/how it can be made with fewer gliders.

[dvgrn]

Of course the hard part is writing an evaluation algorithm that can rate each predecessor for "likely glider-constructibility".

Guess what? We don't need an evaluation algorithm. We use our brains... This is called retrosynthesis, and here humans are always better than hot, hard silicon chips.

I definitely agree with the spirit of this, but "always" seems a bit much. An inspired combination of human brains and silicon chips is likely to work better than a competition between the two. Paul Chapman's Seeds of Destruction puzzle program is a recent experiment with this kind of thing, letting the computer do what it's good at doing but leaving room for human experience and intuition to make the key choices in the search.

Here's a quick and very artificial example of a problem that silicon can solve better than carbon can... Let's say you want a glider construction for the following constellation:

Code: Select all

x = 17, y = 20, rule = B3/S23
3$3b2o$2bo2bo$3bo2bo$4b2obob2o$7bob2o$7bo$5bobo$5b2o$9b2o$8bobo$8bo$5b
2obo$5b2obob2o$9bo2bo$10bo2bo$11b2o!

Having to build two of these 19-bit objects doesn't leave a lot of room for an incremental construction to work (though I'm sure it's possible -- I don't need anyone to work on proving that!) But luckily this object is within reach of a search program that can find an all-at-once construction. Paul Chapman's 'Glue' can build each half with unsynchronized gliders all coming from one direction (!)

Human intuition will have a very tough time guessing which particular blinker+block+loaf+glider collision will crystallize into that 19-bit still life. But an automated search can find it easily -- and 'Glue' has only barely scratched the surface of what can be found with today's computer hardware. That would seem to indicate there's a place for inspired computer algorithms, as well as inspired human brains, in glider-synthesis discoveries.

Code: Select all

x = 153, y = 132, rule = B3/S23
18bo$19bo$17b3o13$27bo$28b2o$27b2o7$46bobo19bo$47b2o20bo$47bo19b3o$54b
obo$55b2o$55bo3$49bo15bo$50b2o14bo$49b2o13b3o5$72bo$73bo$71b3o10$82bo$
83bo$81b3o3$81b2o$81b2o3$2bo$obo2b2o$b2o2b2o3b3o3$3b2o10bo$2bo2bo8bobo
$3bobo8bo2bo$4bo10b2o3$7b3o3b2o2b2o$13b2o2bobo$17bo$87b2o$87b2o3$86b3o
$86bo$87bo10$96b3o$96bo$97bo5$103b3o13b2o$103bo14b2o$104bo15bo3$114bo$
113b2o$113bobo$100b3o19bo$100bo20b2o$101bo19bobo7$141b2o$140b2o$142bo
13$150b3o$150bo$151bo!

But we've already synthesized the Snark with around 50 gliders. We're trying to see if/how it can be made with fewer gliders.

Seems to me the true smallest recipe for a Snark is likely to be around (insert wild guess here) 12 to 25 gliders, building the big still life not incrementally but pretty much all at once. But any recipe in that size range is pretty much unfindable for the foreseeable future -- given the size of the search space, a needle in a haystack would be much easier to find...! Are there search shortcuts that can make the haystack smaller, or make the needle more visible?

[Tropylium]

Of course the hard part is writing an evaluation algorithm that can rate each predecessor for "likely glider-constructibility". Maybe there's a way to backtrack selectively, looking let's say for ancestors that are as close to stable as possible -- or just ancestors that stay as small as possible but contain as many gliders and glider collision products as possible.

Intuitively this does not seem like an intractable problem to me. Ancestors should presumably be prioritized if they show a "star-like" structure, which could be backtracked to separate smaller areas of activity. Plotting some kind of an "interaction graph" among the cells of the pattern (over a couple generations), then identifying & magnifying bottlenecks in it. Spark interaction identification would also help a lot I assume: if a particular area of a reaction consists of a cleanly dying set of cells that ends up contributing to birth/suppression of the main area, there should be no need to backtrack this individually, known spark-generating reactions could be plugged in straight.

It also seems to me that a better understading of small reactions and transient patterns — the "physical chemistry" of Life — might be required to make progress here? We have, by now, vast indexes of still lifes and oscillators by size and by frequency of occurrence; but not for non-stable patterns. The collectiv understanding of these seems to be stuck at the early 70s stage of only knowing a small, barely dubble-digit number of the most common ones.

One easy approach to this area, I find, is generating random soups and then analyzing these backwards to see what are the most typical, low-entropy sources for a certain object or constellation or explosion (although not all transient objects leave a clean outcome with any appreciable frequency, e.g. ∏ or R). If this could be automated, it would be possible to focus on rarer but still natural objects as well (by combing thru large amounts of soups). At this point then we could manually attempt to examine these typical precedessors and use this data for reaching towards a definition of "easily constructible".

There's also the bottom-up approach of bilding a collection of smallish glider recipies that insert some kind of a handy still life, or spark or other transient object. This exists up to 4-5 gliders IIUC, but if automated object recognition existed, there should be the possibility of getting a much bigger library together.