Unproven conjectures

For general discussion about Conway's Game of Life.
User avatar
Hdjensofjfnen
Posts: 1516
Joined: March 15th, 2016, 6:41 pm
Location: r cis θ

Re: Unproven conjectures

Post by Hdjensofjfnen » March 19th, 2019, 10:46 pm

Bullet51 wrote:
Hdjensofjfnen wrote:Maybe unrelated, but does anyone have a proof that any speed greater than c/4 diagonal is unachievable in Life? After all, there's a 2c/7 in a rule one transition from Life:

Code: Select all

x = 5, y = 5, rule = B3/S234w
3o$b2o$2b3o$3b2o$4bo!
Here: http://www.njohnston.ca/2009/10/spacesh ... -automata/
Huh! Interesting. Never thought it was a matter of overpopulation (but it should be obvious given that the spaceship above requires S4w to survive).
"A man said to the universe:
'Sir, I exist!'
'However,' replied the universe,
'The fact has not created in me
A sense of obligation.'" -Stephen Crane

Code: Select all

x = 7, y = 5, rule = B3/S2-i3-y4i
4b3o$6bo$o3b3o$2o$bo!

User avatar
testitemqlstudop
Posts: 1362
Joined: July 21st, 2016, 11:45 am
Location: in catagolue
Contact:

Re: Unproven conjectures

Post by testitemqlstudop » March 19th, 2019, 11:11 pm

OCA:

Is cellular automaton omnivelocital? (i.e. that 7,1c/8)
Are there spaceships in 1d B3/S23? (credits to hdjen)
What are the least transitions required for Turing-completeness in isotropic non-totalistic 2-dimensional CA? What about non-isotropic?

CA:

Can Life support all sub-c/2 orthogonal velocities? What about diagonal or oblique?

Sarp
Posts: 214
Joined: March 1st, 2015, 1:28 pm

Re: Unproven conjectures

Post by Sarp » March 20th, 2019, 3:15 am

testitemqlstudop wrote: What are the least transitions required for Turing-completeness in isotropic non-totalistic 2-dimensional CA?
We have proven B2ae/S and B2ac/S to be Turing complete in the discord.

Code: Select all

x = 140, y = 120, rule = B2ae/S
13$93bo$94bo2$69bo17bo12bo17bo$70bo16bo12bo16bo$121bo$120bo4$40bo$41bo
2$16bo17bo12bo17bo26bo2bo$17bo16bo12bo16bo28b2o9$39bo2bo77b2o$40b2o2$
104bo$103bo$111bo$110bo12bo$20bo89bo13bo$21bo89bo$21bo$20bo3$120b2o3$
39bo2bo$40b2o6$97bo$96bo$8bo$9bo4$120bo$121bo$39bo2bo$40b2o10$8b2o5$
18bo15bo4bo2bo$6bo12bo15bo4b2o$5bo13bo15bo$18bo15bo2$40bo$39bo2$8b2o
17$9bo$8bo!

Code: Select all

x = 249, y = 163, rule = B2ac/S
49bobo$54bo2$52b2o2$52b2o2$51bo2bo2$52b2o4$43bo$41bo3bo$41bo3bo$43bo$
38b2o2$37bo2bo10bo2$38b2o12b2o3$170bobo$24bo2$24bo6bo11bo$27bobo3bo11b
o$27bobo3bo11bo57bo71bo23bo23bo11bo5bo$25bo5bo71bo65b2o4bo23bo23bo11bo
5bo$105bo71bo23bo23bo22bo$171bo$233b2o13bo6$232bo2bo3$214b2o2$216bo18b
obo7$224bo$218bo$218bo$169b2o43b2o8bo4bo2$171bo57bo4$214b2o7$216bobo
11$169b2o2$171bo3$97bobo5$99bo2bo6$86bo13b2o2$86bo34bo23bo23bo$93bo5bo
23bo23bo23bo$93bo5bo23bo23bo23bobo11bo5bo$173bo11bo5bo$175bo22bo2$30bo
bo136b2o12b2o13bo2$171bo4$182bo2bo$33b2o$183bo$179bo$173bo7bo$19bo82b
2o69bo$169b2o8bo$19bo4bo8b2o66bo$30bo$30bo$24bo2$169b2o5$11bobo18bo2$
33b2o136bobo3$13bo2bo6$o13b2o$102b2o$o22bo23bo23bo23bo24bo23bo$7bo5bo
11bo23bo23bo23bo3bo20bo23bo$7bo5bo11bo23bo23bo23bo24bo23bo4bo2$151bo4$
93bo$99bo$99bo$88bo4bo8b2o2$88bo4$102b2o2$51bo2$51bo3$99bobo!
However I'm not sure if any 1 transition TC rules exist
WADUFI

