Unproven conjectures

[PK22]

Probably true, but hard to prove: There exists a spaceship in Life with a phase in which all cells survive to the next generation.
Finding an elementary example would be very difficult, but an engineered example should be possible.

Between generations 6 and 7 of the below collision between a glider and long boat (which is an OTT), all cells survive. (There are likely other examples that could be used).

Code: Select all

x = 4, y = 9, rule = B3/S23
o$b2o$2o3$bo$obo$bobo$2b2o!

This means that if the rest of the spaceship is made up entirely of still lifes, there will be a phase where all cells survive. It is therefore possible for the spaceship to be made up of a long tape, a 1G seed that produces a tape reader (which also moves the tape, similar to the unidimensional spaceship project), which is triggered by the output glider from the glider + long boat collision, and some form of mechanism to stop the tape reader at the end, which should return a spaceship back towards the main mechanism. The instructions on the tape need to reproduce the 1G seed translated, rebuild the stopper at the end using xWSSes or gliders, and then trigger the 1G seed by hitting the long boat with a glider.

I think the easiest method is to set up a (shot)gun which is fired at a diagonal tape of blocks. It then moves the blocks and sends return gliders back to the reader in two different positions, depending on each block's position. From there, a bit of Herschel circuitry should be sufficient to create PULL and DFIRE operations, and with a receding Corderpuffer to produce blocks, that is sufficient for universal construction.

[WhiteHawk]

Probably true, but hard to prove: There exists a spaceship in Life with a phase in which all cells survive to the next generation.
Finding an elementary example would be very difficult, but an engineered example should be possible.

Note also that the "house" stage of the pi also has cells which stay on for multiple generations after, as does step 3

Code: Select all

x = 5, y = 3, rule = B3/S23
b3o$o3bo$2ob2o!

Edit: step 9 of the pi also stays alive

Code: Select all

x = 11, y = 8, rule = B3/S23
4b3o$3bo3bo$3bo3bo$b2ob3ob2o$obo5bobo$o9bo$2obo3bob2o$2b2o3b2o!

[muzik]

A phoenix is a pattern where every living cell dies in the next generation, i.e. lasts exactly one generation.
Do there exist oscillators where every living cell lasts exactly 2 generations? 3? 4? Any number?

Created a page to track a generalized version of this question: https://conwaylife.com/wiki/List_of_osc ... quencies#4

As of currently, there's only one unsolved period-3 case, which is this one. There are six unsolved period-4 cases, five of which are statorless, and the final of which corresponds to a period-4 oscillator with a stator and in which every cell that oscillates is only alive once in a cycle. Generating period maps via LifeViewer makes this investigation considerably easier.

How would we go about disproving any of these cases, if examples of them cannot be found?

[muzik]

Can we prove that it is impossible for a spaceship to be eaten, i.e. collision between it and any p1 constellation must necessarily result in some mess being left behind?

Given the cyclical nature of large engineered spaceships such that removing one element causes widespread circuit failure, as well as the weird space-dusty nature of larger elementary spaceships, it seems difficult to construct eaters for things, but I don't know if we can rule it out entirely for some theoretical given "inedible spaceship".

[b-engine]

Can we prove that it is impossible for a spaceship to be eaten, i.e. collision between it and any p1 constellation must necessarily result in some mess being left behind?

Given the cyclical nature of large engineered spaceships such that removing one element causes widespread circuit failure, as well as the weird space-dusty nature of larger elementary spaceships, it seems difficult to construct eaters for things, but I don't know if we can rule it out entirely for some theoretical given "inedible spaceship".

If there's a glider that escapes from the mess, we can use stable circuitries to turn that glider into salvos to destroy the residue and rebuild the bait.
If there's no glider, try another collision or simply add more still lifes until a glider comes out.
Very large spaceships, no matter elementary or not, is almost always guaranteed to have gliders in the ash of collision.
Therefore, there's no inedible spaceship in Life.

[LuveelVoom]

Almost always is by no means the same as always.

[Resu]

Can we prove that it is impossible for a spaceship to be eaten, i.e. collision between it and any p1 constellation must necessarily result in some mess being left behind?

Given the cyclical nature of large engineered spaceships such that removing one element causes widespread circuit failure, as well as the weird space-dusty nature of larger elementary spaceships, it seems difficult to construct eaters for things, but I don't know if we can rule it out entirely for some theoretical given "inedible spaceship".

If you use a rule like seeds, there are no p1 eaters.

[PK22]

I managed to prove that all strict still lives with <= 19 cells have a 1G or 2G destruction by using a script. #
Here's a zip file containing a destruction for all of them:

destructions.7z

(1.84 MiB) Downloaded 136 times

I will run a search on all natural still lifes to see if I can find a reasonably small SL that cannot be destroyed in 2 gliders.

EDIT 27/9/2025: Turns out every natural SL can be destroyed in <= 2G. It's impressive how far two gliders can go. I will instead feed in some large semi-natural SL to try and find an upper bound.

EDIT 2: xs80_y1j9m44m9jz35s2521y01252s53z65125ak8w8ka52156zy164311346 seems to be nearly indestructible with 2G, but I need independent confirmation on that. Assuming I am correct, then the smallest SL which cannot be destroyed with two gliders has N cells, where 19 < N < 81.

