Unproven conjectures

For general discussion about Conway's Game of Life.
Post Reply
User avatar
77551enpassant
Posts: 46
Joined: February 18th, 2022, 9:06 pm
Location: Portland, Oregon

Re: Unproven conjectures

Post by 77551enpassant » April 28th, 2022, 11:52 am

I don't know how this was found, but can the same method used to find this agar be generalized to agars of different periods, creating unsynthesizable oscillators of different periods?
I enjoy self-supporting spaceships

Code: Select all

x = 11, y = 14, rule = B3/S23
2bo$3b2o$obo$o9$10bo$9b2o!
#C[[ THEME Golly GRID ]]

User avatar
wwei47
Posts: 1651
Joined: February 18th, 2021, 11:18 am

Re: Unproven conjectures

Post by wwei47 » April 28th, 2022, 2:30 pm

More reduction:

Code: Select all

x = 65, y = 53
28booboo$28bo3bo$29b3o$17bobo5boo7boo5bobo$15bo3bobo3boo7boo3bobo3bo$13bobbo4bob
obbobb3obbobbobo4bobbo$11bobbobo4bobb3obobobob3obbo4bobobbo$12boboo4boobobo3bobo
3boboboo4boobo$9boboo10bo5b3o5bo10boobo$8boboo6b5ob5o3b5ob5o6boobo$9booboboobobo
3bobbobo3bobobbo3bobobooboboo$12b3o3boboobobb3o3b3obboboobo3b3o$7b3o5bobb3obb3o
3b3o3b3obb3obbo5b3o$7bobbo3boboo5bobo3bobo3bobo5boobo3bo3bo$9boo3boobobbobb3obbo
bobobb3obbobboboo4boobo$11boobobooboboo3booboboboo3booboboobobo4bo$11bobbobo3bob
o3bobo3bobo3bobo3bobob5o$9boobboo5booboboboo3booboboboo5bo6b3o$8bo6b5obbobobobb
3obbobobobb5ob5o4bo$5boobb3oboobbobo3bobo3bobo3bobo3bobobbo3bo3bobo$4bobboobboob
obb3o3boobobb3o3boobobb3obboboobooboboo$4b3obb4obboo3b3obboboo3b3obboboo3b3obb4o
bo$7bobo4bobo3bobo3bobo3bobo3bobo3bobo7bo$6boobo3b4o3b3obbobobobb3obbobobobb3obb
o4boboo$7boobboo4b3o3booboboboo3booboboboo3boobobbooboo$8bo3boo3bobo3bobo3bobo3b
obo3bobo3boboobbo$6boboboobooboboboboboboboboboboboboboboboboboboboo$5boboobo4bo
bobobobobobobobobobobobobobobobobobboboo$5bo5boboobo3bobo3bobo3bobo3bobo3bobo7bo
bo$3boob3oboobb3o3booboboboo3booboboboo3boobob4o4bo$4bobobbobo5b3obbobobobb3obbo
bobobb3obbobo4b5obbo$3bobboob3obbobbobo3bobo3bobo3bobo3bobo3boboobo5b3o$3boobobo
3boobob3o3boobobb3o3boobobb3o3b3obboob3o$boo5bo3bobo5b3obboboo3b3obboboo3b3o5bob
obboboo$bobb3obobbobobobobbobo3bobo3bobo3bobo3bobobbobb3oboobbo$bboobbooboobobob
obob3obbobobobb3obboboo3b3oboboo3bobo$4bobobbobo3bobo5booboboboo3boobobb3o5bobo
3bo3bo$4bobobboobobobobobobbobo3bobo3bobo3bobobbobobobobbobo$3boobbobbobobbobobo
boboobobobobobobobobb3obobobobobooboobbo$5boo5bo5bobo3bobobboboboboboboo5bobo3bo
bobboboo$5bob4ob4oboboo5bo5bobo3bobobboboboboboboob3o$6boo3bo4bobobb4ob4obobobob
oboobobobobobbobo5boo$9bobboboobo3bobo4bobob3obbobo3bobo5bo5bobo$6booboobobb3o3b
oobboobboo6bo5boobob4obob3obbo$7bo4bo5b3obbobo3boobb3obob4obbobo5boo3boo$7bob3o
3bobobbobbobo6bobo3bobobo3bobooboo3boo$8bo3boob4ob3obo3bobobooboobobboo3b3o3bo4b
o$9boo3bo5boboo3boboobboboobobobb3o5bo4bo$11b3ob3o9bo3boo5bobobo3bobobbobobo$11b
obbobobbobboo4b3o7bob4ob4obooboo$14bo3boobobbo5bo5boobo8bo3bo$15b3o3bobo12bobbob
obbobboboobo$17bo3boo15booboo3boobobo!
Help me find high-period c/2 technology!
My guide: https://bit.ly/3uJtzu9
My c/2 tech collection: https://bit.ly/3qUJg0u
Overview of periods: https://bit.ly/3LwE0I5
Most wanted periods: 76,116

