Unproven conjectures
 Tom Mazanec
 Posts: 31
 Joined: December 18th, 2017, 5:22 pm
Unproven conjectures
Are there any interesting unproven conjectures in the Game of Life?
Re: Unproven conjectures
Omniperiodicity is the big one, in my opinionthe question of whether there exists a oscillator for every possible period. Herschel conduits prove the existence of p58 and above, and snark loops prove p43 and above. Almost every period between p1 and p42 also has an example, except for p19, p34 (only trivial examples), and p38.
A p19 oscillator is the past piece of the puzzle to show that Life is sort of omniperiodic; a trivial p38 could be constructed from the p19 and a blinker. To show true omniperiodicity, however, one would need to provide a p19, p34, and p38 that have a cell that cycles at the full period.
A p19 oscillator is the past piece of the puzzle to show that Life is sort of omniperiodic; a trivial p38 could be constructed from the p19 and a blinker. To show true omniperiodicity, however, one would need to provide a p19, p34, and p38 that have a cell that cycles at the full period.
Tanner Jacobi
Coldlander, a novel, available in paperback and as an ebook. Now on Amazon.
Coldlander, a novel, available in paperback and as an ebook. Now on Amazon.
 Majestas32
 Posts: 547
 Joined: November 20th, 2017, 12:22 pm
 Location: 'Merica
Re: Unproven conjectures
You forgot p23 and p41.Kazyan wrote:Omniperiodicity is the big one, in my opinionthe question of whether there exists a oscillator for every possible period. Herschel conduits prove the existence of p58 and above, and snark loops prove p43 and above. Almost every period between p1 and p42 also has an example, except for p19, p34 (only trivial examples), and p38.
A p19 oscillator is the past piece of the puzzle to show that Life is sort of omniperiodic; a trivial p38 could be constructed from the p19 and a blinker. To show true omniperiodicity, however, one would need to provide a p19, p34, and p38 that have a cell that cycles at the full period.
Searching:
b2a5k6n7cs12i3ij4k5j8
b2a3c7cs12i
Currently looking for help searching these rules.
b2a5k6n7cs12i3ij4k5j8
b2a3c7cs12i
Currently looking for help searching these rules.
Re: Unproven conjectures
I did a quick pass through the LifeWiki DidYouKnow collection, and came up with these:Tom Mazanec wrote:Are there any interesting unproven conjectures in the Game of Life?
Conjecture: There are 16x16 infinitegrowth and quadraticgrowth random soups.
(The blocklaying switch engine and the gliderproducing switch engine, and various combinations of two switch engines, are the only infinitelygrowing patterns that are known to have ever occurred naturally from an asymmetric random starting configuration.)
Conjecture: Life is omniperiodic.
(Currently oscillators are known that oscillate at all periods other than 19, 23, 34, 38 and 41.)
Conjecture: there are an unlimited number of onecellthick oscillators.
(The blinker is the only known oscillator that is one cell thick.)
Conjecture: Starting from gliders sent one at a time with arbitrarily long delays between gliders, aimed at a single block target, it is possible to construct any Life object that can be constructed with any number of synchronized gliders  even if the gliders are restricted to one color and one phase.
(Several candidate universal constructors have been demonstrated. None have been formally proven to be universal, but Adam P. Goucher's 'slmake' search program is a convincing practical demonstration of a universal construction system. It was shown in 2014 that any salvo of gliders, no matter how tightly packed, can be constructed by crashing together gliders whose initial positions are farther apart than any chosen finite distance.
Conjecture: a highspeed oblique spaceship can be constructed using (13,1)c/31 reactions.
(The waterbear is the single known highspeed oblique spaceship, many orders of magnitude faster than Gemini spaceships and halfbaked knightships.)
Conjecture: There exists a direct 90degree 2c/3 wire elbow.
(There are no known direct reflectors for signals in 2c/3 wires, or for orthogonal lightspeed wire signals, but very large reflectors for 2c/3 wire signals or beehivechain lightspeed wire signals can be constructed using stable or periodic circuitry.)
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.)
Conjecture: All still lifes can be synthesized by colliding a number of gliders less than the population of the still life.
(This one seems unlikely for higher bit counts, actually. Still lifes up to 16 cells can be synthesized at a cost of less than one glider per cell.)
Conjecture: Any gliderconstructible Life pattern can be constructed with less than 1000 gliders.
(Any gliderconstructible Life pattern can be constructed with a some fixed maximum number of gliders N. N is the number of gliders required to construct a slidingblock decoder that converts the position of a very fardistant block into a slowsalvo recipe. The slowsalvo recipe constructs the required pattern and also builds whatever temporary structure is needed to destroy the decoder.)
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.)
Conjecture: Reasonably small "elementary" oblique spaceships exist  fitting in a 50x50 bounding box, let's say.
(A 79x31 elementary knightship was discovered on March 6, 2018, which fits inside a 2500cell bounding box but not inside 50x50.)
Conjecture: There exists a Garden of Eden inside a 4xN bounding box.
(It is known that no Garden of Eden patterns exist that are 1, 2, or 3 cells high, and Steven Eker found some 5cellhigh Gardens of Eden in 2016, but it is currently an open question whether a 4cellhigh GoE can be constructed.)
Conjecture: Patterns exist that have greatgreatgreatgrandparents but no greatgreatgreatgreatgrandparents.
(In 2016, patterns were found that have greatgreatgrandparents but no greatgreatgreatgrandparents. Examples of all limitedancestry patterns with fewer "great"s are already known.)
Conjecture: Any rectangular repetition of any 3x3 pattern can be shown to have at least one parent pattern  i.e. such a pattern is not a Garden of Eden.
(No way is known for a 3x3 pattern to be tiled into an MxN rectangle to produce a Garden of Eden, but there are 4x3, 4x4 and larger tiles that can be repeated in this way to produce GoEs.)
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
Thank you; I was going off a table that I must have misread.Majestas32 wrote:You forgot p23 and p41.
Tanner Jacobi
Coldlander, a novel, available in paperback and as an ebook. Now on Amazon.
Coldlander, a novel, available in paperback and as an ebook. Now on Amazon.
 praosylen
 Posts: 2434
 Joined: September 13th, 2014, 5:36 pm
 Location: Pembina University, Home of the Gliders
 Contact:
