Either way, the part in italics should now be updated IMO.77topaz wrote:Technically, it doesn't actually fit in a 50*50 box, though.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)
Unproven conjectures

 Posts: 795
 Joined: May 30th, 2016, 8:47 pm
 Location: Milky Way Galaxy: Planet Earth
Re: Unproven conjectures
Code: Select all
x = 81, y = 96, rule = LifeHistory
58.2A$58.2A3$59.2A17.2A$59.2A17.2A3$79.2A$79.2A2$57.A$56.A$56.3A4$27.
A$27.A.A$27.2A21$3.2A$3.2A2.2A$7.2A18$7.2A$7.2A2.2A$11.2A11$2A$2A2.2A
$4.2A18$4.2A$4.2A2.2A$8.2A!
Re: Unproven conjectures
I think this one is somewhat easier to tackle than others; Is it proved?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.)
The definition of "recovery time" of a catalyst isn't very welldefined, 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:
Code: Select all
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);
 Hdjensofjfnen
 Posts: 1727
 Joined: March 15th, 2016, 6:41 pm
 Location: r cis θ
Re: Unproven conjectures
Is the smallest possible Garden of Eden known?
Code: Select all
x = 5, y = 9, rule = B3jqr/S01c2in3
3bo$4bo$o2bo$2o2$2o$o2bo$4bo$3bo!
Code: Select all
x = 7, y = 5, rule = B3/S2i3y4i
4b3o$6bo$o3b3o$2o$bo!
Re: Unproven conjectures
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.Hdjensofjfnen wrote:Is the smallest possible Garden of Eden known?
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.
 Hdjensofjfnen
 Posts: 1727
 Joined: March 15th, 2016, 6:41 pm
 Location: r cis θ
Re: Unproven conjectures
What is the smallest pattern that has exactly one father?
Code: Select all
x = 5, y = 9, rule = B3jqr/S01c2in3
3bo$4bo$o2bo$2o2$2o$o2bo$4bo$3bo!
Code: Select all
x = 7, y = 5, rule = B3/S2i3y4i
4b3o$6bo$o3b3o$2o$bo!
Re: Unproven conjectures
I'd guess no, yes, no, no, yes, no.dvgrn wrote: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.simsim314 wrote: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...Tom Mazanec wrote:How about things where we don't even have a conjecture as to the answer, much less a theorem?
Is there a true period14 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 twoengine Cordership using a lucky clean c/12 debrisburning reaction?
... I'd guess yes, yes, no, yes, yes, no, but what do I know really? These aren't particularly longstanding or important questions, by the way  there are hundreds more just like them.
Forgotten.
Re: Unproven conjectures
There is a known 2engine Cordership.
What do you do with ill crystallographers? Take them to the monoclinic!
Re: Unproven conjectures
Oh, I forget that.calcyman wrote:There is a known 2engine Cordership.
Forgotten.
Re: Unproven conjectures
A billion ticks is a lot.
Re: Unproven conjectures
A classic timetraveler paradox involves accidentally becoming one's own parent.
Are there any Still Life objects where the only father is themselves?
Are there any Still Life objects where the only father is themselves?
Re: Unproven conjectures
This question showed up on the previous page of this thread, in a couple of variants:EdPeggJr wrote:A classic timetraveler paradox involves accidentally becoming one's own parent.
Are there any Still Life objects where the only father is themselves?
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.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 DidYouKnow form is as follows: It is currently an open question whether there exists a periodic pattern whose only predecessors are its own evolutionary sequence.)
Re: Unproven conjectures
Oh, of course. The Unique father problem.
Are there any handy fatherfinding programs? I'd like to see other fathers for this pattern.
Are there any handy fatherfinding programs? I'd like to see other fathers for this pattern.
Code: Select all
x = 9, y = 9, rule = B3/S23
4bo$3bobo$2bobobo$bo2bo2bo$ob2ob2obo$bo2bo2bo$2bobobo$3bobo$4bo!

 Posts: 1222
 Joined: October 27th, 2017, 3:43 pm
 Location: Somewhere in a Sparse Life soup, forming into a giant spaceclearing replicator.
 Contact:
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:
That's my most frequently used 'parent finder', but I think you can get WLS/JLS to do it. Idk
EDIT: Oh, here's one from catagolue:
Code: Select all
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!
d
Re: Unproven conjectures
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.danny wrote:[Catagolue]'s my most frequently used 'parent finder', but I think you can get WLS/JLS to do it.
Then in generation 1, draw all OFF cells (select all, then rightclick), 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.
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.
 Hdjensofjfnen
 Posts: 1727
 Joined: March 15th, 2016, 6:41 pm
 Location: r cis θ