User avatar
Hdjensofjfnen
Posts: 1516
Joined: March 15th, 2016, 6:41 pm
Location: r cis θ

Re: Unproven conjectures

Post by Hdjensofjfnen » March 20th, 2019, 5:01 am

testitemqlstudop wrote: Can Life support all sub-c/2 orthogonal velocities? What about diagonal or oblique?
Life is known to support all sub-c/4 orthogonal velocities. However, I'm not sure about the speeds between c/4 and c/2. As for diagonal and oblique, I'm not sure either.
"A man said to the universe:
'Sir, I exist!'
'However,' replied the universe,
'The fact has not created in me
A sense of obligation.'" -Stephen Crane

Code: Select all

x = 7, y = 5, rule = B3/S2-i3-y4i
4b3o$6bo$o3b3o$2o$bo!

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

Re: Unproven conjectures

Post by calcyman » March 20th, 2019, 5:36 am

Hdjensofjfnen wrote:
testitemqlstudop wrote: Can Life support all sub-c/2 orthogonal velocities? What about diagonal or oblique?
Life is known to support all sub-c/4 orthogonal velocities. However, I'm not sure about the speeds between c/4 and c/2. As for diagonal and oblique, I'm not sure either.
From a universal constructor argument (using blinker puffers), you can achieve any rational velocity *strictly* below the vacuum speed limit -- that is to say, you can attain any (a,b)c/d where 2(a + b) < d.

As a partial converse, it's impossible to attain (a,b)c/d where 2(a + b) > d (originally proved by Conway).

What remains are the velocities where 2(a + b) == d, where there's neither a proof of existence nor non-existence. Currently there are only three known examples: the velocities of the glider, the LWSS, and Sir Robin.
What do you do with ill crystallographers? Take them to the mono-clinic!

muzik
Posts: 3785
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Unproven conjectures

Post by muzik » March 20th, 2019, 6:46 am

Can there exist a rule where the speeds of spaceships cannot be a certain value, but are able to approach it infinitely closely?

Life's top (orthogonal) spaceship speed is c/2: I'm thinking of a rule where c/2 spaceships cannot be achieved, but speeds approaching c/2 such as 2c/5, 3c/7, 4c/9, 5c/11, ... nc/2n+1 all can.


Also, how far have we enumerated each possible different n-cell rotor in Life?
Bored of using the Moore neighbourhood for everything? Introducing the Range-2 von Neumann isotropic non-totalistic rulespace!

Hunting
Posts: 3000
Joined: September 11th, 2017, 2:54 am

Re: Unproven conjectures

Post by Hunting » March 21st, 2019, 12:08 am

Sarp wrote:
testitemqlstudop wrote: What are the least transitions required for Turing-completeness in isotropic non-totalistic 2-dimensional CA?
However I'm not sure if any 1 transition TC rules exist
It's not possible. Because rules with 1 transition cannot have spaceship.
MLP will live on forever, so does John Horton Conway.
Moosey wrote:
February 5th, 2019, 7:51 pm
“New knightship tagalong!”
“Quick, hide it!”
My TODO list

LeapLife - DirtyLife - LispLife

I could make a rule in ten seconds flat

Sarp
Posts: 214
Joined: March 1st, 2015, 1:28 pm

Re: Unproven conjectures

Post by Sarp » March 21st, 2019, 5:01 am

Hunting wrote:
Sarp wrote:
testitemqlstudop wrote: What are the least transitions required for Turing-completeness in isotropic non-totalistic 2-dimensional CA?
However I'm not sure if any 1 transition TC rules exist
It's not possible. Because rules with 1 transition cannot have spaceship.
You can have infinite but finitely describable universes which would also prove TC'ness without using spaceships. You can use b3i to simulate W22 and b3e for W68 but neither are TC. With finite starting patterns all rules except b2a are easily provable to be non-TC. Also banks and Wireworld are TC rules without spaceships.
WADUFI

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

Re: Unproven conjectures

Post by toroidalet » March 23rd, 2019, 3:01 pm