Re: Unproven conjectures
A special case of the glider synthesis conjecture that I find interesting: do all MxN arrays of adjacent blocks have glider syntheses? This is known to be the case for min(M,N) <= 3, but unknown as far as I know for greater values.
former username: A for Awesome
praosylen#5847 (Discord)
The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...
praosylen#5847 (Discord)
The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...
 Tom Mazanec
 Posts: 31
 Joined: December 18th, 2017, 5:22 pm
Re: Unproven conjectures
dvgrn
I thought conjectures by definition were things unknown, if suspected, or I would have checked the Did you know
I thought conjectures by definition were things unknown, if suspected, or I would have checked the Did you know
Re: Unproven conjectures
Yeah, I picked out the Did You Knows that said things like "It is an open question whether..." And for some of them I kind of stretched the definition, but most of the list is in fact things that are technically unknown but suspected  often very strongly suspected.Tom Mazanec wrote:dvgrn
I thought conjectures by definition were things unknown, if suspected, or I would have checked the Did you know[s]
It would be a huge shock if it were somehow proved absolutely that Life isn't omniperiodic
... or that there's no knightship inside a 50x50 box
... or if there are no greatgreatgreatgreatgrandparentless patterns that have greatgreatgreatgrandparents
... or even if there's no onecellthick spaceship, since there are some ideas worked out for how that might be possible.
But in most cases, while a proof of nonexistence seems incredibly unlikely, the only likely proof of existence is a proof by construction  and since nobody has put together an explicit example of these things yet, they are still technically conjectures.
For some of the others the negative form of the conjecture might be more likely to be true, like the "All still lifes can be synthesized by colliding salvos of gliders." As A for awesome says, it's not clear how to construct even a large grid of MxN blocks, let alone a hollow rectangle with delicately balanced junk hiding in the middle. Then again, people have gotten a lot better at incremental constructions recently  who's to say that the trend might not continue?
Anyway, I do think the list includes a fair fraction of known longstanding Conway's Life conjectures  not counting ones that have already been formally proven or disproven, like the Coolout Conjecture, the constructability of all finite glider salvos, the Grandfather Problem, etc.
 Tom Mazanec
 Posts: 31
 Joined: December 18th, 2017, 5:22 pm
