Unproven conjectures

For general discussion about Conway's Game of Life.
Post Reply
Ilkka Törmä
Posts: 14
Joined: December 3rd, 2019, 4:16 am
Contact:

Re: Unproven conjectures

Post by Ilkka Törmä » January 2nd, 2022, 11:08 am

pcallahan wrote:
January 24th, 2020, 3:35 pm
Infinite still life patterns could not be handled with this approach, and maybe some of them have only themselves as a predecessor. For the periodic case, these can be viewed as finite patterns on a toroidal grid.
I ran a search for such a periodic pattern and found one of size 6x3:

Code: Select all

#C [[ THUMBNAIL ]]
x = 6, y = 3, rule = B3/S23:T6,3
bbobbo$
boboob$
oobbob!
The periodic agar has no predecessors (even ones with a higher period or no period at all) except itself. This is because every predecessor of this 20x11 patch has the above pattern at the center:

Code: Select all

#C [[ THUMBNAIL ]]
x =20, y = 11, rule = B3/S23
boobboboobboboobbobo$
obbobbobbobbobbobbob$
bboboobboboobboboobb$
boobboboobboboobbobo$
obbobbobbobbobbobbob$
bboboobboboobboboobb$
boobboboobboboobbobo$
obbobbobbobbobbobbob$
bboboobboboobboboobb$
boobboboobboboobbobo$
obbobbobbobbobbobbob!
I've checked this with a Python script that calls a SAT solver, and a colleague verified it independently with a different script. I also checked that no smaller pattern than 6x3 has this property. I have a feeling that this is already known, since 6x3 is small enough for someone to have already catalogued all agars of that period, and their possible predecessors...

To be clear, this is not a solution to the unique father problem, since it (implicitly) asks for a configuration with finitely many live cells.

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

Re: Unproven conjectures

Post by dvgrn » January 2nd, 2022, 11:59 am

Ilkka Törmä wrote:
January 2nd, 2022, 11:08 am
The periodic agar has no predecessors (even ones with a higher period or no period at all) except itself
...
To be clear, this is not a solution to the unique father problem, since it (implicitly) asks for a configuration with finitely many live cells.
Thanks for posting this! It's very easy to stabilize finite patches of the agar, even with just a two-cells-wide boundary region:

Code: Select all

x = 34, y = 31, rule = B3/S23
31b2o$5b2o4b2o4b2o4b2o5bo2bo$4bo2bo2bo2bo2bo2bo2bo2bo2bo2b2o$3bob2o2bo
b2o2bob2o2bob2o2bob2o$b3o2bob2o2bob2o2bob2o2bob2o2bo$o3bo2bo2bo2bo2bo
2bo2bo2bo2bo2b2o$o2bob2o2bob2o2bob2o2bob2o2bob2o2bo$b3o2bob2o2bob2o2bo
b2o2bob2o2bo2bo$4bo2bo2bo2bo2bo2bo2bo2bo2bo2b2o$3bob2o2bob2o2bob2o2bob
2o2bob2o$b3o2bob2o2bob2o2bob2o2bob2o2bo$o3bo2bo2bo2bo2bo2bo2bo2bo2bo2b
2o$o2bob2o2bob2o2bob2o2bob2o2bob2o2bo$b3o2bob2o2bob2o2bob2o2bob2o2bo2b
o$4bo2bo2bo2bo2bo2bo2bo2bo2bo2b2o$3bob2o2bob2o2bob2o2bob2o2bob2o$b3o2b
ob2o2bob2o2bob2o2bob2o2bo$o3bo2bo2bo2bo2bo2bo2bo2bo2bo2b2o$o2bob2o2bob
2o2bob2o2bob2o2bob2o2bo$b3o2bob2o2bob2o2bob2o2bob2o2bo2bo$4bo2bo2bo2bo
2bo2bo2bo2bo2bo2b2o$3bob2o2bob2o2bob2o2bob2o2bob2o$b3o2bob2o2bob2o2bob
2o2bob2o2bo$o3bo2bo2bo2bo2bo2bo2bo2bo2bo2b2o$o2bob2o2bob2o2bob2o2bob2o
2bob2o2bo$b3o2bob2o2bob2o2bob2o2bob2o2bo2bo$4bo2bo2bo2bo2bo2bo2bo2bo2b
o2b2o$3bob2o2bob2o2bob2o2bob2o2bob2o$b3o2bob2o2bob2o2bob2o2bob2o2bo$o
3bobo3bobo3bobo3bobo3bobob2o$2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2obo!
#C [[ THUMBNAIL THUMBSIZE 2 ]]
So even if it doesn't allow for a solution to the Unique Father problem, it does seem like it allows for the creation of finite patterns that contain cells whose history is uniquely known for arbitrarily long times.

For example, the above 34x31 pattern contains a 30x28 patch of agar. I think that means that if this pattern shows up in an old universe, the center 6x3 patch is guaranteed to have existed unchanged for at least a few ticks -- and if we want to guarantee no changes at the center farther back in time, we just have to make the patch bigger.

I'm not sure yet exactly how many no-change ticks can be claimed for a given size; the usual lightspeed limitation doesn't seem to apply when thinking backwards in time. All we can say is that the existence of a 20x11 patch in the previous tick implies a 6x3 patch in the current tick, so I guess the required area grows horizontally at a factor of 7 times the number of required no-change ticks, and vertically at a factor of 4. (?)

Is that implication still true for all 17 frame-shifted versions of the central patch, or is it specific to the particular 18-cell rectangle shown above?

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

Re: Unproven conjectures

Post by Ilkka Törmä » January 3rd, 2022, 7:07 am

dvgrn wrote:
January 2nd, 2022, 11:59 am
For example, the above 34x31 pattern contains a 30x28 patch of agar. I think that means that if this pattern shows up in an old universe, the center 6x3 patch is guaranteed to have existed unchanged for at least a few ticks -- and if we want to guarantee no changes at the center farther back in time, we just have to make the patch bigger.

I'm not sure yet exactly how many no-change ticks can be claimed for a given size; the usual lightspeed limitation doesn't seem to apply when thinking backwards in time. All we can say is that the existence of a 20x11 patch in the previous tick implies a 6x3 patch in the current tick, so I guess the required area grows horizontally at a factor of 7 times the number of required no-change ticks, and vertically at a factor of 4. (?)
You're absolutely right: if we find a (14n+6)x(8n+3) patch of the agar in the correct phase, then we know that every predecessor contains a (14(n-1)+6)x(8(n-1)+3) patch centered at the same position, for all n ≥ 1. In particular, all predecessors up to and including the n'th one (if they exist) must contain the 6x3 pattern at the center of the patch.
dvgrn wrote:
January 2nd, 2022, 11:59 am
Is that implication still true for all 17 frame-shifted versions of the central patch, or is it specific to the particular 18-cell rectangle shown above?
I computed the minimal number of extra rows and columns needed to enforce each shifted version. Each row

Code: Select all

x y t b l r
means that the (x,y)-shifted pattern is forced into all predecessors when we continue the pattern t rows up, b rows down, l columns to the left, and r columns to the right. In particular, the (2,0)-shifted version only needs 6 columns on its left and right, which is a slight improvement.

Code: Select all

0 0 4 4 7 7
0 1 3 5 5 7
0 2 4 4 5 7
1 0 4 4 7 6
1 1 5 3 7 5
1 2 6 6 6 5
2 0 4 4 6 6
2 1 5 3 6 6
2 2 3 5 6 6
3 0 4 4 5 7
3 1 5 3 5 7
3 2 4 4 7 7
4 0 6 6 6 5
4 1 3 5 7 5
4 2 4 4 7 6
5 0 5 3 6 6
5 1 3 5 6 6
5 2 4 4 6 6

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

Re: Unproven conjectures

Post by dvgrn » January 3rd, 2022, 9:47 am

Ilkka Törmä wrote:
January 3rd, 2022, 7:07 am
In particular, the (2,0)-shifted version only needs 6 columns on its left and right, which is a slight improvement.
Interesting! Looks like the 7-cell buffer horizontally was a maximum value needed for any frame shift, but the 4-cell vertical buffer needs some padding; it takes 6 cells to be safe for any frame of the agar.

How computationally intensive is the analysis being done here? I suppose I'm asking about both the initial search (to find the "most forcing" stable agar in an MxN box) and the frame-shift analysis. But I guess once the stability-compatible MxN agars are enumerated, all the frames will already be in the list somewhere -- if you're doing things that way.

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

Re: Unproven conjectures

Post by pcallahan » January 3rd, 2022, 1:46 pm

Ilkka Törmä wrote:
January 2nd, 2022, 11:08 am
I ran a search for such a periodic pattern and found one of size 6x3:
Oh, that is interesting. I had to search back to see why I even wrote that. I guess my point was "I can't think of good reason this shouldn't exist." so it's cool that it does. As dvgrn points out, I am more interested in whether a finite stabilization is always possible.