[muzik]

Presumably an easy one to prove: at least in a range-1 2-state rule, an isolated cell of a given period cannot be surrounded by eight cells of a lower period (such that all eight of them are the same).

These two oscillators, as shown in their period maps, have plenty of lower-period cells surrounded by higher-period cells, but no higher-period cells completely surrounded by lower-period cells:

Code: Select all

x = 258, y = 212, rule = B3aeikr4cekrtwy5ckq6cei7/S2cen3-jr4cei5eikq6-a7c8
60b3o$59bobobo$38bo19bob3obo$57bob5obo$38b3obo13bob7obo$41b3o11bob9ob
o$42b3o9bob11obo$43b3o7bob13obo$45b2o5bob15obo$44bob2o3bob17obo$46b3o
bob19obo$48bobo3b19o$50b2obob16obo$47bo3bo2bob14obo$51bo3bob12obo$52b
o3bob10obo$53b2o2bob8obo$55bo2bob6obo$52b3obo2bob4obo$53b2o2bo2bob2ob
o$56bobo3bobo$55b3ob2o2bo$36bo18bo2bob3o$35b3o21b2o$34b5o21b3o$33b7o21b
3o47bo$33b2o3b3o21b3o20b4o$40b2o21b3o21b3o23bo$35bo4b3o22b2o21b3o21b3o
$34bo6b3o21b3o19bo2b2o21b3o$41b4o18b6o21b3o19b5o$42b4o18b2ob3o19b5o19b
o2b2o$43bob2o19bob3o19b5o21b3o$43b2ob2o19bob3o22b2o22b2o$44b5o21b3o21b
3o21b3o$47b3o20b4o19bo2b2o20b4o$45b6o21b3o21b3o19bob3o$48b4o22b2o22b2o
21b3o$50b3o20bob2o19b5o22b2o$51b3o20bob2o20b4o21b3o$51b4o21b3o20b4o19b
o2b2o$49bobo2b2o17b2o2b3o20b4o21b3o$50b2obob2o17bo2bob2o22b2o21b3o$54b
ob2o21b3o21b3o21b3o$56b3o21b3o21b3o17bo2bob2o$57b3o21b3o20b4o14b2o3b5o
$36bo20b4o22b2o21b3o12bobo4b5o$35b3o21b3o21b3o21b3o11b2o6b5o$34b5o20b
4o16b2o3b3o21b3o22b2o$33b7o19bob3o15b2o2bob3o21b3o21b3o$32b9o18bob4o13b
o5bo2b2o20b4o18b6o$31b4ob6o19b5o12b2o7b3o21b3o18b2o2b2o$30b2o8b3o16bo
bo2b3o11b2o7b4o18bo2b3o18bo2b3o$29b3o7bob3o16bobo2b3o20b4o21b3o20b4o$
28b2o10b5o21b3o21b3o21b3o20bob2o$27b2obo10bo2b2o21b3o22b2o21b3o21b3o$
26b3o15b3o22b2o19b5o21b3o20b4o$25b4o16b3o20bob2o20b4o19b5o21b3o$24b4o
17bob2o21b3o20b4o17b7o22b2o$23b3o18b2ob3o19b5o20b4o17b7o20bob2o$22b3o
22b4o18bob4o20b4o17b3ob3o13b3o5b3o$23bo2bo21b4o18bob4o20b4o17b2o2b3o12b
4o4b4o$20bo30b2o19b5o20b4o20b4o12b2o6b4o$27bo23b3o17bo3b3o20b4o16bo3b
4o22b2o$21bo30b3o17bo3b3o22b2o20b4o21b3o69bo$53b3o21b3o21b3o21b3o18b2o
2b2o69bo$49bo2bob3o20b4o19b5o21b3o21b3o71bo$53b5o22b2o21b3o22b2o20b4o
69b3o$54bob3o19bob3o19bob3o21b3o18bob4o69b3o$57b3o18bo3b2o21b3o16bo3b
4o15bo5b3o69b3o$36bo18bo2b3o14bob4ob3o18bob4o20b4o20b4o67b5o$35b3o19b
5o20b4o19b5o18bob4o19b5o44bo2bo22b2o$34b5o20b4o17bo3b3o20b4o17b3o2b2o
21b3o44bo2bo21b3o$33b7o20b4o21b3o20b4o16bo4b3o17bo4b2o42bobob2o21b3o$
32b3o3b3o20b4o20b4o18bob4o22b2o20bob2o43b5o21b3o$31b4o4b3o17b7o19b5o19b
ob3o21b3o21b3o45b3o20b4o$18bo11b3o8b2o17bob5o19b5o21b3o19bo2b2o21b3o21b
obo22b2o21b3o$19bo9b4o6b5o16bobob4o20b4o21b3o21b3o20b4o19bo2b2o20bob2o
21b3o$16bo11b5o6bo2b3o17b7o20b4o22b2o21b3o19b5o18b2o2b2o21b3o22b2o$15b
4o8b2o15b2o20b4o18b6o20bob2o21b3o19b5o18bo2b3o21b3o21b3o$14b5o7b3o14b
ob2o16bo2b5o17b2o2b3o21b3o21b3o19b5o22b2o21b3o18b6o$13b4o8b3o16bob2o20b
4o16bo3b4o20b4o17b2o2b3o19b5o21b3o17bob5o18b2ob3o$12b3obo7b3o9bo7b5o18b
o2b3o20b4o20b4o19bo2b2o19b5o18b6o17bob5o21b3o$11b3o2bo6b3o9b3o8b4o19b
2ob2o20b4o21b3o21b3o20b4o18b6o17bo3b3o20b4o$10b6o6b4o8b5o8b4o18b6o22b
2o22b2o21b3o19b5o18b2ob3o17b2o2b3o21b3o$9b4o8b2o10b7o8bob2o21b3o21b3o
19bob3o21b3o18bob4o20b4o21b3o21b3o$8b5o7b3o9b9o7bob3o17bo2b4o17bo3b3o
21b3o22b2o20b4o18bo3b2o20bob2o22b2o$7b6o6b3o9b5ob5o10b2o21b3o18bo3b2o
18bob4o21b3o18b6o17b2o2b3o19bob3o20bob2o$8b5o7b2o10b3o3b5o9b3o21b3o20b
4o19b5o19b5o21b3o22b2o18bob4o21b3o$9b4o8b5o7bo5b5o7b5o18bo2b3o19bob3o
19bob3o19bob3o22b2o21b3o17b2ob4o21b3o$10b3o9b5o13b5o4b8o20b4o20b4o20b
4o21b3o21b3o21b3o19b5o20b4o$11b2o10b4o13b4o7b5o21b3o16bo3b4o19bob3o22b
2o19bob3o21b3o19bob3o19b5o$12b3obo7b3o12b4o9b3o20b4o18bob4o18b6o21b3o
16b3o2b3o21b3o22b2o19b5o$13b4obo6b4o7bobob2o10b2o21b3o19bob3o19b5o18b
o3b2o18b2ob3o21b3o15bo3bob3o20b4o$14b5o7b4o8b3o9b3o21b3o22b2o16bo3b4o
17bobob3o20b4o21b3o17b2o3b2o21b3o$15b4o8b3o6b4o8b4o20bob2o21b3o20b4o19b
ob3o21b3o19bo2b2o18b6o21b3o$bo14b5o7b3o4bob2o8b4o22b2o21b3o18bo2b3o22b
2o17b2ob4o21b3o19bob3o20bob2o$bo15b5o7b3o2b4o9b3o18bo2b3o20bob2o18b6o
21b3o18bob4o21b3o20b4o22b2o$18b5o7b7o7bo2b2o18b2o2b2o22b2o18b6o21b3o22b
2o20b4o21b3o20b4o$19b4o8b5o9b3o21b3o21b3o21b3o20b4o20b4o19b5o20b4o20b
4o$3o17b3o9b3o4bo5b2o17bo4b2o22b2o17bob5o20b4o20bob2o19b5o17bo2b4o20b
4o$21b2obo8bo9b3o16bobob4o20b4o17bo2b4o17bo2b4o22b2o21b3o21b3o21b3o$2o
20b2o17bob2o16bo3b4o17bo2b4o19b5o21b3o21b3o19bo2b2o21b3o21b3o$obobo18b
3o16b2o17b3ob3o21b3o20b4o22b2o21b3o21b3o15bo5b3o20b4o$6o18b3o13b3o22b
2o22b2o20b4o20b4o19bo2b2o22b2o15b2o4b3o20b4o$b3obo19b2o12b3o20b4o20b4o
19b5o20b4o21b3o20b4o17bo2b4o21b3o$2b2o22b5o5b5o15bo5b3o20b4o19b5o21b3o
17bobo2b2o20b4o21b3o16b2o2b4o$3b5o19b3o2bo4b3o18b6o21b3o19b5o21b3o19b
5o20bob2o21b3o19b5o$4b5o19b2o3bo2b3o16bo3b4o20bob2o20b4o19bob3o20b4o21b
3o21b3o20b4o$5b4o20b9o19b5o22b2o21b3o20bob2o21b3o19b5o20b4o21b3o$6b6o
18b7o20b4o19b5o20bob2o19b5o19bo2b2o19bob3o20b4o20b4o$7b3o3bobo15b5o21b
3o19b5o22b2o20b4o21b3o21b3o20b4o20b4o$8b3obo19b3o20bob2o17bob5o21b3o19b
5o16bo3bob2o18b3ob2o19b5o21b3o$9b2obo20bo22b2o17bo3b3o21b3o22b2o16bo4b
3o18bo2b3o19b5o17bo4b2o$10b2o2bo39b3o21b3o21b3o21b3o16b2ob5o18bob4o20b
4o17b2o2b3o28b3o$11b3o37bo2b2o21b3o16bo2bo2b2o20b4o15bo4b4o18bob4o21b
3o22b2o28bobobo$12b2o4bo33b3o17bo3b3o21b3o19b5o18b6o19bob3o21b3o21b3o
28bob3obo$13b6obobo27b4o17b2ob4o21b3o21b3o18bob4o20b4o19bo2b2o20b4o29b
7o$14b5obo28b4o17b7o19bob3o18b2ob3o20b4o19bo2b2o21b3o20b4o30bob3obo$15b
3o4bo26b3o17b2ob4o21b3o20b4o16bo4b3o21b3o22b2o20b4o32bobobo$16b4o25bo
3b2o19b5o22b2o20b4o16bo3bob2o20bob2o17bo3b3o21b3o34b3o$17b3o26b4o21b3o
20b4o19bob3o19bo2b2o19b5o17bo3b3o21b3o$18b2o2bo23b3o15bo3bob3o21b3o21b
3o18bob4o22b2o21b3o20bob2o$19b3obo18b6o18bobob2o15bobo3b3o22b2o13bobo
3bob3o15b2o4b3o21b3o22b2o$20b3o15bob2o3b2o19b5o15b9o17b2ob4o14b4o3b3o
16b4o2b2o21b3o21b3o$21b2o19b4o20b4o15b9o18bob4o15bobo4b2o17b7o21b3o20b
4o$22b3o15bob3o20b4o18b6o20bob2o21b3o18b6o21b3o21b3o$23b3o13b5o21b3o20b
4o22b2o20b4o20b4o21b3o21b3o$24b2o2bo9bob3o21b3o21b3o18b6o21b3o21b3o20b
4o22b2o42bo$25b3o10b4o20bob2o21b3o20b4o19bo2b2o20b4o17bo2b4o21b3o43bo
$26b2o10b3o18b2o2b2o19bo2b2o19bob3o19bob3o19b5o21b3o21b3o$27b3o3b7o20b
4o21b3o21b3o22b2o19b5o18bo3b2o17bo2b4o45bo$28b2o2bo3b3o18bob4o22b2o19b
5o21b3o19b5o17bo3b3o16bo4b3o41bo2b4o$29b9o19b5o21b3o21b3o22b2o19b5o21b
3o16bo4b3o45b3o$30b7o14bobo3b4o20bob2o20b4o20b4o20b4o21b3o20bob2o43bo
b3o$31b5o16bo4b3o16bo5b2o21b3o20b4o21b3o21b3o22b2o44b4o$13bo18b3o16bo
4b3o14bo2b2o2b3o21b3o19bob3o16bobob4o20b4o21b3o41bo2b4o$33bo17b4ob2o21b
3o21b3o20bob2o17bobob3o19b5o21b3o44b4o$11b3o41b2o18bo2b3o21b3o21b3o19b
o2b2o21b3o19b5o44b4o$11b3obo35bob3o20b4o21b3o17bo3b3o18bob4o19bob3o18b
ob4o45b3o$12b4o34bo2b2o20b4o15bo2b2ob3o19bo2b2o21b3o18bob4o21b3o41bo2b
4o$13b4o33b4o21b3o16bobo2b3o18b6o19b2ob2o20b4o18b6o43b5o$14b3o33b3o19b
o2b2o17bo2bob2o19b5o17b2o3b2o20b4o20b4o44b4o$15b2obo29b4o19bob3o20bob
2o21b3o17b7o16b2o2bob2o20b4o44b4o$16b2obo27b4o21b3o21b3o22b2o17b3ob3o
17b2obob2o19bo2b2o46b2o$17b3o4bo21b4o22b2o21b3o21b3o17b3ob3o16bo2bob3o
21b3o43b5o$18b3o4bo20b3o21b3o21b3o20b4o18b2ob3o17bo4b2o19bob3o44b4o$19b
6o16b2o2b3o21b3o17bo2b4o20b4o19bob3o19bob3o18bo2b3o45b3o$20b4obo15bo3b
2o21b3o21b3o20b4o20b4o18b6o18b6o18bo2b2o22b3o$21b3o18b4o21b3o22b2o21b
3o16bo4b3o21b3o19bob3o18b2o2b2o21b3o$22b3o14b2ob3o21b3o20b4o21b3o16b2o
2b4o21b3o22b2o20b4o19bo2b2o$23b4o11b6o20b4o20b4o20bob2o16b8o22b2o19b5o
19bob3o21b3o$24b3o10b6o21b3o16bo4b3o22b2o16b8o21b3o19b5o20bob2o20bob2o
$25b3o6bob6o21b3o20b4o17bo3b3o16b8o21b3o21b3o21b3o21b3o$26b3o4bo4b3o21b
3o21b3o17b3ob3o16b8o16bo2bo2b2o19bo2b2o15bo4b4o23bo$27b2obo4b5o20b4o20b
4o17b7o16b8o16bo4b3o18b2ob3o18b6o$28b2o5b4o17bo3b3o20b4o20b4o19b5o18b
6o18b6o19b5o$29b3o3b3o19b5o21b3o20b4o14b2o4b4o18bob4o21b3o20b4o$30b2o
2b3o19bob3o21b3o18b2ob3o13bo6b4o19bob3o22b2o20b4o$31b5o20b4o22b2o18b6o
15bo2bo3b2o19b5o19b5o21b3o$32b3o17b2o2b3o21b3o19b5o14bo2bo3b3o18bob4o
19b5o19bo2b2o$33bo17b7o20b4o19bob3o15bo3bo2b2o21b3o20b4o17bo3b3o$50b2o
b4o20b4o21b3o18bo2b3o20b4o17bo3b3o22b2o$50b6o20b4o18bobob2o18bo3b2o15b
obob5o19b5o21b3o$49bob4o18bo2b3o19b5o21b3o20b4o23bo20bob2o$19b2o29b4o
19b5o20b4o19bob3o17b7o43b2ob2o$50b3o21b3o20b4o19b5o17bob5o23bo22b2o$18b
o28bo2b2o21b3o21b3o19b2ob2o19b5o40bo3b4o$20bo25b5o20bob2o21b3o19bo2b2o
18b6o40bo4b3o$19b2o26b3o22b2o22b2o21b3o20b4o41b7o$18b2obo20bo2bob2o21b
3o21b3o22b2o17b2o2b3o42bobo2bo$19b2o22b5o20bob2o21b3o21b3o18bo3b2o44b
obo$20b3o18b6o17bo4b2o21b3o20bob2o21b3o$21b5o17b3o21b3o19bo2b2o22b2o21b
3o$22b5o16b2o18bo2b3o19bob3o21b3o19b5o$23b5o13b3o21b3o21b3o20bob2o20b
4o$24b5o6bo4b3o21b3o22b2o22b2o21b3o$25b3o8bo2b3o20b4o21b3o21b3o17bo3b
3o$26b4o4bo3b3o18bo2b3o19bob3o20b4o20b4o$27b6o3b4o18b2o2b2o21b3o20b4o
20b4o$28b4o2b5o21b3o21b3o18b2ob3o19bob3o$29b9o22b2o14bo6b3o20bob2o18b
o3b2o$30b7o19bob3o22b2o21b3o17bo2b4o$31b5o18bobob2o19bob3o18bo2b3o17b
o2b4o$32b3o21b3o20b4o17bobo2b2o20b4o$33bo21b3o18bo2b3o18bob4o21b3o$54b
3o18b2ob3o21b3o20b4o$52bob2o21b3o22b2o$53b2o17b2o3b2o21b3o$51b3o21b3o
21b3o$50b3o21b3o19bo2b2o$45bo4b2o21b3o19b5o$47b4o22b2o21b3o$46b4o20b4o
22b2o$46b3o20b4o21b3o$46b2o17b2o2b3o21b3o$43b4o17b3o2b2o21b3o$38bo3b4o
18bob4o21b3o$37bo2b5o19bob3o22b2o$30bo9bob2o20b4o$41b2o21b3o$29b3o3b2o
2b3o20bob2o$29bo5bo2b3o22b2o$27b5o3bob3o21b3o$28b3o2bo2b3o21b3o$29b3o
3b3o20bob2o$30b7o18b3ob2o$31b5o19b5o$32b3o22b2o$33bo23bo$54bo$55bo!
[[ AUTOIDENTIFY ]]