Re: Unproven conjectures
How about things where we don't even have a conjecture as to the answer, much less a theorem?
Re: Unproven conjectures
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, say is there a ship with speed of 499c/1000, with period 1000, we don't even know if there is 4c/9 ship with p9 but we guess there is, for higher periods we don't have a clue.Tom Mazanec wrote:How about things where we don't even have a conjecture as to the answer, much less a theorem?
Re: Unproven conjectures
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?
EDIT: YES on this last one. Let's change it to "oneengine Cordership".
... 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.
Re: Unproven conjectures
I think the existence of a (2,1)c/6 knightship is also pretty difficult to guess. A least for omniperiodicity you can imagine finding a fast signalturner and therefore being able to build oscillators of all periods. But I see no way at all to build a maxspeed knightship with any kind of technology. You just have to hope one appears.
Re: Unproven conjectures
True enough. I put that one in my earlier "conjectures" list, because I think the partials found so far suggest a near100% probability that there's a way to finish a (2,1)c/6 knightship inside 50x50 or so... and that an omniscient being would know what that way is, even if it's too big for any nearfuture quantum computer to find. So for me it's in the Conjecture Category  I kind of assume it's true, it's just apparently too hard to prove at the moment.Macbi wrote:I think the existence of a (2,1)c/6 knightship is also pretty difficult to guess. A least for omniperiodicity you can imagine finding a fast signalturner and therefore being able to build oscillators of all periods. But I see no way at all to build a maxspeed knightship with any kind of technology. You just have to hope one appears.
 It occurs to me that if some (pre1970) religion's holy book turned out to have a working (2,1)c/6 knightship encoded in one of its verses, I might have to seriously consider becoming a convert...
Re: Unproven conjectures
I counterconjecture Dave's claim about the existence of a 16x16 Methuselah with a stabilisation time exceeding 10^9. I strongly believe such patterns do exist.
As evidence, there's a b38s23/C1 soup which takes 750 000 ticks to stabilise, and it's entirely conceivable that analogous patterns exist in b3s23. 2^256 is a very large number, after all.
Also, there's a 'lucky 1engine Cordership' where a c/12 universal constructor or swarm of diagonal Caterloopillars chases a blocklaying switch engine and removes its debris. You'll need some very arbitrary definition to disallow that as a 'switch engine with complicated clean exhaust'.
As evidence, there's a b38s23/C1 soup which takes 750 000 ticks to stabilise, and it's entirely conceivable that analogous patterns exist in b3s23. 2^256 is a very large number, after all.
Also, there's a 'lucky 1engine Cordership' where a c/12 universal constructor or swarm of diagonal Caterloopillars chases a blocklaying switch engine and removes its debris. You'll need some very arbitrary definition to disallow that as a 'switch engine with complicated clean exhaust'.
What do you do with ill crystallographers? Take them to the monoclinic!
Re: Unproven conjectures
Hmm, so you'll win if you can prove such patterns' existence  probably by finding an actual 16x16 soup example that fails to settle until after T=10^9. I'll win if as soon as I finish running through all 2^256 such patterns and show that all of them settle by T=10^9. (Ha, ha. I'd have the Great Prophet Zarquon give a report at the Restaurant at the End of the Universe, except that won't be nearly long enough.) Or as soon as I produce a clever proof that no 16x16 pattern can remain chaotic for that long... but I strongly believe that no such proof is possible.calcyman wrote:I counterconjecture Dave's claim about the existence of a 16x16 Methuselah with a stabilisation time exceeding 10^9. I strongly believe such patterns do exist.
As evidence, there's a b38s23/C1 soup which takes 750 000 ticks to stabilise, and it's entirely conceivable that analogous patterns exist in b3s23. 2^256 is a very large number, after all.
I suspect we're going to be stuck in our current state of somebodyiswrongbutwedon'tknowwho, for quite a long time... though it certainly might evolve into "weknowDaveiswrongbutwecan'tproveit" sooner or later.
 I did think for a good while about that 10^9 number. My original statement was just "no 16x16 methuselah takes more than a million ticks to stabilize"  but I wasn't at all confident about that one.