Your example also has the property that every 3x3 window contains exactly 4 live cells. These still life patterns have a simple characterization I posted here. I wonder if there are others like it with only themselves as their ancestor.

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

Re: Unproven conjectures

Post by Ilkka Törmä » January 5th, 2022, 9:50 am

dvgrn wrote:
January 3rd, 2022, 9:47 am
How computationally intensive is the analysis being done here? I suppose I'm asking about both the initial search (to find the "most forcing" stable agar in an MxN box) and the frame-shift analysis. But I guess once the stability-compatible MxN agars are enumerated, all the frames will already be in the list somewhere -- if you're doing things that way.
Finding the agar took 3.5 minutes once I tried size 6x3, and checking the bounds for the shifts took about 5 minutes in total on my unexceptional laptop. It might be faster if I used a smarter algorithm. Once I have the agar and the correct bounds, I can check in 2 seconds that 4 and 7 cells are enough to force it.
pcallahan wrote:
January 3rd, 2022, 1:46 pm
As dvgrn points out, I am more interested in whether a finite stabilization is always possible.
Do you mean whether finite still-life compatible patches can always be extended into finite still lives?

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

Re: Unproven conjectures

Post by pcallahan » January 5th, 2022, 1:23 pm

Ilkka Törmä wrote:
January 5th, 2022, 9:50 am
Do you mean whether finite still-life compatible patches can always be extended into finite still lives?
Yes. One of my obstacles in making any progress is an inability to characterize whether a patch can be stabilized at all. So maybe another way to express it is the reverse: is there a patch of cells that can only be stabilized to a still life with an infinite still life stabilizer? Dean Hickerson has conjectured that any such patch can be stabilized with a border of 5 or 6 cells around it. I am not sure if he had an idea for a proof or if this was just his observation. Note that this does not mean any mXn bounding box can be stabilized as (m+k)X(n+k) for some constant k and in fact there's a counterexample viewtopic.php?f=7&t=3180&p=86646&hilit=hickerson#p86644 But if the border is not box-shaped it could still hold. (Edited: as calcyman points out below, the preceding statement is incorrect, and in fact there counterexample shows there is not always a constant-border stabilization.)

If you have any ideas for proving this, I'd love to see it. As far as I know it's still open.

BTW, if true (assuming stabilizer size is polynomial in the original size), it follows that it is an NP-complete problem to check whether a set of assigned cells can be stabilized into a still life (way back I had some gadgets for the NP-hard proof and they should not be hard to reconstruct). If in some cases the stabilizer must be infinite, then the question could potentially be undecidable for some assignments (like completing certain sets of Wang tiles). That would be interesting, but I suspect it's not as hard as all that. I still believe that there is some constant-width stabilizing border for any such patch. (Edited: no, that has been disproven. So the question is whether the cells forced by a patch are polynomial in the size of the patch and whether there is a stabilizer for them.)
Last edited by pcallahan on January 6th, 2022, 7:46 pm, edited 1 time in total.

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

Re: Unproven conjectures

Post by calcyman » January 5th, 2022, 5:30 pm

pcallahan wrote:
January 5th, 2022, 1:23 pm
Yes. One of my obstacles in making any progress is an inability to characterize whether a patch can be stabilized at all. So maybe another way to express it is the reverse: is there a patch of cells that can only be stabilized to a still life with an infinite still life stabilizer? Dean Hickerson has conjectured that any such patch can be stabilized with a border of 5 or 6 cells around it. I am not sure if he had an idea for a proof or if this was just his observation. Note that this does not mean any mXn bounding box can be stabilized as (m+k)X(n+k) for some constant k and in fact there's a counterexample viewtopic.php?f=7&t=3180&p=86646&hilit=hickerson#p86644 But if the border is not box-shaped it could still hold.
Wait, what? If a patch of still-life is stabilisable with a k-cell border, then that k-cell border must be contained within the (m+2k)-by-(n+2k) rectangle centred on the original m-by-n bounding box of the original patch, unless I'm misunderstanding what you mean by 'k-cell border'?
What do you do with ill crystallographers? Take them to the mono-clinic!

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

Re: Unproven conjectures

Post by pcallahan » January 5th, 2022, 5:42 pm

calcyman wrote:
January 5th, 2022, 5:30 pm
Wait, what? If a patch of still-life is stabilisable with a k-cell border, then that k-cell border must be contained within the (m+2k)-by-(n+2k) rectangle centred on the original m-by-n bounding box of the original patch, unless I'm misunderstanding what you mean by 'k-cell border'?
Never mind. You're right. I wasn't thinking clearly. I'm referring to this counterexample.
Extrementhusiast wrote:
December 28th, 2019, 3:01 pm
I may have found a counterexample:

Code: Select all

x = 90, y = 3, rule = B3/S23
b2o3b2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o3b
2o2b2o3b2o$2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o3b2o
2b2o3b2o2b2o3b2o2b2o$3b2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o
3b2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o!
According to JLS, the only way to stabilize it is with more copies of itself, bounded by a line of slope -1/3.
So in this case, if we start with a 3 row by n column patch, we have to add O(n) more rows to complete it.

Edited: This is also disproven by the counterexample because we need to add more rows than we had columns: "It's possible (i.e. not disproven) that there is always a stabilized pattern with a diameter within an additive constant of the original patch, but I can't really claim that's what I meant."

My intuition was always that you should be able to stabilize with a constant border, and the above counterexample shows it's incorrect. The best I would now claim is that the diameter of the stabilized patch is within a constant multiplicative factor of the patch.

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

Re: Unproven conjectures

Post by erictom333 » January 5th, 2022, 6:31 pm

pcallahan wrote:
January 5th, 2022, 5:42 pm
calcyman wrote:
January 5th, 2022, 5:30 pm
Wait, what? If a patch of still-life is stabilisable with a k-cell border, then that k-cell border must be contained within the (m+2k)-by-(n+2k) rectangle centred on the original m-by-n bounding box of the original patch, unless I'm misunderstanding what you mean by 'k-cell border'?
Never mind. You're right. I wasn't thinking clearly. I'm referring to this counterexample.
Extrementhusiast wrote:
December 28th, 2019, 3:01 pm
I may have found a counterexample:

Code: Select all

x = 90, y = 3, rule = B3/S23
b2o3b2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o3b
2o2b2o3b2o$2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o3b2o
2b2o3b2o2b2o3b2o2b2o$3b2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o
3b2o2b2o3b2o2b2o3b2o2b2o3b2o2b2o!
According to JLS, the only way to stabilize it is with more copies of itself, bounded by a line of slope -1/3.
So in this case, if we start with a 3 row by n column patch, we have to add O(n) more rows to complete it.

Edited: This is also disproven by the counterexample because we need to add more rows than we had columns: "It's possible (i.e. not disproven) that there is always a stabilized pattern with a diameter within an additive constant of the original patch, but I can't really claim that's what I meant."

My intuition was always that you should be able to stabilize with a constant border, and the above counterexample shows it's incorrect. The best I would now claim is that the diameter of the stabilized patch is within a constant multiplicative factor of the patch.
Here's my best stabilisation.

Code: Select all

x = 67, y = 28, rule = LifeHistory
53.2A.A$50.2A2.A.3A$47.2A2.2A6.A$44.2A2.2A3.5A.A$41.2A2.2A3.2A2.A2.A.
3A$38.2A2.2A3.2A2.2A9.A$35.2A2.2A3.2A2.2A3.8A.A$32.2A2.2A3.2A2.2A3.2A
2.A2.A2.A.3A$29.2A2.2A3.2A2.2A3.2A2.2A12.A$26.2A2.2A3.2A2.2A3.2A2.2A
3.11A.A$23.2A2.2A3.2A2.2A3.2A2.2A3.2A2.A2.A2.A2.A.2A$20.2A2.2A3.2A2.
2A3.2A2.2A3.2A2.2A$17.2A2.2A3.2A2.2A3.2A2.2A3.2A2.2A3.14A$14.2C2D2C3D
2C2D2C3D2C2D2C3D2C2D2C3D2CD.A2.A2.A2.A2.A$A2.A2.A2.A2.A.D2C3D2C2D2C3D
2C2D2C3D2C2D2C3D2C2D2C$14A3.2A2.2A3.2A2.2A3.2A2.2A3.2A2.2A$14.2A2.2A
3.2A2.2A3.2A2.2A3.2A2.2A$2A.A2.A2.A2.A2.2A3.2A2.2A3.2A2.2A3.2A2.2A$.A
.11A3.2A2.2A3.2A2.2A3.2A2.2A$.A12.2A2.2A3.2A2.2A3.2A2.2A$2.3A.A2.A2.A
2.2A3.2A2.2A3.2A2.2A$4.A.8A3.2A2.2A3.2A2.2A$4.A9.2A2.2A3.2A2.2A$5.3A.
A2.A2.2A3.2A2.2A$7.A.5A3.2A2.2A$7.A6.2A2.2A$8.3A.A2.2A$10.A.2A!

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

