## Unproven conjectures

For general discussion about Conway's Game of Life.

### Re: Unproven conjectures

77topaz wrote:
danny wrote:UPDATE: This one's been proven. Its bounding box is smaller in area than 50*50, and even just barely (31*79 = 2449 = 2500 - 51)

Technically, it doesn't actually fit in a 50*50 box, though.

Either way, the part in italics should now be updated IMO.
Gamedziner

Posts: 602
Joined: May 30th, 2016, 8:47 pm
Location: Milky Way Galaxy: Planet Earth

### Re: Unproven conjectures

dvgrn wrote:Conjecture: No glider eater can be constructed with a recovery time of three ticks or less.
(All known glider eaters take at least four ticks to recover to their original state after eating a glider.)

I think this one is somewhat easier to tackle than others; Is it proved?

The definition of "recovery time" of a catalyst isn't very well-defined, I think...
1) Traditional catalyst searchers / gencols etc. define them as "having a common neighbor".
e.g. two blinkers in a row are "reacting" every 2 generations in this sense.
2) Personally I think it's appropriate to define as the following:
Pattern p, c; // Pattern and Catalyst
reaction_gen(p, c) = min{i | i∈ℕ, p[i] ∪ c[i] != (p∪c)[i]};
recovery_gen(p, c) = min{i | i∈ℕ, i >= first_reaction_gen(p, c), c[i] ⊆ (p∪c)[i]};
recovery_time(p, c) = recovery_gen(p, c) - reaction_gen(p, c);

That makes the eater1's recovery time 3 ticks, which smakes sense in a catalyst-program's perspective, but not so much in Real Life(TM), I guess.
Best wishes to you, Scorbie

Scorbie

Posts: 1368
Joined: December 7th, 2013, 1:05 am

### Re: Unproven conjectures

Is the smallest possible Garden of Eden known?
Life is hard. Deal with it.
My favorite oscillator of all time:
x = 7, y = 3, rule = B3-r4j/S2-i3
o5bo\$2o3b2o\$b2ob2o!

Hdjensofjfnen

Posts: 800
Joined: March 15th, 2016, 6:41 pm
Location: (394234, -234231)

### Re: Unproven conjectures

Hdjensofjfnen wrote:Is the smallest possible Garden of Eden known?

Probably not. There are no Gardens of Eden inside 6x6, as proved by exhaustive search. Extending that search to 6x7 or 7x7 will be quite a computational feat -- roughly 30 times or 8000 times as much work, respectively, as the 6x6 case.

My guess would be that all 7x7 patterns have at least one predecessor, and quite possibly all 8x8 patterns also. There might be a Garden of Eden hiding inside 9x9. Steven Eker has almost made it down to 9x10, but it appears to be very difficult to get rid of those last few cells sticking out into 9x11.

dvgrn
Moderator

Posts: 5208
Joined: May 17th, 2009, 11:00 pm

### Re: Unproven conjectures

What is the smallest pattern that has exactly one father?
Life is hard. Deal with it.
My favorite oscillator of all time:
x = 7, y = 3, rule = B3-r4j/S2-i3
o5bo\$2o3b2o\$b2ob2o!

Hdjensofjfnen

Posts: 800
Joined: March 15th, 2016, 6:41 pm
Location: (394234, -234231)

### Re: Unproven conjectures

dvgrn wrote:
simsim314 wrote:
Tom Mazanec wrote:How about things where we don't even have a conjecture as to the answer, much less a theorem?

I've demonstrated the concept of constructible ship of any speed and direction - but the period of the constructed speed is extremely high. It's completely unknown and we don't have any clue whether there exists ships with relatively low period and very high speed...

A huge number of existence questions are like this. The answer is "yes" or "no", but there isn't enough information to come up with even an educated guess.

Is there a true period-14 glider gun inside a 50x50 box?
Is there a glider collision that produces a 4x4 array of blocks?
Is there a 16x16 methuselah that takes more than a billion ticks to stabilize?
Is there a stable reflector smaller than a Snark?
Is there a 2c/3 signal elbow with a repeat time less than 20?
Is there a two-engine Cordership using a lucky clean c/12 debris-burning reaction?

... I'd guess yes, yes, no, yes, yes, no, but what do I know really? These aren't particularly long-standing or important questions, by the way -- there are hundreds more just like them.

I'd guess no, yes, no, no, yes, no.
Almost c/2:
x = 19, y = 10, rule = LifeHistory
.A.DA.C.2D\$.2C.A2.A3.A2.A.2C\$.CA.2D7.2D.AC\$DC2.2A7.2A2.CD\$2A15.2A!
#C [[ STOP 2 ]]
Hunting

Posts: 585
Joined: September 11th, 2017, 2:54 am
Location: Universe

### Re: Unproven conjectures

There is a known 2-engine Cordership.
What do you do with ill crystallographers? Take them to the mono-clinic!

calcyman

Posts: 1897
Joined: June 1st, 2009, 4:32 pm

### Re: Unproven conjectures

calcyman wrote:There is a known 2-engine Cordership.

Oh, I forget that.
Almost c/2:
x = 19, y = 10, rule = LifeHistory
.A.DA.C.2D\$.2C.A2.A3.A2.A.2C\$.CA.2D7.2D.AC\$DC2.2A7.2A2.CD\$2A15.2A!
#C [[ STOP 2 ]]
Hunting

Posts: 585
Joined: September 11th, 2017, 2:54 am
Location: Universe

### Re: Unproven conjectures

A billion ticks is a lot.

KittyTac

Posts: 533
Joined: December 21st, 2017, 9:58 am

### Re: Unproven conjectures