After some discussion of methuselah power laws with Nathaniel way back in 2009, for 20x20 soups, the rough guess we came up with was that the most longlived 20x20 "normal methuselah" (that just makes a large patch of random ash) would end up lasting something like 200,000 to 500,000 ticks. That's way too close to a million for comfort, though 20x20 is a lot bigger than 16x16.
Jumping up to a billiontick limit makes it pretty sure that any superlonglasting methuselah won't be a simple randomash generator. Instead it will probably be something that produces occasional gliders aimed at some central junk, to keep chaos going as long as possible.
The likeliest arrangement might be a 16x16 predecessor of a pattern vaguely along the following lines. (This is from an offline discussion of "soup eye candy" with Bill Gosper in May 2015.)
The above pattern does last a fair fraction of a billion ticks  but it's from a 32x32 symmetric soup. There are only 2^32 (or somewhere around there) 16x16 soups with that symmetry, and if we want to, we _could_ run through all of those and show that none of them survive more than a billion ticks.The simplest version of that kaleidoscopemaker [~19.7M ticks to settle] takes a similar length of time to stabilize [~17.7M ticks]:
Now I'm thinking about the umpteen gazillion ways of scattering, say, no more than eighty cells' worth of still lifes symmetrically in the center of the above circle. I bet the time to stabilization follows some kind of interesting powerlaw distribution... so there should be an occasional arrangement that runs billions of ticks before stabilizing.Code: Select all
x = 60, y = 60, rule = B3/S23 21bo16bo$20bobo14bobo2$20bo2bo12bo2bo$22b2o12b2o$23bo12bo15$bobo52bobo $o58bo$bo2bo50bo2bo$3b3o48b3o13$3b3o48b3o$bo2bo50bo2bo$o58bo$bobo52bob o15$23bo12bo$22b2o12b2o$20bo2bo12bo2bo2$20bobo14bobo$21bo16bo!
I was going to postulate a trilliontick kaleidoscope, but it would take a Catagoluesized effort to locate that, I suppose.
Maybe there's an equivalent mechanism that only needs fourfold symmetry, and 2^64 is a much less tractable search problem... but I'm not sure that even 2^64 is big enough to make a billiontick methuselah very likely.
(Heh, I've been wrong before, though, and will be happy to be proved wrong again  with an actual counterexample !)
Yes... but... 2^256 may be a very big number, but it's not nearly big enough to have any realistic chance of including any Caterloopillar or universalconstructor predecessors. I think you're meaning that we can't rule out the possibility that there's a lucky oneengine Cordership with a smallish exhaust eater that happens to have a 16x16 predecessor. That's certainly true. On the other hand, it's also equally (!?) possible that no such thing exists. In the absence of an example it's hard to assign probabilities either way.calcyman wrote:Also, there's a 'lucky 1engine Cordership' where a c/12 universal constructor or swarm of diagonal Caterloopillars chases a blocklaying switch engine and removes its debris. You'll need some very arbitrary definition to disallow that as a 'switch engine with complicated clean exhaust'.
In any case, I don't think I agree that a definition of "methuselah" would be arbitrary in the least, if it disallows that case. You can run those trailing cleanup objects for as long as needed to detect the regularity, and you can track the evolution backwards to find the point where the last irregularity disappeared. That point of disappearance is the timetostability of the methuselah. It would be a big pain to write an algorithm that is sure to automatically catch any possible weird case along those lines, but that doesn't mean there's anything wrong with the definition.
What I'd _like_ to see someday is one of the much more interesting cases that I'm sure is out there somewhere in CAland. An example would be a randomash spacefiller that provably grows forever, but builds some kind of nonrepeating quasicrystal structure.
Re: Unproven conjectures
That statement (beyond the 'Also,') was in reference to your sixth question, which didn't impose any size restrictions whatsoever (other than there being <= 2 switchengines in the construction). So I think both of your 'no's should be 'yes's, and I generally agree with the other 'yes's.dvgrn wrote:Yes... but... 2^256 may be a very big number, but it's not nearly big enough to have any realistic chance of including any Caterloopillar or universalconstructor predecessors. I think you're meaning that we can't rule out the possibility that there's a lucky oneengine Cordership with a smallish exhaust eater that happens to have a 16x16 predecessor. That's certainly true. On the other hand, it's also equally (!?) possible that no such thing exists. In the absence of an example it's hard to assign probabilities either way.calcyman wrote:Also, there's a 'lucky 1engine Cordership' where a c/12 universal constructor or swarm of diagonal Caterloopillars chases a blocklaying switch engine and removes its debris. You'll need some very arbitrary definition to disallow that as a 'switch engine with complicated clean exhaust'.
With the possible exception of the small trueperiod p14 glider gun; I see no reason why it should exist. But I'd like to ask another hypothetical question:
 Does there exist a p7 3c/7orthogonal glider backrake?
With a GPU version of an existing search program, this is probably within the GoL community's current resources.
The interesting thing about the Methuselah Stabilisation Function M(n)  i.e. the longest stabilisation time amongst all nbyn patterns which stabilise  is that it grows relatively slowly (polynomially?) for small values of n, but it can be proved that for sufficiently large n (maybe 10000 or so) it overtakes the Busy Beaver function BB(n).dvgrn wrote: I did think for a good while about that 10^9 number. My original statement was just "no 16x16 methuselah takes more than a million ticks to stabilize"  but I wasn't at all confident about that one.
After some discussion of methuselah power laws with Nathaniel way back in 2009, for 20x20 soups, the rough guess we came up with was that the most longlived 20x20 "normal methuselah" (that just makes a large patch of random ash) would end up lasting something like 200,000 to 500,000 ticks. That's way too close to a million for comfort, though 20x20 is a lot bigger than 16x16.
Yes, I agree; the 750k methuselah in b38s23/C1 had a similar design, but with only one puffer emitting backward gliders. But if the frequency of a backwardglideremitting puffer in b3s23/C1 is 2^50  which I think is pessimistic  then we can expect about 2^150 soups with two perpendicular backwardglideremitting puffers. I'd be very surprised if none of these happen to last for over 10^9 ticks.Jumping up to a billiontick limit makes it pretty sure that any superlonglasting methuselah won't be a simple randomash generator. Instead it will probably be something that produces occasional gliders aimed at some central junk, to keep chaos going as long as possible.
The likeliest arrangement might be a 16x16 predecessor of a pattern vaguely along the following lines. (This is from an offline discussion of "soup eye candy" with Bill Gosper in May 2015.)
What do you do with ill crystallographers? Take them to the monoclinic!
Re: Unproven conjectures
Ah, I missed the jump to the sixth question! That makes much more sense.calcyman wrote:That statement (beyond the 'Also,') was in reference to your sixth question, which didn't impose any size restrictions whatsoever (other than there being <= 2 switchengines in the construction).dvgrn wrote:Yes... but... 2^256 may be a very big number, but it's not nearly big enough to have any realistic chance of including any Caterloopillar or universalconstructor predecessors. I think you're meaning that we can't rule out the possibility that there's a lucky oneengine Cordership with a smallish exhaust eater that happens to have a 16x16 predecessor... (?)
To clarify, my intention was to include some kind of reasonable size restriction, but you're right that I didn't make that explicit. (Bah, humbug.)
That's certainly one of the more speculative items on my list. I've tried running WLS searches for such things, and of course that's way too ambitious and WLS doesn't even come close to returning anything... but they certainly don't return zero results!calcyman wrote:With the possible exception of the small trueperiod p14 glider gun; I see no reason why it should exist.
Based on what little I saw, my intuition suggests that there's probably a p14 structure out there somewhere that spits out a glider every fourteen ticks and then recovers. The search space seems to be plenty large enough. But I don't expect to be able to find it, any more than you expect to find the billiontick 16x16 methuselah any time soon.
2^150 seems high to me, just because the soupeyecandy situation requires perfectly synchronized backwardglideremitting puffer pairs hitting completely symmetric junk. If they're not synchronized and symmetric, there are various mechanisms that tend to shut down novelty generation a lot quicker on average.calcyman wrote:if the frequency of a backwardglideremitting puffer in b3s23/C1 is 2^50  which I think is pessimistic  then we can expect about 2^150 soups with two perpendicular backwardglideremitting puffers. I'd be very surprised if none of these happen to last for over 10^9 ticks.
 There's a reason why zz_LINEAR stuff is only showing up in symmetric soups in Catagolue, right? Of course the occasional 16x16 soup _is_ symmetric, or will evolve into something symmetric... but only a very tiny fraction of those will have backwardglideremitting puffers. My estimate would be more like 2^128 times your frequency guess of 2^50, so a "mere" 2^78 cases that might last a long time.

I wrote a bunch more crackpot stuff about power laws eating away at 2^78 pretty quickly (depending on the details)  but the above calculations are quite likely completely irrelevant.
If there are enough ways that, say, three or four backwardglideremitting puffers could interact to produce messy quadratic growth, then there might well be 2^256 / (2^50)^4) =~2^100 or 2^50 of those cases to hunt for methuselahs in. Even a messy quadraticgrowth pattern might settle into predictability eventually, but it seems like an arrangement like that might produce a billiontick methuselah a lot more reliably than the soupeyecandy symmetric method.
A slightly different angle on the same idea: is there a way to calculate roughly the odds of any of Nick Gotts' longerlived Patterns with Eventful Histories mechanisms being generated from a random 16x16 soup? This one, for example, keeps being eventful long enough to make a billion ticks look like chump change:
Code: Select all
#C nikknikkm1r90w4s164
x = 38, y = 198, rule = S23/B3
6bo$5bobo$$4bobbo$4boo$4bo25$34bobo$37bo$33bobbo$32b3o131$28bo3bo$29bo
bo$30bobbo$33bo$33bo24$o$bo$bbo$bo$o$bb3o!
 Apple Bottom
 Posts: 1034
 Joined: July 27th, 2015, 2:06 pm
 Contact:
