- A rule is fertile if there is a finite pattern that eventually escapes any fixed bounding box, such as a spaceship, a replicator, or an infinite growth pattern.
- A rule is mortal if there is a finite, nonempty pattern that dies immediately. Such a pattern is called a vanishing pattern. Examples in Life are displayed below.
Code: Select all
x = 77, y = 7, rule = B3/S23 50bo4bo$13bo5bo15bo7bobo6b2o6bo2bo6bo$13bo6bobo4b2o6bo7bobo5b4o5bo2bo 6bo2b2o$o2b2o2bo3b5o3b3o3b6o2b4o4b7o3b4o3b8o2b9o$8bo4bo4bobo6b2o6b4o4b obo6b2o6bo2bo6bo2b2o$13bo7bo14bo6bobo4bo4bo4bo2bo6bo$36bo!
- For B0 rules, the above two definitions can be extended to the equivalent alternating rule, as implemented in Golly. Example: The rule B03/S23 is equivalent to B1245678/S0145678|B56/S58. A number of fertility and mortality proofs can be derived in this manner.
- A pattern is a still life in a given rule (without B0) iff it vanishes in the rule with same birth conditions and inverted survival conditions (the vanishing dual). Example: the vanishing patterns in Life are precisely the still lives in B3/S0145678, and vice versa.
- With B1c, all patterns expand at c diagonal, which means that such rules are fertile and immortal, and contain no periodic finite patterns. Proof: Let (x,y) be the live cell that maximizes x+y, and also maximizes y among the live cells with the same value of x+y, in generation 0. Then the cell (x,y) is the only live neighbor of (x+1,y+1), which will be born in generation 1.
Code: Select all
#C [[ STOP 1 ]] x = 7, y = 6, rule = B1c/SHistory B$2B2.D$2BEA$2B3E$6B$7B!
- With B1e2a, all patterns expand at c orthogonal, with similar consequences as in (1). Proof: For the cell (x,y) described in (1), the cell (x,y+1) has neighborhood configuration B1e or B2a, so regardless of the state of (x+1,y), this cell will be born in generation 1.
Code: Select all
#C [[ STOP 1 ]] x = 7, y = 6, rule = B1e2a/SHistory B$2B.D$2BEA$2B3E$6B$7B!
- If a rule has B1c, B1e, or B2a, then it is always fertile. In particular, the domino expands at the speed of light in at least one direction.
Code: Select all
#C Change the rule to something with B1c, B1e, or B2a. x = 2, y = 1, rule = B2/S 2o!
- In order for a pattern to escape its initial bounding box, the rule must have at least one of B1c, B1e, B2a, B2c, or B3i. Proof: Let x be the maximum value of x among live cells in generation 0. Then a cell at (x+1,y) for arbitrary fixed y has neighborhood configuration B0, B1c, B1e, B2a, B2c, or B3i, depending on the states of its three neighbors with x-value x.
Code: Select all
#C [[ STOP 1 ]] x = 7, y = 4, rule = B12ac3i/SHistory 3.D$2B3E2B$7B$7B!
- In order for a pattern to escape its initial bounding diamond, the rule must have at least one of B1c, B1e, B2a, B2e, or B3a. Proof: Let x be the maximum value of x among live cells in generation 0. Then a cell at (x+1,y) for arbitrary fixed y has neighborhood configuration B0, B1c, B1e, B2a, B2c, or B3i, depending on the states of its three neighbors with x-value x.
Code: Select all
#C [[ STOP 1 ]] x = 6, y = 6, rule = B12ae3a/SHistory B$2B$2BED$2B2E$5B$6B!
- A rule with B1e or B2a is described as relativistic because patterns can travel up to c orthogonal or c/2 diagonal. For the non-relativistic rules failing (3) but satisfying (4) and (5), the speed limit is c/2 orthogonal or c/3 diagonal; the proof is presented in the glider.c source code. Some rules have a lower speed limit; for example, John Conway showed that in a B3 rule without S4 or S5, or more precisely rules with B3ai and none of B1e2ace/S4w5a, the diagonal speed limit is c/4d. A copy of this proof is included in the source code for Eppstein's lider database; I haven't worked out the extension to other combinations of B2c/B3i and B2e/B3a.
- If (x,y) is the live cell described in (1), then it has one of the neighborhood configurations S0, S1c, S1e, S2a, S2c, S2e, S2k, S3a, S3i, S3j, S3n, or S4a. Thus, any rule with all of these transitions is immortal, and no spaceships can exist since patterns cannot shrink. Certain birth conditions allow immortality on only a subset of these survival conditions, such as OT rules with B2/S0123, B3/S0123, or B23/S0. I haven't yet computed all the INT rulespaces with this behavior.
Code: Select all
#C [[ STOP 1 ]] x = 37, y = 36, rule = B/S01234History B9.B9.B9.B$2B8.2B8.2B8.2B$2BDA6.2BDA6.2BDA6.2BDA$2B3D5.2B2DC5.2BDCD5. 2BD2C$6B4.6B4.6B4.6B$7B3.7B3.7B3.7B5$B9.B9.B9.B$2B8.2B8.2B8.2B$2BDA6. 2BDA6.2BDA6.2BDA$2BC2D5.2BCDC5.2B2CD5.2B3C$6B4.6B4.6B4.6B$7B3.7B3.7B 3.7B5$B9.B9.B9.B$2B8.2B8.2B8.2B$2BCA6.2BCA6.2BCA6.2BCA$2B3D5.2B2DC5. 2BDCD5.2BD2C$6B4.6B4.6B4.6B$7B3.7B3.7B3.7B5$B9.B9.B9.B$2B8.2B8.2B8.2B $2BCA6.2BCA6.2BCA6.2BCA$2BC2D5.2BCDC5.2B2CD5.2B3C$6B4.6B4.6B4.6B$7B3. 7B3.7B3.7B!
- Dean Hickerson showed, by considering the envirionment around the live cell described in (1), that OT rules with B2/S01245, B345/S013, and 18 other rulespaces listed in Eppstein's paper are immortal, but have patterns whose bounding box can shrink. There are 297 rules not covered by the analysis in the paper, but I have not worked out the full list. Several of these rulespaces are known to contain spaceships, such as the following in B345/S013:
Code: Select all
x = 15, y = 29, rule = B345/S013 6b3o$5b2ob2o$4b3ob3o$6bobo$3bo2b3o2bo2$3bo3bo3bo$3b4ob4o$b5o3b5o$bo3bo 3bo3bo$o4bo3bo4bo$4b7o$2bo2bo3bo2bo$7bo$2b2o2bobo2b2o$o2bobo3bobo2bo$o 3bo5bo3bo$o13bo$3bo7bo$bobo7bobo$b4o5b4o$2b3o5b3o$bob2o5b2obo$o4bobobo 4bo$o3bo5bo3bo$2obo7bob2o$obo9bobo$2bo9bo$2b2o7b2o!
- Eppstein showed that there are no spaceships in any OT rule with S123456, B34/S12345, or B345/S1234, because connected patterns cannot shrink. The proofs are lsited in the glider.c source code.
- Eppstein showed that in rules with B3 and none of B1245/S012345, patterns cannot escape their bounding diamond. It remains an open question if spaceships are impossible in B3 rules with S345678 or without S012345.
- Eppstein showed that B3 rules with S234567 cannot have any spaceships, but the proof in glider.c is a bit vague. It would be nice for someone to work out or provide a more rigorous proof.
- If both parts of the alternating rule are immortal, then the B0 rule is obviously immortal. Similarly, if the alternating rule is such that patterns cannot shrink, then spaceships are impossible. For OT rules, this means rules that have S7, B8/S56, B5678/S6, B5678/S5, or B45678, and which lack B1, B23/S0, B2/S0123, B3/S0123, or S01234.
- If both parts of an alternating rule are such that patterns cannot escape their bounding box, then the same is true for the B0 rule. This includes rules with B12ac3i and none of S5i6ac7, and OT rules with B123 and none of S567.
- If both parts of an alternating rule are such that patterns cannot escape their bounding diamond, then the same is true for the B0 rule. This includes rules with B12ae3a and none of S5a6ae7.
- The two parts of the alternating rule can interact in nontrivial ways. For example, if a rule has S6a and none of B1ce2a, then at the cell (x,y) in generation 0 described in (1) (I really need a name for this special site), the cells (x,y+1) and (x+1,y+1) will be dead in generation 1, and (x+1,y+2) will be live in generation 2 — that is, any finite pattern will expand at (2,1)c/2 in all directions, and the rule is immortal with no stable patterns. I can prove the same for rules with B1e2a/S7e and without B1c.
Code: Select all
x = 2, y = 2, rule = B02-a345678/S6a 2o$2o!
Code: Select all
x = 1, y = 1, rule = B01e2345678/S7e o!
- In an OT rule without any of B345678/S34567, or more specifically an isotropic rule with none of B3i4ant5aeijnr6aceik7ce8/S3i4ant5aeijnr6aceik7ce, I showed here are infertile, and more specifically that patterns remain confined to their initial bounding box in even generations.
- Little is known about the speeds allowed in B0 rules, except that some B0 rules without B1c or S7c allow diagonal speeds up to 3c/4d; we know that (2,1)c/2 is impossible, but the proof has not yet been formalized. However, we do know that OT rules with S5 and none of B1/S67 have photons.
- If one part of an alternating rule is confined to its bounding box, then the maximum orthogonal speed is at most c/2o; this includes B0 rules with B1ce2ac3i. Note that if the other part lacks any of B1ce2a, then it is not necessarily true that the orthogonal speed limit is c/4o; for example:
Proof: Let R1|R2 be an alternating rule such that patterns in R1 are confined to their bounding box. If x≤c for all live cells (x,y) in generation 0, then no cell with x-value x+1 can be live in generation 1, but there may be such a live cell in generation 2 if R2 allows patterns to escape their initial bounding box.
Code: Select all
x = 7, y = 5, rule = B012-kn3aciy5n6c/S02ac4n5q6ce 2bobo$3ob3o$2obob2o2$3bo!
- If one part of an alternating rule is confined to its bounding diamond, then the maximum orthogonal speed is at most c/2d; this includes B0 rules with B1ce2ae3a. If the other part lacks B1c (e.g. a B0 rule without S7c), then this speed limit can be lowered to c/4d. Proof: Let R1|R2 be an alternating rule such that patterns in R1 are confined to their bounding diamond. If x+y≤c for all live cells (x,y) in generation 0, then no cell with larger x+y can be live in generation 1, but cells with x+y=c+1 may be live in generation 2 if R2 permits patterns to escape their bounding diamond. A cell (x,y) with x+y=c+2 will be live in generation 2 iff (x-1,y-1) is live in generation 1 and R2 has B1c as a transition, and hence if R2 lacks B1c, then it will take at least 4 generations for (x,y) to become live.
- I conjecture that 3c/4o or c/2d is the maximum in rules with B1/S5 and none of B2/S67, but haven't proved this for certain; it should be pretty easy. I also conjecture an upper speed limit of c/4o or c/6d in OT rules with B123/S5 and no S67.