With infinite patterns B2a/S is probably TC; here is a p32 signal injector, (p32) signal track, and (p32) signal turner:

Code: Select all

x = 130, y = 197, rule = B2a/S
11$71bo$52bo3bo14bo$56bo12b2o$28bo3bo3bo3bo3bo3bo8b2o21bo$32bo7bo7bo
25b2o4bo$33b2o6b2o6b2o22bo4b2o$52b2o19bo$54bo28b2o$28b2o6b2o6b2o8bo3bo
23bo$30bo7bo7bo35bo$30bo3bo3bo3bo3bo3bo2$62bo$62bo$60b2o$41b2o$65b2o$
64bo$64bo5$33b2o6b2o6$57b2o2$33b2o6b2o25b2o2$65b2o4$57b2o6b2o2$41b2o6b
2o3$77b2o3$57b2o2$49b2o17b2o5$11bo110bo$11bo45b2o63bo$9b2o112b2o$77bo
15bo$14b2o61bo15bo24b2o$13bo106bo$13bo40bo3bo61bo$54bo24bo$30bo3bo3bo
3bo3bo3bob2o25bo$30bo7bo7bo33b2o$28b2o6b2o6b2o$57b2o16b2o$56bo11b2o7bo
$33b2o6b2o6b2obo3bo20bo$32bo7bo7bo$28bo3bo3bo3bo3bo3bo9bo4bo$63bo52bo
4bo$64b2o50bo$114b2o$58b2o$60bo59b2o$60bo4bo7bo15bo29bo$73bo15bo24bo4b
o2$57bo4bo53bo4bo$62bo53bo$63b2o49b2o2$57b2o61b2o$59bo37bo21bo$59bo4bo
32bo16bo4bo2$57bo4bo53bo4bo$62bo53bo$63b2o49b2o2$57b2o61b2o$59bo29bo
15bo13bo$59bo4bo24bo15bo8bo4bo2$57bo4bo53bo4bo$62bo53bo$63b2o49b2o2$
57b2o9b2o50b2o$59bo21bo37bo$59bo4bo16bo32bo4bo2$57bo4bo53bo4bo$62bo53b
o$63b2o49b2o2$57b2o61b2o$59bo13bo15bo29bo$59bo4bo8bo15bo24bo4bo2$57bo
4bo53bo4bo$62bo53bo$63b2o49b2o2$57b2o61b2o$59bo37bo21bo$59bo4bo32bo16b
o4bo2$57bo4bo53bo4bo$62bo53bo$63b2o49b2o2$57b2o61b2o$59bo29bo15bo13bo$
59bo4bo24bo15bo8bo4bo2$57bo4bo53bo4bo$62bo53bo$63b2o49b2o2$57b2o9b2o
50b2o$59bo21bo37bo$59bo4bo16bo32bo4bo2$57bo4bo53bo4bo$62bo53bo$63b2o
49b2o2$57b2o61b2o$59bo13bo15bo29bo$59bo4bo8bo15bo24bo4bo22$68b2o17$68b
o$68bo$66b2o2$71b2o$70bo$70bo!
"Build a man a fire and he'll be warm for a day. Set a man on fire and he'll be warm for the rest of his life."

-Terry Pratchett

User avatar
Hdjensofjfnen
Posts: 1516
Joined: March 15th, 2016, 6:41 pm
Location: r cis θ

Re: Unproven conjectures

Post by Hdjensofjfnen » September 26th, 2019, 10:17 pm

If a pattern is a Garden of Eden, its inverse cannot be a Garden of Eden.
"A man said to the universe:
'Sir, I exist!'
'However,' replied the universe,
'The fact has not created in me
A sense of obligation.'" -Stephen Crane

Code: Select all

x = 7, y = 5, rule = B3/S2-i3-y4i
4b3o$6bo$o3b3o$2o$bo!

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

Re: Unproven conjectures

Post by dvgrn » September 26th, 2019, 11:08 pm

Hdjensofjfnen wrote:If a pattern is a Garden of Eden, its inverse cannot be a Garden of Eden.
This came up yesterday on Discord, and as Kazyan mentioned it's very easy to disprove this conjecture.

E.g., the following is a GoE whose inverse is trivially also a GoE:

Code: Select all

