Unproven conjectures

For general discussion about Conway's Game of Life.
Post Reply
User avatar
Tom Mazanec
Posts: 32
Joined: December 18th, 2017, 5:22 pm

Unproven conjectures

Post by Tom Mazanec » December 18th, 2017, 5:25 pm

Are there any interesting unproven conjectures in the Game of Life?

User avatar
Kazyan
Posts: 1247
Joined: February 6th, 2014, 11:02 pm

Re: Unproven conjectures

Post by Kazyan » December 18th, 2017, 5:48 pm

Omniperiodicity is the big one, in my opinion--the 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.
Tanner Jacobi
Coldlander, a novel, available in paperback and as an ebook. Now on Amazon.

User avatar
Majestas32
Posts: 549
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

Re: Unproven conjectures

Post by Majestas32 » December 18th, 2017, 6:00 pm

Kazyan wrote:Omniperiodicity is the big one, in my opinion--the 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.
You forgot p23 and p41.
Searching:
b2-a5k6n7cs12-i3ij4k5j8
b2-a3c7cs12-i

Currently looking for help searching these rules.

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

Re: Unproven conjectures

Post by dvgrn » December 18th, 2017, 7:14 pm

Tom Mazanec wrote:Are there any interesting unproven conjectures in the Game of Life?
I did a quick pass through the LifeWiki Did-You-Know collection, and came up with these:

