Unproven conjectures

For general discussion about Conway's Game of Life.
User avatar
Wyirm
Posts: 307
Joined: October 29th, 2021, 6:54 pm
Location: 30.541634, 47.825445 (on the boat)

Re: Unproven conjectures

Post by Wyirm » November 4th, 2022, 4:09 pm

Can an Icenine theoretically exist? And if it could, couldn't one make the assumption that infinitely many unique instances or kinds of Icenine exist? Finally, If Icenines do exist, and multiple types of Icenine, couldn't one make the argument that 2 different of these hypothetical agars could be thrown at eachother and stop an Icenine?

Code: Select all

x = 36, y = 28, rule = TripleLife
17.G$17.3G$20.G$19.2G11$9.EF$8.FG.GD$8.DGAGF$10.DGD5$2.2G$3.G30.2G$3G
25.2G5.G$G27.G.G.3G$21.2G7.G.G$21.2G7.2G!
Bow down to the Herschel

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

Re: Unproven conjectures

Post by dvgrn » November 4th, 2022, 5:23 pm

Wyirm wrote:
November 4th, 2022, 4:09 pm
Can an Icenine theoretically exist? And if it could, couldn't one make the assumption that infinitely many unique instances or kinds of Icenine exist? Finally, If Icenines do exist, and multiple types of Icenine, couldn't one make the argument that 2 different of these hypothetical agars could be thrown at eachother and stop an Icenine?
My reason for inventing the IceNine "thought experiment" was to say that, while it's extraordinarily unlikely that any such thing as IceNine exists in real Life, it's also hard to imagine that anyone will be able to come up with an airtight proof of its nonexistence.

Beyond that, you are certainly free to assume anything you want about competing hypothetical IceNine variants. But it seems to me that that would be getting very very deep into handwaving / vaporware territory.

You can disprove some things, or rather, show that some properties of hypothetical-things-that-probably-don't-exist are not logically self-consistent.
E.g., it's obviously impossible to have two different IceNines that both unstoppably take over the universe; one of them would have to win, or maybe both of them could win in different circumstances, in which case at least one of them is not unstoppable. But it might be a good idea to resist the temptation to wander too far down into that counterfactual rabbit hole.

AlbertArmStain
Posts: 1233
Joined: January 28th, 2022, 7:18 pm
Location: Planet Z

Re: Unproven conjectures

Post by AlbertArmStain » November 7th, 2022, 6:15 pm

Anything can be constructed in N number of cells
where N is not equal to infinity

User avatar
Wyirm
Posts: 307
Joined: October 29th, 2021, 6:54 pm
Location: 30.541634, 47.825445 (on the boat)

Re: Unproven conjectures

Post by Wyirm » November 7th, 2022, 9:41 pm

AlbertArmStain wrote:
November 7th, 2022, 6:15 pm
Anything can be constructed in N number of cells
where N is not equal to infinity
Gardens of Eden have been proven to exist. In other words, not all patterns have a predecessor.

Code: Select all

x = 36, y = 28, rule = TripleLife
17.G$17.3G$20.G$19.2G11$9.EF$8.FG.GD$8.DGAGF$10.DGD5$2.2G$3.G30.2G$3G
25.2G5.G$G27.G.G.3G$21.2G7.G.G$21.2G7.2G!
Bow down to the Herschel

User avatar
toroidalet
Posts: 1514
Joined: August 7th, 2016, 1:48 pm
Location: My computer
Contact:

Re: Unproven conjectures

Post by toroidalet » November 7th, 2022, 10:27 pm

AlbertArmStain wrote:
November 7th, 2022, 6:15 pm
Anything can be constructed in N number of cells
where N is not equal to infinity
Arbitrarily large patches of the unique father problem still life require about their population to be produced. They themselves are their only predecessors, and can't be synthesized.
Any sufficiently advanced software is indistinguishable from malice.

User avatar
Wyirm
Posts: 307
Joined: October 29th, 2021, 6:54 pm
Location: 30.541634, 47.825445 (on the boat)

Re: Unproven conjectures

Post by Wyirm » November 8th, 2022, 12:24 am

dvgrn wrote:
November 4th, 2022, 5:23 pm
Wyirm wrote:
November 4th, 2022, 4:09 pm
My reason for inventing the IceNine "thought experiment" was to say that, while it's extraordinarily unlikely that any such thing as IceNine exists in real Life, it's also hard to imagine that anyone will be able to come up with an airtight proof of its nonexistence.
...
But it might be a good idea to resist the temptation to wander too far down into that counterfactual rabbit hole.
The only 2 things that come close are ash-clearing computing, which is basically intelligence in cgol, and void agar. Void is the only agar we know of that can sustain imperfections, such as soups or puffers. The lack of a definitive way an icenine would work is the only reason it can't be disproved