x = 12, y = 16, rule = B3/S23
o2b2obo2b3o$b2o2b2obobo$obobo2bobobo$b4o2b2o2bo$o3b3ob4o$2obobo2bob2o$
obo2b3obobo$b4obob4o$o4bobo$bob2o3bobo$2bobob2obo$b3o3bo$o4b2o2b2o$bob
ob2obobo$o2b2o2bobobo$b2o2bob2o!

User avatar
Hdjensofjfnen
Posts: 1516
Joined: March 15th, 2016, 6:41 pm
Location: r cis θ

Re: Unproven conjectures

Post by Hdjensofjfnen » September 26th, 2019, 11:20 pm

dvgrn wrote:
Hdjensofjfnen wrote:If a pattern is a Garden of Eden, its inverse cannot be a Garden of Eden.
This came up yesterday on Discord, and as Kazyan mentioned it's very easy to disprove this conjecture.

E.g., the following is a GoE whose inverse is trivially also a GoE:

Code: Select all

x = 12, y = 16, rule = B3/S23
o2b2obo2b3o$b2o2b2obobo$obobo2bobobo$b4o2b2o2bo$o3b3ob4o$2obobo2bob2o$
obo2b3obobo$b4obob4o$o4bobo$bob2o3bobo$2bobob2obo$b3o3bo$o4b2o2b2o$bob
ob2obobo$o2b2o2bobobo$b2o2bob2o!
Doh! I forget the questions I've asked and haven't asked.
EDIT: Anyway, another conjecture:
Call the set of Gardens of Eden S0. Then call the set of the grandfatherless patterns S1. Then call the set of the great-grandfatherless patterns S2, and so on.
Conjecture a) The number of elements in Sn for arbitrarily large n is smaller than the number of elements in S0. (In essence, there is not necessarily a bijection between the elements of Sn and the elements of Sn-1.)
Conjecture b) There is a nonzero and therefore infinite number of elements in each of S0, S1, S2, ... ad infinitum.
"A man said to the universe:
'Sir, I exist!'
'However,' replied the universe,
'The fact has not created in me
A sense of obligation.'" -Stephen Crane

Code: Select all

x = 7, y = 5, rule = B3/S2-i3-y4i
4b3o$6bo$o3b3o$2o$bo!

User avatar
testitemqlstudop
Posts: 1362
Joined: July 21st, 2016, 11:45 am
Location: in catagolue
Contact:

Re: Unproven conjectures

Post by testitemqlstudop » September 26th, 2019, 11:46 pm

The set of gardens of eden is infinite, so this is equivalent to asking whether or not there is a bijection between S0 and Z/R.

User avatar
Hdjensofjfnen
Posts: 1516
Joined: March 15th, 2016, 6:41 pm
Location: r cis θ

Re: Unproven conjectures

Post by Hdjensofjfnen » September 27th, 2019, 12:09 am

A question:
Call a soup complete if its every cell within its bounding box is contained within its resulting envelope when run. What is the density d so that a random soup with that density has a 50% chance of being complete?
"A man said to the universe:
'Sir, I exist!'
'However,' replied the universe,
'The fact has not created in me
A sense of obligation.'" -Stephen Crane

Code: Select all

x = 7, y = 5, rule = B3/S2-i3-y4i
4b3o$6bo$o3b3o$2o$bo!

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

Re: Unproven conjectures

Post by dvgrn » September 27th, 2019, 8:01 am

Hdjensofjfnen wrote:A question:
Call a soup complete if its every cell within its bounding box is contained within its resulting envelope when run. What is the density d so that a random soup with that density has a 50% chance of being complete?
This seems more like a Basic Question than an Unproven Conjecture. There's no well-defined answer as you've stated the question, because the required density will depend on the size and shape of the soup's bounding box. But above 2x2 d will be fairly low, since any soup with three consecutive ON cells along an edge of its bounding box will automatically be not-complete.

User avatar
Hdjensofjfnen
Posts: 1516
Joined: March 15th, 2016, 6:41 pm
Location: r cis θ

Re: Unproven conjectures

Post by Hdjensofjfnen » September 30th, 2019, 11:22 pm

dvgrn wrote:...any soup with three consecutive ON cells along an edge of its bounding box will automatically be not-complete.
Can you clarify what you mean? I'm not sure I understand your meaning exactly. Do you mean OFF cells?
"A man said to the universe:
'Sir, I exist!'
'However,' replied the universe,
'The fact has not created in me
A sense of obligation.'" -Stephen Crane

