googleplex wrote:Certain transitions change rule dynamics, so I thought I would figure out how transitions (eg. b1a, s4k) effect dynamics of rules (eg. if it's explosive or not)
In a certain literal sense, of course,
all the dynamics of CA rules arise from their transitions. Sometimes they just arise more directly, and from a smaller set of transitions, than in others.
For example, (non-strobing) rules with B1c trivially explode, and cannot support still lifes, spaceships or oscillators, since any finite pattern will expand diagonally at lightspeed. Rules with B1e or B2a also tend to explode, since either a single cell or a pair of adjacent cells will expand orthogonally at lightspeed, but these rules
can support non-exploding patterns. But if you put both B1e and B2a in the same rule, explosion is again guaranteed.
Personally, I've found rules on the 4-cell von Neumann neighborhood to be a nice starting point for this kind of analysis, both because there are fewer possible transitions to consider (only 10 for totalistic rules, or 12 for general isotropic rules) and because the lack of triangles in the cell adjacency graph makes things simpler (since two adjacent cells share no neighbors besides each other). Indeed, all the isotropic rules on the 4-cell neighborhood can be classified as follows:
- For rules without B0, empty space is stable:
- In rules with B1 (and without B0), all patterns explode at lightspeed. In rules without B1 (or B0), patterns cannot expand outside their initial bounding box (but may still have interesting dynamics within that box, e.g. as in the rule below).
Code: Select all
x = 80, y = 80, rule = B24/S23V
80o$3o76bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo
$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o
78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo
$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o
78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo
$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o
78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$o78bo$80o!
- For rules with B0 and S4, empty space will flip once and then stabilize. These rules all have equivalent non-B0 duals obtained by swapping and bitwise complementing the birth and survival transitions, which effectively amounts to just swapping the labels on the dead and live cell states.
(Indeed, all two-state CA rules have such duals, although a few rules are fully state-symmetric and thus self-dual. On the von Neumann neighborhood, these state-symmetric rules are themselves subject to a different kind of duality, where swapping but not complementing the birth/survival transitions yields a different rule with equivalent dynamics if every second cell on the lattice is swapped. This second kind of duality doesn't work on the 8-cell Moore neighborhood, though, since it requires the adjacency graph to be bipartite.)
- Rules with B0 and without S4 are strobing. For the 4-cell neighborhood, these rules are the only ones that can have spaceships, although not all of them do.
- Strobing rules with S3 and no B1 are explosive, just like non-strobing rules with B1.
- Patterns in strobing rules with B1 and no S3 are confined to their bounding boxes, just like in non-strobing rules without B1.
- Again, strobing rules with B1 and S3 are equivalent to their duals with neither.
- Out of the remaining rules (with B0 and no B1/S34), those with B2e are also explosive, as the corners of any pattern with expand diagonally at c/2 (which is the maximum diagonal movement speed on the 4-cell neighborhood).
- That leaves a total of 32 distinct totalistic (or 128 isotropic) rules, plus their duals, that are in principle capable of supporting spaceships on the 4-cell neighborhood. Several of those indeed do:
Code: Select all
x = 2, y = 6, rule = B02/SV
bo$2o3$2o$bo!
Code: Select all
x = 4, y = 10, rule = B02/S1V
2bo2$2b2o$o2bo$b3o$b3o$o2bo$2b2o2$2bo!
Code: Select all
x = 9, y = 5, rule = B024/S1V
3o2$4b5o2$2bo!
Code: Select all
x = 9, y = 10, rule = B03/S1V
6bo$5b3o$6bo2$7bo$7b2o$6bo$5bo$o5bo$4bo!
Code: Select all
x = 14, y = 5, rule = B04/S1V
ob2o5b3o$7b2o3bo$4b4o2bo2bo$7b2o3bo$9b3o!
Macbi wrote:Does anyone know any rules of thumb to determine if a strobing rule is explosive or not?
Well, obviously, any strobing rule with S7c and without B1c must explode diagonally at lightspeed, just like non-strobing B1c rules do. Similarly, S6a7e without B1e2a makes the corners of any pattern expand orthogonally at lightspeed, just like having B1e2a does for non-strobing rules.
Perhaps more interestingly, these can be mixed: a strobing rule with S7c and no B1e2a, or S6a7e and no B1c, will also explode, with the corners spreading out at (2,1)c/2 in alternating diagonal and orthogonal steps:
Code: Select all
x = 1, y = 1, rule = B01e2345678/S6a7e
o!
Conversely, just like non-strobing rules need at least one of the transitions in B1ce2ac3i for patterns to escape their bounding box, a strobing rule will need to
lack at least one transition from both B1ce2ac3i, or to have at least one of S5i6ac7ce, for patterns not to stay confined in boxes. And similarly, just like patterns in non-strobing rules need at least one of B1ce2ae3a to escape their bounding diamond, in strobing rules they need to lack at least one of B1ce2ae3a or to have at least one of S5a6ae7ce.
In general, the most obvious difference between strobing and non-strobing rules, of course, is that adding more birth transitions tends to stabilize strobing rules, whereas it tends to destabilize non-strobing rule. Also, since the "active" cell state alternates between generations, there's no such clear distinction between (non-)birth and survival transitions: adding, say, B3e to a randomly chosen strobing rule has, on average, the same effect as removing S5e. (Or, more precisely: adding B3e to a strobing rule has
exactly the same effect as removing S5e from its dual rule.)