Ilkka Törmä
Posts: 16
Joined: December 3rd, 2019, 4:16 am
Contact:

Re: Unproven conjectures

Post by Ilkka Törmä » April 29th, 2022, 3:09 am

77551enpassant wrote:
April 28th, 2022, 11:52 am
I don't know how this was found, but can the same method used to find this agar be generalized to agars of different periods, creating unsynthesizable oscillators of different periods?
In principle the method works for any period, but you need a "stroke of luck" to get results. The agars and patches were found by a search program (https://github.com/ilkka-torma/gol-agars). There seem to be much fewer period-3 agars than periods 1 and 2 (there are none of size less than 6×6, and only three of size 6×6). Thus we have fewer candidates to analyze for self-forcing patches. Searching for the patches in the agars also becomes much more resource-intensive, although there are simple optimizations that we just haven't implemented yet. We're working on it.

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

Re: Unproven conjectures

Post by dvgrn » May 2nd, 2022, 4:17 pm

wwei47 wrote:
April 28th, 2022, 2:30 pm
More reduction...
For easily confused people like me: if you're having a hard time finding the original unsynthesizable patch in wwei47's reduction, it's because the reduction was posted in a different phase. Here's the other phase, showing the no-synth patch:

Code: Select all

x = 60, y = 53, rule = LifeHistory
27.2A.2A$27.A3.A$28.3A$16.ABAB4.2A3.B3.2A4.BABA$14.AB.BA.AB.B2AB2.B2.
B2AB.BA.AB.BA$12.AB.A4.A.A2.A2.3A2.A2.A.A4.A.BA$10.AB.A.A4.A.B3ABA.A.
AB3AB.A4.A.A.BA$9.B.A.2A4.2A.A.AB.BA.AB.BA.A.2A4.2A.A.B$8.A.2AB9.A3.B
.3A.B3.A9.B2A.A$7.A.2A.B4.5A.5A.B.5A.5A4.B.2A.A$8.2A.A.2A.A.A3.A2.A.A
B.BA.A2.A3.A.A.2A.A.2A$9.2B3A.2BA.2A.A2.3A.B.3A2.A.2A.A2B.3A2B$6.3A5.
AB.3AB.3A.B.3A.B.3A.B3A.BA5.3A$6.A2.A3.A.2A2.B.BA.AB.BA.AB.BA.AB.B2.
2A.A3.A3.A$8.2A3.2A.A2.AB.3A.BA.A.AB.3A.BA2.A.2A4.2A.A$10.2A.A.2ABA.
2A.B.2A.ABA.2A.B.2A.AB2A.A.A4.A$10.A2.A.AB.BA.AB.BA.AB.BA.AB.BA.AB.BA
.A.5A$8.2A2.2A3.BD2CDCDCD2C3D2CDCDCD2CDB3.A6.3A$7.A2.2B2.3ACA2DCDCDC
2D3C2DCDCDC2D3C2A.5A.B2.A$4.2A2.3A.2A2.ADA3DCDC3DCDC3DCDC3DCDC2.A3.A.
2BA.A$3.A2.2A2.2A.A2.A2C3D2CDC2D3C3D2CDC2D3CD.A.2A.2A.A.2A$3.3A2.4A.B
2A.BD3C2DCD2C3D3C2DCD2C3D3C.B4A.A$6.A.A.2B.A.AB.DCDC3DCDC3DCDC3DCDC3D
CDCB.B.B2.A$5.2A.AB.B4A.BD3C2DCDCDC2D3C2DCDCDC2D3CDBA4.A.2A$5.B2AB.2A
2.B.A2C3D2CDCDCD2C3D2CDCDCD2C3DCA.A2.2A.2A$7.A.B.2AB.BADC3DCDC3DCDC3D
CDC3DCDC3DC.2A2.A$5.A.A.2A.2ABA.CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDA.A.2A$
4.A.2A.A4.A.ADCDCDCDCDCDCDCDCDCDCDCDCDCDCDCBA.BA.2A$4.A5.AB2A.AB2DCDC
3DCDC3DCDC3DCDC3DCDCD.B2.B.A.A$2.2A.3AB2A.B3A.2D2CDCDCD2C3D2CDCDCD2C
3D2CDCB4A4.A$3.A.A2.A.AB.B2.A2C2DCDCDC2D3C2DCDCDC2D3C2DCDA4.5A2.A$2.A
2.2A.3A.BA2.ADC3DCDC3DCDC3DCDC3DCDC3DC.2ABA5.3A$2.2ABA.A.B.2A.ABA2C3D
2CDC2D3C3D2CDC2D3C3DC2AB.2AB3A$2A3.B.AB.BA.AB.B.D3C2DCD2C3D3C2DCD2C3D
C2AD.B.BA.A2.A.2A$A2.3A.A.BA.A.ABA2.CDC3DCDCB.BCDC3DCDCB.BCDC2.AB.3A.
2A.BA$.2A2.2A.2A.ABA.A.AB3C2DCDC.AB.3C2DCDCA.B.3ABA.2A.B.A.AB$3.A.A2.
A.AB.BA.AB.B2.2A.ABA.2A.B.2A.AB.3A2.B.BA.AB.BA2.BA$3.A.A2B2A.ABA.A.AB
A2.A.AB.BA.AB.BA.AB.BA.A2.ABA.A.AB.A.AB$2.2A2.A.BA.A2.ABA.A.AB2A.ABA.
A.ABA.A.AB.3ABA.A.ABA.2A.2A.BA$4.2A3.B.A2.B.BA.AB.BA.A2.ABA.A.ABA.2A
2.B.BA.AB.BA.A2.A.2A$4.A.4A.4ABA.2A.B.B.A2.B.BA.AB.BA.A2.ABA.A.ABA.2A
B3A$5.2A3.A4.A.AB.4AB4ABA.A.ABA.2ABA.A.ABA2.A.AB.B2.2A$8.A2.AB2A.AB.B
A.A4.A.A.3A2.A.AB.BA.AB.B2.A2.B2.A.A$5.2A.2A.A.B3A.B.2AB.2A.B2A.B2.B.
A.B.B.2A.AB4A.A.3A2.A$6.A4.A2.B2.3A2.A.A3.2AB.3ABA.4A.BA.A5.2A3.2A$6.
A.3A.2BA.A2.A2.A.A4.B.A.A3.A.A.AB.BA.2A.2A3.2A$7.A3.2A.4A.3A.A3.A.A.
2A.2A.A.B2A.B.3A2B.A4.A$8.2A3.A3.2BA.2A3.A.2A2.A.2A.A.A2.3A2.B2.A4.A$
10.3A.3A3.B5.A3.2A5.A.A.A3.A.AB.A.A.A$10.A2.A.A2.AB.2A4.3A7.A.4A.4A.
2A.2A$13.A3.2A.A2.A5.A5.2A.A3.3B2.A3.A$14.3A3.A.A12.A2.A.AB.A.BA.2A.A
$16.A3.2A15.2A.2A3.2A.A.A!
#C [[ GPS 2 ]]

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

Re: Unproven conjectures

Post by AlbertArmStain » May 2nd, 2022, 4:41 pm

77551enpassant wrote:
April 28th, 2022, 11:52 am
I don't know how this was found, but can the same method used to find this agar be generalized to agars of different periods, creating unsynthesizable oscillators of different periods?
Could it be possible to make unsynthesizable spaceships?

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

Re: Unproven conjectures

Post by dvgrn » May 2nd, 2022, 5:40 pm

AlbertArmStain wrote:
May 2nd, 2022, 4:41 pm
Could it be possible to make unsynthesizable spaceships?
Clearly that's possible, given our current state of knowledge. For all we know, for example, Sir Robin and Sir Sprayer are unsynthesizable spaceships. The more interior spacedust a big blobby spaceship has, the harder it is to find a synthesis for it in practice.

That doesn't prove that no synthesis will ever be found for any particular case, though. Making provably unsynthesizable spaceships seems like quite a tall order at the moment, but I guess you never know what might show up.

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

Re: Unproven conjectures

Post by dani » May 2nd, 2022, 9:50 pm

Actually that doesn't seem that out of the question. One could just use a similar approach to the unsynthesizable p2 agar, but with a p2 c/2 spaceship instead. It'd be much harder to stabilize, though, and still a bit of a longshot. I don't even know of any reasonably small c/2 agars.

User avatar
yujh
Posts: 3066
Joined: February 27th, 2020, 11:23 pm
Location: I'm not sure where I am, so please tell me if you know
Contact:

Re: Unproven conjectures

Post by yujh » May 2nd, 2022, 11:27 pm

dani wrote:
May 2nd, 2022, 9:50 pm
Actually that doesn't seem that out of the question. One could just use a similar approach to the unsynthesizable p2 agar, but with a p2 c/2 spaceship instead. It'd be much harder to stabilize, though, and still a bit of a longshot. I don't even know of any reasonably small c/2 agars.
Hmm. I assume since the p2 agar is not synthesia]sable and has to be there at the start of time, no possible spaceship could contain stuck a pattern. And since we need an unsynthesizable ship, the agar in it must be synthesizable. I have no idea what that would be like