Code: Select all

x = 36, y = 28, rule = TripleLife
17.G$17.3G$20.G$19.2G11$9.EF$8.FG.GD$8.DGAGF$10.DGD5$2.2G$3.G30.2G$3G
25.2G5.G$G27.G.G.3G$21.2G7.G.G$21.2G7.2G!
Bow down to the Herschel

AlbertArmStain
Posts: 1233
Joined: January 28th, 2022, 7:18 pm
Location: Planet Z

Re: Unproven conjectures

Post by AlbertArmStain » November 8th, 2022, 8:01 am

toroidalet wrote:
November 7th, 2022, 10:27 pm
AlbertArmStain wrote:
November 7th, 2022, 6:15 pm
Anything can be constructed in N number of cells
where N is not equal to infinity
Arbitrarily large patches of the unique father problem still life require about their population to be produced. They themselves are their only predecessors, and can't be synthesized.
Your making this considerably difficult
Reworded:
Any constructable object can be constructed in n number of cells, which n being a constant not equal to infinity

hotdogPi
Posts: 1587
Joined: August 12th, 2020, 8:22 pm

Re: Unproven conjectures

Post by hotdogPi » November 8th, 2022, 8:22 am

AlbertArmStain wrote:
November 8th, 2022, 8:01 am
toroidalet wrote:
November 7th, 2022, 10:27 pm
AlbertArmStain wrote:
November 7th, 2022, 6:15 pm
Anything can be constructed in N number of cells
where N is not equal to infinity
Arbitrarily large patches of the unique father problem still life require about their population to be produced. They themselves are their only predecessors, and can't be synthesized.
Your making this considerably difficult
Reworded:
Any constructable object can be constructed in n number of cells, which n being a constant not equal to infinity
RCT says yes. The maximum is 80 (16 gliders), but it's likely lower. 43? (10 each for 4 switch engines and 3 for a pre-block, but I'm not sure.)
User:HotdogPi/My discoveries

Periods discovered: 5-16,⑱,⑳G,㉑G,㉒㉔㉕,㉗-㉛,㉜SG,㉞㉟㊱㊳㊵㊷㊹㊺㊽㊿,54G,55G,56,57G,60,62-66,68,70,73,74S,75,76S,80,84,88,90,96
100,02S,06,08,10,12,14G,16,17G,20,26G,28,38,47,48,54,56,72,74,80,92,96S
217,486,576

S: SKOP
G: gun

AlbertArmStain
Posts: 1233
Joined: January 28th, 2022, 7:18 pm
Location: Planet Z

Re: Unproven conjectures

Post by AlbertArmStain » November 8th, 2022, 11:58 am

hotdogPi wrote:
November 8th, 2022, 8:22 am

RCT says yes. The maximum is 80 (16 gliders), but it's likely lower. 43? (10 each for 4 switch engines and 3 for a pre-block, but I'm not sure.)
True, but I’m including Xwss input

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

Re: Unproven conjectures

Post by calcyman » November 8th, 2022, 12:43 pm

AlbertArmStain wrote:
November 8th, 2022, 11:58 am
hotdogPi wrote:
November 8th, 2022, 8:22 am

RCT says yes. The maximum is 80 (16 gliders), but it's likely lower. 43? (10 each for 4 switch engines and 3 for a pre-block, but I'm not sure.)
True, but I’m including Xwss input
What do you mean by 'Xwss input'? Every glider-constructible pattern has a predecessor consisting of only 16 gliders and nothing else.
What do you do with ill crystallographers? Take them to the mono-clinic!

AlbertArmStain
Posts: 1233
Joined: January 28th, 2022, 7:18 pm
Location: Planet Z

Re: Unproven conjectures

Post by AlbertArmStain » November 8th, 2022, 4:59 pm

calcyman wrote:
November 8th, 2022, 12:43 pm
AlbertArmStain wrote:
November 8th, 2022, 11:58 am
hotdogPi wrote:
November 8th, 2022, 8:22 am