Re: Unproven conjectures

Post by pcallahan » January 5th, 2022, 6:44 pm

erictom333 wrote:
January 5th, 2022, 6:31 pm
Here's my best stabilisation.
I was going by this one:
dvgrn wrote:
December 29th, 2019, 2:10 pm

Code: Select all

x = 46, y = 35, rule = B3/S23
2o$o2b2o$2b2o2b2o$5b2o2b2o$2b3o3b2o2b2o$3bo2b2o3b2o2b2o$bo3b2o2b2o3b2o
2b2o$b2o5b2o2b2o3b2o2b2o5b2o$5b3o3b2o2b2o3b2o2b2o3bo$6bo2b2o3b2o2b2o3b
2o2bo$4bo3b2o2b2o3b2o2b2o3b3o$4b2o5b2o2b2o3b2o2b2o5b2o$8b3o3b2o2b2o3b
2o2b2o3bo$9bo2b2o3b2o2b2o3b2o2bo$7bo3b2o2b2o3b2o2b2o3b3o$7b2o5b2o2b2o
3b2o2b2o5b2o$11b3o3b2o2b2o3b2o2b2o3bo$12bo2b2o3b2o2b2o3b2o2bo$10bo3b2o
2b2o3b2o2b2o3b3o$10b2o5b2o2b2o3b2o2b2o5b2o$14b3o3b2o2b2o3b2o2b2o3bo$
15bo2b2o3b2o2b2o3b2o2bo$13bo3b2o2b2o3b2o2b2o3b3o$13b2o5b2o2b2o3b2o2b2o
5b2o$17b3o3b2o2b2o3b2o2b2o3bo$18bo2b2o3b2o2b2o3b2o2bo$16bo3b2o2b2o3b2o
2b2o3b3o$16b2o5b2o2b2o3b2o2b2o5b2o$26b2o2b2o3b2o2b2o3bo$29b2o2b2o3b2o
2bo$32b2o2b2o3b3o$35b2o2b2o$38b2o2b2o$41b2o2bo$44b2o!
But in either case, the diameter grows by more than an additive constant.

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

Re: Unproven conjectures

Post by Ilkka Törmä » January 6th, 2022, 6:17 pm