Code: Select all

x = 7, y = 5, rule = B3/S2-i3-y4i
4b3o$6bo$o3b3o$2o$bo!

wildmyron
Posts: 1397
Joined: August 9th, 2013, 12:45 am

Re: Unproven conjectures

Post by wildmyron » October 1st, 2019, 1:12 am

I believe there's some confusion here as dvgrn seems to have understood complete as meaning "all cells and only those cells within the bounding box of the soup have been On for at least one generation". With this definition any soup with three adjacent On cells on the boundary of the soup will be not-complete because of the birth outside the bbox on gen 1. With the less restrictive definition (as I believe was intended) this situation does not make the soup not-complete.
The latest version of the 5S Project contains over 226,000 spaceships. There is also a GitHub mirror of the collection. Tabulated pages up to period 160 (out of date) are available on the LifeWiki.

User avatar
Extrementhusiast
Posts: 1832
Joined: June 16th, 2009, 11:24 pm
Location: USA

Re: Unproven conjectures

Post by Extrementhusiast » December 28th, 2019, 3:01 pm

pcallahan wrote:
January 4th, 2018, 3:22 pm
A significant question is still life finitization (I think it has been called that). I do not know if it is currently open. I have had some ideas and never made progress. It is hard but seems tractable (unless it's actually easy and I'm missing something).

The question is: given a still life without finite boundaries (e.g. covering the plane; it need not be periodic or have any other properties), can any MxN finite window of it be preserved within a finite still life by adding appropriate unchanging cells around it (no particular bounds on this, though the question could place size limits in terms of M and N).

A natural conjecture based on experience and the prevalence of still lifes is that there is some fairly small constant k such that any MxN window that exists within an infinite still life can be stabilized within an (M+k)x(N+k) still life.

For instance, take a still life consisting of alternating stripes. That is only stable when infinite, but it is not hard to select a rectangle inside it and add a boundary to stabilize it. This appears to be true for less regular still lifes as well.

The first idea I had was backtracking from a row of empty cells to a populated row. The first row facing empty space must not have more than two live cells adjacent, but it is unclear what conditions are on its successor. My guess is that after several iterations, the conditions are identical to a row within an infinite still life, but I don't see how to prove it (I thought about treating these rows as regular languages, which they are, but that hasn't helped).

The second idea, which seems more tractable, is to pick a specific window size (say 10x10). For any still life of this size including with unstable boundaries, if we remove all cells in a centered subwindow (say 6x6) can we restabilize the bordering cells leaving an empty subwindow (I think 2x2 is big enough). If so, we have an algorithm for "punching holes" in any infinite still life and should be able to separate finite windows from the infinite stabilizer given a succession of hole punches.

I believe the second approach is suitable to an automated proof, but it might not result in a very readable explanation of how it works.

Or, again has someone already figured this out (Noam Elkies?) using more elegant mathematics and am I just way behind the state of the art.
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.
I Like My Heisenburps! (and others)

pcallahan
Posts: 508
Joined: April 26th, 2013, 1:04 pm

Re: Unproven conjectures

Post by pcallahan » December 28th, 2019, 3:24 pm

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.
Thanks! Yes, anyway it looks like a counterexample to the strongest form of the conjecture:
there is some fairly small constant k such that any MxN window that exists within an infinite still life can be stabilized within an (M+k)x(N+k) still life.
That rules out some of the approaches I've taken trying to find finite stabilizations. Has anyone else looked into this recently?

I believe that Dean Hickerson once made the strong form of the conjecture for a specific k like 5 or 6.

I haven't independently verified it, but the top two rows extended infinitely should, I think impose a periodic tiling on the plane. I don't think I've seen that with any other still life pattern. E.g., it's true that an infinite row of all live cells can be stabilized by repeating it alternating over the plane, but you don't need that. Are there finite patterns that impose a periodic stabilization? I would not have thought so but now I don't know.

pcallahan
Posts: 508
Joined: April 26th, 2013, 1:04 pm

Re: Unproven conjectures

Post by pcallahan » December 29th, 2019, 1:07 am

Extrementhusiast wrote:
December 28th, 2019, 3:01 pm
I may have found a counterexample:
I think it's not hard to analyze. The initial pattern is a 2x9 rectangle that repeats periodically across the plane. Label the columns of one of these rectangles with letters a through i. The goal is to place a third row of cells to stabilize row 2. The cell in column e has 3 neighbors, so it must not have any more neighbors. This forces the cells to be empty in row 3 for columns d, e, and f.

