Speed limits and theorems about the existence of periodic objects

[LaundryPizza03]

I had an idea to compile theorems and proofs regarding OCA with regards to the existence of spaceships, oscillators, and still lifes and constraints on speed of propagation through vacuum. Some background since you won't find it on LifeWiki; see also this paper by David Eppstein:

• 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.

Here are some key results for OT and INT rules without B0. In the figures below, try changing a yellow cell to a white or red cell to understand why the specific neighborhood configurations are mentioned.

1. 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!
   

2. 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!
   

3. 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!
   

4. 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!
   

5. 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!
   

6. 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.
7. 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!
   

8. 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!
   

9. 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.
10. 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.
11. 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.

For rules with B0 and without S8, I have the following:

1. 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.
2. 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.
3. 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.
4. 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!
   

5. 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.
6. 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.
7. 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:

   Code: Select all

   x = 7, y = 5, rule = B012-kn3aciy5n6c/S02ac4n5q6ce
   2bobo$3ob3o$2obob2o2$3bo!
   

   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.
8. 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.
9. 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.

It would be interesting to see results about MAP rules, or on other types of neighborhoods like LtL.

[wwei47]

we know that (2,1)c/2 is impossible, but the proof has not yet been formalized.

Higher-period (2,1)c/2 may be possible, but true-period is off the table.

(4,1)c/4 and (6,2)c/6 are definitely possible. Proof: Run these patterns.

Code: Select all

x = 13, y = 2, rule = B02ace3ce4anrw5ej6ae7e/S1c2n3ae4cei5enry6aci
2o2bobo3b3o$2o4bob2ob2o!

Code: Select all

x = 5, y = 4, rule = B01e2ce3-aeqr4ejknrz5enqry6-ei7e8/S1e2ack3ejkqy4-ackq5-any6-ai7e
2o2bo$obobo$2ob2o$5o!

[LaundryPizza03]

I think I formalized the first case out of 10 to prove that true-period (2,1)c/2 is impossible. Maybe one of these 10 cases will reveal the existence of a higher period multiple thereof.

Consider the top row of a pattern, which is assumed to be finite, in an alternating rule R1|R2 where the first part has B1c and the latter does not. At the right end of this row, I deduced 10 possible ways that the top right corner (x,y) can make a (2,1)c/2 frontend, if the B1c-containing part comes in even generations:

1. (x,y) is live in generation 0, and (x-1,y) and (x-2,y) are dead; (x-2,y+1), (x-1,y+1), and (x+1,y+1) are live in generation 1, and (x,y+1) is dead.
2. (x,y) is live in generation 0, and (x-1,y) and (x-2,y) are dead; (x-2,y+1), (x-1,y+1), (x,y+1), and (x+1,y+1) are live in generation 1.
3. (x,y) and (x-2,y) are live in generation 0, and (x-1,y) is dead; (x-1,y+1) and (x+1,y+1) are live in generation 1, and (x-2,y+1) and (x,y+1) are dead.
4. (x,y) and (x-2,y) are live in generation 0, and (x-1,y) is dead; (x-2,y+1), (x-1,y+1), and (x+1,y+1) are live in generation 1, and (x,y+1) is dead.
5. (x,y) and (x-2,y) are live in generation 0, and (x-1,y) is dead; (x-1,y+1), (x,y+1), and (x+1,y+1) are live in generation 1, and (x-2,y+1) is dead.
6. (x,y), (x-1,y), and (x-2,y) are live in generation 0; (x-1,y+1) and (x+1,y+1) are live in generation 1, and (x-2,y+1) and (x,y+1) are dead.
7. (x,y), (x-1,y), and (x-2,y) are live in generation 0; (x-2,y+1), (x-1,y+1), and (x+1,y+1) are live in generation 1, and (x,y+1) is dead.
8. (x,y), (x-1,y), and (x-2,y) are live in generation 0; (x-2,y+1), (x,y+1), and (x+1,y+1) are live in generation 1, and (x-1,y+1) is dead.
9. (x,y), (x-1,y), and (x-2,y) are live in generation 0; (x-1,y+1), (x,y+1), and (x+1,y+1) are live in generation 1, and (x-2,y+1) is dead.
10. (x,y), (x-1,y), and (x-2,y) are live in generation 0; (x-2,y+1), (x-1,y+1), (x,y+1), and (x+1,y+1) are live in generation 1.

Code: Select all

#C Fig. 1: The 10 possible cases for the leading corner of a (2,1)c/2 spaceship
x = 106, y = 60, rule = B/S012345678Super
10.3P6.P3.P7.P$9.P3.P5.2P2.P6.2P$9.P2.2P5.P.P.P7.P$9.P.P.P5.P2.2P7.P$
9.2P2.P5.P3.P7.P$9.P3.P5.P3.P7.P$10.3P6.P3.P6.3P2$7.99P$16.P9.P$.3P$P
3.P11.P5.M3.P5.M$P11.M6.3EA6.3EA$P8.2EA4.P2.3B4.P2.3B$P2.2P4.5B5.5B5.
5B$P3.P4.5B2.P2.5B2.P2.5B$.3P$16.P9.P$7.P.P.P.P.P.P.P.P.P.P.P.P.P.P.P
.P.P.P.P.P.P.P.P.P.P.P.P.P.P.P.P.P.P.P.P.P.P.P.P.P.P.P.P.P.P.P.P.P.P.
P$16.P9.P11.7R13.7R$.3P33.R7.R11.R7.R$P3.P11.P3.2FM3.P3.M.M4.R4.M2.R
4.M.M4.R4.M2.R$P9.M.M6.EAEA6.DADA4.R.2ADA2.R3.D3A4.R.4A2.R$.3P5.2DA4.
P2.2BI4.P2.2BI5.R.2BI3.R3.2BI5.R.2BI3.R$4.P4.5B5.5B5.5B3.R.5B.R3.5B3.
R.5B.R$P3.P4.5B2.P2.5B2.P2.5B3.R.5B.R3.5B3.R.5B.R$.3P33.R7.R11.R7.R$
16.P9.P11.7R13.7R2$16.P9.P21.7R3.7R23.7R$47.R7.R.R7.R21.R7.R$16.P3.MF
M3.P3.2FM7.2FM4.R2.M.M2.R.R4.M2.R4.F2M8.2M4.R2.M.M2.R4.2TM$12.M6.3EA
6.3DA6.A2DA4.R.DADA2.R.R.2ADA2.R3.2D2A6.AD2A4.R.D3A2.R3.4A$9.ADA4.P2.
IBI4.P2.IBI7.IBI5.R.IBI3.R.R.IBI3.R3.IBI7.IBI5.R.IBI3.R3.IBI$9.5B5.5B
5.5B5.5B3.R.5B.R.R.5B.R3.5B5.5B3.R.5B.R3.5B$9.5B2.P2.5B2.P2.5B5.5B3.R
.5B.R.R.5B.R3.5B5.5B3.R.5B.R3.5B$47.R7.R.R7.R21.R7.R$16.P9.P21.7R3.7R
23.7R2$16.P9.P2$16.P3.F2M3.P3.2FM7.2FM47.M.M7.2TM$10.2TM6.3EA6.3DA6.A
2DA46.D3A6.4A$9.D2A4.P2.B2I4.P2.B2I7.B2I47.B2I7.B2I$9.5B5.5B5.5B5.5B
45.5B5.5B$9.5B2.P2.5B2.P2.5B5.5B45.5B5.5B2$16.P9.P2$16.P9.P21.7R3.7R
13.7R3.7R3.7R$47.R7.R.R7.R11.R7.R.R7.R.R7.R$16.P3.3M3.P3.2FM7.2FM4.R
2.M.M2.R.R4.M2.R4.F2M4.R3.2M2.R.R2.M.M2.R.R2.2TM2.R$12.M6.3EA6.3DA6.A
2DA4.R.DADA2.R.R.2ADA2.R3.2D2A4.R.AD2A2.R.R.D3A2.R.R.4A2.R$9.3A4.P2.
3I4.P2.3I7.3I5.R.3I3.R.R.3I3.R3.3I5.R.3I3.R.R.3I3.R.R.3I3.R$9.5B5.5B
5.5B5.5B3.R.5B.R.R.5B.R3.5B3.R.5B.R.R.5B.R.R.5B.R$9.5B2.P2.5B2.P2.5B
5.5B3.R.5B.R.R.5B.R3.5B3.R.5B.R.R.5B.R.R.5B.R$47.R7.R.R7.R11.R7.R.R7.
R.R7.R$16.P9.P21.7R3.7R13.7R3.7R3.7R2$16.P9.P!