Conjecture: There are 16x16 infinite-growth and quadratic-growth random soups.
(The block-laying switch engine and the glider-producing switch engine, and various combinations of two switch engines, are the only infinitely-growing 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 one-cell-thick 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 high-speed oblique spaceship can be constructed using (13,1)c/31 reactions.
(The waterbear is the single known high-speed oblique spaceship, many orders of magnitude faster than Gemini spaceships and half-baked knightships.)

Conjecture: There exists a direct 90-degree 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 beehive-chain 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 glider-constructible Life pattern can be constructed with less than 1000 gliders.
(Any glider-constructible Life pattern can be constructed with a some fixed maximum number of gliders N. N is the number of gliders required to construct a sliding-block decoder that converts the position of a very far-distant block into a slow-salvo recipe. The slow-salvo 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 2500-cell 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 5-cell-high Gardens of Eden in 2016, but it is currently an open question whether a 4-cell-high GoE can be constructed.)

Conjecture: Patterns exist that have great-great-great-grandparents but no great-great-great-great-grandparents.
(In 2016, patterns were found that have great-great-grandparents but no great-great-great-grandparents. Examples of all limited-ancestry 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 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.)

User avatar
Kazyan
Posts: 1247
Joined: February 6th, 2014, 11:02 pm

Re: Unproven conjectures

Post by Kazyan » December 18th, 2017, 7:21 pm

Majestas32 wrote:You forgot p23 and p41.
Thank you; I was going off a table that I must have misread.
Tanner Jacobi
Coldlander, a novel, available in paperback and as an ebook. Now on Amazon.

User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: Unproven conjectures

Post by praosylen » December 18th, 2017, 7:54 pm

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...

User avatar
Tom Mazanec
Posts: 32
Joined: December 18th, 2017, 5:22 pm

Re: Unproven conjectures

Post by Tom Mazanec » December 18th, 2017, 9:44 pm

dvgrn
I thought conjectures by definition were things unknown, if suspected, or I would have checked the Did you know

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

Re: Unproven conjectures

Post by dvgrn » December 18th, 2017, 10:28 pm

Tom Mazanec wrote:dvgrn
I thought conjectures by definition were things unknown, if suspected, or I would have checked the Did you know[s]
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.

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 great-great-great-great-grandparentless patterns that have great-great-great-grandparents
... or even if there's no one-cell-thick spaceship, since there are some ideas worked out for how that might be possible.

But in most cases, while a proof of non-existence 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 long-standing 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.

User avatar
Tom Mazanec
Posts: 32
Joined: December 18th, 2017, 5:22 pm

Re: Unproven conjectures

Post by Tom Mazanec » December 19th, 2017, 2:28 pm

How about things where we don't even have a conjecture as to the answer, much less a theorem?

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Unproven conjectures

Post by simsim314 » December 19th, 2017, 5:44 pm

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, 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.

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

Re: Unproven conjectures

Post by dvgrn » December 19th, 2017, 6:51 pm

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?
EDIT: YES on this last one. Let's change it to "one-engine Cordership".

... 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.

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: Unproven conjectures

Post by Macbi » December 19th, 2017, 7:42 pm

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 signal-turner and therefore being able to build oscillators of all periods. But I see no way at all to build a max-speed knightship with any kind of technology. You just have to hope one appears.

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

Re: Unproven conjectures

Post by dvgrn » December 19th, 2017, 8:23 pm

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 signal-turner and therefore being able to build oscillators of all periods. But I see no way at all to build a max-speed knightship with any kind of technology. You just have to hope one appears.
True enough. I put that one in my earlier "conjectures" list, because I think the partials found so far suggest a near-100% 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 near-future 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.

-- It occurs to me that if some (pre-1970) 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...

User avatar
calcyman
Moderator
Posts: 2929
Joined: June 1st, 2009, 4:32 pm

Re: Unproven conjectures

Post by calcyman » December 20th, 2017, 11:12 am

I counter-conjecture 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 1-engine Cordership' where a c/12 universal constructor or swarm of diagonal Caterloopillars chases a block-laying 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 mono-clinic!

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

Re: Unproven conjectures

Post by dvgrn » December 20th, 2017, 2:10 pm

calcyman wrote:I counter-conjecture 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.
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.

I suspect we're going to be stuck in our current state of somebody-is-wrong-but-we-don't-know-who, for quite a long time... though it certainly might evolve into "we-know-Dave-is-wrong-but-we-can't-prove-it" 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 long-lived 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 billion-tick limit makes it pretty sure that any super-long-lasting methuselah won't be a simple random-ash 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 simplest version of that kaleidoscope-maker [~19.7M ticks to settle] takes a similar length of time to stabilize [~17.7M ticks]:

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!
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 power-law distribution... so there should be an occasional arrangement that runs billions of ticks before stabilizing.

I was going to postulate a trillion-tick kaleidoscope, but it would take a Catagolue-sized effort to locate that, I suppose.
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.

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 billion-tick methuselah very likely.

(Heh, I've been wrong before, though, and will be happy to be proved wrong again -- with an actual counterexample --!)
calcyman wrote:Also, there's a 'lucky 1-engine Cordership' where a c/12 universal constructor or swarm of diagonal Caterloopillars chases a block-laying switch engine and removes its debris. You'll need some very arbitrary definition to disallow that as a 'switch engine with complicated clean exhaust'.
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 universal-constructor predecessors. I think you're meaning that we can't rule out the possibility that there's a lucky one-engine 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.

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 time-to-stability 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 CA-land. An example would be a random-ash spacefiller that provably grows forever, but builds some kind of non-repeating quasicrystal structure.

User avatar
calcyman
Moderator
Posts: 2929
Joined: June 1st, 2009, 4:32 pm

Re: Unproven conjectures

Post by calcyman » December 21st, 2017, 9:10 am

dvgrn wrote:
calcyman wrote:Also, there's a 'lucky 1-engine Cordership' where a c/12 universal constructor or swarm of diagonal Caterloopillars chases a block-laying switch engine and removes its debris. You'll need some very arbitrary definition to disallow that as a 'switch engine with complicated clean exhaust'.
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 universal-constructor predecessors. I think you're meaning that we can't rule out the possibility that there's a lucky one-engine 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.
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 switch-engines in the construction). So I think both of your 'no's should be 'yes's, and I generally agree with the other 'yes's.

With the possible exception of the small true-period 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/7-orthogonal glider backrake?
The existence of the p8 c/2 backrake and the p7 3c/7 spaghetti monster point at a possible 'yes' answer, and it's semi-obvious how one would search for this: do a back-to-front spaceship search for long partials which terminate in a 3c/7 glider stream (or two, possibly) and a regular front-to-back spaceship search, and meet-in-the-middle with a large hashtable of hashed tuples of adjacent rows.

With a GPU version of an existing search program, this is probably within the GoL community's current resources.
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 long-lived 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.
The interesting thing about the Methuselah Stabilisation Function M(n) -- i.e. the longest stabilisation time amongst all n-by-n 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).
Jumping up to a billion-tick limit makes it pretty sure that any super-long-lasting methuselah won't be a simple random-ash 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.)
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 backward-glider-emitting puffer in b3s23/C1 is 2^-50 -- which I think is pessimistic -- then we can expect about 2^150 soups with two perpendicular backward-glider-emitting puffers. I'd be very surprised if none of these happen to last for over 10^9 ticks.
What do you do with ill crystallographers? Take them to the mono-clinic!

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