Re: Unproven conjectures
Does there exist a synthesis for every billiard table?
Does there exist a glider synthesis for every stable object?
Does there exist a glider synthesis for every stable object?
Code: Select all
x = 5, y = 9, rule = B3jqr/S01c2in3
3bo$4bo$o2bo$2o2$2o$o2bo$4bo$3bo!
Code: Select all
x = 7, y = 5, rule = B3/S2i3y4i
4b3o$6bo$o3b3o$2o$bo!
 testitemqlstudop
 Posts: 1368
 Joined: July 21st, 2016, 11:45 am
 Location: in catagolue
 Contact:
Re: Unproven conjectures
or you can use LLS, it's simplerdvgrn wrote: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.danny wrote:[Catagolue]'s my most frequently used 'parent finder', but I think you can get WLS/JLS to do it.
Then in generation 1, draw all OFF cells (select all, then rightclick), 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.
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.
Re: Unproven conjectures
The answer to both those questions is the same: It is unknown whether there exists a glider synthesis for every still life or for every oscillator. I'm not sure if it would be worthwhile making a distinction between billiard tables and other oscillators.Hdjensofjfnen wrote:Does there exist a synthesis for every billiard table?
Does there exist a glider synthesis for every stable object?
For the second of those about stable objects you can find some discussion in this very thread, as well as elsewhere on this board. From the top of the first page:
dvgrn wrote:Conjecture: All still lifes can be synthesized by colliding salvos of gliders.
(All still lifes up to 18 bits have a known glider synthesis, but it is still not known whether all still lifes are synthesizable.)
The latest version of the 5S Project contains over 226,000 spaceships. There is also a GitHub mirror of the collection. Tabulated pages up to period 160 (out of date) are available on the LifeWiki.
Currently inactive here due to a severe case of LWTDS.
Currently inactive here due to a severe case of LWTDS.
Re: Unproven conjectures
Well, I guess that can't exist. Even though there are many still life They are composed by simple components.danny wrote:How would I go about searching for a still life with only one parent?
Forgotten.
Re: Unproven conjectures
You'd want to take a program that searches for GoEs and adapt it. You'd have to change two things, one is to make it only check still lives, and the other is to allow the pattern to have itself as a predecessor. I think you'd probably want to use the program in this paper. For each potential GoE it creates a SAT instance that asks for a predecessor of the pattern. The instance is satisfiable if and only if the pattern is not a GoE. So you would want to add clauses to the SAT instance that ban the predecessor from being the pattern itself. You'd then want to find some quick way to find still lives to feed into this program. I think Nathaniel has been working on some stilllife generating projects so he might have such a program.danny wrote:How would I go about searching for a still life with only one parent?
Re: Unproven conjectures
There's a little more defining and decisionmaking that might have to be done. Any still life is guaranteed to have multiple predecessors by normal definitions: just pick any edge and add a single cell or a domino spark or whatever, to make a new larger cluster, but the spark fades away harmlessly. At worst you can always duplicate the entire outermost edge of the still life two cells away. Still life edges can't have more than two cells next to each other, so the line of dots and dominos on the other side of the temporary gutter will always fade in one tick.Macbi wrote:You'd want to take a program that searches for GoEs and adapt it. You'd have to change two things, one is to make it only check still lives, and the other is to allow the pattern to have itself as a predecessor.danny wrote:How would I go about searching for a still life with only one parent?
If for some reason you want the parent to be connected in the same way as the still life, we should be able to enumerate all possible width2 strips of edges of valid still lifes  say for a 12x3 strip  and then I bet we can show for each one that there's some modification that adds one or more cells toward the center of the adjacent row, such that the ends of the strip aren't affected but the strip converges to the same still life after one tick.
In other words, Dvgrn's Incautious Conjecture is that there are multiple parents of every 10x4 strip of still life edge with one blank row, even if you only alter the centered 8x3 section of the strip that includes the blank row.
It might not be an impossible task these days to enumerate all of those strips, and then run each one through LLS and find a nontrivial predecessor. But maybe just doing the enumeration would suggest a line of attack that would simplify the proof of nonexistence. Start with smaller strips and see if a centered 4x3 or 5x3 or 6x3 section is enough, maybe?
 I should probably have said sooner that this is all something of a wild herring, or a red goose chase, or whatever you call it. Conway's statement of the problem from LIFELINE 6:1 is "is there a stable configuration whose only father is itself (with some fading junk some distance away not being counted)?" Slightly extending that, I think it's okay if the edges of a still life can have multiple parents, as long as there's an MxN chunk in the middle that is common to all possible ancestors.
