Unsolved life problems

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.
Post Reply
hobbyprogrammer77
Posts: 25
Joined: June 12th, 2013, 10:47 am

Unsolved life problems

Post by hobbyprogrammer77 » June 16th, 2013, 9:19 am

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

User avatar
Freywa
Posts: 589
Joined: June 23rd, 2011, 3:20 am
Location: Singapore
Contact:

Re: Unsolved life problems

Post by Freywa » June 16th, 2013, 12:09 pm

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?
Princess of Science, Parcly Taxel

User avatar
velcrorex
Posts: 339
Joined: November 1st, 2009, 1:33 pm

Re: Unsolved life problems

Post by velcrorex » June 16th, 2013, 12:20 pm

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.
Last edited by velcrorex on June 16th, 2013, 6:12 pm, edited 1 time in total.
-Josh Ball.

Sokwe
Moderator
Posts: 1480
Joined: July 9th, 2009, 2:44 pm

Re: Unsolved life problems

Post by Sokwe » June 16th, 2013, 5:28 pm

velcrorex wrote: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.
-Matthias Merzenich

User avatar
codeholic
Moderator
Posts: 1142
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Unsolved life problems

Post by codeholic » June 17th, 2013, 10:53 am

Sokwe wrote: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 ;)
Ivan Fomichev

Sphenocorona
Posts: 480
Joined: April 9th, 2013, 11:03 pm

Re: Unsolved life problems

Post by Sphenocorona » June 17th, 2013, 4:05 pm

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?

User avatar
codeholic
Moderator
Posts: 1142
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Unsolved life problems

Post by codeholic » June 17th, 2013, 4:14 pm

Sphenocorona wrote: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.
Ivan Fomichev

User avatar
dvgrn
Moderator
Posts: 5888
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Unsolved life problems

Post by dvgrn » June 18th, 2013, 12:28 pm

codeholic wrote: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.

User avatar
velcrorex
Posts: 339
Joined: November 1st, 2009, 1:33 pm

Re: Unsolved life problems

Post by velcrorex » June 18th, 2013, 1:08 pm

dvgrn wrote: - 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.
-Josh Ball.

skomick
Posts: 74
Joined: February 11th, 2011, 11:41 pm

Re: Unsolved life problems

Post by skomick » June 18th, 2013, 1:10 pm

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!
Shannon Omick

User avatar
DivusIulius
Posts: 89
Joined: April 1st, 2009, 11:23 am
Contact:

Re: Unsolved life problems

Post by DivusIulius » June 18th, 2013, 3:30 pm

skomick wrote:I believe it was Jason Summers who showed us a p3 oscillator in which every cell oscillates
*slow clap* :D

User avatar
Tropylium
Posts: 406
Joined: May 31st, 2011, 7:12 pm
Location: Finland

Re: Unsolved life problems

Post by Tropylium » June 19th, 2013, 1:41 pm

dvgrn wrote:- 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.

User avatar
dvgrn
Moderator
Posts: 5888
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Unsolved life problems

Post by dvgrn » June 21st, 2013, 7:57 am

Tropylium wrote:
dvgrn wrote: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...!

User avatar
Freywa
Posts: 589
Joined: June 23rd, 2011, 3:20 am
Location: Singapore
Contact:

Re: Unsolved life problems

Post by Freywa » June 21st, 2013, 9:11 am

dvgrn wrote: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.
Princess of Science, Parcly Taxel

User avatar
Extrementhusiast
Posts: 1797
Joined: June 16th, 2009, 11:24 pm
Location: USA

Re: Unsolved life problems

Post by Extrementhusiast » June 21st, 2013, 11:24 am

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.
I Like My Heisenburps! (and others)

User avatar
dvgrn
Moderator
Posts: 5888
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Unsolved life problems

Post by dvgrn » June 21st, 2013, 5:18 pm

Freywa wrote:
dvgrn wrote: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!
Extrementhusiast wrote: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?

User avatar
Tropylium
Posts: 406
Joined: May 31st, 2011, 7:12 pm
Location: Finland

Re: Unsolved life problems

Post by Tropylium » June 22nd, 2013, 4:24 pm

dvgrn wrote: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.

Post Reply