Code: Select all

                              a b c d e f g h i
o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . .
. o o . . . o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . . o o .
                                    . . .
But that would lead to a birth in column d row 2 unless a cell is there in column c row 3 to suppress it.

Code: Select all

                              a b c d e f g h i
o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . .
. o o . . . o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . . o o .
                                  o . . .
Next a cell is needed in column b row 3 to suppress a birth in column c row 2 caused by the live cell added above. The cell in column a row 3 must be empty to avoid overcrowding the live cell above it.

Code: Select all

                              a b c d e f g h i
o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . .
. o o . . . o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . . o o .
                              . o o . . .
Considering cells to the right, it seems at first that we have a choice. We could leave column g empty in row 3. But if we do that, we must also leave column h empty to avoid a birth in column g row 2. That leaves i to assign. Note that the cell to its right must be empty like column a, since it is forced by the pattern to its right.

If column i row 3 is live, we get a birth in column h.

Code: Select all

                              a b c d e f g h i a
o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . .
. o o . . . o o . . o o . . . o o . . o o . * . o o . . o o . . . o o . . o o .
                              . o o . . . . . o .
If it is empty, we get a birth in column i.

Code: Select all

                              a b c d e f g h i a
o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . .
. o o . . . o o . . o o . . . o o . . o o . . * o o . . o o . . . o o . . o o .
                              . o o . . . . . . .
So it follows from the above that we cannot leave column g empty. Once we set it, the rest is forced by a similar analysis.

Finally, this stabilization works and it is unique:

Code: Select all

                              a b c d e f g h i
o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . .
. o o . . . o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . . o o .
                              . o o . . . o o .
Because these 9 cells are forced uniquely, the entire periodic row must be forced.

Are there any other still life stabilizations that force periodicity in this way? I guess a trivial case is this 2x2 block:

Code: Select all

o .
o .
If you make it wider, though, you can find finite stabilizations.

The general question is about still lifes in an n-column universe that is wrapped horizontally but not vertically. If 2 consecutive rows of cells are assigned, is it possible to find some finite m such that the rows and their stabilization fit in an mXn box. The above is a counterexample for n=9. It should be possible to enumerate patterns like this for somewhat larger values of n (maybe up to 20 or a little higher).

Each such pattern should imply that the stabilization must exceed a fixed number of rows when the rectangle is repeated an increasing number of times in a row of an unbounded universe.

How to enumerate?
One way that I think should work for a given n is to construct 3Xn rectangles such that the center row is consistent with still-life constraints with neighbors wrapped horizontally. Next form a directed graph of nodes that are 2Xn rectangles connected by a directed edge if they overlap into one of the above 3xN rectangles.

For finite stabilizations, we should find that there is a path to the 2Xn rectangle consisting of all empty cells (0s). Ones without such a stabilization should be in strongly connected components that do not include the empty rectangle. Note that for n=9, this is a very reasonable-sized problem to solve on a graph of 2^18 nodes. It should be feasible even for significantly larger values of n (I would guess up to at least 20 or so).
Last edited by pcallahan on December 29th, 2019, 3:32 pm, edited 2 times in total.

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

Re: Unproven conjectures

Post by dvgrn » December 29th, 2019, 2:10 pm

pcallahan wrote:
December 29th, 2019, 1:07 am
Finally, this stabilization works and it is unique:

Code: Select all

                              a b c d e f g h i
o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . .
. o o . . . o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . . o o .
                              . o o . . . o o .
Because these 9 cells are forced uniquely, the entire periodic row must be forced.
Segue to another unproven conjecture: if there's a forced stabilization for a patch of this agar, does that mean that a still life like this

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!
might not have a glider synthesis recipe? There would be no incremental way to build it one S-tetromino at a time -- it would have to be built up a full row at a time, at best, and if the rows are long enough there might not be room for enough gliders to get in and make the necessary adjustments. Is there a likely angle of attack for one of these things?

I'm not saying this would be a candidate for the Unique Father Problem. At least for small diamonds, there seems to be no shortage of predecessors:

Code: Select all