It seems intuitively unlikely to me that any such MxN chunk is possible. But do we have enough computing power these days to enumerate all possible MxN chunks consistent with stilllifeishness, and then find a way to alter each center (M2)*(N2) area in a way that converges back to the same MxN chunk? ... Maybe we do, actually. Would that be not good enough for some reason? What did I miss?
Re: Unproven conjectures
This is all strongly related to the question of whether every still life is synthesizable. In order to demonstrate that not every still life is synthesizable it would suffice to produce a arrangement of alive and dead cells which could be extended to a still life and such that the parent of any pattern containing that arrangement also contained that arrangement in the same place.
If we wanted to disprove that such an arrangement existed then one way to do it would be to find by computer search some M and N such that for every N×M pattern that can extend to a still life there are some cells in the interior (N2)×(M2) rectangle that can be changed to produce a parent.
If we wanted to disprove that such an arrangement existed then one way to do it would be to find by computer search some M and N such that for every N×M pattern that can extend to a still life there are some cells in the interior (N2)×(M2) rectangle that can be changed to produce a parent.
Re: Unproven conjectures
That seems like a good short modern restatement of Conway's uniquefather problem. I guess I never noticed before that that conjecture isn't very well named. Seems like "unique father" ought to mean "find a pattern that has only one parent", but it actually means "find a stable pattern where some part in the middle of it has only one parent".Macbi wrote:This is all strongly related to the question of whether every still life is synthesizable. In order to demonstrate that not every still life is synthesizable it would suffice to produce a arrangement of alive and dead cells which could be extended to a still life and such that the parent of any pattern containing that arrangement also contained that arrangement in the same place.
Anyway, yeah, I'd definitely put my research time on the "disprove that such an arrangement exists" side of that idea. I think that these days we might actually be able to exhaustively search MxN rectangles until we find parents for every possible (M2)x(N2) stilllifecompatible configuration.
That doesn't mean that I'd bet on all still lifes being synthesizable, though. I still vaguely suspect there's an unsynthesizable still life out there somewhere. But I'm glad I don't have to prove it. My real bet would be that neither a proof nor a disproof will be coming along in my lifetime.
 Hdjensofjfnen
 Posts: 1727
 Joined: March 15th, 2016, 6:41 pm
 Location: r cis θ
Re: Unproven conjectures
Maybe unrelated, but does anyone have a proof that any speed greater than c/4 diagonal is unachievable in Life? After all, there's a 2c/7 in a rule one transition from Life:
Code: Select all
x = 5, y = 5, rule = B3/S234w
3o$b2o$2b3o$3b2o$4bo!
Code: Select all
x = 5, y = 9, rule = B3jqr/S01c2in3
3bo$4bo$o2bo$2o2$2o$o2bo$4bo$3bo!
Code: Select all
x = 7, y = 5, rule = B3/S2i3y4i
4b3o$6bo$o3b3o$2o$bo!
Re: Unproven conjectures
Here: http://www.njohnston.ca/2009/10/spacesh ... automata/Hdjensofjfnen wrote:Maybe unrelated, but does anyone have a proof that any speed greater than c/4 diagonal is unachievable in Life? After all, there's a 2c/7 in a rule one transition from Life:Code: Select all
x = 5, y = 5, rule = B3/S234w 3o$b2o$2b3o$3b2o$4bo!
Still drifting.