Rule-minimal pattern projects

For discussion of other cellular automata.
Post Reply
User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Rule-minimal pattern projects

Post by praosylen » January 20th, 2021, 12:56 am

Last year, some of us over on the Discord had been working on a few related projects to find the smallest possible (by population) of several different types of patterns in every rule in various outer-totalistic rulespaces. I realize I've been a bit remiss in actually saying something about this on the forums, and some people on here have made discoveries that fit into the umbrellas of these projects (like FWKnightship's 144-cell p1 photon in B24/S13, for instance), so I thought it was time to go to the effort of writing up everything we've found so far. The three main things that we've worked on so far are finding minimal still lifes in range-1 Moore outer-totalistic rules, period-1 photons in range-1 Moore outer-totalistic rules, and minimal still lifes in range-1 hexagonal outer-totalistic rules*. Mateon1 on the Discord also made a bit of progress on enumerating a subset of small rule-minimal p2s in non-B0 Moore outer-totalistic rules using a custom SAT solver, as well as a few of the smallest minimal range-1 Moore INT still lives. Recently, there's been a hiatus in these projects, with not much progress beyond the occasional new photon being made — I originally wrote this post several months ago but never edited/posted it until now. I recognize that there's now a thread for minimal still lives in (range-1 Moore) INT rules (which we worked on a bit at the beginning in March or April or so but mostly gave up on because the rulespace was so large), which didn't exist when I wrote most of this post, but since the scope of these projects is larger than just still lives and deals with many different rulespaces I thought it would be better to make a separate thread. (Some side discoveries from these projects might end up going in the other thread if I can find where they were posted again.)

* [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: The notation for all of the spreadsheets is pretty similar. A definite numeric value in a cell in the spreadsheet indicates a still life or photon that is known to be or almost certainly (as in "isn't mathematically proven to be, but seems beyond reasonable doubt to be") minimal. A ? sign after a value indicates a "probably" minimal value, and a ≤ sign before a value indicates a value whose minimality is unknown but is the population of the smallest known example in that rule. On the negative side, a - or -- indicates a proof that no still lifes or p1 photons can exist in that rule; -? indicates a proof of nonexistence is suspected to be fairly trivial, -?? indicates that nonexistence is suspected but a proof is likely to be (either somewhat or highly) nontrivial, and ??? indicates that there's no reason to suspect still lifes or p1 photons don't exist in a rule but extensive searches have turned up empty. -* indicates there is a proof that's pending verification. An empty cell indicates an unknown value that hasn't been extensively explored. For the p1 photon spreadsheet I also added color-coding to indicate discoverers. Unfortunately, I haven't been keeping close tabs on the precise patterns that are minimal in each rule, so the separate sheets listing each minimal still life and photon are woefully incomplete (except for the hexagonal still lifes). I think most of the hard-to-find ones are floating around on the Discord somewhere, and most of the others should be within the range of quick searches with various programs to re-find.

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!
2 cells, B3456/S1H:

Code: Select all

x = 2, y = 1, rule = B3456/S1H
2o!
3 cells, B3456/S2H:

Code: Select all

x = 2, y = 2, rule = B3456/S2H
o$2o!
4 cells, B2456/S13H:

Code: Select all

x = 3, y = 3, rule = B2456/S13H
bo$2o$2bo!
6 cells, B2456/S124H:

Code: Select all

x = 4, y = 3, rule = B2456/S124H
bo$4o$2bo!
72 cells, B2356/S123H:

Code: Select all

x = 13, y = 13, rule = B2356/S123H
obobobo$b6o$2o5b2o$bob4obo$2ob2ob2ob2o$bobo4bobo$2ob2o3b2ob2o$2bobo4b
obo$2b2ob2ob2ob2o$4bob4obo$4b2o5b2o$6b6o$6bobobobo!
91 cells, B2356/S1345H:

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!
101 cells, B256/S145H (inner-totalistic):

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!
132 cells, B236/S1356H:

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!
181 cells, B2356/S134H:

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!
All but the 181-cell still life are strongly expected to be minimal; the 181-cell one was verified to be the smallest still life in the rule fitting inside a 31x31 rhombus, but larger areas haven't been checked. Proofs of nonexistence, however, are the harder part:
  • 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.
Apart from that, there are several other rule ranges that I strongly expect not to have still lifes:
  • 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.
Uniquely for these projects so far, I'm at least fairly confident that this is in fact the true rule-minimal–by–population set of hex-OT still lives — there are no rules where I have any real doubts about whether or not still lifes exist, or whether the ones I've found are minimal. That's not the case yet for Moore OT still lives or c/1 ships, which will be the subject of the next two posts on this thread, if I ever get around to making them — there are many tricky cases for which it's difficult to tell if still lives or ships exist, let alone prove it.

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.)
I know this is kind of a long post, and I'm sure not everything I wrote here is fully clear, so feel free to ask whatever questions might arise — and also feel free to contribute still lives, photons, and even projects in other rulespaces or for other types of objects if you want!
former username: A for Awesome
praosylen#5847 (Discord)

The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...

Post Reply