x = 13, y = 12, rule = B3/S23
2o5b2o$o2bobo2bo$2b2o4bobo$5bob3o2bo$2b3obo2b2obo$bobo2b2obo$5bo2b2obo
$b4o3bo2bo$2bob2o$bobo2b2o2bo$3b2o4b4o$2bobob2o3bo!
Not sure about larger patches -- so far with JLS I'm getting swatches of the agar, but no complete solutions:

Code: Select all

x = 17, y = 18, rule = B3/S23
4bo2bo$3bobob5o2bo$b2o6b4o$2bob2o6bo$bob2o2b2o2bobo$5bob2o2bo3b2o$o2b
2o3bobo5bo$6b2o5bo$3o6b3obo2bo$bo2b2o5bo3bo$o2b2o2bobob3o2bo$o2bo2b2o
2bo$3b2o2b3o3b2obo$2b2o2bo5bo2b2o$b3o7b2obo$2bo2b2o2bobobo$3bob4ob2o$
4bo5bo!

pcallahan
Posts: 508
Joined: April 26th, 2013, 1:04 pm

Re: Unproven conjectures

Post by pcallahan » December 29th, 2019, 3:28 pm

dvgrn wrote:
December 29th, 2019, 2:10 pm
There would be no incremental way to build it one S-tetromino at a time -- it would have to be built up a full row at a time, at best, and if the rows are long enough there might not be room for enough gliders to get in and make the necessary adjustments. Is there a likely angle of attack for one of these things?
I don't know the answer, but it seems hard to rule out volatile patterns that "magically" stabilize into the required context, or even some period-2 context that could hold it indefinitely for the next glider. I lack the experience with still-life synthesis to guess at the likelihood, but it just seems hard to prove a negative result.

I wonder even in the still life counterexample if there is a narrower stabilization that has constant width but is not a still life. Maybe the conflicting births could be turned into blinking cells (I have not looked at it enough to see if that idea even makes sense).

Aside: another interesting thing about this still life (the periodic part) is that every 3x3 window has exactly 4 live cells, either a live cell with 3 neighbors or 4 cells overcrowding a birth. That's highly constrained, though obviously not unique because it can be shifted.

pcallahan
Posts: 508
Joined: April 26th, 2013, 1:04 pm

Re: Unproven conjectures

Post by pcallahan » January 8th, 2020, 2:22 pm

pcallahan wrote:
December 29th, 2019, 1:07 am
Finally, this stabilization works and it is unique:

Code: Select all

                              a b c d e f g h i
o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . .
. o o . . . o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . . o o .
                              . o o . . . o o .
I made the analysis a lot harder than necessary.

Just start with the two forced empty cells as shown, and head left, filling in the ?s.

Code: Select all

o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . .
. o o . . . o o . . o o . . . o o . . o o . . . o o . . o o . . . o o . . o o .
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? . .
Each ? is either forced to be o to suppress a birth, or . to avoid overcrowding a live cell.
Last edited by pcallahan on January 20th, 2020, 5:09 pm, edited 2 times in total.

User avatar
Entity Valkyrie 2
Posts: 538
Joined: February 26th, 2019, 7:13 pm
Location: Hijuatl, Zumaland
Contact:

Re: Unproven conjectures

Post by Entity Valkyrie 2 » January 10th, 2020, 4:10 am

Conjecture: is there a Thessalonic glider reflector?
Conjecture: is there a Thessalonic g-to-h?
Conjecture: is there a Thessalonic glider duplicator?

There is almost a Thessalonic glider reflector:

Code: Select all

x = 24, y = 23, rule = B3/S23
5bo$6b2o$5b2o4$22b2o$22bo$20bobo$20b2o$2b2o$bobo$bo$2o$14b2o$14b2o6b2o
$22b2o3$11b2o$12bo$9b3o$9bo!
The ENEERG-y of the EVAD is watching.
The 70th NAI-ve guy is watching.

Please click here for my own pages.

Also, please apgsearch B34t5y7/S23 (B-life)

User avatar
Rhombic
Posts: 1064
Joined: June 1st, 2013, 5:41 pm

Re: Unproven conjectures

Post by Rhombic » January 10th, 2020, 6:56 pm

A philosophical question...

If a still life only has itself as a predecessor, clearly it is its only father, its only grandfather, its only great-grandfather and so on. Does that mean that it would be a Garden of Eden, by induction?
SoL : FreeElectronics : DeadlyEnemies : 6a-ite : Rule X3VI
what is “sesame oil”?

Post Reply