Ilkka Törmä
Posts: 16
Joined: December 3rd, 2019, 4:16 am
Contact:

Re: Unproven conjectures

Post by Ilkka Törmä » May 3rd, 2022, 5:57 am

AlbertArmStain wrote:
May 2nd, 2022, 4:41 pm
Could it be possible to make unsynthesizable spaceships?
In principle, yes, with the same approach. We'd just search for self-forcing agars that evolve into translated versions of themselves after n steps, and then search for finite patches of them that force themselves in their nth predecessor but translated. Again the main limiting factor is that there are very few such agars with reasonable parameters -- in fact, we haven't found any self-forcing agars with (1,0) or (1,1) as the translation vector. Of course, even if by some miracle we found such a patch, we'd still have to complete it into a spaceship.

erictom333
Posts: 171
Joined: January 9th, 2019, 2:44 am

Re: Unproven conjectures

Post by erictom333 » July 12th, 2022, 6:25 am

Would it be possible to create a way to send, receive or eat lightspeed signals?

Code: Select all

x = 25, y = 15, rule = B3/S23
3$3bo2bo2bo2bo2bo2bo2bo$3b19o2$3b5o2b12o$2bo4b2o13bo$3b5o2b12o2$3b19o
$3bo2bo2bo2bo2bo2bo2bo!


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