RCT says yes. The maximum is 80 (16 gliders), but it's likely lower. 43? (10 each for 4 switch engines and 3 for a pre-block, but I'm not sure.)
True, but I’m including Xwss input
What do you mean by 'Xwss input'? Every glider-constructible pattern has a predecessor consisting of only 16 gliders and nothing else.
Then what are these?
Attachments
Screenshot 2022-11-08 at 3.58.56 PM.png
Screenshot 2022-11-08 at 3.58.56 PM.png (101.69 KiB) Viewed 1237 times

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

Re: Unproven conjectures

Post by dani » November 8th, 2022, 5:53 pm

Those produce the signals that would otherwise be produced by the bit-reading glider. This is done to make it run in linear time instead of exponential time. The way the script that produces that pattern works is adaptable to producing the actual pattern, but we don't have a way to run it due to its ~million*-digit area bounding box.

EDIT: trillion->million. I had for some reason assumed that multiplying two million-digit numbers together would also multiply their digit counts instead of adding them :oops:
Last edited by dani on November 8th, 2022, 6:27 pm, edited 1 time in total.

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

Re: Unproven conjectures

Post by calcyman » November 8th, 2022, 6:17 pm

AlbertArmStain wrote:
November 8th, 2022, 4:59 pm
calcyman wrote:
November 8th, 2022, 12:43 pm
AlbertArmStain wrote:
November 8th, 2022, 11:58 am

True, but I’m including Xwss input
What do you mean by 'Xwss input'? Every glider-constructible pattern has a predecessor consisting of only 16 gliders and nothing else.
Then what are these?
That's not the RCT; that's a pattern that emulates how the RCT would behave whilst being fast enough to run in Golly. It's called a 'semilator', because it partially uses the true RCT mechanism (for ~ 30 of the bits in the recipe) and partially emulates by cheating with MWSSes (for the remaining ~ 1.6 million bits in the recipe). The semilator is useful because it allows us to test how the real thing would work to ensure that there are no errors in the recipe.

The true RCT has only 16 gliders, no MWSSes, and has a diameter of about 10^500000 instead of a mere 10^12. The time and memory complexities of running an unemulated n-bit RCT recipe in HashLife are O(n^3) and O(n^2), respectively. As such, the largest recipe that could be run in Golly on reasonable hardware in a reasonable amount of time was the ~ 2000-bit recipe for building a shillelagh, much lower than the 1.6 million bits that we need for the RCT to clean up its own GPSE ash trails.

I'm confused, though -- if you didn't realise this, then what did you think the whole purpose of the RCT project was in the first place? There are much more efficient choices of construction arm, such as a block with a simeksian single-channel recipe aimed at it (SPEBOE), which are vastly more useful in practice and don't require complicated bootstrapping stages and cleanup mechanisms. The raison d'etre of the RCT is to be able to prove that every glider-constructible pattern has an N-glider synthesis where N is some universal constant which was gradually reduced from 329 to 16 over the last few years.

The recent collaborative effort in 2022 has been an exercise in rigour -- namely to show that the 16-glider RCT (the most advanced version of the idea, designed by MathAndCode and Danielle) is actually workable, and that there aren't any insurmountable obstacles to implementation that we slipped under the rug through excessive handwaving. There's also been a drive for optimisation: early estimates of the diameter of a minimal self-cleaning RCT were 10^billions (or even trillions), but now it's been brought down to around 10^500000.

Dave has written a multitude of articles on the topic of the RCT, with the first installment in the series being the one that introduces the RCT idea in the first place:

http://b3s23life.blogspot.com/2018/06/t ... st-of.html

back when it had a much higher glider cost of 329. (And before the RCT idea came along, fixed-cost universal construction would have taken thousands of gliders, using sliding-block registers and a universal counter machine attached to a construction arm.)
dani wrote:
November 8th, 2022, 5:53 pm
Those produce the signals that would otherwise be produced by the bit-reading glider. This is done to make it run in linear time instead of exponential time. The way the script that produces that pattern works is adaptable to producing the actual pattern, but we don't have a way to run it
^^ exactly, this.
due to its trillion-digit area bounding box.
...just under million-digit area, I think? 10^500000 by 10^500000 is a nice round 10^10^6.
What do you do with ill crystallographers? Take them to the mono-clinic!

AlbertArmStain
Posts: 1233
Joined: January 28th, 2022, 7:18 pm
Location: Planet Z

Re: Unproven conjectures

Post by AlbertArmStain » November 15th, 2022, 12:26 pm

Here’s another conjecture, anything with a glider synthesis is spartan

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

Re: Unproven conjectures

Post by dvgrn » November 15th, 2022, 12:39 pm