Code: Select all

x = 191, y = 144, rule = B3aiky4ace5aejk6in/S2en3cij4aciw5-cn6aei7e
12$122bo$123bo5$112bo13b3o$110b5o11bobo$108b4ob4o11bo$106b3obo3bob3o$
104b4obo4bo2bo$102b3obobo5bobo$103bobo$102b3obo$101bobobo$104b2o$102b
3o2$112bo$110b5o$108b4ob4o18bo$106b3obo3bob3o15b2o$104b4o2bo3bo2b4o14b
2o$102b3obo7bobobob3o11bobo$100b4o2bo8b2ob2ob4o8bob3o$99b2ob2o2bo8bo3b
o2bob2o6bobob2o$98b2obo17bobobob2o6b3ob2o$98bob2o24bo5bob3obo$97b5o2bo
20b3o7b5o$97b4ob3o21b2o4b3ob4o$96b2ob4o9bo12bob2o5b4ob2o$96bob3o9b5o
13bo7b3obo$95b4o9b4ob4o8b5o8b4o$95b3o9b2ob2ob2ob2o9b3o9b3o$94b2o10b2ob
2o3bo2b2o10b2o10b2o$94bo11bo2bo4b3obo11bo11bo$93b5o7b4o8b3o9b3o9b3o$
93b3o9b3o7b2obo11bo11bo$92b2o10b2o8b2ob2o10b2o10b2o$81bo10bo11bobo8b3o
9b3o10b2o$79bob3o7b3o9b3o10bo10b3o9b3o$80bo11bo11bobo19bobo9bobo$80b2o
10b2o10b2o21b2o10b2o$81b3o9b3o9b2o19b2o9b3o$81bob3o7b3o9b3o16b4o7b5o$
84bo9bobo9bo15b3obo6b2o3bo$94b2o10b2o2bo11bo2b2o7b2ob2o$95b2o10b2ob2o
9b2ob2o10b2o$95b4o9b4ob2o3bo2b4o8b5o$96bo13b3ob2ob2ob3o13bo$96b2o14b4o
b4o8b2o4b2o$97b3o14b5o10bo3b3o$97b3o16bo11b2o3b3o$98bobo2b3o22bob3obo$
98b2o5bo21b5ob2o$99b2ob3obo20b4ob2o$100b4obo20b2ob4o$102b3obobo17bob3o
$104b4obo13bob4o$106b3ob2o2bo3bo2b2ob3o$108b4o2bo3bo2b4o$110b3obo3bob
3o$112b4ob4o$114b5o$116bo!
[[ AUTOIDENTIFY ]]