I got together with Ville Salo this week to think about this self-forcing agar. We ended up solving the generalized version of the grandfather problem (https://www.conwaylife.com/wiki/Grandfather_problem): for all n there exists a pattern that has an nth predecessor but not an (n+1)st predecessor.
I'll sketch the proof below.

So, it turns out that up to shifts and reflections, there are exactly eleven 6x3-periodic still life agars with unique predecessors.
For each of them, if you repeat the pattern a certain (finite) number of rows/columns in each direction, the central 6x3 patch of each preimage is forced to be the original pattern, just like with the first one I found.

Code: Select all

000101
011010
101001

000101
010010
111010

001001
010110
110010

001001
001011
110100

000001
001011
111100

000101
011001
101010

000001
011100
101011

000001
011110
110010

000101
011010
110010

000001
010110
111010

000000
010111
111010
Let's focus on number 7 from the top, shifted to make the structure clearer:

Code: Select all

#C [[ THUMBNAIL ]]
x = 6, y = 3, rule = B3/S23:T6,3
ooobbb$
bobooo$
bbbbob!
It happens to have the following additional property: all finite perturbations spread to the left and right at lightspeed. More explicitly, let X be the infinite agar, and let Y be any other universe that differs from X in some finite set of cells. If the leftmost difference between X and Y is in column i, then the leftmost difference between X and the successor of Y is in column i-1. Symmetrically for the rightmost difference. The proof is a simple case analysis: depending on which column of the agar pattern i is, let (i,j) be either the highest or lowest cell on that column that differs between X and Y, and check that in each case one of the cells (i-1,j-1), (i-1,j) or (i-1,j+1) of Y will be flipped on the next step.

Using the above property we construct, for any given n, a pattern with an nth predecessor but not an (n+1)st one. Start with a large patch of the agar and flip one cell in the center. Let this pattern P evolve for n steps and call the result Q. If the initial patch was large enough, Q still has a large patch of the agar that now contains a perturbation of width 2n+1.

This Q has at least one nth predecessor, namely P. Suppose for a contradiction that it has a chain of n+1 predecessors R(0), R(1), R(2), ... R(n+1) = Q. If the initial patch was large enough, the self-forcing property of the agar pattern guarantees that each R(i) contains a "ring" of the agar pattern around the central cell. They are positioned so that the ring of R(i) is contained in the ring or R(i+1). The thickness of the rings decreases at a constant rate as we decrease i, so we can guarantee that R(0) has a ring of thickness at least 2. Since Q contains a finite perturbation of the agar, it has to come from somewhere, so R(0) also contains a finite perturbation inside the ring. If the width of that perturbation is w, then it will spread into a perturbation of width w+2(n+1) in R(n+1) = Q. But the perturbation in Q has width 2n+1 < w+2(n+1), a contradiction. End of proof sketch.

Now, the neat thing about this proof technique is that it can be automated, in the sense that I can write a script (and hopefully will find the time to do so) that takes in a CA rule and searches for a self-forcing agar pattern with the property that all finite perturbations spread in opposite directions at constant speed. In fact I first verified the property with a program, followed by Ville doing the case analysis on paper. If the script finds such an agar, the above argument shows that the input CA also has patterns with nth-but-not-(n+1)st predecessors for all n.

Our proof works as such for 15 other totalistic rules, since we don't actually care what happens to live cells with 0, 7 or 8 live neighbors, or dead cells with 8 live neighbors; these patterns just don't occur in the agar nor come up in the case analysis.

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

Re: Unproven conjectures

Post by dvgrn » January 6th, 2022, 6:32 pm

Ilkka Törmä wrote:
January 6th, 2022, 6:17 pm
We ended up solving the generalized version of the grandfather problem (https://www.conwaylife.com/wiki/Grandfather_problem): for all n there exists a pattern that has an nth predecessor but not an (n+1)st predecessor.
Looks great! Assuming that the case analysis works out as you describe, I certainly don't see any holes in that proof outline. Congratulations!

Here's a viewer that allows the eleven 6x3 agars to be copy/pasted into Golly, with the key #7 one highlighted:

Code: Select all

x = 26, y = 23, rule = LifeHistory
8F.8F.8F$F3.A.AF.F3.A.AF.F2.A2.AF$F.2A.A.F.F.A2.A.F.F.A.2A.F$FA.A2.AF
.F3A.A.F.F2A2.A.F$8F.8F.8F2$8F.8F.8F$F2.A2.AF.F5.AF.F3.A.AF$F2.A.2AF.
F2.A.2AF.F.2A2.AF$F2A.A2.F.F4A2.F.FA.A.A.F$8F.8F.8F2$8F.8F.8F$F5BCF.F
5.AF.F3.A.AF$FB3C2BF.F.4A.F.F.2A.A.F$FCBCB2CF.F2A2.A.F.F2A2.A.F$8F.8F
.8F2$8F.8F$F5.AF.F6.F$F.A.2A.F.F.A.3AF$F3A.A.F.F3A.A.F$8F.8F!
#C [[ HEIGHT 500 ZOOM 20 THUMBNAIL THUMBSIZE 3 ]]
It's interesting to have a method of generating grand^N-orphans that doesn't have to rely on checking exponentially increasing number of predecessors as the value of N increases. Just "flip one cell in the center" of a large enough agar patch instantly guarantees a Garden of Eden, none of whose decendants down to T = N can have any ancestors farther back in time than it is.

(Did I say that right?)

EDIT: It does seem as if stabilizing an internal hole in the agar is out of reach, I guess because of the property of peturbations spreading at lightspeed, though it's easy enough to build solid finite rectangular patches. You can see both patches of agar behaving as advertised as they break down:

Code: Select all

x = 310, y = 116, rule = B3/S23
b2ob2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o
2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o41b2ob
2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o
2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o$2bob2o2b
2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o
2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2bo43bob2o2b2o2b2o
2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b
2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2bo$bo131bo41bo131bo$b
133o41b133o$7bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo53bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
$3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o45b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o$2bobob3obob3obob3obob3obob3ob
ob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3ob
ob3obob3obobo43bobob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obobo$bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo41bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$bob3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3obo41bob3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3obo$2bobob3obob3obob3obob3obob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obobo43bobob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o
bob3obob3obob3obob3obob3obob3obob3obob3obob3obobo$7bo5bo5bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo53bo5bo5bo5bo5bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o45b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o$2bobob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o
bob3obob3obob3obob3obob3obob3obob3obob3obob3obobo43bobob3obob3obob3obo
b3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obo
b3obob3obob3obob3obobo$bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo41bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo$bob3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3obo41bob3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3obo$
2bobob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obo
b3obob3obob3obob3obob3obob3obob3obob3obobo43bobob3obob3obob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obob3obob3obobo$7bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5b
o5bo5bo5bo53bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5b
o5bo$3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o45b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o$2bobob3obob3obob3obob3obo
b3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obo
b3obob3obob3obobo43bobob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obobo$bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo41bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$bob3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3obo41bob3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3obo$2bobob3obob3obob3obob3obob3obob3o
bob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o
bob3obobo43bobob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obo
b3obob3obob3obob3obob3obob3obob3obob3obob3obob3obobo$7bo5bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo53bo5bo5bo5bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o45b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o$2bobob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3ob
ob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obobo43bobob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obob3obob3obob3obob3obobo$bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo5bo5bo41bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo5bo5bo$bob3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3obo41bob3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
bo$2bobob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obobo43bobob3obob3obob3obob3o
bob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o
bob3obob3obob3obobo$7bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5b
o5bo5bo5bo5bo53bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5b
o5bo5bo$3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o45b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o$2bobob3obob3obob3obob3o
bob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o
bob3obob3obob3obobo43bobob3obob3obob3obob3obob3obob3obob3obob3obob3obo
b3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obobo$bo5bo5b
o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo41bo5bo5b
o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$bob3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3obo41bob3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3obo$2bobob3obob3obob3obob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obob3obobo43bobob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o
bob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obobo$7bo5bo5bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo53bo5bo5bo5bo5bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o45b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o$2bobob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obobo43bobob3obob3o
bob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o
bob3obob3obob3obob3obob3obobo$bo5bo5bo5bo5bo5bo5bo5bo47bo5bo5bo5bo5bo
5bo5bo5bo41bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo5bo$bob3o3b3o3b3o3b3o3b3o3b3o3b3o3b45o3b3o3b3o3b3o3b3o3b3o3b3o3b
3obo41bob3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3obo$2bobob3obob3obob3obob3obob3obob3obob3o3bo
2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2b3obob3obob3obob3obob3obob3obo
b3obobo43bobob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obobo$7bo5bo5bo5bo5bo5bo
5bo47bo5bo5bo5bo5bo5bo5bo53bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo$3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo43bo3b3o3b3o3b3o3b
3o3b3o3b3o3b3o45b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o$2bobob3obob3obob3obob3obob3obob3obo
b3obo41bob3obob3obob3obob3obob3obob3obob3obobo43bobob3obob3obob3obob3o
bob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o
bob3obob3obob3obobo$bo5bo5bo5bo5bo5bo5bo5bo2bo41bo2bo5bo5bo5bo5bo5bo5b
o5bo41bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5b
o5bo$bob3o3b3o3b3o3b3o3b3o3b3o3b3o3bo43bo3b3o3b3o3b3o3b3o3b3o3b3o3b3ob
o41bob3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3obo$2bobob3obob3obob3obob3obob3obob3obob3o45b3obo
b3obob3obob3obob3obob3obob3obobo43bobob3obob3obob3obob3obob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obobo$7bo5bo5bo5bo5bo5bo5bo47bo5bo5bo5bo5bo5bo5bo53bo5bo5bo5bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3bo43bo3b3o3b3o3b3o3b3o3b3o3b3o3b3o45b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o$2bobob3obob
3obob3obob3obob3obob3obob3obo41bob3obob3obob3obob3obob3obob3obob3obobo
43bobob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3ob
ob3obob3obob3obob3obob3obob3obob3obob3obobo$bo5bo5bo5bo5bo5bo5bo5bo2bo
41bo2bo5bo5bo5bo5bo5bo5bo5bo41bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo5bo5bo5bo$bob3o3b3o3b3o3b3o3b3o3b3o3b3o3bo43bo3b3o
3b3o3b3o3b3o3b3o3b3o3b3obo41bob3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3obo$2bobob3obob3obob3ob
ob3obob3obob3obob3o45b3obob3obob3obob3obob3obob3obob3obobo43bobob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obob3obob3obob3obob3obob3obobo$7bo5bo5bo5bo5bo5bo5bo47bo5bo5bo5bo5bo
5bo5bo53bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
$3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo43bo3b3o3b3o3b3o3b3o3b3o3b3o3b3o45b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o$2bobob3obob3obob3obob3obob3obob3obob3obo41bob3obob3obob
3obob3obob3obob3obob3obobo43bobob3obob3obob3obob3obob3obob3obob3obob3o
bob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obobo$
bo5bo5bo5bo5bo5bo5bo5bo2bo41bo2bo5bo5bo5bo5bo5bo5bo5bo41bo5bo5bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$bob3o3b3o3b3o3b
3o3b3o3b3o3b3o3bo43bo3b3o3b3o3b3o3b3o3b3o3b3o3b3obo41bob3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3obo$2bobob3obob3obob3obob3obob3obob3obob3o45b3obob3obob3obob3obob3obo
b3obob3obobo43bobob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obobo$7bo5bo5bo5bo
5bo5bo5bo47bo5bo5bo5bo5bo5bo5bo53bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo5bo5bo$3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo43bo3b3o3b3o
3b3o3b3o3b3o3b3o3b3o45b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o$2bobob3obob3obob3obob3obob3ob
ob3obob3obo41bob3obob3obob3obob3obob3obob3obob3obobo43bobob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obob3obob3obob3obob3obobo$bo5bo5bo5bo5bo5bo5bo5bo2bo41bo2bo5bo5bo5bo
5bo5bo5bo5bo41bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo5bo5bo$bob3o3b3o3b3o3b3o3b3o3b3o3b3o3bo43bo3b3o3b3o3b3o3b3o3b3o
3b3o3b3obo41bob3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3obo$2bobob3obob3obob3obob3obob3obob3obo
b3o45b3obob3obob3obob3obob3obob3obob3obobo43bobob3obob3obob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obob3obob3obobo$7bo5bo5bo5bo5bo5bo5bo47bo5bo5bo5bo5bo5bo5bo53bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3bo43bo3b3o3b3o3b3o3b3o3b3o3b3o3b3o45b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o$
2bobob3obob3obob3obob3obob3obob3obob3obo41bob3obob3obob3obob3obob3obob
3obob3obobo43bobob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o
bob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obobo$bo5bo5bo5bo5bo
5bo5bo5bo2bo41bo2bo5bo5bo5bo5bo5bo5bo5bo41bo5bo5bo5bo5bo5bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$bob3o3b3o3b3o3b3o3b3o3b3o3b3o
3bo43bo3b3o3b3o3b3o3b3o3b3o3b3o3b3obo41bob3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3obo$2bobob3ob
ob3obob3obob3obob3obob3obob3o45b3obob3obob3obob3obob3obob3obob3obobo
43bobob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3ob
ob3obob3obob3obob3obob3obob3obob3obob3obobo$7bo5bo5bo5bo5bo5bo5bo47bo
5bo5bo5bo5bo5bo5bo53bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo5bo5bo$3b3o3b3o3b3o3b3o3b3o3b3o3b3o51b3o3b3o3b3o3b3o3b3o3b3o3b3o
45b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o$2bobob3obob3obob3obob3obob3obob3obob5o2b2o2b2o2b
2o2b2o2b2o2b2o2b2o2b2o2b2o2b2obob3obob3obob3obob3obob3obob3obob3obobo
43bobob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3ob
ob3obob3obob3obob3obob3obob3obob3obob3obobo$bo5bo5bo5bo5bo5bo5bo5bo2bo
2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2ob2obo5bo5bo5bo5bo5bo5bo5bo41bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$bob
3o3b3o3b3o3b3o3b3o3b3o3b3o51b3o3b3o3b3o3b3o3b3o3b3o3b3obo41bob3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3obo$2bobob3obob3obob3obob3obob3obob3obob51obob3obob3obob3obob3o
bob3obob3obobo43bobob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obo
b3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obobo$7bo5bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo53bo5bo5bo5bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o45b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o$2bobob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obo
b3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obobo43bobob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obob3obob3obob3obob3obob3obobo$bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo41bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$bob3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3obo41bob3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3obo$2bobob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o
bob3obob3obob3obob3obob3obob3obob3obob3obob3obobo43bobob3obob3obob3obo
b3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obo
b3obob3obob3obob3obobo$7bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo53bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5b
o5bo5bo5bo$3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o45b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o$2bobob3obob3obob3ob
ob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3ob
ob3obob3obob3obob3obobo43bobob3obob3obob3obob3obob3obob3obob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obobo$bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo41bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$bob
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3obo41bob3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3obo$2bobob3obob3obob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obob3obob3obobo43bobob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o
bob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obobo$7bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo53bo5bo5bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
45b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o$2bobob3obob3obob3obob3obob3obob3obob3obob3obob3ob
ob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obobo43bobob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obob3obob3obob3obob3obob3obob3obobo$bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo41bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$bob3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3obo41bob3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3obo$2bobob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obobo43bobob3obob3o
bob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o
bob3obob3obob3obob3obob3obobo$7bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo5bo53bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo5bo5bo5bo5bo$3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o45b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o$2bobob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obob3obob3obob3obob3obob3obobo43bobob3obob3obob3obob3obob3obob3obob3o
bob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o
bobo$bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo41bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo$bob3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3obo41bob3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3obo$2bobob3obob3obob3ob
ob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3ob
ob3obob3obob3obob3obobo43bobob3obob3obob3obob3obob3obob3obob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obobo$7bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo53bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o45b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o$2bobob3obob3obob3obob3obob3obob3obob3obob3obo
b3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obobo43b
obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obobo$bo5bo5bo5bo5bo5bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo41bo5bo5bo5bo5bo5bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$bob3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3obo41bob3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3obo$2bobob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o
bob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obobo43bobob3obo
b3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obo
b3obob3obob3obob3obob3obob3obobo$7bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo53bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo$3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o45b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o$2bobob3ob
ob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3ob
ob3obob3obob3obob3obob3obob3obobo43bobob3obob3obob3obob3obob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obobo$bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo41bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo$bob3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3obo41bob3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3obo$2bobob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obob3obob3obob3obob3obobo43bobob3obob3obob3obob3obob3obob3obob3obob3o
bob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obobo
2$135o39b135o$o2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo
2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo
2bo2bo2bo2bo38bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo
2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo
2bo2bo2bo2bo$134b2o172b2o!
For a while I was thinking that some kind of tricky counterexample ought to be implied by experiments like this, which almost seem to suggest an alternate stabilization of an area in the center of an agar:

Code: Select all

x = 60, y = 45, rule = B3/S23
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o$bob3obob3obob3obob3obob3obob3ob
ob3obob3obob3obob3o$4bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o$bob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3o$4bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o$bob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o$4bo5bo5bo23bo5bo
5bo5bo$3o3b3o3b3o3b21o3b3o3b3o3b3o$bob3obob3obob3obo17bob3obob3obob3ob
ob3o$4bo5bo5bo5b14o4bo5bo5bo5bo$3o3b3o3b3o3b5o12b4o3b3o3b3o3b3o$bob3ob
ob3obob3obo5b8o6b3obob3obob3obob3o$4bo5bo5bo5b4o6b6o2bo5bo5bo5bo$3o3b
3o3b3o3b5o5b2o7b2o3b3o3b3o3b3o$bob3obob3obob3obo4b2o2b2o2b4o3b3obob3ob
ob3obob3o$4bo5bo5bo4b2obo7bo2bob2obo5bo5bo5bo$3o3b3o3b3o3b3obobobo6bob
obo6bo3b3o3b3o$bob3obob3obob3o7b2o7bo8bob3obob3obob3o$4bo5bo5bo26bo2bo
5bo5bo$3o3b3o3b3obo27bo3b3o3b3o$bob3obob3obobo29b3obob3obob3o$4bo5bo
35bo5bo5bo$3o3b3o3b3o29bo3b3o3b3o$bob3obob3obobo27bob3obob3obob3o$4bo
5bo5bo26bo2bo5bo5bo$3o3b3o3b3obo27bo3b3o3b3o$bob3obob3obobo3bo2bo2bo2b
o2bo2bo2bo2bo4b3obob3obob3o$4bo5bo8b4o2b4o2b4o2b4o5bo5bo5bo$3o3b3o3b3o
33b3o3b3o$bob3obob3obob33obob3obob3o$4bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o$bob3obob3obob3obob3obob3obob3obob
3obob3obob3obob3o$4bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o$bob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o$
4bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o$
bob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o$4bo5bo5bo5bo5bo5bo
5bo5bo5bo5bo$3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o$bob3obob3obob3obob
3obob3obob3obob3obob3obob3obob3o$4bo5bo5bo5bo5bo5bo5bo5bo5bo5bo!
But the property of "perturbations always spread left and right at lightspeed" should rule out any such completions, and I think ultimately they do rule them out. The issue might be that the perturbation may also travel diagonally while it's moving left and right.

kuluma
Posts: 8
Joined: December 16th, 2021, 5:32 am

Re: Unproven conjectures

Post by kuluma » January 6th, 2022, 10:46 pm

dvgrn wrote:
January 6th, 2022, 6:32 pm
It's interesting to have a method of generating grand^N-orphans that doesn't have to rely on checking exponentially increasing number of predecessors as the value of N increases. Just "flip one cell in the center" of a large enough agar patch instantly guarantees a Garden of Eden, none of whose decendants down to T = N can have any ancestors farther back in time than it is.

(Did I say that right?)
You have to flip one cell in the agar, then apply the CA n times, then a linear size patch of that will be an nth step orphan. Maybe that's what you meant. So indeed there is nothing to "check" if you want to generate these things, it's really a polynomial time algorithm that, given n in unary, produces an orphan of level n, with size linear in n.

For more variety, you can in fact change any finite subset of the agar and iterate. Then you may have a few extra preimages but only a function of the diameter of the original change; I think to know the exact maximal preimage chain length you need to do a search exponential in the diameter of the area you started with.

While the higher orphans are quick to generate, they do not have a simple description (beyond running GoL for n steps), since the explosion inside the agar is always very crazy.

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

Re: Unproven conjectures

Post by Ilkka Törmä » January 7th, 2022, 8:23 am

I forgot to include bounds for the sizes of the patches. According to my computations, a padding of 12 cells in every direction is enough to force any 6x3 patch of the agar into its predecessors. This means that to get a level-n orphan, it's enough to take any (28n+13)x(28n+7) patch of the agar, flip the central cell, and evolve for n steps. For n = 4 (the lowest previously unknown case), we can start with a 125x119 patch and evolve it for 4 steps, resulting in the following 117x111 pattern that is a level-4 orphan. (I didn't verify this one separately yet.)

Code: Select all

x = 117, y = 111, rule = B3/S23
2obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obo
b3obob3obob3obob3obob3obob3o$o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3bo$2obob3obob3obob3obob3obob3obob3obob3obo
b3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o$o5bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo$2obob3obo
b3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3ob
ob3obob3obob3obob3o$o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3bo$2obob3obob3obob3obob3obob3obob3obob3obob3obob3obo
b3obob3obob3obob3obob3obob3obob3obob3obob3obob3o$o5bo5bo5bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo$2obob3obob3obob3obob3o
bob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o
bob3o$o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$2b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3bo$2obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3ob
ob3obob3obob3obob3obob3obob3obob3o$o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo$2obob3obob3obob3obob3obob3obob3ob
ob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o$o5bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo$2ob
ob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o
bob3obob3obob3obob3obob3o$o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3bo$2obob3obob3obob3obob3obob3obob3obob3obob3ob
ob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o$o5bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo$2obob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obo
b3obob3obob3o$o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3bo$2obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3o$o5bo5bo5bo5bo5bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo$2obob3obob3obob3obob3obob3o
bob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o
$o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$2b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo
$2obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3ob
ob3obob3obob3obob3obob3obob3o$o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3bo$2obob3obob3obob3obob3obob3obob3obob3obo
b3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o$o5bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo$2obob3obo
b3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3ob
ob3obob3obob3obob3o$o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3bo$2obob3obob3obob3obob3obob3obob3obob3obob3obob3obo
b3obob3obob3obob3obob3obob3obob3obob3obob3obob3o$o5bo5bo5bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo$2obob3obob3obob3obob3o
bob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o
bob3o$o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$2b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3bo$2obob3obob3obob3obob3obob3obob3obob3obob3obob3o3b3obob3obob3obo
b3obob3obob3obob3obob3obob3obob3o$o5bo5bo5bo5bo5bo5bo5bo5bo5b2obo2b2o
4bo5bo5bo5bo5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3obob3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo$2obob3obob3obob3obob3obob3obo
b3obob3obob3obob2ob2o4b2ob3obob3obob3obob3obob3obob3obob3obob3obob3o$
o5bo5bo5bo5bo5bo5bo5bo5bo5b5o3bo3bo5bo5bo5bo5bo5bo5bo5bo5bo$2b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3obobo2b2ob3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3bo$2obob3obob3obob3obob3obob3obob3obob3obob3obob2o2b3obobob3obob3obo
b3obob3obob3obob3obob3obob3obob3o$o5bo5bo5bo5bo5bo5bo5bo5bo5bobobob2o
4bo5bo5bo5bo5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo5b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo$2obob3obob3obob3obob3obob3obob3o
bob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o$o5b
o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo$2ob
ob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o
bob3obob3obob3obob3obob3o$o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3bo$2obob3obob3obob3obob3obob3obob3obob3obob3ob
ob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o$o5bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo$2obob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obo
b3obob3obob3o$o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3bo$2obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3o$o5bo5bo5bo5bo5bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo$2obob3obob3obob3obob3obob3o
bob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o
$o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$2b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo
$2obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3ob
ob3obob3obob3obob3obob3obob3o$o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3bo$2obob3obob3obob3obob3obob3obob3obob3obo
b3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o$o5bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo$2obob3obo
b3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3ob
ob3obob3obob3obob3o$o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3bo$2obob3obob3obob3obob3obob3obob3obob3obob3obob3obo
b3obob3obob3obob3obob3obob3obob3obob3obob3obob3o$o5bo5bo5bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo$2obob3obob3obob3obob3o
bob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o
bob3o$o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$2b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3bo$2obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3ob
ob3obob3obob3obob3obob3obob3obob3o$o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo5bo5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o
3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo$2obob3obob3obob3obob3obob3obob3ob
ob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o$o5bo
5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo$2ob
ob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o
bob3obob3obob3obob3obob3o$o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3bo$2obob3obob3obob3obob3obob3obob3obob3obob3ob
ob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3o$o5bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo$2obob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obo
b3obob3obob3o$o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo
5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3bo$2obob3obob3obob3obob3obob3obob3obob3obob3obob3obob3obob
3obob3obob3obob3obob3obob3obob3obob3obob3o$o5bo5bo5bo5bo5bo5bo5bo5bo5b
o5bo5bo5bo5bo5bo5bo5bo5bo5bo5bo$2b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b
3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3b3o3bo!
#C [[ THUMBNAIL ]]
EDIT: These are pretty crude upper bounds and can probably be improved quite a bit.
Last edited by Ilkka Törmä on January 7th, 2022, 8:38 am, edited 2 times in total.

kuluma
Posts: 8
Joined: December 16th, 2021, 5:32 am

Re: Unproven conjectures

Post by kuluma » January 7th, 2022, 8:24 am

From https://www.conwaylife.com/wiki/Grandfather_problem:
Next levels
"A father and grandfather, but no great-grandfather" pattern[7], and a "father, grandfather and great-grandfather, but no great-great-grandfather" pattern[8], have also been constructed by the same method.

No further levels have been found yet, but they almost certainly do exist
This seems to have been added to the wiki by mtve, if I'm reading history correctly. I would be interested in hearing why it was conjectured that this holds, my guess was 50-50 really. I guess it's a question to mtve, but then again no one has questioned this on the wiki. I guess before mtve's solution to the grandfather problem, no one really wondered about higher orphans out loud?

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

Re: Unproven conjectures

Post by dvgrn » January 7th, 2022, 9:29 am

kuluma wrote:
January 7th, 2022, 8:24 am
I would be interested in hearing why it was conjectured that this holds, my guess was 50-50 really. I guess it's a question to mtve, but then again no one has questioned this on the wiki. I guess before mtve's solution to the grandfather problem, no one really wondered about higher orphans out loud?
My reading of mtve’s statement was always something like “at least one additional level almost certainly exists” — presumably because the SAT~solver methods mtve was using didn’t seem to be running into any insurmountable walls, just getting a little more CPU-intensive for each level.

So I didn’t argue with that “almost certainly”, but I would have put the odds of an unbounded series of Grand^N-Orphans at more like 50-50 odds.

kuluma
Posts: 8
Joined: December 16th, 2021, 5:32 am

Re: Unproven conjectures

Post by kuluma » January 7th, 2022, 9:48 am

dvgrn wrote:
January 7th, 2022, 9:29 am
My reading of mtve’s statement was always something like “at least one additional level almost certainly exists” — presumably because the SAT~solver methods mtve was using didn’t seem to be running into any insurmountable walls, just getting a little more CPU-intensive for each level.

So I didn’t argue with that “almost certainly”, but I would have put the odds of an unbounded series of Grand^N-Orphans at more like 50-50 odds.
Ah, indeed that is a more sensible reading. Yes, that at least a couple more levels exist sounds quite reasonable, why would GoL happen to reach its limit set exactly when some SAT solver runs out of steam.

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

Re: Unproven conjectures

Post by dvgrn » January 7th, 2022, 4:50 pm

JavaLifeSearch has some interesting things to say about the above level-4 orphan.

When I set up a search four ticks back in time, looking for any predecessors at all in a 17x17 area around the center of the disturbance -- and assuming that the agar remains undisturbed outside that area -- then JLS instantly fills in all of the cells for all four previous generations.

That is to say, there's a unique predecessor for each step backwards, ending with the original agar with just one bit flipped. JLS doesn't even have to run an actual search to decide this; that result shows up just from the preliminary instantaneous analysis of which cells are forced by a surrounding ring of that agar. If you actually run the four-tick search, the result is confirmed -- there's only one possible solution for that region.

Somewhat similarly, setting up a search five ticks back in time doesn't work: JLS does its preliminary analysis and identifies a few cells in the undisturbed agar ring as being "errors" -- self-contradictory. As you step backwards in time, you can see that one more column of cells on each edge of the 17x17 area is forced to match the agar, every tick you go backwards.

Now, I know that setting up JLS to assume an undisturbed agar outside of 17x17 is a little bit suspect: I'm not actually doing a rigorous independent check that the candidate level-4 orphan really has no 5-tick predecessors of any kind. Still, it's interesting to see what JLS can deduce by looking at these problems -- see attached.

Maybe some JLS expert can see that I'm doing something terribly wrong here... but if not, it looks to me like there will probably turn out to be a much lower bound for the necessary size than 117x111.
Attachments
4-and-5-tick-predecessor-searches.zip
sample JLS setup files for central perturbation
(3.41 KiB) Downloaded 22 times

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

Re: Unproven conjectures

Post by Ilkka Törmä » January 10th, 2022, 6:37 pm

dvgrn wrote:
January 7th, 2022, 4:50 pm
there's a unique predecessor for each step backwards, ending with the original agar with just one bit flipped. JLS doesn't even have to run an actual search to decide this; that result shows up just from the preliminary instantaneous analysis of which cells are forced by a surrounding ring of that agar.
That's interesting, especially since it's due to local analysis of forced cells. My guess is that all finite disturbances within the agar spread in some other pairs of opposite directions besides left and right. Then it would force the nth predecessor to have a disturbance of width 1 in each of those directions, so it would have to be a single cell in the correct position.
dvgrn wrote:
January 7th, 2022, 4:50 pm
Now, I know that setting up JLS to assume an undisturbed agar outside of 17x17 is a little bit suspect: I'm not actually doing a rigorous independent check that the candidate level-4 orphan really has no 5-tick predecessors of any kind. Still, it's interesting to see what JLS can deduce by looking at these problems -- see attached.

Maybe some JLS expert can see that I'm doing something terribly wrong here... but if not, it looks to me like there will probably turn out to be a much lower bound for the necessary size than 117x111.
I don't know how exactly JLS works, but this is as expected. If you can guarantee (possibly by hardcoding it like you did here) that all predecessors up to and including the (n+1)st one have a ring of the agar pattern at the same position surrounding the finite disturbance, then the (n+1)st predecessor actually doesn't exist, no matter what the size of the ring is. I don't think this analysis has much bearing on the size of the patterns, since that's mostly determined by the number of extra rows and columns needed to enforce the ring in the predecessors.

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

Re: Unproven conjectures

Post by Ilkka Törmä » January 13th, 2022, 6:35 pm

New results (by me and Ville Salo). There exists a finite pattern that forces itself to occur entirely in each of its preimages. It's this one (surrounded by gray cells):

Code: Select all

x = 30, y = 24, rule = LifeHistory
5.22F$2.4FA4.2A4.2A4.2A.2F$.2FA2.A.2A2.A.2A2.A.2A2.A.A2F$2F2A.A2.2A.A
2.2A.A2.2A.A2.2AF$F4.2A4.2A4.2A4.2A3.F$F2A.A2.2A.A2.2A.A2.2A.A2.2A.2F
$FA.2A2.A.2A2.A.2A2.A.2A2.A.2AF$F4.2A4.2A4.2A4.2A4.F$F.2A2.A.2A2.A.2A
2.A.2A2.A.2A.F$F.2A.A2.2A.A2.2A.A2.2A.A2.2A.F$F4.2A4.2A4.2A4.2A4.F$F2A
.A2.2A.A2.2A.A2.2A.A2.2A.AF$FA.2A2.A.2A2.A.2A2.A.2A2.A.2AF$F4.2A4.2A4.
2A4.2A4.F$F.2A2.A.2A2.A.2A2.A.2A2.A.2A.F$F.2A.A2.2A.A2.2A.A2.2A.A2.2A
.F$F4.2A4.2A4.2A4.2A4.F$F2A.A2.2A.A2.2A.A2.2A.A2.2A.AF$2F.2A2.A.2A2.A
.2A2.A.2A2.A.2AF$.F3.2A4.2A4.2A4.2A4.F$.F2A2.A.2A2.A.2A2.A.2A2.A.2A2F
$.2FA.A2.2A.A2.2A.A2.2A.A2.A2F$2.2F.2A4.2A4.2A4.A4F$3.22F!
#C [[ THUMBNAIL ]]
Wherever it occurs in a universe, it must also occur in every predecessor at the same position (we verified this with a SAT solver). Of course, the same holds for the grandfather, and the great-grandfather, and so on. Hence, if you see this pattern somewhere, it must've been there from the beginning of time. It's extracted from the infinite agar tiled by the 6x6 pattern with two snakes and a block. It baffles us that this pattern also generates an agar with a unique predecessor, but it does.

We found the pattern by enumerating 6x6-periodic agars with a unique predecessor until we found one that contains a pattern of size at most 70x70 that forces itself in its predecessors (this agar was the 32nd one we found, and the first one to contain such a pattern). The search took about 3.5 hours, most of which was used by the SAT solver. I don't know how much longer it would take to enumerate all 6x6 agars with unique predecessors, nor how many more there are, but I'll try to run the full search at some point to find out.

The pattern can easily be completed into a still life. Since the pattern inside it can't be created by anything else than itself, it's not glider-constructible (meaning that it doesn't have a glider synthesis). More strongly, this still life can't be constructed on empty space by any gadget whatsoever, so Life doesn't support a universal constructor for all still lifes.

Code: Select all

x = 32, y = 26, rule = B3/S23
2b2obo2b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o2bob2o$2o4b2o4b
2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b
2obo2b2obo$2o4b2o4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo2b2obo$2bob
2o2bob2o2bob2o2bob2o2bob2o$2o4b2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2b
ob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o4b2o$
2b2obo2b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o2bob2o$2o4b2o4b
2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b
2obo2b2obo$2o4b2o4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo2b2obo$2bob
2o2bob2o2bob2o2bob2o2bob2o$2o4b2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2b
ob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o4b2o$
2b2obo2b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o2bob2o!
#C [[ THUMBNAIL ]]

kuluma
Posts: 8
Joined: December 16th, 2021, 5:32 am

Re: Unproven conjectures

Post by kuluma » January 13th, 2022, 7:09 pm

Let me add that dynamically this has the consequence that Game of Life restricted to its limit set (the set of configurations that can be seen after arbitrarily many steps) is not "chain-transitive". In particular it is not topologically transitive or topologically mixing. This is something we have thought about for a long time. I actually thought it would be as hard to solve as the question of sensitivity to initial conditions (very roughly, the question of whether indestructible patterns are possible), which stays wide open (but these agars keep on giving...).

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

Re: Unproven conjectures

Post by dvgrn » January 13th, 2022, 10:05 pm

Wow, this has certainly caused a lot of excitement, though mostly on the ConwayLife Lounge on Discord so far. It's not every day that a half-century-old Life problem gets a shiny new solution -- many congratulations!

I suppose this result must imply a tighter upper bound on the necessary size of a patch of agar with a central disturbance, that is an easily provable Grand^N Orphan. It seems as if the size of the agar patch should only have to expand at lightspeed, on average, to force the no-Nth-grandparent property. (?)

kuluma
Posts: 8
Joined: December 16th, 2021, 5:32 am

Re: Unproven conjectures

Post by kuluma » January 14th, 2022, 12:06 am

dvgrn wrote:
January 13th, 2022, 10:05 pm
I suppose this result must imply a tighter upper bound on the necessary size of a patch of agar with a central disturbance, that is an easily provable Grand^N Orphan. It seems as if the size of the agar patch should only have to expand at lightspeed, on average, to force the no-Nth-grandparent property. (?)
This pattern can only be used for the new result, not for the old one. (EDIT: This refers to the old proof, see calcyman's messages and mine after that.) Namely, it can be easily stabilized from the inside by a sneaky snaky.

Code: Select all

x = 44, y = 44, rule = B3/S23
2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o2bo
b2o2bob2o2bob2o$2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2bob2o
2bob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo$2o4b
2o4b2o4b2o4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo$
2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o$2o4b2o28b2o4b2o$bob2o2bob2o
bo20b2o2bob2o2bo$o2b2obo2bob2o21bobo2b2obo$2o4b2o25bo2b2o4b2o$2b2obo
27b2o3b2obo$2bob2o32bob2o$2o4b2o28b2o4b2o$bob2o2bo29bob2o2bo$o2b2obo
29bo2b2obo$2o4b2o28b2o4b2o$2b2obo32b2obo$2bob2o32bob2o$2o4b2o28b2o4b2o
$bob2o2bo29bob2o2bo$o2b2obo29bo2b2obo$2o4b2o28b2o4b2o$2b2obo32b2obo$2b
ob2o32bob2o$2o4b2o28b2o4b2o$bob2o2bo29bob2o2bo$o2b2obo29bo2b2obo$2o4b
2o28b2o4b2o$2b2obo32b2obo$2bob2o3b2o27bob2o$2o4b2o2bo25b2o4b2o$bob2o2b
obo21b2obo2bob2o2bo$o2b2obo2b2o20bob2obo2b2obo$2o4b2o28b2o4b2o$2b2obo
2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o2bob2o2bo
b2o2bob2o$2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2bob2o2bob2o
2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo$2o4b2o4b2o
4b2o4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo$2bob2o
2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o!
Last edited by kuluma on January 14th, 2022, 12:36 am, edited 1 time in total.

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

Re: Unproven conjectures

Post by calcyman » January 14th, 2022, 12:13 am

Congratulations to Illka and Ville!
dvgrn wrote:
January 13th, 2022, 10:05 pm
Wow, this has certainly caused a lot of excitement, though mostly on the ConwayLife Lounge on Discord so far. It's not every day that a half-century-old Life problem gets a shiny new solution -- many congratulations!

I suppose this result must imply a tighter upper bound on the necessary size of a patch of agar with a central disturbance, that is an easily provable Grand^N Orphan. It seems as if the size of the agar patch should only have to expand at lightspeed, on average, to force the no-Nth-grandparent property. (?)
It implies an overwhelmingly stronger result: for all N, there exists a pattern with an Nth grandparent but no (N+1)th grandparent, and this pattern fits in a box of diameter O(sqrt(log(N))).

For example, consider the following pattern:

Code: Select all

x = 176, y = 134, rule = B3/S23
2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2o
bo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b
2obo2b2obo2b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o2bob2o2bob
2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2b
ob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o
$2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b
2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2b
ob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o
2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob
2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b
2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo
2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o
4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b
2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo2b2obo2b2ob
o2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b
2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo
$2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bo
b2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o
2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o$2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b
2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o
4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o
2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob
2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b
2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo
2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2o
bo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b
2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o
$2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b
2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo
2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o2bob2o2bo
b2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o
2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob
2o$2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o
4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o
2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob
2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2b
ob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo
2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2o
bo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b
2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o
4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo2b2obo2b
2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo
2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2o
bo$2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o
2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob
2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o$2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o
4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b
2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob
2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2b
ob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bo$o2b2obo2b2obo
2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2o
bo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b
2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o
4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b
2o$2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo
2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2o
bo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o2bob2o
2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob
2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2b
ob2o$2o4b2o4b2o4b2o4b2o124b2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2bob2o
2bob3o117b2o2bob2o2bob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2obo2bo2b
o41b2o2bo71bobo2b2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o3b2o40bob4o
69bobob2o4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo47bo30bo43b2o4b2obo
2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o45b2ob7o23b3o47bob2o2bob2o
2bob2o2bob2o$2o4b2o4b2o4b2o4b2o41bo2bobo6bo25bo44b2o4b2o4b2o4b2o4b2o$b
ob2o2bob2o2bob2o2bob2o2bo41b2o3bob2o2b2o24b2o45bob2o2bob2o2bob2o2bob2o
2bo$o2b2obo2b2obo2b2obo2b2obo46b2ob2o7b2o65bo2b2obo2b2obo2b2obo2b2obo$
2o4b2o4b2o4b2o4b2o58bo65b2o4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo
58bo69b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o58b5o65bob2o2bob
2o2bob2o2bob2o$2o4b2o4b2o4b2o4b2o60bo63b2o4b2o4b2o4b2o4b2o$bob2o2bob2o
2bob2o2bob2o2bo54b4o67bob2o2bob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b
2obo49b2o4bo2bo66bo2b2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o48b2o74b
2o4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo63b2o63b2obo2b2obo2b2obo2b
2obo$2bob2o2bob2o2bob2o2bob2o58b2obo2bo9b2o5b2o45bob2o2bob2o2bob2o2bob
2o$2o4b2o4b2o4b2o4b2o56b2ob2o11b2o5b2o43b2o4b2o4b2o4b2o4b2o$bob2o2bob
2o2bob2o2bob2o2bo125bob2o2bob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2o
bo77b2o46bo2b2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o76b2o46b2o4b2o4b
2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo83b2o43b2obo2b2obo2b2obo2b2obo$2bob
2o2bob2o2bob2o2bob2o47b2o33bo2bo42bob2o2bob2o2bob2o2bob2o$2o4b2o4b2o4b
2o4b2o46bo33bo2bo40b2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2bob2o2bo43b3o
21b2o11b5o14b2o24bob2o2bob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2obo
44bo23bo15b2ob2o11b2o23bo2b2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o
48b2o19bo15bo38b2o4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo18b2o31bo
18b2o26b2o5b2o21b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o18bo
32bobo14bo3b2o24b2o5b2o21bob2o2bob2o2bob2o2bob2o$2o4b2o4b2o4b2o4b2o11b
2o5bo31b2o14b4o2bo51b2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2bob2o2bo11bo
5b2o50bob2o52bob2o2bob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2obo9b2ob
o47b2o5b2obobo34b2o16bo2b2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o8bo
2bob2o2b2o40b2o5b2obobo35bo16b2o4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b
2obo12b2obo3b2o50bob2o5b2o2bo22bo5b2o13b2obo2b2obo2b2obo2b2obo$2bob2o
2bob2o2bob2o2bob2o15bo55bo7bob4o22b2o5bo13bob2o2bob2o2bob2o2bob2o$2o4b
2o4b2o4b2o4b2o13b2o52bobo7bo34bob2o8b2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bo
b2o2bob2o2bo6b2o59b2o6b2ob7o20b2o2b2obo2bo9bob2o2bob2o2bob2o2bob2o2bo$
o2b2obo2b2obo2b2obo2b2obo6bobo52b2o11bo2bobo6bo19b2o3bob2o10bo2b2obo2b
2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o5bo55bo11b2o3bob2o2b2o24bo13b2o4b2o
4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo4b2obo50b2o3bob2o12b2ob2o7b2o18b
2o15b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o5bobob2o5b2o17b2o
21b2o2b2obo2bo23bo25b2o8bob2o2bob2o2bob2o2bob2o$2o4b2o4b2o4b2o4b2o3bob
ob2o5b2o18bo28bob2o21bo27bobo5b2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2bo
b2o2bo2b2obo26bo19b2o2b2o5bo24b5o25bo6bob2o2bob2o2bob2o2bob2o2bo$o2b2o
bo2b2obo2b2obo2b2obo3bo2b4o14b2o7b2o18bo3bo5b2o28bo25bob2o2bo2b2obo2b
2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o3b2o3bo14bobo4b2o3bo14bobo5bo27b4o
18b2o5b2obobo3b2o4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo7b2o18bo3bo
2b4o14b2o5b2o21b2o4bo2bo18b2o5b2obobo5b2obo2b2obo2b2obo2b2obo$2bob2o2b
ob2o2bob2o2bob2o7bo19b2o2b2obo47b2o36bob2o4bob2o2bob2o2bob2o2bob2o$2o
4b2o4b2o4b2o4b2o7bo22bobob2o5b2o50b2o4b2o14b4o2bo2b2o4b2o4b2o4b2o4b2o$
bob2o2bob2o2bob2o2bob2o2bo6b2o22bobob2o5b2o45b2obo2bo3bobo14bo3b2o4bob
2o2bob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2obo30b2obo55b2ob2o5bo18b
2o5bo2b2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o32bo64b2o19bo5b2o4b2o
4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo34bobo81bo9b2obo2b2obo2b2obo2b2ob
o$2bob2o2bob2o2bob2o2bob2o35b2o24bo31bo24b2o8bob2o2bob2o2bob2o2bob2o$
2o4b2o4b2o4b2o4b2o40b2o17b3o29b3o30b2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob
2o2bob2o2bo40bo21bo14b2o15bo30bob2o2bob2o2bob2o2bob2o2bo$o2b2obo2b2obo
2b2obo2b2obo38b2obo3b2o15b2o15bo14b2o29bo2b2obo2b2obo2b2obo2b2obo$2o4b
2o4b2o4b2o4b2o35bo2bob2o2b2o29b3o46b2o4b2o4b2o4b2o4b2o$2b2obo2b2obo2b
2obo2b2obo37b2obo36bo50b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bob
2o40bo5b2o80bob2o2bob2o2bob2o2bob2o$2o4b2o4b2o4b2o4b2o38b2o5bo78b2o4b
2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2bob2o2bo43bo28b2ob2o27b2ob2o16bob2o2b
ob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2obo44b2o27b2obo2bo25b2obo2bo
13bo2b2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o77b2o30b2o13b2o4b2o4b2o
4b2o4b2o$2b2obo2b2obo2b2obo2b2obo66b2o30b2o28b2obo2b2obo2b2obo2b2obo$
2bob2o2bob2o2bob2o2bob2o66b2o4bo2bo22b2o4bo2bo20bob2o2bob2o2bob2o2bob
2o$2o4b2o4b2o4b2o4b2o70b4o28b4o18b2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o
2bob2o2bo76bo31bo16bob2o2bob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2ob
o73b5o27b5o15bo2b2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o72bo31bo19b
2o4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo76bo31bo19b2obo2b2obo2b2obo
2b2obo$2bob2o2bob2o2bob2o2bob2o63b2ob2o7b2o18b2ob2o7b2o19bob2o2bob2o2b
ob2o2bob2o$2o4b2o4b2o4b2o4b2o57b2o3bob2o2b2o19b2o3bob2o2b2o22b2o4b2o4b
2o4b2o4b2o$bob2o2bob2o2bob2o2bob2o2bo57bo2bobo6bo19bo2bobo6bo23bob2o2b
ob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2obo60b2ob7o22b2ob7o23bo2b2ob
o2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o61bo31bo30b2o4b2o4b2o4b2o4b2o$2b
2obo2b2obo2b2obo2b2obo63bob4o26bob4o27b2obo2b2obo2b2obo2b2obo$2bob2o2b
ob2o2bob2o2bob2o4b2o58b2o2bo27b2o2bo27bob2o2bob2o2bob2o2bob2o$2o4b2o4b
2o4b2o4b2obobo115b2o3b2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2bob2o2bobo
117bo2bo2bob2o2bob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2obo2b2o117b
3obo2b2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o124b2o4b2o4b2o4b2o4b2o$
2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2o
bo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b
2obo2b2obo2b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o2bob2o2bob
2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2b
ob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o
$2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b
2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2b
ob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o
2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob
2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b
2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo
2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o
4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b
2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo2b2obo2b2ob
o2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b
2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo
$2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bo
b2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o
2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o$2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b
2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o
4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o
2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob
2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b
2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo
2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2o
bo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b
2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o
$2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b
2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo
2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o2bob2o2bo
b2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o
2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob
2o$2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o
4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o
2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob
2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2b
ob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo
2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2o
bo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b
2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o
4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo2b2obo2b
2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo
2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2o
bo$2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o
2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob
2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o$2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o
4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b
2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob
2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2b
ob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bo$o2b2obo2b2obo
2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2o
bo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b
2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o
4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o4b
2o$2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo
2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo2b2o
bo2b2obo2b2obo2b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o2bob2o
2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob
2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2bob2o2b
ob2o!
Note that any ancestor must contain that annular wall.

Now, it's very easy to rewind it for 7,000,000 ticks. On the other hand, it's impossible to rewind it for 2^12000 ticks, because any (2^12000)-generation ancestor cannot breach the annular wall within those 2^12000 ticks, and therefore the interior of the central clearing must have become periodic within those 2^12000 generations (by the pigeonhole principle; there aren't that many different configurations of the central clearing). But the state that's shown in the central clearing of the RLE above is not the phase of any oscillator, because it breaches the annular wall very soon whereas an oscillator must continue forever.

Therefore there's some N between 7,000,000 and 2^12000 for which this pattern has an Nth grandparent but not an (N+1)th. Then, you get corresponding patterns for all values of M <= N by rewinding this pattern by N-M generations.

It's clear that this lower bound on N (7,000,000) grows like exp(O(sidelength^2)), because we can pack a quadratic number of pulse dividers into the central clearing. The upper bound also grows like exp(O(sidelength^2)), but hiding a different constant inside the 'O'. The result follows.

Note that the proof is only constructive in a mathematical sense, not a practical one: it's computationally intractable to determine the exact value of N for the RLE above. I'm sure that you can do much better than my incredibly loose bounds, but narrowing the gap completely is infeasible in practice.
What do you do with ill crystallographers? Take them to the mono-clinic!

Post Reply