AlbertArmStain wrote:
November 15th, 2022, 12:26 pm
Here’s another conjecture, anything with a glider synthesis is spartan
That's not an unproven conjecture. It's trivially true for some definitions of "Spartan", and trivially false for other definitions of "Spartan".

Personally I don't think I approve of any of the definitions of "Spartan" for which this conjecture is true. Why would we ever want to label as "Spartan" something like Canada Grey?

User avatar
DroneBetter
Posts: 94
Joined: December 1st, 2021, 5:16 am
Location: The UK (a delightful place)
Contact:

Re: Unproven conjectures

Post by DroneBetter » November 20th, 2022, 10:11 pm

If there are patterns with tetrational time complexity to termination with respect to population and bounding box, and reverse caber-tossers store the necessary information (proportional to the time necessary to construct patterns) in the modulo values of the switch engines' offsets after recursive floordivs by glider bounces, it would be possible to construct an RCT-reconstructing pattern by 15-glider RCT that, upon the RCT's self-cleanup, creates 2-engine corderships receding in the directions of each of the original block-laying switch engines comprising the RTC, waits until they are at the original displacement (which requires exponential time with respect to its own complexity, but (if adjusted correctly) a feasibly small remainder when the largest tetration of 2 (for instance) beneath it is subtracted) and converts them to elbows (in what is used in the end of the 2EC construction-arm-extending reaction) and uses them to create gliders moving towards the original block-laying switch engines' locations, then cleans itself up, thus there are infinitely many such "quine" oscillators and spaceships of minimum population <=75, yes? (If true, this would only be an upper bound, I wonder what the true value would be)
Edit: A stronger statement from this is that there are infinitely many speeds of spaceship, because infinitely many nonequivalent spaceships of the same speed within a population limit and period are attainable for likely lower population (by wickstretchers followed by wick-burn-initiating spaceships), and infinitely many periods of a speed are by, for instance, two (1,0)*c/4 spaceships bouncing a glider back and forth between them, though I don't know whether any patterns under 75//2-5=32 cells exist such that collisions reflect gliders and displace them so that things like boxships could be made, and infinitely many 29-cell oscillators can be made with the p60 glider shuttle's mechanism, perhaps a better conjecture about still lifes is that there exists a set of infinitely many with coprime periods with the same finite maximum population (beneath that of snark loops)
That concludes my post (I hope you liked it)

User avatar
Pavgran
Posts: 220
Joined: June 12th, 2019, 12:14 pm

Re: Unproven conjectures

Post by Pavgran » November 21st, 2022, 8:40 am

DroneBetter wrote:
November 20th, 2022, 10:11 pm
thus there are infinitely many such "quine" oscillators and spaceships of minimum population <=75, yes? (If true, this would only be an upper bound, I wonder what the true value would be)
Correct. Although in the case of oscillators and spaceships there is a simpler solution, namely, don't clean up debris left from launch completely, but instead use them to build one-time seed that would reproduce the initial configuration. And then activate these seeds by carefully timed gliders from the center.

Quine idea is perfectly valid for constructing more complex designs, for example, there was an idea of making an RCT that constructs itself out of 0E0P metacells.

AlbertArmStain
Posts: 1233
Joined: January 28th, 2022, 7:18 pm
Location: Planet Z

Re: Unproven conjectures

Post by AlbertArmStain » November 28th, 2022, 12:46 pm

Can an indestructible object exist?

hotdogPi
Posts: 1587
Joined: August 12th, 2020, 8:22 pm

Re: Unproven conjectures

Post by hotdogPi » November 28th, 2022, 12:48 pm

AlbertArmStain wrote:
November 28th, 2022, 12:46 pm
Can an indestructible object exist?
This has asked many times before. We don't know.
User:HotdogPi/My discoveries

Periods discovered: 5-16,⑱,⑳G,㉑G,㉒㉔㉕,㉗-㉛,㉜SG,㉞㉟㊱㊳㊵㊷㊹㊺㊽㊿,54G,55G,56,57G,60,62-66,68,70,73,74S,75,76S,80,84,88,90,96
100,02S,06,08,10,12,14G,16,17G,20,26G,28,38,47,48,54,56,72,74,80,92,96S
217,486,576

S: SKOP
G: gun

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

Re: Unproven conjectures

Post by dvgrn » November 28th, 2022, 12:59 pm

AlbertArmStain wrote:
November 28th, 2022, 12:46 pm
Can an indestructible object exist?
Here's the last time a similar question was asked. There's some more detail in the "Structures resistant to attack" thread.

User avatar
pipsqueek
Posts: 265
Joined: September 10th, 2022, 4:42 pm