[vilc]

Presumably an easy one to prove: at least in a range-1 2-state rule, an isolated cell of a given period cannot be surrounded by eight cells of a lower period (such that all eight of them are the same).

If I understand your conjecture correctly, here is a counterexample :

Code: Select all

x = 3, y = 3, rule = B2eik3-i4cjknt/S4e5y6ik
obo2$obo!

The middle cell is p4 while all its neighbours are p2.
(found with LLS with an input generated by jls-to-lls.py)

There is however the following weaker result which is valid for any cellular automaton with k states :
If the neighbourhood of a cell in a periodic pattern repeats every n generations, then the period of this cell is at most k * n.

Proof:
Consider such a cell. The transition function of the CA can be written locally as
T : (N, S) -> S'
where N is a state of the neighbourhood, S the current state of the cell and S' the next state. In our case, N is determined by the congruence of the generation mod n. We can modify our function T into
T' : (g, S) -> (g+1, S')
where g is the generation number reduced mod n. We are now looking at recurring sequences in a finite set with cardinality n * k. It follows that the sequence of iterates must have period at most n * k. In particular, this bounds the period of our cell.

[PK22]

I managed to prove that all strict still lives with <= 19 cells have a 1G or 2G destruction by using a script. #
Here's a zip file containing a destruction for all of them:
destructions.7z
I will run a search on all natural still lifes to see if I can find a reasonably small SL that cannot be destroyed in 2 gliders.