Re: Unproven conjectures

Post by dvgrn » December 21st, 2017, 12:32 pm

calcyman wrote:
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 universal-constructor predecessors. I think you're meaning that we can't rule out the possibility that there's a lucky one-engine Cordership with a smallish exhaust eater that happens to have a 16x16 predecessor... (?)
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 switch-engines in the construction).
Ah, I missed the jump to the sixth question! That makes much more sense.

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.)
calcyman wrote:With the possible exception of the small true-period p14 glider gun; I see no reason why it should exist.
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!

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 billion-tick 16x16 methuselah any time soon.
calcyman wrote:if the frequency of a backward-glider-emitting puffer in b3s23/C1 is 2^-50 -- which I think is pessimistic -- then we can expect about 2^150 soups with two perpendicular backward-glider-emitting puffers. I'd be very surprised if none of these happen to last for over 10^9 ticks.
2^150 seems high to me, just because the soup-eye-candy situation requires perfectly synchronized backward-glider-emitting 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.

-- 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 backward-glider-emitting 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 backward-glider-emitting 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 quadratic-growth pattern might settle into predictability eventually, but it seems like an arrangement like that might produce a billion-tick methuselah a lot more reliably than the soup-eye-candy symmetric method.

A slightly different angle on the same idea: is there a way to calculate roughly the odds of any of Nick Gotts' longer-lived 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 nikk-nikkm1r90-w4s164
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!
This is all a long way of saying "you're almost certainly right on this one, but I don't have to admit I'm wrong until I see an actual 16x16 counterexample."

User avatar
Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Unproven conjectures

Post by Apple Bottom » December 21st, 2017, 2:21 pm

Just to link to it, there's also a (very incomplete, additions-and-improvements-welcome) 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!

User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: Unproven conjectures

Post by praosylen » December 21st, 2017, 5:02 pm

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 non-corollary 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...

User avatar
muzik
Posts: 5578
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Unproven conjectures

Post by muzik » December 21st, 2017, 6:33 pm


User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: Unproven conjectures

Post by praosylen » December 21st, 2017, 7:46 pm

muzik wrote:How about these?
Never mind.
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...

User avatar
pcallahan
Posts: 844
Joined: April 26th, 2013, 1:04 pm

Re: Unproven conjectures

Post by pcallahan » January 4th, 2018, 3:22 pm

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.

dani
Posts: 1222
Joined: October 27th, 2017, 3:43 pm

Re: Unproven conjectures

Post by dani » March 7th, 2018, 3:59 pm

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.)
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)

User avatar
77topaz
Posts: 1496
Joined: January 12th, 2018, 9:19 pm

Re: Unproven conjectures

Post by 77topaz » March 7th, 2018, 4:01 pm

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. :P

User avatar
Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Unproven conjectures

Post by Apple Bottom » March 7th, 2018, 4:40 pm

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. :P
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. ;)
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!

Post Reply