For case #1, R1 must have no B1e, and R2 must have B1e and no B2a or B2c. The cell (x-2,y+1) has at most one live neighbor in generation 0, so to be live in generation 1, (x-3,y) must be live in generation 0. So in order for (x-2,y+2) to be live in generation 2, (x-3,y+1) must be live in generation 1 and R2 must have the transition B3i. Since this is impossible if (x-4,y) is dead in generation 0, that cell must be live and R1 must have B2a. Now consider the top left corner (x',y); we need (x'+1,y+2) to be the top left corner in generation 2. At this point, the cell (x'-1,y+1) must be live in generation 1. If (x'+1,y) is live in generation 0, then (x',y+1) will be dead in generation 1, and (x'-1,y+2) will be live in generation 2. If (x'+1,y) is live in generation 0 and (x'+2,y) is dead, then (x',y+1) and (x'+1,y+1) must be live in generation 1, and (x',y+2) will be live in generation 2. However, if (x'2,y) is also live in generation 0 and R1 does not have B3i, then (x',y+1) will still be on in generation 1, but (x'+1,y+1) will be off. Unfortunately, this means that regardless of the state of (x'+2,y+1), (x'+1,y+2) will be off in generation 2, which is not what we wanted. In conclusion, the top left corner cannot advance northeast at (2,1)c/2.

Code: Select all

#C Fig. 2: Analysis for case #1
x = 31, y = 48, rule = B/S012345678Super
3.3P6.G10.4G$2.P3.P5.G10.G3.G$2.P9.G10.G3.G$2.P9.G10.4G$2.P2.2P5.G10.
G.G$2.P3.P5.G10.G2.G$3.3P6.5G6.G3.G2$10P21G$9.P9.P2$3.2FM3.P3.MFT3.P
4.3FM$2.2ADA7.ADAE5.ED2ADA$2.2BI4.P4.I2B2.P2.BI2BI$2.5B5.5B5.7B$2.5B
2.P2.5B2.P2.7B2$9.P9.P$P.P.P.P.P$9.P9.P2$9.P3.MFT3.P4.M2FM$13.AD2E5.E
3ADA$9.P4.IBI2.P2.2I2BI$12.5B5.7B$9.P2.5B2.P2.7B2$9.P9.P2$9.P9.P2$9.P
3.FM4.P$13.3AE$9.P4.2IB2.P$12.5B$9.P2.5B2.P2$9.P9.P2$9.P9.P2$9.P3.3F
3.P$13.2ADE$9.P4.3I2.P$12.5B$9.P2.5B2.P2$9.P9.P!

If this partial proof is sound, try another case.

[LaundryPizza03]

Impossiblity of (2,1)c/2: For case #2, R1 must have B1e, and R2 must have B2a and no B3i. The cell (x-2,y+1) has at most one live neighbor in generation 0, so to be live in generation 1, (x-3,y) must be live in generation 0. Thus, we need (x-2,y+2) to be live in generation 2. If the cell (x-4,y+1) is dead in generation 0, then (x-2,y+2) will surely have neighborhood configuration B3i, and must be dead in generation 2, which is not what we wanted. If (x-4,y) is live in generation 0, then (x-3,y+1) will be live in generation 1 iff R1 has B2a. If this is true, then (x-2,y+2) will be dead in generation 2, but it will be live if R1 does not have B2a. In the latter case, the cell (x-3,y+2) will be live in generation 2 if (x-4,y+1) is live in generation 1 and R2 has B2c; in order for this to be true, (x-5,y) must be live in generation 0 so that (x-4,y+1) has neighborhood B3i. Then the cell (x-4,y+2) will have either neighborhood B1e or B2a in generation 1, depending on the state of (x-5,y+1). But if R2 has B1e and 2a, then since R1 has B1c the pattern will expand at (2,1)c/2 in all directions.

