Unproven conjectures

[hotdogPi]

are there any patterns whose predecessor(s) has/have to have an infinite amount of cells (each)?

one way to approach this is to find a pattern whose predecessor(s) converge(s) into an agar that will always leave at least one cell (that isn't supposed to be there) at the edge of it/them.

https://conwaylife.com/wiki/American_Dream

[get_snackeTWO]

https://conwaylife.com/wiki/American_Dream

had read about that, but didn't know it was supposed to be the solution to the conjecture.

[pipsqueek]

what about a pattern with exactly 1 predecessor? how about 2 or 3?

[dvgrn]

what about a pattern with exactly 1 predecessor? how about 2 or 3?

Start with Unique father problem.

The difficulty here is that as soon as a finite pattern in an unbounded universe has one predecessor, it trivially has an unbounded number -- just sprinkle isolated dots and dominos to taste, anywhere in the empty spaces.

So when you talk about a pattern with two or three predecessors, you're either talking about an infinitely large pattern -- an agar like the Unique Father still life agar, for example -- or there's some additional constraint you haven't mentioned.

I wouldn't be surprised if there's some slight adjustment of a cell or two of the Unique Father still life agar, that would cause the entire universe to have exactly two or three or N predecessors. Haven't thought about it much, because it generally seems more fun to work with bounded patterns with non-infinite population.

[pipsqueek]

what about a pattern with exactly 1 predecessor? how about 2 or 3?

Start with Unique father problem.
The difficulty here is that as soon as a finite pattern in an unbounded universe has one predecessor, it trivially has an unbounded number -- just sprinkle isolated dots and dominos to taste, anywhere in the empty spaces.

lets say that the pattern may have many predecessors, but all of them must contain the 1 true predecessor. the solution to the unique father problem works, but lets say its not a still life or oscillator. in other words, is there an unsynthesizable active region?

[squareroot12621]

…in other words, is there an unsynthesizable active region?

Yeah, just hit the unsynthesizable still life with a glider.

Code: Select all

x = 43, y = 35, rule = B3/S23
41bo$40bo$40b3o7$2b2obo2b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bo
b2o2bob2o$2o4b2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2bob2o2bob2o2bo$o2b
2obo2b2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2ob
o2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o2bob2o$2o4b2o4b2o4b2o4b2o4b2o$b
ob2o2bob2o2bob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2obo2b2obo$2o4b2o
4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bo
b2o2bob2o$2o4b2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2bob2o2bob2o2bo$o2b
2obo2b2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2ob
o2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o2bob2o$2o4b2o4b2o4b2o4b2o4b2o$b
ob2o2bob2o2bob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2obo2b2obo$2o4b2o
4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bo
b2o2bob2o!

If this were synthesizable, the original still life would be (just hit the incoming glider with another glider). This is clearly impossible, so the still life plus the glider is unsynthesizable.

[dingxutong]

The OEIS sequence https://oeis.org/A061342 is the period of the stationary component of the pattern which a row of n cells becomes in Conway's Game of Life.

Are the following conjectures right?

• The periods are always 1, 2, 3, 6, 15 (I forgot this one at first) or 30;
• There are finite odd terms.

Are they correct? Are there any other interesting properties in the sequence?

[pipsqueek]

I think you made a mistake, a line of 10 cells produces a p15 pentadecathlon.

Code: Select all

x = 10, y = 1, rule = B3/S23
10o!

[dingxutong]

I think you made a mistake, a line of 10 cells produces a p15 pentadecathlon.

Code: Select all

x = 10, y = 1, rule = B3/S23
10o!

Thanks! I've edited it.

[pipsqueek]

conjecture: every pattern has at least one parent which is a GoE

[dvgrn]

conjecture: every pattern has at least one parent which is a GoE

That's an interesting one -- assuming that you add the caveat "every pattern that has any parents at all". Otherwise it's definitely just not true.

"Every pattern" includes the empty pattern, so it will have to be possible to find a GOE pattern where every cell has either more than three neighbors or less than two, such that it will die out completely in one tick.

Once you have that, just add it at a safe distance to any parent of any pattern, and you've got a proof of the modified conjecture.

I don't think there are any known GOEs that die completely in one tick, but I suspect that's just because nobody has searched for them (or possibly just because I don't know about them). Let's see, quite possibly an instant-death GOE can be fabricated from one of the highest-density known GOEs...

... yup, here's one, I think, based on Roger Banks' original GoE:

Code: Select all

x = 38, y = 14, rule = B3/S23
3bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo$3bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo
$2b33o$4obob3ob3ob2obobobobobobobobob2o$2bobob3ob3ob4ob3obobobobobobob
3o$2b5ob3ob3ob4ob15o$3obob2ob3ob3obob3obobobobobobobo$2b4ob3ob3ob5ob2o
bobobobobob3o$3b2ob3ob3ob3obobob14obo$2b2ob2ob3ob3ob2ob4obobobobobobo$
20ob16o$2bo2bo2bo2bo2bo2b7o2bo2bo2bobo$2bo2bo2bo2bo2bo4bobo4bo2bo2bobo
$19bobo!

Achim Flammenkamp's 14x14 GoE from 1991 also has no cells that survive except at the boundary, so it's easy to put it in a box and make it an instantly vanishing GoE:

Code: Select all

x = 20, y = 19, rule = B3/S23
2bo2bo2bo2bo2bo2bo$2bo2bo2bo2bo2bo2bo$20o$2b3obobobob2obobo$2b2ob3ob3o
b2ob2o$7ob3ob2obob3o$2b4obobobob5o$2bob3obob3ob2obo$10ob4ob4o$2bobobob
8obo$2b2ob3ob2obobob2o$9ob6ob3o$2b2ob2ob5obob2o$2b4ob9obo$3ob3obobobob
6o$2b4obobobob2ob2o$4ob15o$2bo3bo2bo2bo2bobo$2bo3bo2bo2bo2bobo!

Add either one of these patches to any parent of a pattern, and you have the one required GOE parent to prove the conjecture.

The big question is: what's the smallest instantly vanishing GoE? It sure isn't going to be either of the above!

[pipsqueek]

more conjectures

• there is no GoE such that removing any singular cell gives another GoE
• there is a GoE made entirely of 2x2 blocks
• there is a GoE made entirely of 1x2 blocks
• there is no GoE made entirely of 3x3 blocks
• there is no GoE in which all cells die of underpopulation in the next generation

[dvgrn]

more conjectures

• there is no GoE such that removing any singular cell gives another GoE
• there is a GoE made entirely of 2x2 blocks
• there is a GoE made entirely of 1x2 blocks
• there is no GoE made entirely of 3x3 blocks
• there is no GoE in which all cells die of underpopulation in the next generation

I think item 1 can easily be proven false. Pick any two GOEs and put them anywhere in the same universe, not overlapping. Remove any singular cell from this combined pattern and you still have a GOE.

I would suspect that item 5 is true, but I'm not sure if it can easily be proven simply by some kind of exhaustive enumeration of cases.

[Ilkka Törmä]

conjecture: every pattern has at least one parent which is a GoE

That's an interesting one -- assuming that you add the caveat "every pattern that has any parents at all". Otherwise it's definitely just not true.

"Every pattern" includes the empty pattern, so it will have to be possible to find a GOE pattern where every cell has either more than three neighbors or less than two, such that it will die out completely in one tick.

Once you have that, just add it at a safe distance to any parent of any pattern, and you've got a proof of the modified conjecture.

You're tacitly assuming that the pattern has a parent with enough empty space to put the GOE pattern. In principle, there might be a finite pattern P that has a parent, but every parent is forced to be filled with some instantly dying periodic motif apart from the finite patch that evolves into P. Like the American Dream, but forcing the entire plane instead of just the infinite strip. With an even greater stroke of luck it might happen that none of the (finitely many) parents is a GOE...

[wirehead]

I have a conjecture. It might be easily disproven...

Any Hashlife-friendly pattern (i.e. one with a power of two period), after being run long enough and with a sufficient amount of memory, will eventually benefit so much from Hashlife's speedup that it's running as fast or faster than directly simulating the underlying algorithm the pattern implements. For example, if you made a p65536 Turing machine in CGoL, after you run it enough under HashLife you're really just running the Turing machine itself, and not a CGoL pattern that emulates a Turing machine.

[AlbertArmStain]

Does there exist a pattern which, when all cells in its bounding box are inverted, will become itself in any n generations? (excluding junk produced from the object)

[Macbi]

Does there exist a pattern which, when all cells in its bounding box are inverted, will become itself in any n generations? (excluding junk produced from the object)

Code: Select all

x = 4, y = 4, rule = B3/S23
b2o$4o$4o$b2o!

[dvgrn]

Code: Select all

x = 4, y = 4, rule = B3/S23
b2o$4o$4o$b2o!

Technically the inverse of that pattern is the answer to the question, right?

Code: Select all

x = 4, y = 4, rule = B3/S23
o2bo3$o2bo!

There are at least four degenerate solutions in a smaller bounding box -- b! and 2b! and 14b! and 15b! I don't think there are any 2xN or 3xN "die-easy" patterns smaller than 16 cells, but none of these seem too interesting anyway so I haven't bothered to double-check.

Seems like a lot more solutions would show up if that vague extra clause "excluding junk produced from the object" could be invoked. Seems like a clearer definition would be needed there, like maybe adding "... outside the bounding box"? But it's not clear that the new solutions would be more interesting than the current set.

[hotdogPi]

This one doesn't die out.

Code: Select all

x = 4, y = 4, rule = B3/S23
o2bo$b2o$b2o$o2bo!

Extending this to 5×4 (i.e. phi spark), 6×4, 6×5, and as much as you want in either or both dimensions are also one-generation solutions.

Code: Select all

x = 6, y = 7, rule = B3/S23
o4bo$b4o$b4o$b4o$b4o$b4o$o4bo!

[confocaloid]

Does there exist a pattern which, when all cells in its bounding box are inverted, will become itself in any n generations? (excluding junk produced from the object)

If "all cells in its bounding box are inverted" is relaxed to not require the smallest possible bounding box, then there are solutions like this (n = 17 ticks):

Code: Select all

x = 10, y = 10, rule = B3/S23
10o$10o$10o$4o2b4o$3ob2ob3o$3ob2ob3o$4o2b4o$10o$10o$10o!

In theory, even something like a pair of parallel blinkers might happen to be a solution for some arrangement (at least, I do not see any obvious reason why that would be impossible). Some non-solutions to illustrate the idea:

Code: Select all

x = 23, y = 8, rule = B3/S23
22o$22o$22o$23o$23o$b22o$b22o$b22o!

Code: Select all

x = 24, y = 41, rule = B3/S23
21o$24o$24o$24o$24o$24o$24o$24o$24o$24o$24o$24o$24o$24o$24o$24o$24o$
24o$24o$24o$24o$24o$24o$24o$24o$24o$24o$24o$24o$24o$24o$24o$24o$24o$
24o$24o$24o$24o$24o$24o$3b21o!

Code: Select all

x = 21, y = 41, rule = B3/S23
18o$21o$21o$21o$21o$21o$21o$21o$21o$21o$21o$21o$21o$21o$21o$21o$21o$
21o$21o$21o$21o$21o$21o$21o$21o$21o$21o$21o$21o$21o$21o$21o$21o$21o$
21o$21o$21o$21o$21o$21o$3b18o!

[Entity Valkyrie 2]

…in other words, is there an unsynthesizable active region?

Yeah, just hit the unsynthesizable still life with a glider.

Code: Select all

x = 43, y = 35, rule = B3/S23
41bo$40bo$40b3o7$2b2obo2b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bo
b2o2bob2o$2o4b2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2bob2o2bob2o2bo$o2b
2obo2b2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2ob
o2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o2bob2o$2o4b2o4b2o4b2o4b2o4b2o$b
ob2o2bob2o2bob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2obo2b2obo$2o4b2o
4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bo
b2o2bob2o$2o4b2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2bob2o2bob2o2bo$o2b
2obo2b2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2ob
o2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o2bob2o$2o4b2o4b2o4b2o4b2o4b2o$b
ob2o2bob2o2bob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2obo2b2obo$2o4b2o
4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bo
b2o2bob2o!

If this were synthesizable, the original still life would be (just hit the incoming glider with another glider). This is clearly impossible, so the still life plus the glider is unsynthesizable.

This proof sounds incomplete to me; how do we know that there isn't an alternative way to synthesize the same active region?

[dvgrn]

This proof sounds incomplete to me; how do we know that there isn't an alternative way to synthesize the same active region?

The glider-plus-unsynthesizable-still-life is an active region, and is provably unsynthesizable because the stable part is unsynthesizable.

If you don't like that particular choice of active region, feel free to build a different one that doesn't contain a glider -- it should be equally unsynthesizable if you just add a dot in the corner. But it's not the descendants of these active regions that are unsynthesizable, it's the T=0 active region itself:

Code: Select all

x = 32, y = 26, rule = B3/S23
2b2obo2b2obo2b2obo2b2obo2b2obobo$2bob2o2bob2o2bob2o2bob2o2bob2o$2o4b2o
4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo
2b2obo2b2obo$2o4b2o4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo2b2obo$2b
ob2o2bob2o2bob2o2bob2o2bob2o$2o4b2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o
2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o4b2o
$2b2obo2b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o2bob2o$2o4b2o
4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo
2b2obo2b2obo$2o4b2o4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo2b2obo$2b
ob2o2bob2o2bob2o2bob2o2bob2o$2o4b2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o
2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o4b2o
$2b2obo2b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o2bob2o!

[AlbertArmStain]

Does there exist a Garden of Eden that, when inverted, still is a garden of Eden, which is not a Garden of Eden and an inverted Garden of Eden in the same bounding box.

[hotdogPi]

Does there exist a Garden of Eden that, when inverted, still is a garden of Eden, which is not a Garden of Eden and an inverted Garden of Eden in the same bounding box.

Yes. Most 50% 1000×1000 soups are Gardens of Eden, and this is still true when inverting it.

[wirehead]

I have a conjecture. It might be easily disproven...

Any Hashlife-friendly pattern (i.e. one with a power of two period), after being run long enough and with a sufficient amount of memory, will eventually benefit so much from Hashlife's speedup that it's running as fast or faster than directly simulating the underlying algorithm the pattern implements.

I've been thinking about this one of mine, and if the "or faster" part can be proven, it would have profound implications for not just the CA community, but also the computer science and cybersecurity community and the entire world. Suppose it is true (and I'm moderately sure it is): now that means that once you are able to construct an optimized pattern to run some algorithm (say, factoring 4096-bit RSA keys!!) the bottleneck is no longer raw processing power or speed and becomes access to large amounts of fast RAM. Quantum computers' advantage is that they can be in all possible states at once; I see similarities here to Haslife's cache - under the same rule, hashtiles are immutable, and they only need to be computed once and then can be reused a lot faster than recomputing them every time. Now imagine running Hashlife on a quantum computer -- that would be killer!!