EDIT 27/9/2025: Turns out every natural SL can be destroyed in <= 2G. It's impressive how far two gliders can go. I will instead feed in some large semi-natural SL to try and find an upper bound.

EDIT 2: xs80_y1j9m44m9jz35s2521y01252s53z65125ak8w8ka52156zy164311346 seems to be nearly indestructible with 2G, but I need independent confirmation on that. Assuming I am correct, then the smallest SL which cannot be destroyed with two gliders has N cells, where 19 < N < 81.

Improved the lower bound to N <= 21 by modifying the script to allow for parallel instances:

[vilc]

EDIT 2: xs80_y1j9m44m9jz35s2521y01252s53z65125ak8w8ka52156zy164311346 seems to be nearly indestructible with 2G, but I need independent confirmation on that. Assuming I am correct, then the smallest SL which cannot be destroyed with two gliders has N cells, where 19 < N < 81.

Here is a 2G destruction of xs80_y1j9m44m9jz35s2521y01252s53z65125ak8w8ka52156zy164311346, though not with slow gliders.

Code: Select all

x = 75, y = 55, rule = B3/S23
obo$b2o$bo7$74bo$72b2o$73b2o26$27b2o4b2o$27bobo2bobo$29b4o$28bo4bo$27b
obo2bobo$22b2o2bobo4bobo2b2o$22bo2bobo6bobo2bo$23b2obo8bob2o$24bo12bo$
24bo12bo$23b2obo8bob2o$22bo2bobo6bobo2bo$22b2o2bobo4bobo2b2o$27bobo2bo
bo$28bo4bo$29b4o$27bobo2bobo$27b2o4b2o!