Re: Unproven conjectures

Post by dvgrn » July 12th, 2022, 7:37 am

erictom333 wrote:
July 12th, 2022, 6:25 am
Would it be possible to create a way to send, receive or eat lightspeed signals?
Certainly nobody has proven that it's impossible.

Here's a previous time a similar question was asked, and an answer to the question with some very rough and possibly crackpot calculations, and there are some interesting responses below that. I don't think much of anything in that 2015 discussion has gone terribly far out of date with recent discoveries.

"Eat" might be relatively easy for the lightspeed signal in your post, though I don't believe any such thing has been found yet. But "send" and "receive" amount to "glider -> lightspeed signal" and "lightspeed signal -> glider". A direct search for converters like that currently seems to be about as difficult as a direct search for a p14 object with a particular spark.

We haven't figured out how to do searches like that successfully yet. We can maybe stretch to p8 or p9, but each time we add 1 to the period, the problem gets several orders of magnitude more difficult, so p14 seems to be out of reach at the moment.

That said, given that we've figured out how to spark the beginning of a 2c/3 wire to get a signal in, and make a converter that produces a spark at the other end of a wire to get a signal back out again, there's clearly some hope that the same can be done for orthogonal wires. Maybe there are clever shortcuts.

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 » July 28th, 2022, 11:29 pm

I'm back. Conjecture: any growth rate between x and x^2 can be constructed by taking the derivative of the growth rate and constructing a "breeder" generating linear growth patterns at that rate.
Examples:
d/dx x^1.5 = sqrt(x)
d/dx xln(x) = ln(x)

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
wwei47
Posts: 1651
Joined: February 18th, 2021, 11:18 am

Re: Unproven conjectures

Post by wwei47 » August 8th, 2022, 9:43 am