A classic time-traveler paradox involves accidentally becoming one's own parent.

Are there any Still Life objects where the only father is themselves?
EdPeggJr

Posts: 5
Joined: September 27th, 2018, 3:31 pm

### Re: Unproven conjectures

EdPeggJr wrote:A classic time-traveler paradox involves accidentally becoming one's own parent.

Are there any Still Life objects where the only father is themselves?

This question showed up on the previous page of this thread, in a couple of variants:

Conjecture: No still life can be constructed such that every possible predecessor pattern contains the same set of ON cells.
(The existence of one of these would disprove the "All still lifes can be synthesized by colliding salvos of gliders" conjecture, among other things.)

Conjecture: No oscillator or spaceship can be constructed such that the only predecessors include the same oscillator or spaceship (some fading junk around the edges not being counted).
(The LifeWiki Did-You-Know form is as follows: It is currently an open question whether there exists a periodic pattern whose only predecessors are its own evolutionary sequence.)

It's also in the Open Problems list on the LifeWiki, listed as having been posed in LifeLine Volume 6 by John Conway Himself -- the "unique father problem". Not sure if the \$50 prize is still available, or if there was some kind of statute of limitations on it... but in either case the problem is definitely still open.

dvgrn
Moderator

Posts: 5208
Joined: May 17th, 2009, 11:00 pm

### Re: Unproven conjectures

Oh, of course. The Unique father problem.
Are there any handy father-finding programs? I'd like to see other fathers for this pattern.

x = 9, y = 9, rule = B3/S23
4bo\$3bobo\$2bobobo\$bo2bo2bo\$ob2ob2obo\$bo2bo2bo\$2bobobo\$3bobo\$4bo!
EdPeggJr

Posts: 5
Joined: September 27th, 2018, 3:31 pm

### Re: Unproven conjectures

Wait...ARE there parents for that? My mind says it's really unlikely that that...thing has any nontrivial parents whatsoever But of course it's probably wrong of me to assume that.

EDIT: Oh, here's one from catagolue:
x = 31, y = 31, rule = B3/S23
oobobooobbbbbbbooboooboobobbbbo\$
oobbboboboooboobbbbboooboooooob\$
bbbbbobboobbboboobbbobobobbobob\$
obboobooobobooboobboooooobbooob\$
bbboooobooooobboboobboooboobbob\$
ooobooboobbooobobbboobboooobboo\$
obboobbobbbobbobooboobobbobooob\$
ooboboooobobobooobboobbobooobbo\$
bbooooboobobbooobbooboobobooooo\$
boobobbbbboobobobbbbobobbboobob\$
boboobbooooobobbobobooboooboooo\$
bobbooobboobobobbbobbboooobobbo\$
bbbooobobbboboboooboobobbbobbbo\$
booobobbooobooboboobbbbbobobbbb\$
bobbbbooobbobbbobbobobboobboobo\$
oboooobooobbooooooobboooboooobo\$
oboobboobbobobbobbbobbooobbbbob\$
bbbbobobbbbbooboboobooobbobooob\$
obbbobbboboobooobobobbbobooobbb\$
obboboooobbbobbboboboobbooobbob\$
ooooboooboobobobbobooooobboobob\$
boboobbbobobbbboboboobbbbboboob\$
ooooobobooboobbooobbobooboooobb\$
obbooobobboobbooobobobooooboboo\$
booobobbobooboobobbobbbobboobbo\$
oobboooobboobbbobooobbooboobooo\$
bobboobooobboobobboooooboooobbb\$
booobboooooobboobooboboooboobbo\$
bobobbobobobbboobobbboobbobbbbb\$
boooooobooobbbbboobooobobobbboo\$
obbbbobooboooboobbbbbbboooboboo!

That's my most frequently used 'parent finder', but I think you can get WLS/JLS to do it. Idk
Please stop using my full name. Refer to me as dani.

she/they

"I'm always on duty, even when I'm off duty." -Cody Kolodziejzyk, Ph.D.

danny

Posts: 870
Joined: October 27th, 2017, 3:43 pm
Location: i love to eat bees

### Re: Unproven conjectures

danny wrote:[Catagolue]'s my most frequently used 'parent finder', but I think you can get WLS/JLS to do it.

Yup. In JLS, if you just want to find a simple predecessor, you choose a search size under Edit > Properties, and also set the number of generations to 2 and in the Tiling/translation tab set the "After the last generation is..." setting to Unknown.

Then in generation 1, draw all OFF cells (select all, then right-click), then draw the ON cells you want. In generation 0, draw all OFF cells also, then hollow out an area of empty cells where you want to allow either ON or off.

For a challenging search, it's often important to set the search options correctly -- Search > Options > Sorting and Search > Options > Constraints. Maybe the most important detail is to try to start the search from the most difficult point and work outwards from there. If you start the search in an easy corner somewhere with a lot of possibilities, JLS will take enormously longer, or sometimes roughly forever, to get through the entire search. If you start the search in the right place, it will be able to eliminate huge swaths of the search space without having to fill in those easy corners in all possible ways.

Here's a .jdf file that shows a sample setup. Run it and in a second or two it will report 11,902 father patterns for the pattern in question, inside the arbitrary space I defined for Generation 0.

sample-parent-search.jdf.txt
Sample setup with unnecessarily large area (but you should leave a couple of blank cells around the edges, like the top and bottom here)

If you want to actually see the solutions it finds, change the "Pause search after each solution" and/or "Append solutions to file" settings in Search > Options > Processing.

dvgrn
Moderator

Posts: 5208
Joined: May 17th, 2009, 11:00 pm