[PK22]

Here is a 2G destruction of xs80_y1j9m44m9jz35s2521y01252s53z65125ak8w8ka52156zy164311346, though not with slow gliders.

Code: Select all

rle

That's fine; the original question was "What is the smallest still life without a two-glider destruction?", so a synchronised pair is fine.
This does remove the upper bound I conjectured, however.

Here is the program I have been using, in case someone with more computing power wants to improve the lower bound:

Code: Select all

#Set up lifelib
import lifelib
sess = lifelib.load_rules('b3s23')
lt = sess.lifetree(n_layers = 1, memory = 1000)
#Import other modules
import os, random, urllib.request, time, hashlib
seed = hashlib.sha256(str(time.time()).encode('utf-8')).hexdigest()
hexdict = {'0':0,'1':1,'2':2,'3':3,'4':4,'5':5,'6':6,'7':7,'8':8,'9':9,'a':10,'b':11,'c':12,'d':13,'e':14,'f':15}
def getcanon(pattern):
    digests = []
    orientations = []
    period = pattern.period
    for x in range(period):
        for y in range(2):
            for z in range(4):
                pattern = pattern('rccw')
                if pattern.digest() not in digests:
                    digests.append(pattern.digest())
                    orientations.append(lt.pattern(pattern.rle_string()))
            pattern = pattern('flip_x')
        pattern = pattern[1]
    return orientations
glider = lt.pattern('bob$2bo$3o!')
gliders = getcanon(glider)
def rewind40(collision):
    components = collision.components()
    for x in components:
        if x.wechsler in ['153', '163']:
            collision = collision - x
            x2 = x(-x.displacement[0]*2, -x.displacement[1]*2)
            collision = collision + x2
    return collision                     
def savedestruction(apgcode, pt):
    cwd = os.getcwd()
    if not os.path.exists(cwd + '/destructions/' + apgcode[0:apgcode.find('_')]):
        os.mkdir(cwd + '/destructions/' + apgcode[0:apgcode.find('_')])
    if not os.path.exists(cwd + '/destructions/' + apgcode[0:apgcode.find('_')] + '/' + apgcode + '.rle'):
        f = open(cwd + '/destructions/' + apgcode[0:apgcode.find('_')] + '/' + apgcode + '.rle', 'w')
        f.write(pt.rle_string())
        f.close()