Thus, we will focus from here on on the case where R1 has B1ce3i and no B2a, and R2 has B2ac and no B1e or B3i. At the top-left corner (x',y), the cell (x-1,y+1) must be born in generation 0; in order for the cell (x-1,y+2) to be dead in generation 2, (x,y+1) must be dead, which can happen only if (x+1,y) is dead in generation 0. Then if (x+1,y+1) is live in generation 1, the cell (x,y+2) will be born in generation 2, which which is not what we wanted since (x-1,y) was dead in generation 0. Otherwise, the cell (x+1,y+2) has at most neighborhood configuration B0 or B1c in generation 1, and thus must be dead in generation 2, but we wanted it to be live in generation 2.

Code: Select all

#C Fig. 3: Analysis for case #2
x = 61, y = 66, rule = B/S012345678Super
3.3P8.4P25.3P8.P$2.P3.P7.P3.P23.P3.P7.P$2.P11.P3.P23.P11.P$2.P11.4P
24.P11.P$2.P2.2P7.P.P25.P2.2P7.P$2.P3.P7.P2.P24.P3.P7.P$3.3P8.P3.P24.
3P8.5P2$23P15.23P$9.P41.P2$5.M3.P5.T3FM21.4M2FM3.P3.M3T$2.4A8.E5A20.D
2AD4A7.2A2E$2.2BI4.P4.BI2BI21.4I2BI4.P4.IBJ$2.5B7.7B19.9B5.5B$2.5B2.P
4.7B19.9B2.P2.5B2$9.P41.P$P.P.P.P.P29.P.P.P.P.P.P.P$9.P41.P2$9.P6.3FM
31.P3.FMT$14.E5A35.ADAE$9.P4.2I2BI32.P4.3I$14.7B33.5B$9.P4.7B30.P2.5B
2$9.P41.P2$9.P41.P2$9.P6.M2FM31.P3.F$14.ED4A35.A2DE$9.P4.2I2BI32.P4.
2IB$14.7B33.5B$9.P4.7B30.P2.5B2$9.P41.P2$9.P2$9.P5.FM2FM$14.2D4A$9.P
4.2I2BI$14.7B$9.P4.7B2$9.P2$9.P2$9.P4.3M2FM$13.DAD4A$9.P3.3I2BI$13.8B
$9.P3.8B2$9.P2$9.P2$9.P3.4M2FM$12.D2AD4A$9.P2.4I2BI$12.9B$9.P2.9B!

I can also prove that with B1e and no B2a, B2c, or B3i, only photons are possible. Proof: Let x be the maximum x-value of any live cell in a pattern in generation 0. Assume for fixed arbitrary y that (x+1,y) is live in generation 0. This can happen only if the cell (x,y) is live, and (x,y+1) and (x,y-1) are dead, in generation 0. Regardless of the above, (x+1,y+1) and (x+1,y-1) will be dead in generation 1 since these cells have neighborhood configuration B1c or B2c in generation 0, so we have B1e neigborhood around (x+2,y), and this repeats ad infinitum at the speed of light.

Code: Select all

#C A graphical proof of the above statement
x = 5, y = 15, rule = B/S012345678Super
2BE$2BDF$2BAM$2BDF$2BE6$2BJE$3BDF$2BIAM$3BDF$2BJE!

[LaundryPizza03]

Here's a proof from rachel at Discord that there are no 3-cell spaceships in B2a that travel at a speed (X,Y)/P with X+Y = P and X,Y ≠ 0.

so we need B2a for light speed, and we need to push the bounding diagonal every generation, including the first. that already implies that the first generation has two cells that are moore neighbors. if they share an edge, then to prevent two B2a-induced expansions at (1,0)c/1 (in opposite directions), we need the third cell to be in one of two positions, making the possible patterns 3o and ob2o, but both of these are symmetric along an orthogonal axis, which means the speed also has to be symmetric along that axis, i.e. the speed has to be orthogonal itself, which is the explicitly excluded case.
so we need the first generation to have two cells that share a vertex, and no two cells that share an edge. then to push the bounding diagonal, we need B2e. excluding the pattern o$bo$2bo due to its high symmetry (forcing it to not be a spaceship), there's no way to push the bounding diagonal in the next generation without the survival of one of the two cells causing the B2e. then excluding o$bo$o due to its orthogonal symmetry (which would force the speed to be orthogonal again), the only way to ensure that is S1c, meaning they both survive. but since they both survive and the cell on the new bounding diagonal adjacent to both of them is born, that causes potential B2a-induced expansions at (1,0)c/1 in two directions, and the third cell in the starting configuration can't stop both of those.

This actually settles the optimality of 68 5s ships:

Code: Select all

4, B2ac/S1, 1, 1, 2, 2bo2$b2o$o!
4, B2-ei3aq4ik5ceq/S02aei3acjn4aijny5ejkn6ein7e, 2, 2, 4, o$b2o$bo!
4, B2ac3a/S02-ik3a, 3, 3, 6, o$b2o$bo!
4, B2acn3y4e/S12-ei3c4ey, 4, 4, 8, 2bo2$b2o$o!
4, B2acn3cen4qt5aik6cek7e/S12a3-knqr4ntwz5knr6c7e, 5, 5, 10, 2bo2$b2o$o!
4, B2acn3ey5j/S12-ei3c4nr, 6, 6, 12, 2bo2$b2o$o!
4, B2ack3en4ckntyz5cr6ek8/S1, 7, 7, 14, 2bo2$b2o$o!
4, B2acn3eky6e/S12-ei3c, 8, 8, 16, 2bo2$b2o$o!
4, B2ac3ey4y/S12ack3y4ik5c, 9, 9, 18, 2bo2$b2o$o!
4, B2acn3ey5j/S12-ei3c5a, 10, 10, 20, 2bo2$b2o$o!
4, B2ac3ky4ey/S12-ei4ky, 11, 11, 22, 2bo2$b2o$o!
4, B2-ik3ce4qrw5a7c8/S1c2c3ciknq4aeiyz5cekr6ak7c, 12, 12, 24, 3bo2$3bo$obo!
4, B2ac3cy4ey/S12ack3c4ky, 13, 13, 26, 2bo2$b2o$o!
4, B2ac3kqry4ejn5k6a/S1e2n3aikry4aqry5nr6ace7c, 14, 14, 28, 2bo$2bo$obo!
4, B2aci3cekny4ei5ackr6ck7/S012ac3cnr4ikny5jr, 15, 15, 30, ob2o$bo!
4, B2-ek3c4ejqr5acijk6ckn7c8/S01e3acn4ijtwz5-ceiq6ekn7e, 16, 16, 32, o2$2b2o$bo!
4, B2acn3cey4q5jr/S12-ei3ce4aty, 17, 17, 34, 3bo$2bo$obo!
4, B2ac3cr4jnrty5-jnr6eik/S1e2n3cjk4-crwy5ceiry6ik7, 18, 18, 36, o2$3o!
4, B2acn3ky4eintwyz5ajry6i7e/S01e3ciqy4eyz5aejnq6k7e, 19, 19, 38, o2$3o!
4, B2-ek3y4jq5-ceny6k/S01e2i3acq4ajkqz5cijny6e, 20, 20, 40, o$3bo$2bo$2bo!
4, B2acn3c4iqw5aejy6ac7e/S01e2n3ackr4aeirty5ij, 21, 21, 42, 3bo$o$2bo$2bo!
4, B2acn3kn4ceiqtwz5ckny6e7/S13an4acikqz5-cjkq6-ae, 22, 22, 44, 2bo2$b2o$o!
4, B2-ek3c4qwy5-ceik6a7e/S01e3ackn4iknw5eir6a7e8, 23, 23, 46, o2$2b2o$bo!
4, B2acn3cey4cq5cjr/S12-ei3ce4aqty5i6cn, 25, 25, 50, 3bo$2bo$obo!
4, B2acn4ciqy5aejy/S01e2n3ajkr4ajkry5cin6i, 26, 26, 52, 2bo4$2b2o$o!
4, B2acn3cey4eq5cjry6a/S12-ei3cqy4iknwy5y6a, 27, 27, 54, 2bo2$b2o$o!
4, B2acn3ey4iqy5ck6ak/S12-n4ikt5ceij6e7e, 29, 29, 58, 3bo$2bo$obo!
4, B2acn3cey4ein5cjknr7c/S12-ei3cy4iknqtyz5aj7e, 31, 31, 62, 2bo2$b2o$o!
4, B2ac3ey4enqty5cjkq/S12-e3cjr4ciknrty5cjknq7e, 33, 33, 66, 2bo2$b2o$o!
4, B2ac3ey4iy5cekn7c/S12-ei3c4ik5ciy6c7e, 35, 35, 70, 3bo$2bo$obo!
4, B2acn4cikqtwy5jy6c/S01e2n3acjkr4ackr5cinry6i, 36, 36, 72, 2bo4$2b2o$o!
4, B2acn3eqy4ceiny/S12-ei3cr4ikwy5cik6ce7e, 37, 37, 74, 3bo$2bo$obo!
4, B2acn3cey4enqt5cjkr6n/S12-ei3cy4ikny5aen6n, 39, 39, 78, 2bo2$b2o$o!
4, B2acn3cey4ent5cjkr/S12-ei3cy4iknqwy5aejn6n, 47, 47, 94, 3bo$2bo$obo!
4, B2acn3cey4enq5cjkr6n/S12-ei3cy4iknty5aen, 71, 71, 142, 3bo$2bo$obo!
4, B2ac3-aeij4-ikt5-acin6-a78/S1e2ekn3eknr4aceyz5-aery678, 3, 1, 4, 2bo2$3o!
4, B2ace3cr4ceinwyz56-k7c8/S1e2cen3ac4cejktwy5-qr678, 3, 2, 5, obo$2bo$2bo!
4, B2aci3aq4acikwyz5-cqry6n8/S1e2n3aeijr4acjkrwz5-cjnq6ikn7, 4, 2, 6, 2bo2$2bo$obo!
4, B2aci3acn4ajnwz5-qy6akn78/S01e2ai3ajq4-nrt5ciq6-e78, 5, 2, 7, 2bo2$obo$2bo!
4, B2-ek3an4cijnqy5-inry6-c7e/S01e2ac3ak4ejkrwz5aejnr6-k7c8, 4, 3, 7, 2bo2$2bo$obo!
4, B2-kn3nry4aenrt5eqy6ci7c/S01e2cin3jkr4t5-aiqy6ae7e8, 6, 2, 8, bo$bo$bo$o!
4, B2aci3-eijn4enqz5ejk6ekn8/S01e2ce3y4ejrtwyz5ajkq6-i7, 5, 3, 8, obo$2bo$2bo!
4, B2ac3j4aceiqrt5-cjkn6ai7/S12ak3eijry4eikwy5cknr6ai7, 7, 2, 9, bo$o$o$o!
4, B2ace3cnq4ajknqyz5ijry6ain7c8/S2ak3eiqy4eqrtw5aknr6ckn, 6, 3, 9, bo$o$bo$bo!
4, B2ac3eq4ntyz5aqr6-en7e8/S12ak3-cnqr4enqrwy5-eiky6-ek, 5, 4, 9, 2bo2$b2o$o!
4, B2-ik3jr4cknty5acjqr6cen7/S1e2n3ajky4akqt5enqy67e8, 7, 3, 10, obo$2bo$2bo!
4, B2ac3ery4inty5jr6a/S1e2e3aq4ejqty5jy, 6, 4, 10, obo$2bo$2bo!
4, B2aci3acry4akqrt5ciky6aei7e/S2-ci3ejkr4ejn5cir6ac7e8, 8, 3, 11, bo$o$bo$bo!
4, B2ac3kn4aeijnt5ackq6ek7e8/S1e2cek3ny4acekqry5in6k7e, 7, 4, 11, o2$3o!
4, B2aci3aky4aijry5aikq6ik8/S2aek3ckr4ekry5-jry6ci7e8, 6, 5, 11, bo$ob2o!
4, B2ac3anq4-cek5-jkn6-ac8/S01e2i3aijky4eijrz5jkry6ain78, 9, 3, 12, 2bo2$2bo$obo!
4, B2-ik3ey4-eiqr5cjry6-ck7e8/S1e2cin3cijkr4cqry5aqr6ck7e8, 8, 4, 12, 2bo2$2bo$obo!
4, B2acn3an4aijqtwz5cekr6ae/S01e2ei3aiy4aceirz5-ery6ckn8, 7, 5, 12, 2bo2$2bo$obo!
4, B2ac3ajny4acitwz5eiy6-cn7e/S01e2i3-ainq4ejkqtz5ejkq6eik7c, 9, 4, 13, 2bo$2bo$2bo$o!
4, B2ac3anr4acy5cejky6akn7c/S1e2ik3-ejy4aeqrw5-ei6ek7c8, 8, 5, 13, 3bo2$ob2o!
4, B2ac3aenqr4aenw5ekry6cek/S1e2ikn3-ckn4acert5acq6ace8, 7, 6, 13, 2bo2$2bo$obo!
4, B2acn3ar4aik5aqr6ekn8/S01e2a3acjr4aeiy5acr6k, 11, 3, 14, 3bo2$2b2o2$o!
4, B2ac3cnqr4ajt5aen6ik7/S1e2k3jkny4ijryz5ek6aik7e, 9, 5, 14, 3bo2$ob2o!
4, B2ac3aknr4aqtyz5qry6-in7c/S1e2ein3-cqy4acerw5acinq6n78, 8, 6, 14, 2bo2$2bo$obo!
4, B2ac3ery4knrwz5-aejy6cik7e/S1e2k3k4aijktwy5er6ek, 8, 7, 15, obo$2bo$2bo!
4, B2ace3kn4aiqry5aeiy6aik7c/S1e2-ak3nq4ijnty5inr6ei, 12, 4, 16, bo$bo$bo$o!
4, B2-ik4ajkqtyz5-aekq6ae/S2-ce3ejy4acjktw5aikn6k, 11, 5, 16, bo$o$bo$bo!
4, B2aci3qry4jknwyz5cjnr6aen7e/S1e2ce3aek4akrty5-r6c7c, 10, 6, 16, obo$2bo$2bo!
4, B2-ek3er4nrty5cenr6-n7/S1e2ek3acekn4aiktwz5knqr7c8, 9, 7, 16, o2$3o!
4, B2acn3r4inty5-acky6an/S1e2e3aq4jkqrty5acjy6ik, 12, 8, 20, obo$2bo$2bo!
4, B2acn3ry4iny5ijqr6-cn/S1e2e3aq4jqtyz5-enqr6-ci7c, 15, 10, 25, obo$2bo$2bo!
4, B2acn3r4cinwyz5-k6aek/S1e2e3aq4jkqrty5-cenq6-ac7e, 18, 12, 30, obo$2bo$2bo!
4, B2acn4iqw5jy6ik7e/S01e2n3-cinq4acqrty5acinr6i, 17, 15, 32, 5bo2$o3bo$4bo!

They also proved that there are no still lifes other than the block in B3/S3 (actually, B3aijnq/S3):

the trick is to ignore all blocks in the hypothetical SL. then we just look at an edge of the bounding diamond of the rest (for ease of writing, let's specify that it's the top right edge).
first, notice that we can't have o$2o on that edge, since that would make a B3a outside of the bounding diamond of the blockless part of the SL, so we could only prevent that with blocks, which would force an infinite amount of blocks via B3nq.
then notice that if there was a 2o$o on the edge, then (since we're not making a block) the top left cell could only be stabilized through S3k, and if the top left cell of that S3k didn't have a live cell above it, that would cause a B3j which once again can't be stopped by finitely many blocks. so the top left cell of the S3k must have a live cell c1 above it. now to stabilize c1 without overpopulating the cell below c1, we need a live cell c2 to the top left of c1, and then to prevent o$2o on the edge, we need a live cell to the bottom left of c1. but then to stabilize c2 without overpopulating c1, we either make another 2o$o further up the edge of the bounding diamond, or we have a live cell c3 to the top left of c2, and in the latter case, again to prevent o$2o, we need a live cell to the bottom left of c2. to stabilize c3 without overpopulating c2, we then need to either make another 2o$o further up the edge of the bounding diamond, or we have a live cell c4 to the top left of c3, and in the latter case, again to prevent o$2o, we need a live cell to the bottom left of c3. this continues on, and since our still life is finite, we're eventually forced to choose the first option and make another 2o$o further up the edge of the bounding diamond. so a 2o$o forces another one further up, but that will force yet another, etc. and our SL will be infinite. so we can't have a 2o$o on the edge at all.
now, since there can't be an o$2o or a 2o$o on the edge, this means that if any live cell on the edge had a live VN neighbor, then it could only have two neighbors, and that's a problem because we only have S3. but no VN neighbors leaves only S3c as a possibility, and each S3c on the edge forces another S3c further up on the edge, so we once again get an infinite SL.
so no matter what, the blockless part of the SL would have to be infinite or empty. and if it's empty, then... well the SL itself would just be a bunch of blocks, it doesn't count as a separate SL.

edit: i think i didn't explain well enough why the top left cell of the 2o$o must be stabilized with an S3k (and not with e.g. an S3j). it's because the 2o$o is forced to be part of a 2o$obo$bo, so the bottom left cell of the 2o$o already has 3 neighbors. this only works because we're on the edge of the bounding diamond, otherwise the 2o$obo$bo wouldn't be forced.

[LaundryPizza03]

Another result from rachel at Discord: 5-cell 4c/5o is optimal.

Code: Select all

x = 2, y = 5, rule = B2ace4a5in/S2aik3ae4in5q8
bo$bo$o$bo$bo!

They considered a ship where in one phase, the leading edge has an isolated cell. Their resoning narrowed down a possible 4-cell 4c/5o to two possibilities: ob2o$5bo! or ob2o$4bo!. They continued:

let's assume without loss of generality that the spaceship moves to the right.

B0 is not allowed, and then rules with B1c obviously can't have a spaceship.

if there was B1e, that would require at least two cells on each edge of the bounding box (BB) in each phase, and in the 4-cell phase, that's only possible if each cell is on two BB edges, which implies the cells are just the corners of a rectangle. too symmetric to be a spaceship in INT.

so there is no B1e. then to surpass c/2, we need B2a used on the front (i.e. right) BB edge, and without B2c, that implies lightspeed, so we need B2c. similarly, with B3i, it also implies lightspeed, so there is no B3i. this means that the rule's transitions that are subsets of B3i are exactly B2ac. subsets of B3i are precisely the transitions that can advance the front BB edge, and they're also the only relevant transitions in some other contexts.

since the spaceship is 4c/5, and at each time, the front BB edge can only advance by 1, there are exactly 4 times when the front BB edge advances, and one time when the front BB edge doesn't move. let's call these times 0,1,2,3,4 in chronological order, with the offset chosen so that after time 4, the front BB edge doesn't move. the front BB edge at time t will be called l(0,t), and the vertical line behind (i.e. to the left of) l(n,t) will be called l(n+1,t). let f(n,t) be the y value of the top cell of l(n,t), and g(n,t) be the y value of the bottom cell of l(n,t).

if we look at the front BB edge's evolution from time 0 to time 4, it is simply a 1D cellular automaton (specifically W104), because l(0,t+1) depends only on l(0,t), and is determined from it by the fact that there's B2ac and none of B013i. so it's clear that f(0,t+1)<=f(0,t) and g(0,t+1)>=g(0,t). it's also easy to verify that if l(0,t), l(0,t+1) and l(0,t+2) all have a B2a at the same y value, then that B2a cannot be stopped, and so the pattern cannot be a sub-lightspeed spaceship, which is a contradiction. so if there are two consecutive B2a's at the same y value, then there cannot be a third.

then if f(0,t)=f(0,t+1)=f(0,t+2), since the top cell can only be reborn in the next generation via B2a, this means that there were two consecutive B2a's at y=f(0,t), so there cannot be a third and there cannot be a B2c either, which means f(0,t+3)<f(0,t). and if f(0,t)=f(0,t+1)=f(0,t+2) is false, then of course we have f(0,t+3)<=f(0,t+2)<f(0,t), so actually f(0,t+3)<f(0,t) always holds. this means that f(0,4)<=f(0,3)<f(0,0). similarly, g(0,4)>g(0,0).

now, let h(n,t)=f(n,t)-g(n,t)+1, i.e. h(n,t) is the height of l(n,t). of course, h(0,t)>0, otherwise the pattern would be empty. we also can't have h(0,t)=2, since that would imply a domino at the front BB edge, which would imply lightspeed. and we can't have h(0,4)=3, because that has two options (`obo` and `3o`), and in both of them, the front BB edge would move forward, which is in contradiction with how we labeled the times. so h(0,4) is either 1 or >=4.

if h(0,4)>=4, then that means h(0,t)>=4 for all times t. then if the 4-cell phase is at a time t<4, we need h(0,t+1)>=4, which requires two cells in l(0,t+1) so far away that their neighborhoods don't intersect, and each of their neighborhoods must contain two cells, and these two cells must of course be in l(0,t). that's 4 cells in l(0,t), so all cells at time t are in one vertical line. but that implies symmetry along this vertical line, so it can't be a spaceship moving horizontally.

if h(0,4)>=4 and the 4-cell phase is at time 4, then we need a cell above the top cell of l(0,4) to be born, and we need a cell below the bottom cell of l(0,4) to be born. since these two cells are too far away from each other to share any neighbors, and the rule doesn't have B01, we see that all 4 cells need to be neighbors of these two cells that are being born (2 cells are neighbors of the top one and 2 cells are neighbors of the bottom one). then there is no cell in l(0,4) other than the top and the bottom cell (at heights f(0,4) and g(0,4)), and the remaining two cells are in l(1,4), with the top one being at height f(1,4)∈{f(0,4), f(0,4)+1, f(0,4)+2}, and the bottom one being at height g(1,4)∈{g(0,4), g(0,4)+1, g(0,4)+2}. if f(1,4)=f(0,4), then we have a domino at the top edge of the bounding box, which means this isn't a right-moving spaceship, and similarly for g(1,4)=g(0,4), so neither of these can be the case. but then in the remaining two possibilities, the only cells being born in l(0,4) are the cell directly above the top cell of l(0,4), and the cell directly below the bottom cell of l(0,4), so l(0,0) is just two dominoes. since h(0,4)>=4, these two dominoes are too far away to interact, so this would move at lightspeed. so we can't have h(0,4)>=4 either.

now we're left with h(0,4)=1. that means l(0,4) is just `o`, so we can simply look for its ancestors up to 4 generations back in W104, and easily arrive at the conclusion that (up to reflection along a horizontal axis) there are only two possible values of l(0,0): `obobobobo` and `3obo`. in both cases, the `o` after 4 generations is in the middle of l(0,0). the size of these values compared to the size of l(0,4) already indicates that this is going to be simple.

let's first look at the `obobobobo` case. we immediately see that l(0,0) has more than 4 cells, so that can't be the 4-cell phase. l(0,1) has 4 cells, but it also can't be the 4-cell phase due to its symmetry along a vertical axis. l(0,2), l(0,3) and l(0,4) all have at least one cell, and since f(0,4)<f(0,3)<f(0,2)<f(0,1)<f(0,0) and g(0,4)>g(0,3)>g(0,2)>g(0,1)>g(0,0), we can use this to show that if t is the time of the 4-cell phase, then we need the set of the top two cells of l(1,t) to be disjoint from the set of the bottom two cells of l(1,t), due to f(0,0)-f(0,t)>=2 and g(0,t)-g(0,0)>=2 (both of which can be easily verified) and no B01 in the rule (again, neighborhoods far away from each other, each requiring two cells). that means l(1,t) contains at least 4 cells, and then since l(0,t) has at least 1 cell, that's more than 4 cells in total, contradicting that t is the time of the 4-cell phase.

now we have the `3obo` case left. again, l(0,0) has 4 cells, so time 0 can't be the 4-cell phase due to symmetry. time 4 also can't be the 4-cell phase because there are two cells in l(0,0) with disjoint neighborhoods that don't contain the cell in l(0,4), which means there are at least 4 cells in l(1,4), so more than 4 cells in the whole pattern at time 4. for the remaining times, we can use the asymmetry of `3obo` along the horizontal axis: it implies that l(1,4) together with l(0,4) must be asymmetric, and since there are only two ways to cause births of the top and bottom cell of l(0,0) with h(1,4)<=5 (specifically l(1,4) being either `2ob2o` or `5o`), and both of those ways are symmetric together with l(0,4), we see that h(1,4)>=6 (and trivially f(1,4)>=f(0,0) and g(1,4)<=g(0,0), so the h(1,4)>=6 is just telling us that one of these inequalities is strict). then once again, to ensure the birth of the top and bottom cells of h(1,4) and h(1,3), we need f(1,2)>=f(1,3)>=f(1,4) and g(1,2)<=g(1,3)<=g(1,4), which implies h(1,2)>=h(1,3)>=h(1,4)>=6.

so since the only possible times of the 4-cell phase are already known to be 1, 2 and 3, we know that if the 4-cell phase is at time t, then h(1,t+1)>=6, f(1,t+1)>=f(0,0) and g(1,t+1)<=g(0,0). for t in {2,3}, it's easy to compute h(0,t)=3, and also f(0,t)<f(0,0)<=f(1,t+1) and g(0,t)>g(0,0)>=g(1,t+1), so that means to ensure the birth of the top and bottom cells of l(1,t+1), we need at least one cell in l(1,t) for each, and due to h(1,t+1)-h(0,t)>=6-3=3, we actually need two cells in l(1,t) for either the top or the bottom cell as opposed to just one, which means we need at least 3 cells in l(1,t), and since l(0,t) has at least 2 cells, the whole pattern must have more than 4 cells, so the 4-cell phase cannot be at time 2 or time 3, which only leaves time 1. if the 4-cell phase is at time 1, then we can only have one cell in l(1,1) since there are already three cells in l(0,1). but h(0,1)=4 and h(1,2)>=6, so h(1,2)-h(0,1)>=2, which means that either a cell in l(1,2) needs at least two neighbors from l(1,1) in order to be born, or two cells in l(1,2) with disjoint neighborhoods need a neighbor from l(1,1) in order to be born. in both cases, that means l(1,1) contains at least 2 cells, and since l(0,1) is `ob2o`, it has 3 cells, for a total of at least 5 cells in the pattern, which is more than 4.

that finishes the proof that there is no 4-cell (4,0)c/5 in 2D euclidean square grid range-1 Moore neighborhood INT rules without B0.

For 3c/4o, the second case does yield a spaceship with 4 cells, such as:

Code: Select all

x = 5, y = 2, rule = B2-kn3ekn4qt5c7e/S2ac3r4ny5r
2obo$4bo!

For nc/(n+1) with n ≥ 5, that case is not necessary to prove a lower bound of 5 cells. That also establishes minimality of the 5-cell 5c/6o.

Code: Select all

x = 2, y = 5, rule = B2ace3ejr5ein6a/S2aik3jn4r5ey6c7e
bo$bo$o$bo$bo!

The proof above includes a lemma that with B2a without B2c or B3i, there are no spaceships with speeds faster than c/2o, but slower than c.

I can prove that with B2a with B3i and without B2c, no pattern can escape its bounding box without expanding at the speed of light. Proof: Let x be the maximum x-value of any live cell in a pattern in generation 0. Assume for fixed arbitrary y that (x+1,y) is live in generation 1. This can happen only if (x,y) and at least one of (x,y-1) or (x,y+1) is live in generation 0. However, regardless of the other cells in the rightmost column, this means that at least one of (x+1,y-1) or (x+1,y+1) is live in generation 1, so we have B2a or B3i frontend around all three cells from (x+2,y-1) through (x+2,y+1), and this repeats ad infinitum at the speed of light.

Code: Select all

#C A graphical proof of the above statement
x = 4, y = 15, rule = B/S012345678Super
2BE$2BDF$2BAM$2BAM$2BE6$2BE$2BAM$2BAM$2BAM$2BE!

[LaundryPizza03]

A new discussion on the Discord asks which speeds are possible in. It is conjectured that with, it is impossible to have orthogonal speeds faster than 2c/3o, which implies that a ship with speed (X,Y)/P (where X ≥ Y ≥ 0) can exist only if 3X + Y < 2P. Here are some examples found by AforAmpere of speeds where 2X > P:

Code: Select all

#C 2c/3o, 3X+Y=6
x = 2, y = 5, rule = B2ace3i4j6c/S01e2c3y
bo2$2o2$bo!

Code: Select all

#C 4c/7o, 3X+Y=12
x = 4, y = 9, rule = B2ack3ciny4ky5cjky6ck/S12ck3cjkry4eijnw5cijnq6-ei
3bo$2bo$2obo$b2o$bobo$b2o$2obo$2bo$3bo!

Code: Select all

#C (4,2)c/7, 3X+Y=14
x = 5, y = 5, rule = B2ac3einry5ain6ci7e/S01e2c3eiqr4aejt5aeknr6ce
o2bo$b3o$4bo$3bo$bobo!

Code: Select all

#C (6,3)c/11, 3X+Y=21
x = 4, y = 4, rule = B2-ek3i4ijnt5ijry/S01e2cin3aijkn4tw5acn6ak7
2bo$3bo$2bo$obo!

Code: Select all

#C (3,1)c/5, 3X+Y=10
x = 8, y = 6, rule = B2ac3aeikq4ikn5cir6i7e/S1c2c3-akny4eqy5aqr6ak7e
2bo$6bo$4bo2bo$bobo2bo$obo2b2o$bo3bo!

(2,1)c/3 (3X+Y=7) and (3,2)c/5 (3X+Y=11) could not be found by AforAmpere, consistent with the conjecture.

EDIT: I have formally proved this conjecture.

In a B2a rule with B2c and B3i, let (x0,y0) be a live cell in generation 0 with that maximizes 3x+y among all live cells in the pattern; we will denote this maximal value as c0. (Fig. 1) We want to make sure that this pattern does not propagate east at the speed of light.

Code: Select all

#C Fig. 1: The initial setup for our pattern. Green is the live cell at (x0,y0), and blue are other cells with 3x+y <= c0.
x = 7, y = 15, rule = B2ac3i/SHistory
7B$7B$7B$6B$6B$6B$5B$5B$4BC$4B$4B$4B$3B$3B$3B!

If (x0,y0-1) is live in generation 0, then we immediately have an east-facing lightspeed frontend, since (x0+1,y0) and (x0+1,y0-1) are necessarily live in generation 1, independent of the state of (x0,y0-2). (Fig. 2a) Therefore, (x0,y0-1) must be dead. This forces (x0+1,y0) to be dead, and (x0+1,y0+1) is already necessarily dead. It is still possible for (x0+1,y0-1) to be born via B2c if (x0,y0-2) was live in generation 0. (Fig. 2b) The value of 3x+y for this cell is c0+2. By translation, this implies that the maximal value of 3x+y increases by at most 2 per generation.

Code: Select all

#C Fig. 2: Case analysis for generation 1. Red cells are dead, green cells are alive, and yellow cells are undetermined.
x = 26, y = 27, rule = B2ac3i/SHistory
F13.3F7.F$F12.F3.F5.2F$3F2.5F3.F2.2F6.F$F12.F.F.F6.F$F4.5F3.2F2.F6.F$
F12.F3.F6.F$.2F11.3F6.3F3$12.5B4.5B$12.3BE5.4B$6.3F3.3BA5.4BA$9.F2.3B
A5.4BA$6.4F2.3B6.3B$5.F3.F2.3B6.3B$6.4F2.3B6.3B3$12.5B4.5B$5.F6.5B4.
5B$5.F6.5B4.5B$5.F6.3BE5.4B$5.F.2F3.3BD5.4BE$5.2F2.F2.3BA5.4BD$5.F3.F
2.3B6.3B$5.4F3.3B6.3B$12.3B6.3B!

Therefore, for a spaceship in the rule with displacement (X,Y)/P, we must have 3X+Y ≥ P, plus rotations and reflections of this constraint. Q.E.D.

EDIT2: The equivalent of JHC's proof for nonrelativistic rules with B2e without B3a is that c/3d ship can exist only if the rule does not have both S2n and S3c. With both B2e and B3a, there are no restrictions.

Code: Select all

x = 86, y = 44, rule = B2e3a/S4w5aHistory
4F3.3F27.F11.B9.B9.B9.B$F3.F.F3.F26.F3.F3.F3.2B8.2B8.2B8.2B$F3.F5.F2.
3F9.3F2.F.2F3.F3.F3.F3.3B7.2BA7.3BA6.3B.A$4F5.F2.F3.F7.F3.F.2F2.F2.F
4.4F3.3BA6.2BDA6.3BDA5.4B$F3.F3.F3.5F7.F3.F.F3.F2.F7.F3.5B5.2BEDA5.5B
5.5B$F3.F2.F4.F11.F3.F.F3.F2.F3.F3.F3.6B4.6B4.6B4.6B$4F2.5F2.4F8.3F2.
F3.F3.2F2.3F4.7B3.7B3.7B3.7B14$4F3.3F27.F11.B9.B9.B9.B$F3.F.F3.F26.F
3.F3.F3.2B8.2B8.2B8.2B$F3.F5.F2.3F9.3F2.F.2F3.F3.F3.F3.3B7.2BA7.3BA6.
3B.A$4F4.2F6.F7.F3.F.2F2.F2.F4.4F3.3BA6.2B2A6.3B2A5.4B$F3.F5.F2.4F7.F
3.F.F3.F2.F7.F3.5B5.2BE2A5.5B5.5B$F3.F.F3.F.F3.F7.F3.F.F3.F2.F3.F3.F
3.6B4.6B4.6B4.6B$4F3.3F3.4F8.3F2.F3.F3.2F2.3F4.7B3.7B3.7B3.7B11$5.4F
3.3F14.4F3.3F10.B9.B9.B9.B$5.F3.F.F3.F9.F3.F3.F.F3.F9.2B8.2B8.2B8.2B$
5.F3.F5.F2.3F4.F3.F3.F5.F2.3F4.3B7.2BA7.3BA6.3B.A$5.4F5.F2.F3.F.5F.4F
4.2F6.F3.3BA6.2BEA6.3BEA5.4B$5.F3.F3.F3.5F3.F3.F3.F5.F2.4F3.5B5.2B2EA
5.5B5.5B$5.F3.F2.F4.F7.F3.F3.F.F3.F.F3.F3.6B4.6B4.6B4.6B$5.4F2.5F2.4F
7.4F3.3F3.4F3.7B3.7B3.7B3.7B!

[hotdogPi]

I'm confused here. There's a 4c/5o in the previous post, and now you say it's impossible?

[lemon41625]

Ok so I was working on some proofs for HROT rules, here they are.

Definitions
Let w_ij be the weights of the rule in the ith column and the jth row and they can either be 0 or 1 (the 0th row/column is the centre one). We will assume the neighbourhood weights are D8 symmetric.

Let the sets B, S represent the set of birth and survival conditions and R be the range of the rule. We will also define w_i as the sum of all weights within a row i.

General Theorems

Escaping Bounding Box. To escape the bounding box, the rule needs B to contain at least one element from { sum(S): S ∈ 𝒫({w_ij : i < 0}) }.
- Moore: min(B) ≤ R*(2R+1)
- Von Neumann: min(B) ≤ R^2
- Cross: min(B) ≤ R

Escaping Bounding Diamond. To escape the bounding diamond, the rule needs B to contain at least one element from { sum(S): S ∈ 𝒫({w_ij : i + j < 0}) }.
- Moore: min(B) ≤ R*(2R+1)
- Von Neumann: min(B) ≤ (R + 1)(R + 2)/2 - 1
- Cross: min(B) ≤ 2R

General Speed Limits. Consider a quantity q = max(x + ny) where n is some positive integer and (x, y) are the coordinates of any live cell. If q can only increase by m per generation, then all ships / finite fronts in the rule must move at a speed (X, Y)c/P where X, Y ≤ RP & X + nY ≤ mP. (note that this bound is not tight)

For a given rule, this can be done by looking through each birth condition and finding the largest increase in q allowed. Then find a rule's maximum speed, we can check each value of n and see which value will give the tightest bound. For specific neighbourhoods, the speed limits are listed (these were generated by a program):

Code: Select all

R1 Moore
----------
B2: 1c/1o, 1c/2d
B3: 1c/2o, 1c/3d

R2 Moore
----------
B2: (1,2)c/1o, 3c/2d
B3: 4c/2o, 4c/3d
B4: 2c/1o, 2c/2d
B5: 2c/1o, 2c/2d
B6: 2c/1o, 2c/2d
B7: 1c/1o, 1c/2d
B8: 1c/1o, 1c/2d
B9: 1c/1o, 1c/2d
B10: 1c/2o, 1c/3d

R3 Moore
----------
B2: (2,3)c/1o, 5c/2d
B3: (1,6)c/2o, 7c/3d
B4: (1,3)c/1o, 4c/2d
B5: (1,3)c/1o, 4c/2d
B6: (1,3)c/1o, 4c/2d
B7: 3c/1o, 3c/2d
B8: 3c/1o, 3c/2d
B9: 3c/1o, 3c/2d
B10: 4c/2o, 4c/3d
B11: 2c/1o, 2c/2d
B12: 2c/1o, 2c/2d
B13: 2c/1o, 2c/2d
B14: 2c/1o, 2c/2d
B15: 2c/1o, 2c/2d
B16: 1c/1o, 1c/2d
B17: 1c/1o, 1c/2d
B18: 1c/1o, 1c/2d
B19: 1c/1o, 1c/2d
B20: 1c/2o, 1c/3d
B21: 1c/2o, 1c/3d

R4 Moore
----------
B2: (3,4)c/1o, 7c/2d
B3: (2,8)c/2o, 10c/3d
B4: (2,4)c/1o, 6c/2d
B5: (2,4)c/1o, 6c/2d
B6: (2,4)c/1o, 6c/2d
B7: (1,4)c/1o, 5c/2d
B8: (1,4)c/1o, 5c/2d
B9: (1,4)c/1o, 5c/2d
B10: 7c/2o, 7c/3d
B11: 4c/1o, 4c/2d
B12: 4c/1o, 4c/2d
B13: 4c/1o, 4c/2d
B14: 4c/1o, 4c/2d
B15: 4c/1o, 4c/2d
B16: 3c/1o, 3c/2d
B17: 3c/1o, 3c/2d
B18: 3c/1o, 3c/2d
B19: 3c/1o, 3c/2d
B20: 3c/1o, 3c/2d
B21: 4c/2o, 4c/3d
B22: 2c/1o, 2c/2d
B23: 2c/1o, 2c/2d
B24: 2c/1o, 2c/2d
B25: 2c/1o, 2c/2d
B26: 2c/1o, 2c/2d
B27: 2c/1o, 2c/2d
B28: 2c/1o, 2c/2d
B29: 1c/1o, 1c/2d
B30: 1c/1o, 1c/2d
B31: 1c/1o, 1c/2d
B32: 1c/1o, 1c/2d
B33: 1c/1o, 1c/2d
B34: 1c/1o, 1c/2d
B35: 1c/2o, 1c/3d
B36: 1c/2o, 1c/3d

===================================

R1 Von Neumann
----------

R2 Von Neumann
----------
B2: 2c/1o, 2c/2d
B3: 2c/2o, 2c/3d
B4: 1c/1o, 1c/2d

R3 Von Neumann
----------
B2: 3c/1o, 3c/2d
B3: 4c/2o, 4c/3d
B4: 5c/3o, 5c/4d
B5: 2c/1o, 2c/2d
B6: 2c/1o, 2c/2d
B7: 3c/3o, 3c/4d
B8: 1c/1o, 1c/2d
B9: 1c/1o, 1c/2d

R4 Von Neumann
----------
B2: 4c/1o, 4c/2d
B3: 4c/1o, 4c/2d
B4: 4c/1o, 4c/2d
B5: 5c/2o, 5c/3d
B6: 3c/1o, 3c/2d
B7: 3c/1o, 3c/2d
B8: 4c/2o, 4c/3d
B9: 5c/3o, 5c/4d
B10: 2c/1o, 2c/2d
B11: 2c/1o, 2c/2d
B12: 2c/1o, 2c/2d
B13: 4c/4o, 4c/5d
B14: 2c/2o, 2c/3d
B15: 1c/1o, 1c/2d
B16: 1c/1o, 1c/2d

===================================

R1 Circular
----------
B2: 1c/1o, 1c/2d
B3: 1c/2o, 1c/3d

R2 Circular
----------
B2: 4c/2o, 4c/3d
B3: 2c/1o, 2c/2d
B4: 2c/1o, 2c/2d
B5: 2c/1o, 2c/2d
B6: 1c/1o, 1c/2d
B7: 1c/1o, 1c/2d
B8: 1c/2o, 1c/3d

R3 Circular
----------
B2: (1,3)c/1o, 4c/2d
B3: (1,3)c/1o, 4c/2d
B4: 3c/1o, 3c/2d
B5: 3c/1o, 3c/2d
B6: 3c/1o, 3c/2d
B7: 4c/2o, 4c/3d
B8: 2c/1o, 2c/2d
B9: 2c/1o, 2c/2d
B10: 2c/1o, 2c/2d
B11: 2c/1o, 2c/2d
B12: 2c/2o, 2c/3d
B13: 1c/1o, 1c/2d
B14: 1c/1o, 1c/2d
B15: 1c/2o, 1c/3d

R4 Circular
----------
B2: (2,4)c/1o, 6c/2d
B3: (2,4)c/1o, 6c/2d
B4: (1,4)c/1o, 5c/2d
B5: (1,4)c/1o, 5c/2d
B6: (1,4)c/1o, 5c/2d
B7: 7c/2o, 7c/3d
B8: 4c/1o, 4c/2d
B9: 4c/1o, 4c/2d
B10: 4c/1o, 4c/2d
B11: 4c/1o, 4c/2d
B12: 4c/1o, 4c/2d
B13: 3c/1o, 3c/2d
B14: 3c/1o, 3c/2d
B15: 3c/1o, 3c/2d
B16: 3c/1o, 3c/2d
B17: 4c/2o, 4c/3d
B18: 4c/2o, 4c/3d
B19: 2c/1o, 2c/2d
B20: 2c/1o, 2c/2d
B21: 2c/1o, 2c/2d
B22: 2c/1o, 2c/2d
B23: 2c/1o, 2c/2d
B24: 2c/1o, 2c/2d
B25: 2c/2o, 2c/3d
B26: 1c/1o, 1c/2d
B27: 1c/1o, 1c/2d
B28: 1c/1o, 1c/2d
B29: 1c/2o, 1c/3d
B30: 1c/2o, 1c/3d

===================================

R1 Euclidean
----------

R2 Euclidean
----------
B2: 2c/1o, 2c/2d
B3: 2c/2o, 2c/3d
B4: 1c/1o, 1c/2d

R3 Euclidean
----------
B2: 3c/1o, 3c/2d
B3: 3c/1o, 3c/2d
B4: 4c/2o, 4c/3d
B5: 5c/3o, 5c/4d
B6: 2c/1o, 2c/2d
B7: 2c/1o, 2c/2d
B8: 2c/1o, 2c/2d
B9: 1c/1o, 1c/2d
B10: 1c/1o, 1c/2d
B11: 1c/1o, 1c/2d

R4 Euclidean
----------
B2: (1,4)c/1o, 5c/2d
B3: 4c/1o, 4c/2d
B4: 4c/1o, 4c/2d
B5: 4c/1o, 4c/2d
B6: 4c/1o, 4c/2d
B7: 5c/2o, 5c/3d
B8: 3c/1o, 3c/2d
B9: 3c/1o, 3c/2d
B10: 4c/2o, 4c/3d
B11: 4c/2o, 4c/3d
B12: 2c/1o, 2c/2d
B13: 2c/1o, 2c/2d
B14: 2c/1o, 2c/2d
B15: 2c/1o, 2c/2d
B16: 2c/1o, 2c/2d
B17: 1c/1o, 1c/2d
B18: 1c/1o, 1c/2d
B19: 1c/1o, 1c/2d
B20: 1c/2o, 1c/3d

===================================

R1 Cross
----------

R2 Cross
----------
B2: 2c/2o, 2c/3d

R3 Cross
----------
B2: 4c/2o, 4c/3d
B3: 3c/3o, 3c/4d

R4 Cross
----------
B2: 4c/1o, 4c/2d
B3: 4c/2o, 4c/3d
B4: 4c/4o, 4c/5d

Specific Theorems

R2 Von Neumann

Cannot shrink bounding box. In rules with B4 and S0-6, B3 and S0-5 and B23 and S0-4, patterns cannot shrink their bounding box.
Proof: Consider a cell (x, y) such that x is minimised with ties broken by minimising y. The cell (x, y) will have a neighbourhood that looks like this

Code: Select all

x = 4, y = 9, rule = LifeHistory
4B$4B$E3B$2E2B$A2EB$.E2B$.3B$.3B$.3B!

With S0-6, (x, y) cannot die.
With B3 and S0-5, (x, y) will die if all its neighbours (in yellow) are alive. However, this will cause (x+1, y+1) to be born.
With B23 and S0-4, if (x, y) dies, either (x+1, y+1) or (x+1, y) will be born.

Thus, the bounding box of the pattern cannot shrink.

Trailing edge cannot die. In rules with B2 and S01, the trailing edge of the pattern cannot die.
Proof: Consider a cell (x, y) such that y is minimised and of those, choose minimum x. In this row of cells, we know that they must all die for the pattern to move and no new cells in that row can be born.

Code: Select all

x = 9, y = 6, rule = LifeHistory
9B$9B$9B$2B2DE4B$B5D3B$4.A2D2B!

In order for that to be true, we need the red cells to be dead, to ensure no new cells are born (since we have B2). Hence, the only cells who state is uncertain in (x, y)'s neighbourhood are the yellow cells. Then, (x, y) can have at most 1 neighbour. Hence, with B2 and S01, (x, y) cannot die without causing more cells to be born and the trailing edge cannot die.

Cannot escape bounding box without immortal pattern. With B3/B4 and S1-9, patterns cannot escape their bounding diamond without immortal pattern.
Proof: In order for a cell with a larger value of x+y than any currently alive cell to be born, it requires one of the following transitions.

Code: Select all

x = 51, y = 30, rule = LifeHistory
38.A.A5.A3.A$7.A.A5.A.A.A$38.A3.A3.A3.A$7.A3.A7.A$38.A.A.A3.A.A.A$7.A
.A.A3.A.A.A$38.A3.A7.A$7.A3.A7.A$38.A.A9.A$7.A.A5.A.A.A$43.B$2.B10.B10.
B17.3B$.3B8.3B8.3B15.5B$5B6.5B6.5B15.BE3B$.BE3B6.BE3B6.BD3B15.DE3B$2.
DE3B6.DE3B6.DE3B14.A2E3B$2.ADE3B5.AED3B5.A2E3B15.3B$4.3B8.3B8.3B17.B$
5.B10.B10.B4$2.B10.B$.3B8.3B$5B6.5B$.BD3B6.BE3B$2.2E3B6.ED3B$2.AED3B5.
AED3B$4.3B8.3B$5.B10.B!

Each of these configurations of cells will be immortal with S1-9. Hence, with S1-9 and either B3/B4, patterns will not be able to escape their bounding diamond without creating an immortal pattern, thus, ruling out the existence of ships.

Conjecture: Photons are only possible in B3 rules with S3.

[tommyaweosme]

lsited

my stance on speed limits is as long as the rule has spaceships you can use hrot to manipulate it to be anything you want
an example: glider 2,3c/4

Code: Select all

x = 0, y = 0, rule = R3,C2,S2-3,B3,NW0101010000000000000000100010000000000000000101010
bbobb$
bbbbb$
bbbbb$
bbbbo$
bbbbb$
bbbbb$
obobo!

[lemon41625]

I was also thinking about why some generations rules seem to have missing speeds.

I have managed to prove that for rules like Brian's Brain with no survival conditions, ships with k = 1 can only exist with period of 1 or period larger than the number of states. The proof is attached as a PDF because I like LaTeX.

I also conjecture that this likely applies to all ships, not just ships with k = 1, but the proof is kind of difficult and I haven't been able to find an elegant way to prove it, especially for oblique ships and gcd(k, p) > 1 because representing them in the gfind-representation which I used in the proof makes the math quite complicated.

The other idea I had to try and extend Eppstein's proofs for 2-state rules to Generations rules. I'm fairly certain that most of them are valid, except for the one on the trailing edge and maybe the ones about connected patterns not shrinking (I haven't thought about those yet).

The idea was that in some cases, the row just below the last row with a live cell would be filled with dying states and hence, invalidating Eppstein's proof and allowing ships to exist. So that would explain why 0/23/3 has only photons while 0/23/4, 0/23/5, ... have c/2o ships. However, one problem, is that I can't prove the the cells beyond the live cell of that last row will be in state 0 (i.e. can be born), so David Eppstein's proof is still invalidated, even if the row after that can be guaranteed to be all dead. Maybe someone can also help to shed some light on this?