* [It should be noted that both still lifes and p1 photons are trivial, the latter not existing at all, in von Neumann (outer-totalistic and isotropic non-totalistic) and 3-neighbor triangular outer-totalistic rules, and photons of any period cannot exist in 2-state isotropic range-1 hexagonal rules. Additionally, none of us have found any results worth reporting for any larger neighborhoods, or hex or Moore INT rules, because these rulespaces are for the most part too large to enumerate reasonably, except maybe hex INT.]
For each of these projects, I've been maintaining publicly-editable spreadsheets (based off of a copy of a view-only one created for the Moore still lifes project by dani) listing the minimum population count known for every rule in the rulespace:
- Smallest still lifes (in every range-1 Moore OT rule and every range-1 hex OT rule): this set of spreadsheets
- Smallest known p1 photons (in every range-1 Moore OT rule): this spreadsheet
Since there's a lot to report, this first post (which might be the only one for a while as I collect patterns for the other ones in and amongst doing actual real-life things like "taking classes" and "studying" and "hopefully actually getting some kind of social life") will only focus on the simplest nontrivial case, finding the lowest-population still life in every outer-totalistic range-1 hexagonal rule, which is very nearly complete and is only missing a few difficult proofs of nonexistence or minimality.
The full set of rule-minimal hex still lifes has 51 members with populations ranging from 1 to 181 (the latter only conjectured to be minimal). Most of these were found by me either manually or using rlifesrc, and I think one of them (B2356/S12356H iirc) was found by wildmyron also with rlifesrc. Every such still life is listed on the still lives spreadsheet. For reference, here are the five smallest still lifes and the five largest ones in the most restrictive rule in which they function — any birth transition(s) can be omitted or survival transition(s) added and the still life will still work:
1 cell, B23456/S0H:
Code: Select all
x = 1, y = 1, rule = B23456/S0H
o!
Code: Select all
x = 2, y = 1, rule = B3456/S1H
2o!
Code: Select all
x = 2, y = 2, rule = B3456/S2H
o$2o!
Code: Select all
x = 3, y = 3, rule = B2456/S13H
bo$2o$2bo!
Code: Select all
x = 4, y = 3, rule = B2456/S124H
bo$4o$2bo!
Code: Select all
x = 13, y = 13, rule = B2356/S123H
obobobo$b6o$2o5b2o$bob4obo$2ob2ob2ob2o$bobo4bobo$2ob2o3b2ob2o$2bobo4b
obo$2b2ob2ob2ob2o$4bob4obo$4b2o5b2o$6b6o$6bobobobo!
Code: Select all
x = 15, y = 17, rule = B2356/S1345H
2bobo$3b2o$ob5obo$b3o2b3o$5obo2b2o$2bo2b3obo$2b2obo2b3o$3b4ob3o$2b2o2b
3o2b2o$4bobo2bobo$4b4ob4o$5bo2b3obo$4b3ob3o2b2o$6b3o2b3o$6bob2ob2obo$
10b2o$10bobo!
Code: Select all
x = 13, y = 17, rule = B256/S145H
obo2bo$bob3o$o2b4o$bob2ob3o$o2b2o2bo$b4ob3o$b5o2b3o$3o2b2ob2o$2b2o2b4o
$2ob5ob2o$3b5o2b3o$2ob2o3b4o$3b2obob4o$2b3o2b3o2bo$4b6o$5b3o2bo$5bo2b
o!
Code: Select all
x = 17, y = 17, rule = B236/S1356H
obo3bobo$b2o4b2o$2ob2ob2ob2o$2bob4obo$2b9o$3b8o$ob5ob5obo$b5o4b5o$2o2b
3o3b3o2b2o$2b5o4b5o$2bob5ob5obo$6b8o$6b9o$7bob4obo$6b2ob2ob2ob2o$8b2o
4b2o$8bobo3bobo!
Code: Select all
x = 25, y = 25, rule = B2356/S134H
2bobo$3b2o$ob2ob2obo$b3o2b3o$3ob3o2b2obo$2bo2b2obob3o$2b4o2bobo2b2obo
$3bobob3o2bob3o$2b2o2bo2b4obo2b2o$4b5obobob2obo$4b2o4bo2bob4o$5bob8o3b
o$4b3o2b2ob2ob3ob2o$6b3obo2bo2bo2bo$6bob2ob6ob3o$10bob2o2b2o2bo$10b2o
bobob3ob2o$11bobobobo3bo$10b3o2b2o2b4o$12b4ob4obo$12bob2o2bobo2b2o$16b
3o2b3o$16bob5obo$20b2o$20bobo!
- Rules with B0 or B1 trivially contain no still lifes, as patterns cannot have a bounded population.
- The rules B2(3456)/S(3456)H cannot contain still lifes, as a live cell on the edge of a pattern's bounding hexagon must immediately either die or cause a birth beyond the edge.
- The rules B2(3456)/S2(6)H cannot contain still lifes, as the only pattern for which similar logic doesn't apply is a simple 3-cell triangle, which is obviously not a still life, or groupings thereof.
- The rules B234/S(123456)H cannot contain still lifes, as two live cells cannot border each other on the edge of a potential still life's bounding hexagon, and each dead cell on the boundary next to a live cell on the boundary must be bordering no other live cells, enforcing a S0H configuration.
- B23/S(23456)H rules cannot have still lifes, because without S1H the only boundary configuration satisfying B23H is a infinite alternation of live and dead cells at the boundary and an infinite row of all live cells one row behind the boundary, which does not help for constructing finite still lives.
- B23/S1(56)H still lifes are impossible because without any of S234H, a S1H configuration (the only remaining one that can exist at a boundary) must be part of a simple dihex island, which cannot exist stably at a boundary when B23H are present.
- And lastly for the easy ones, B3456/S(345)H cannot contain still lifes, as all B345H still lifes must have a convex boundary (i.e. be filled convex hexagons), and since without S2H such a hexagonal still life must have all side lengths >1, death on six alive neighbors must be triggered in the interior of the hexagon.
- B(3)4(56)/S3H, when considering the leftmost cell on the upper boundary of a still life, seem to allow nothing but an infinite regular wick stretching along the boundary to the right. I posted a proof outline on Discord several months ago, which hasn't been verified.
- B23(56)/S12(56)H: I posted a proof outline on Discord, which again hasn't been verified. This one doesn't need to involve wicks of any kind, luckily.
- B346/S35H: I posted a proof outline on Discord, but that outline was wrong. I think a proof would still be practical, but there are a lot of cases one would have to manually enumerate.
- B2(456)/S1(56)H: Similar to B23/S1(56)H, but a bit harder because infinite dihex wicks exist. This is mostly an exercise in mathematical induction I haven't bothered to do yet.
- B2456/S24(6)H: Probably doable purely deductively, but I haven't gotten to it yet. I wish LLS supported hex rules so I could automate these.
- B2456/S145H: More case analysis, I think. Setting a cell on the top edge as on seems to force something looking like the B245/S145H still life, but it's not stable due to B6H.
- B23(56)/S145H: Fairly complicated, but there don't seem to be any repeating components on orthogonal edges. Just a lot of case analysis.
- B2(456)/S25H: Setting the leftmost cell on the top edge on seems to produce a wick stretching infinitely to the right. Probably a reasonably straightforward inductive proof.
- B245(6)/S23(6)H: Might be provable with simple induction, but a lot of cases to handle within that. It's easy to construct still life "shells", but the insides can't be filled in.
- B236/S1356H with any or all, but not none, of the following changes: add B5, remove S5, remove S6: The case analysis is almost certainly too complicated to do manually, but even very large searches (50x50 or so) finish quickly with no results. Not sure how to effectively prove this without a SAT solver or similar, which may or may not even work if there are repeating components.
- B2(3456)/S14H: A whole can of worms with tons of agars and wicks, including domino wicks. Partial still lifes seem to have a component that it's impossible to "turn a corner" on. The B23(456)/S14H subcase seems easier (mostly just case analysis), but probably redundant. Need wholly new techniques (to me) to prove this. Searches very quickly, but slower than the last one.
Just a quick preliminary overview of the other two projects' status, before I do full write-ups for them:
- Moore OT still lives: largely complete, there are only twenty-two rules marked "???" — but many more either will have difficult-to-impossible proofs or still need to have their still lifes confirmed as minimal at a higher radius for checking (or in a few cases — for example, the 293-cell still life in B247/S24 — they are decently likely not to be minimal after all). All remaining undecided rules are either B2 rules or rules with neither of B23 (B3 rules turn out to be fairly trivial, and B0 and B1 rules lack still lifes altogether) — only two lack both of B23 (with a further six being difficult-to-disprove cases) and the rest are in B2. The number of distinct minimal still lifes is not something I've kept track of, but is likely in the low hundreds. All "large" (>100 cells) cases that are decided lie in the B2 rulespace.
- Moore OT p1 photons: very much incomplete. Only a few impossibility proofs have been attempted, and fairly few photons (so far mostly just ones from glider.db or rules therein) have been shown to be (almost certainly) minimal. Not only is the rulespace for which deciding whether p1 photons exist and if so what the smallest examples are is an interesting problem much larger than that for still lifes, but the photon-finding problem also lacks key simplifying features of the still-life-finding problem — mainly, that adding survival conditions to and removing birth conditions from a rule supporting a still life always gives another rule supporting that still life, which is not the case for photons except in certain special cases involving B0 and S8. Multiple hundred distinct photons have been found in my estimation, but the rulespace is nowhere near fully searched, and even when photons are found the smallest examples findable with existing search techniques are often in the thousands of cells, making minimality verification all but impossible. The project has essentially become a photon catalog first and a photon minimality project second, although again the actual patterns haven't been kept track of well enough (most are somewhere on Discord, but some will need re-searching to find). Ultimately, I would be happy if the project got anywhere close to finding p1 photons in most rules where p1 photons are likely to exist — but since the effort has largely died out recently I don't know if that will happen. (A special shoutout to everyone who has been searching far and wide for photons to add to the spreadsheet over the past year — most notably 400spartans on Discord, who has done many of the longest and hardest searches.)