def validate(collision):
    return rewind40(collision)[8] == collision
def destroyobj(apgcode):
    ipt = lt.pattern(apgcode)
    orientations = getcanon(ipt)
    for pt in orientations:
        bbox = pt.bounding_box
        x = bbox[0]
        y = bbox[1]
        dx = bbox[2]
        dy = bbox[3]
        for a in range(8 + dx + dy):
            collision = pt
            collision = collision + glider(x - 13 - dy + a, y - 10)
            if collision[200].empty():
                return collision
    return None
def destroy2G(apgcode):
    pt = lt.pattern(apgcode)
    for x in range(1000000):
        randseed = hashlib.sha1((seed + apgcode + str(x)).encode('utf-8')).hexdigest()
        pt2 = pt
        for y in range(2):
            glider = gliders[hexdict[randseed[3*y]]]
            displacement = glider.displacement
            glider = glider(-25 * displacement[0], -25 * displacement[0])
            dx = hexdict[randseed[3*y+1]]-8
            dy = hexdict[randseed[3*y+2]]-8
            glider = glider(dx, dy)
            pt2 = pt2 + glider
            if validate(pt2):
                evolvedpt = pt2[250]
                if evolvedpt.empty():
                    return pt2

def process(obj):
    if obj != '':
        apgcode = lt.pattern(obj).apgcode
        cwd = os.getcwd()
        if not os.path.exists(cwd + '/destructions/' + apgcode[0:apgcode.find('_')] + '/' + apgcode + '.rle'):
            attempt1 = destroyobj(apgcode)
            if type(attempt1) != type(None):
                savedestruction(apgcode, attempt1)
                return None
            attempt2 = destroy2G(apgcode)
            if type(attempt2) != type(None):
                savedestruction(apgcode, attempt2)
                return None
        else:
            return None
        print('Unable to destroy '+apgcode)

f = open('21_bits_strict.txt', 'r')
thelist = f.readlines()
f.close()
random.shuffle(thelist)
for x in range(len(thelist)):
    if x%100== 0:
        print(x)
    process(thelist[x])

You will need a directory named 'destructions', and you can generate the list of SL using Simon Ekstrom's still life searcher.
I suggest running it with multiple terminal windows open; the instances have a random search order, and ignore SL that have already been destroyed and saved, so you can run multiple instances in parallel.

[NickGotts]

andrewthelifer:

Probviously true, but intractable: in the long run (and at large range), an arbitrarily sparse but non-zero-density Life universe will have no moving objects as all spaceships and puffers will collide into something eventually.