Re: Unproven conjectures

Post by pipsqueek » November 28th, 2022, 5:05 pm

AlbertArmStain wrote:
November 28th, 2022, 12:46 pm
Can an indestructible object exist?
One thing we know is that such an object would have to be able to regenerate from temporary damage, rather than
avoiding all damage completely (assuming it is stable)

PROOF:
imagine a stable pattern (a non-empty one). we know at all four corners of the pattern, there must exist a dead cell with exactly 1 live neighbor.
so two cells could easily be placed to make that dead cell be born. the former dead cell has (or had) 1 live neighbor. and that neighbor
must have 2 or 3 live neighbors. either way, one of those cells must be within range of the newly alive cell. and.. uhh. I'm not sure how to conclude the proof but I'm sure its easy to see why this is true

Code: Select all

x=17,y=16,rule=B3/S23
3bo3bobo2bob2o$bobo4bo4b4o$bobo5bobo2b3o$b2obob2o3b2o$3o4b2ob2o2b2o$4b
o4bo$4b2obobob2ob3o$3ob3o2b2o$b3o2bobobo5bo$o3b2o3bobo2b2o$4bo3bob2o3b
o$2obo2bobobo2b2o$3b3o5bo2b2o$2obo4bo2bob2o$o3bob2obo3b2o$2bo8bobobo![[ STOP 3 GPS 4 ]]

User avatar
Wyirm
Posts: 307
Joined: October 29th, 2021, 6:54 pm
Location: 30.541634, 47.825445 (on the boat)

Re: Unproven conjectures

Post by Wyirm » December 14th, 2022, 2:46 pm

Conjecture: GCOL does not follow the second law of thermodynamics, entropy must always increase. We can't disprove an icenine, and cgol doesn't have the issue that decreasing entropy requires energy. The very existence of people proves this, it is possible for an extremely organized pattern or replicator to appear in ash and decrease entropy. Obviously this is a lot more difficult, as the mechanisms of chemistry and physics facilitate the creation of complex structures, but the point still stands.

Code: Select all

x = 36, y = 28, rule = TripleLife
17.G$17.3G$20.G$19.2G11$9.EF$8.FG.GD$8.DGAGF$10.DGD5$2.2G$3.G30.2G$3G
25.2G5.G$G27.G.G.3G$21.2G7.G.G$21.2G7.2G!
Bow down to the Herschel

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

Re: Unproven conjectures

Post by dvgrn » December 14th, 2022, 4:45 pm

Wyirm wrote:
December 14th, 2022, 2:46 pm
Conjecture: GCOL does not follow the second law of thermodynamics, entropy must always increase...
Without a formal definition of "entropy" in the context of CGoL, this seems to me more like an "unprovable conjecture" than an "unproven conjecture".

Depending on the definition, it seems likely to end up being trivially true. We don't need hypothetical patterns like icenine when we have Pavgran's replicator, 0E0P metacells, Hydras, and so forth and so on.

AlbertArmStain
Posts: 1233
Joined: January 28th, 2022, 7:18 pm
Location: Planet Z

Re: Unproven conjectures

Post by AlbertArmStain » December 19th, 2022, 11:30 am

dvgrn wrote:
November 15th, 2022, 12:39 pm

That's not an unproven conjecture. It's trivially true for some definitions of "Spartan", and trivially false for other definitions of "Spartan".

Personally I don't think I approve of any of the definitions of "Spartan" for which this conjecture is true. Why would we ever want to label as "Spartan" something like Canada Grey?
The real question is if it’s possible to make objects fully from one time turners and duplicators

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

Re: Unproven conjectures

Post by dvgrn » December 19th, 2022, 12:02 pm

AlbertArmStain wrote:
December 19th, 2022, 11:30 am
dvgrn wrote:
November 15th, 2022, 12:39 pm

That's not an unproven conjecture. It's trivially true for some definitions of "Spartan", and trivially false for other definitions of "Spartan".

Personally I don't think I approve of any of the definitions of "Spartan" for which this conjecture is true. Why would we ever want to label as "Spartan" something like Canada Grey?
The real question is if it’s possible to make objects fully from one time turners and duplicators
I'm not clear on whether this "real question" is related to the previous quote or not -- the connection is not obvious, at least to me.

This question also is not any kind of unproven conjecture. It's generally known at this point that if an object can be constructed by colliding gliders together, then it can be constructed by hitting a constellation of blocks with a single glider. See Theorem 5.2 of the Life textbook.

Post Reply