Re: Unproven conjectures
Just to link to it, there's also a (very incomplete, additionsandimprovementswelcome) article on the LifeWiki, here: http://conwaylife.com/wiki/Problem
If you speak, your speech must be better than your silence would have been. — Arabian proverb
Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_
Proud member of the Pattern Raiders!
Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_
Proud member of the Pattern Raiders!
 praosylen
 Posts: 2434
 Joined: September 13th, 2014, 5:36 pm
 Location: Pembina University, Home of the Gliders
 Contact:
Re: Unproven conjectures
Here's one from a different rule: There are no still lives besides the block, beehive, boat, ship, and long ship in B34/S23.
EDIT: False noncorollary deleted.
EDIT: False noncorollary deleted.
Last edited by praosylen on December 21st, 2017, 7:46 pm, edited 1 time in total.
former username: A for Awesome
praosylen#5847 (Discord)
The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...
praosylen#5847 (Discord)
The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...
 praosylen
 Posts: 2434
 Joined: September 13th, 2014, 5:36 pm
 Location: Pembina University, Home of the Gliders
 Contact:
Re: Unproven conjectures
Never mind.muzik wrote:How about these?
former username: A for Awesome
praosylen#5847 (Discord)
The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...
praosylen#5847 (Discord)
The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...
Re: Unproven conjectures
A significant question is still life finitization (I think it has been called that). I do not know if it is currently open. I have had some ideas and never made progress. It is hard but seems tractable (unless it's actually easy and I'm missing something).
The question is: given a still life without finite boundaries (e.g. covering the plane; it need not be periodic or have any other properties), can any MxN finite window of it be preserved within a finite still life by adding appropriate unchanging cells around it (no particular bounds on this, though the question could place size limits in terms of M and N).
A natural conjecture based on experience and the prevalence of still lifes is that there is some fairly small constant k such that any MxN window that exists within an infinite still life can be stabilized within an (M+k)x(N+k) still life.
For instance, take a still life consisting of alternating stripes. That is only stable when infinite, but it is not hard to select a rectangle inside it and add a boundary to stabilize it. This appears to be true for less regular still lifes as well.
The first idea I had was backtracking from a row of empty cells to a populated row. The first row facing empty space must not have more than two live cells adjacent, but it is unclear what conditions are on its successor. My guess is that after several iterations, the conditions are identical to a row within an infinite still life, but I don't see how to prove it (I thought about treating these rows as regular languages, which they are, but that hasn't helped).
The second idea, which seems more tractable, is to pick a specific window size (say 10x10). For any still life of this size including with unstable boundaries, if we remove all cells in a centered subwindow (say 6x6) can we restabilize the bordering cells leaving an empty subwindow (I think 2x2 is big enough). If so, we have an algorithm for "punching holes" in any infinite still life and should be able to separate finite windows from the infinite stabilizer given a succession of hole punches.
I believe the second approach is suitable to an automated proof, but it might not result in a very readable explanation of how it works.
Or, again has someone already figured this out (Noam Elkies?) using more elegant mathematics and am I just way behind the state of the art.
The question is: given a still life without finite boundaries (e.g. covering the plane; it need not be periodic or have any other properties), can any MxN finite window of it be preserved within a finite still life by adding appropriate unchanging cells around it (no particular bounds on this, though the question could place size limits in terms of M and N).
A natural conjecture based on experience and the prevalence of still lifes is that there is some fairly small constant k such that any MxN window that exists within an infinite still life can be stabilized within an (M+k)x(N+k) still life.
For instance, take a still life consisting of alternating stripes. That is only stable when infinite, but it is not hard to select a rectangle inside it and add a boundary to stabilize it. This appears to be true for less regular still lifes as well.
The first idea I had was backtracking from a row of empty cells to a populated row. The first row facing empty space must not have more than two live cells adjacent, but it is unclear what conditions are on its successor. My guess is that after several iterations, the conditions are identical to a row within an infinite still life, but I don't see how to prove it (I thought about treating these rows as regular languages, which they are, but that hasn't helped).
The second idea, which seems more tractable, is to pick a specific window size (say 10x10). For any still life of this size including with unstable boundaries, if we remove all cells in a centered subwindow (say 6x6) can we restabilize the bordering cells leaving an empty subwindow (I think 2x2 is big enough). If so, we have an algorithm for "punching holes" in any infinite still life and should be able to separate finite windows from the infinite stabilizer given a succession of hole punches.
I believe the second approach is suitable to an automated proof, but it might not result in a very readable explanation of how it works.
Or, again has someone already figured this out (Noam Elkies?) using more elegant mathematics and am I just way behind the state of the art.

 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
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)dvgrn wrote:Conjecture: Reasonably small "elementary" oblique spaceships exist  fitting in a 50x50 bounding box, let's say.
(No elementary knightships have been discovered as of 2016, but there has been at least one very close call.)
d
Re: Unproven conjectures
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)
 Apple Bottom
 Posts: 1034
 Joined: July 27th, 2015, 2:06 pm
 Contact:
Re: Unproven conjectures
Technically, Dave only stipulated that the ship should be "reasonably small", though. The 50x50 bounding box was merely an example of what that might mean.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)
If you speak, your speech must be better than your silence would have been. — Arabian proverb
Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_
Proud member of the Pattern Raiders!
Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_
Proud member of the Pattern Raiders!