This is false, if I understand you correctly. If we assume the Life universe to be infinite, then whatever its density, any glider-constructable arrangement of cells will exist after any number of steps, because for any such arrangement, and for any number s of steps greater than some minimum, there will be arbitrarily large regions containing nothing but a collection of gliders that give rise to that arrangement after s steps. More generally, in analysing Sparse Life (i.e. an arbitrarily sparse but non-zero-density [infinite (or finite but arbitrarily large enough to contain a finite but arbitraily large number of initial on-cells)] Life universe) - sorry about the nested brackets - we need to consider three timescales:
* Short-term: what has happened after s steps for some finite s.
* Long-term: what arrangements of cells will and will not continue to exist after any number of steps. That includes everything glider-constructible, excludes any arrangment that includes an "orphan" or descendant of orphans on every line of descent, and leaves a lot undetermined in between.
* Medium-term: We can define "eras" in terms of the reciprocal N of the initial density d. Consider the originally-existing gliders in a Sparse universe. They will be present at step 0 at O(d^5) locations - i.e., O(d^5) cells will form part of such a glider, while O(d^3) cells will form part of a blinker or preblock. Now consider the possible path of such a glider. For "almost all" such gliders (I'll be more precise below) the first thing in their path will be a blinker or (from step 1) a block (twice as many will have a block than a blinker in this position), and that blonk will be O(N^3) cells away, and the glider will hit it after O(N^3) steps. But for a proportion O(d) of the initial gliders, the first thing in their path will be something requiring four or more initial on-cells, and for O(d) of the initial gliders again, the first thing in their path will be at a distance of O(N^2) or less. I've written several articles on Sparse Life, and am currently preparing to return to the topic after a long break.

[NickGotts]

I should add that in the "long term" we can also consider whether the density of certain patterns which we know will always exist (see above) tends to 0 (or indeed to any other value). But not enough is known about Sparse Life, or an infinite random field with any density other than 0 and 1, to determine this for any pattern.

[hth3]

Conjecture: Life does not have an universal catalyst.

[LuveelVoom]

Conjecture: Life does not have an universal catalyst.

Define universial?

[hth3]

Conjecture: Life does not have an universal catalyst.

Define universial?

A still life or oscillator that resists any impact

[b-engine]

A still life or oscillator that resists any impact

"Resist any impact" might mean that it always recover from collision with anything.
Such thing might not exist in Life, since they you can destroy the hypothetical catalyst while it's recovering.

[FlutterWithKSparkler]

Has the sierpinski wolfram rule been proven TC?
Just curious, cuz otherwise this could be a counterexample:

Code: Select all

x = 1, y = 1, rule = B15k/S012-i3-a45-kr678
o!

If you mean an XOR rule that produces Sierpinski-like patterns, each generation is just a linear combination of the previous one, so you can effectively write a closed form solution for the value as far off in the future as you like. I don't see how that could be Turing complete.

This matter has been raised by User:Lysandre Terrisse at stackexchange in a similar form as well. With the help of MAPPer.lua and create-custom-ltl.lua, here is an attempt at enumerating these affine cellular automata for the 2-state (0/1), anisotropic cases on the range-1 Moore neighbourhood unique up to reflecction and rotation, but only 102 of the 153 cases (it is unclear where the rest 51 are):

2state_anisotropic_range1_moore.txt

(13.46 KiB) Downloaded 120 times

They just look like OCA:Fredkin B1357/S02468 since most if not all are just parity replicators running on custom neighbourhoods, and my opinion would be that they may instead get a proof of non-Turing completeness one day.

[PK22]

Improved the lower bound to N <= 21 by modifying the script to allow for parallel instances:

All still lifes up to 22 cells now have a <=2G destruction, but even the zipped file is too big to post here, so I've moved the destructions to GitHub.

I predict that running my script on all 23 cell SL could take 24 hours, if not even longer. Past that, it could take several days to get the LB up to 24, and getting it up to 28 might take two to four months, so I really hope that there is some resilient 23 or 24 cell still life out there. Unfortunately, larger SL do seem structurally weaker, based on some random sampling of the results.

Regardless, I will optimise the program (one of my new plans, as inefficient as it sounds, is to have a separate locally hosted HTTP server to handle the storage of destructions) and keep making progress.

EDIT: The local server works quite well for allocation of work to client programs. I am considering registering a domain and setting this up as a distributed project in order to make more progress.

EDIT: N <= 23 now, after an overnight search using an HTTP server. 24 hours seems like a more accurate estimate for getting N <= 24.

[qqd]

Probably true, but hard to prove: There exists a spaceship in Life with a phase in which all cells survive to the next generation.
Finding an elementary example would be very difficult, but an engineered example should be possible.

Between generations 6 and 7 of the below collision between a glider and long boat (which is an OTT), all cells survive. (There are likely other examples that could be used).

Code: Select all

x = 4, y = 9, rule = B3/S23
o$b2o$2o3$bo$obo$bobo$2b2o!

This means that if the rest of the spaceship is made up entirely of still lifes, there will be a phase where all cells survive...

We already have a Stable Storage Spaceship with the initial phase being a glider hitting a stable constellation of population 633523. Seems like a variant of the spaceship should be enough to prove the conjecture.

[dvgrn]

Between generations 6 and 7 of the below collision between a glider and long boat (which is an OTT), all cells survive. (There are likely other examples that could be used).

We already have a Stable Storage Spaceship with the initial phase being a glider hitting a stable constellation of population 633523. Seems like a variant of the spaceship should be enough to prove the conjecture.

Yup, re-compiling the Stable Storage Spaceship recipe to add just some single-digit number of still lifes should do the trick. Pi heptominoes and centuries and many other active objects have all-cells-survive steps in their evolution, so it's probably just a matter of picking the smallest 0-degree one-time turner with a 0hd lane shift that has an all-cells-survive stage in it, and building that into the Stable Storage Spaceship recipe in the path of the activation glider.

Let's see, none of the two-object "Lane+00" turners have an all-cells-survive stage, though a couple of them are only one cell away. The above glider+longboat collision allows any number of easy four-object additions with four 90-degree OTTs (at least one being a longboat) bouncing the glider off the input lane and back on again.

There might be a three-object addition starting with a glider hitting a block, and two more objects interacting with the pi to get a glider back out again after the pi's all-cells-survive stage. Or we could look for a two-object 90-degree OTT that fits after the longboat OTT, that throws its output glider back the right distance to put it back on the original lane.

[Naszvadi]

There is a simple explicit construction of elementary cirtuitry in rule B34/S0134V on every Euclydean lattice with at least 2 dimensions, in the latter case, B34.*/B0134.*V is the regex that should match the rulestring. Layz Boi constructed all necessary elements (wires, delays, flips, corders, splittes and an ANDNOT gate), I just constructed a P32n crossover, and together with signal generators, every logic gate can be constructed. I made a W110 unit cell, see here:
viewtopic.php?f=11&t=2597&start=125#p223249

I would like to ask some mathematicians here for "proofreading".

Corollaries: of course on a $Z^d$ lattice,. with von Neumann neighbourhood, a spaceship could not exist with only two states if the cellular automata has a quiescent state 0 so B0 including blinking rules are omitted. Without B0, any bounded nonempty pattern in B1.*V rules will expand its bounding brick in all 2*d directions. Without B1, a bounded pattern cannot escape from its bounding brick. So these rules does not support spaceships.

Focusing on these vN rules is reasonable: unlike CGoL, their neighbourhood graphs are vertex- and edge transitive.

[NNlk05]

Conjecture: Life is omnidirectional.
There exists an elementary spaceship for every direction and every speed.
Note: I am probably not the first one to come up with this.