Wyirm wrote:
July 28th, 2022, 11:29 pm
d/dx x^1.5 = sqrt(x)
d/dx xln(x) = ln(x)
I'm a bit confused. I thought that d/dx x^1.5=1.5sqrt(x) and that d/dx xln(x)=ln(x)+1.
Help me find high-period c/2 technology!
My guide: https://bit.ly/3uJtzu9
My c/2 tech collection: https://bit.ly/3qUJg0u
Overview of periods: https://bit.ly/3LwE0I5
Most wanted periods: 76,116

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

Re: Unproven conjectures

Post by hotdogPi » August 8th, 2022, 9:50 am

wwei47 wrote:
August 8th, 2022, 9:43 am
Wyirm wrote:
July 28th, 2022, 11:29 pm
d/dx x^1.5 = sqrt(x)
d/dx xln(x) = ln(x)
I'm a bit confused. I thought that d/dx x^1.5=1.5sqrt(x) and that d/dx xln(x)=ln(x)+1.
You're the one who's really into O(n), so I'm surprised that you missed this: both Wyirm's and yours have the same growth rate.
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
83bismuth38
Posts: 556
Joined: March 2nd, 2017, 4:23 pm
Location: perpendicular to your eyes
Contact:

Re: Unproven conjectures

Post by 83bismuth38 » August 17th, 2022, 10:53 pm

83bismuth38 wrote:
February 3rd, 2022, 10:47 am
i set up a more exhaustive search (but not surely exhaustive), here's the results:

Code: Select all

six cell high p4s
I've attempted a search a few times with no success, are there any other seven cell high p5s other than fumarole and Silver's p5? what about for other periods?
looking to support hive five (n+18) and charity's oboo reaction (2n+18)

Code: Select all

x = 28, y = 13, rule = B3/S23
19bo$3bo15bo4b2o$2bobo14bo4bobo$2bobo20b2o$3bo11b3o2$25b3o$b2o22b3o$o
2bo$b2o12b2o$10b2o2bobo$bo8b2o2b2o$obo7b2o!

qqd
Posts: 424
Joined: September 10th, 2022, 4:24 pm

Re: Unproven conjectures

Post by qqd » October 1st, 2022, 1:12 pm

What if the number of n-glider syntheses is asymptotic to BB(n)(the busy beaver function?(https://en.wikipedia.org/wiki/Busy_beaver)). There is evidence, such as why does the number suddenly jump from 71 2-glider collisions to over 460,000 3-glider ones? Besides, Life is undecidable, so of course we can't solve the general problem, perhaps not even GC(3)! (unless I do something about that!)
My new p2p:

Code: Select all

x = 20, y = 13, rule = B3/S23
4bo5b2obo$2b3o5bob2o$bo14b2o$bo2b3o4b3o2bobo$2obo3bo2bo3bobobo$3bo3b4o
3bobob2o$3bo3bo2bo3bobobo$4b3o4b3o2bobo$16b2o$4b3o4b3o$4bo2bo3bo2bo$6b
obo4bobo$7bo6bo!

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

Re: Unproven conjectures

Post by Macbi » October 1st, 2022, 2:38 pm

qqd wrote:
October 1st, 2022, 1:12 pm
What if the number of n-glider syntheses is asymptotic to BB(n)(the busy beaver function?(https://en.wikipedia.org/wiki/Busy_beaver)). There is evidence, such as why does the number suddenly jump from 71 2-glider collisions to over 460,000 3-glider ones? Besides, Life is undecidable, so of course we can't solve the general problem, perhaps not even GC(3)! (unless I do something about that!)
The number of 3-glider collisions is already infinite. You can collide two gliders to make a reaction that kicks out other gliders, then wait as long as you like, then collide the third glider into one of these gliders.

qqd
Posts: 424
Joined: September 10th, 2022, 4:24 pm

Re: Unproven conjectures

Post by qqd » October 1st, 2022, 2:46 pm

Macbi wrote:
October 1st, 2022, 2:38 pm
qqd wrote:
October 1st, 2022, 1:12 pm
What if the number of n-glider syntheses is asymptotic to BB(n)(the busy beaver function?(https://en.wikipedia.org/wiki/Busy_beaver)). There is evidence, such as why does the number suddenly jump from 71 2-glider collisions to over 460,000 3-glider ones? Besides, Life is undecidable, so of course we can't solve the general problem, perhaps not even GC(3)! (unless I do something about that!)
The number of 3-glider collisions is already infinite. You can collide two gliders to make a reaction that kicks out other gliders, then wait as long as you like, then collide the third glider into one of these gliders.
I was meaning non-trivial examples because these collisions are extremely trivial and don't produce anything new.
My new p2p:

Code: Select all

x = 20, y = 13, rule = B3/S23
4bo5b2obo$2b3o5bob2o$bo14b2o$bo2b3o4b3o2bobo$2obo3bo2bo3bobobo$3bo3b4o
3bobob2o$3bo3bo2bo3bobobo$4b3o4b3o2bobo$16b2o$4b3o4b3o$4bo2bo3bo2bo$6b
obo4bobo$7bo6bo!

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

Re: Unproven conjectures

Post by Macbi » October 1st, 2022, 3:26 pm

qqd wrote:
October 1st, 2022, 2:46 pm
Macbi wrote:
October 1st, 2022, 2:38 pm
qqd wrote:
October 1st, 2022, 1:12 pm
What if the number of n-glider syntheses is asymptotic to BB(n)(the busy beaver function?(https://en.wikipedia.org/wiki/Busy_beaver)). There is evidence, such as why does the number suddenly jump from 71 2-glider collisions to over 460,000 3-glider ones? Besides, Life is undecidable, so of course we can't solve the general problem, perhaps not even GC(3)! (unless I do something about that!)
The number of 3-glider collisions is already infinite. You can collide two gliders to make a reaction that kicks out other gliders, then wait as long as you like, then collide the third glider into one of these gliders.
I was meaning non-trivial examples because these collisions are extremely trivial and don't produce anything new.
Even then you'll get infinitely many collisions for some n, since you can build some very complicated machine and then interrupt it at any point.

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

Re: Unproven conjectures

Post by toroidalet » October 1st, 2022, 3:27 pm

With four gliders, you can synthesize blobs of junk with an arbitrarily large population (and probably any sufficiently large population). Because they have different populations, they must be distinct, and so there are an infinite number of four-glider syntheses. Additionally, with 17 gliders you can synthesize any pattern which can be synthesized with gliders (again, infinitely many syntheses).
If you restrict them to an a*b bounding box, the number of n-glider syntheses becomes O((a*b)^n), which is less than the busy beaver function. However, the maximum (stable population/generations/period/number of giant Mandelbrot sets/almost any metric) of a glider synthesis inside an a*b bounding box is on the order of BB(a*b).

The number of glider syntheses is a combinatorial problem, and it is actually independent of the rule you use. So a decidable rule like B3aijn/S2ae3jnr would have the same number of collisions, but they wouldn't synthesize anything, and thus there is no reason that undecidability should be involved.
Any sufficiently advanced software is indistinguishable from malice.

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

Re: Unproven conjectures

Post by dvgrn » October 1st, 2022, 10:41 pm

toroidalet wrote:
October 1st, 2022, 3:27 pm
The number of glider syntheses is a combinatorial problem, and it is actually independent of the rule you use.
Obligatory Annoying Quibble (TM): it's not quite independent of the rule. For example, there are 2-glider collisions in LeapLife that aren't collisions at all in regular Conway's Life (because without the "2n", the gliders don't interact at all):

Code: Select all

x = 7, y = 7, rule = B2n3/S23-q
3o$2bo$bo2$5bo$4b2o$4bobo!
Less quibble-ish-ly, for rules where there are a finite number of 3-glider collisions (for example), the exact number can vary wildly depending on how long the various 2-glider collisions last, and therefore how many different phases are available to crash the third glider into.

qqd
Posts: 424
Joined: September 10th, 2022, 4:24 pm

Re: Unproven conjectures

Post by qqd » October 2nd, 2022, 3:59 am

All this means that (at least for Life) only the value of NGC(3) is unknown (NGC(n) means the number of Non-trivial Glider Collisions for n gliders) Therefore, I state:
Conjecture: The value of NGC(3) is finite
(It's extremely unlikely, but perhaps somehow we can reduce the RCT to 3 gliders)
My new p2p:

Code: Select all

x = 20, y = 13, rule = B3/S23
4bo5b2obo$2b3o5bob2o$bo14b2o$bo2b3o4b3o2bobo$2obo3bo2bo3bobobo$3bo3b4o
3bobob2o$3bo3bo2bo3bobobo$4b3o4b3o2bobo$16b2o$4b3o4b3o$4bo2bo3bo2bo$6b
obo4bobo$7bo6bo!

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

Re: Unproven conjectures

Post by dvgrn » October 2nd, 2022, 9:49 am

qqd wrote:
October 2nd, 2022, 3:59 am
All this means that (at least for Life) only the value of NGC(3) is unknown (NGC(n) means the number of Non-trivial Glider Collisions for n gliders) Therefore, I state:
Conjecture: The value of NGC(3) is finite
(It's extremely unlikely, but perhaps somehow we can reduce the RCT to 3 gliders)
The notion of "Nontrivial Glider Collisions" isn't quite clear without a more specific definition, I think.

For example, with three gliders you can get an unbounded number of different patterns with different bounding boxes -- e.g., pairs of traffic lights separated by more and more distance, just by moving the topmost glider upward by 2N ticks for N>=0:

Code: Select all

x = 19, y = 30, rule = B3/S23
17bo$16bo$16b3o18$bo$o$3o5$b3o$bo$2bo!
According to the way I use "trivial", those 3G collisions are all non-trivially different. Some of them are worth cataloguing in a 3G database because they're potentially useful in synthesis projects, but then at some arbitrary point it stops being worth including them in the database.

For this conjecture to be anything but trivially false, it needs to be clear that all cases like this are excluded, along with the "trivial" unbounded part of infinite series such as a pair of 2-glider-mess (2GM) collisions:

Code: Select all

x = 11, y = 98, rule = B3/S23
8bobo$8b2o$9bo84$obo$2o$bo7$3b3o$3bo$4bo!
The above is clearly a non-trivial collision, different from what you get when you move the top glider up or down by two ticks. But moving the top glider up by four ticks gets you to the first collision in a series that you'd have to call "trivial":

Code: Select all

x = 11, y = 102, rule = B3/S23
8bobo$8b2o$9bo88$obo$2o$bo7$3b3o$3bo$4bo!
From here on, as the top glider moves up in steps of two, the two 2-glider-mess blobs no longer interact with each other while they're still active. The only interaction of any kind is the deletion of a single ship, which happens later and later but ultimately produces the same result -- two 2-glider-mess ash blobs separated by some number of cells diagonally, and half a dozen gliders receding to infinity, on different lanes depending on the initial separation.
qqd wrote:
October 2nd, 2022, 3:59 am
(It's extremely unlikely, but perhaps somehow we can reduce the RCT to 3 gliders)
I think that with a little work we can very safely rule out a 3G RCT, or even a 3G "messy RCT" where an unbounded number of different these Nontrivial Glider Constructions exist that build something in an RCT kind of way, but with extra gliders escaping to infinity. A lot of this investigation has probably already been done, by Nick Gotts among others -- anyone have a good link?

Beyond a certain distance, the gliders bouncing back from any of these secondary 2GM collisions will only get back to the first 2GM collision after it has turned into settled ash. Some of them will bounce gliders back the other way, but again after some point they will only reach the second 2GM collision after it has become settled ash.

I don't know what the maximum number of back-and-forth bounces is, but none of these reactions will change in a non-trivial way by widening the distance between collisions any further. So with only three gliders it won't be possible to make adjustments to two very very very widely separated pieces, in such a way that the distance between the pieces can be measured repeatedly to extract a series of bits to run a construction arm.

This is the sense in which 3-glider collisions are known to be exhaustively enumerable, and the reason why calcyman's statement
calcyman wrote:
August 15th, 2015, 7:45 pm
I doubt anyone could ever prove the falsity of the following claim:

"There is a 4-glider synthesis of the Caterpillar."
puts the lower limit at 4G and not 3G. We do know that there isn't a 3G Caterpillar synthesis.

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

Re: Unproven conjectures

Post by AlbertArmStain » November 4th, 2022, 11:26 am

Can an ice nine be constructed with 16 gliders?

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

Re: Unproven conjectures

Post by Macbi » November 4th, 2022, 11:52 am

AlbertArmStain wrote:
November 4th, 2022, 11:26 am
Can an ice nine be constructed with 16 gliders?
The idea behind ice nine is that it arises in sufficiently large random soups. So it should be very easy to construct. You just smash together 10^100 gliders at random. And of course you can use the RCT to make this with 16 starting gliders.

Post Reply