Intro Soup Recipe Shelf Sink Chef
Take me higher...

LwoD (continued)

Blocking in LwoD raises the most delicate issues of the construction since a horizontal ladder crashing into the side of a vertical one creates uncontrolled chutes and lava unless the collision has the right timing. So let us denote the 8 possible phases of such an interaction as (h,v), where h in Z4 and v in Z2 are the horizontal and vertical spatial phases. We represent h by the shape of the horizontal ladder's head the first time it advances to a new column, while v is 0 or 1 depending on whether the top row of the horizontal ladder lines up with an occupied or unoccupied cell on the vertical ladder's left edge.

Fig. 8 shows the two clean blocking collisions which arise. If we label the lower one as (0,0), the upper one is (2,1) since the head of its horizontal ladder has an identical shape but is two cells further to the left, while it has opposite parity with respect to the boundary of the vertical ladder. (There are also two 'dirty' collisions, which create small transient eruptions of lava, but these are not needed for our purposes.) Note that the final fates of the two collisions are mirror images; this is a consequence of the head's flip symmetry after half a cycle. To complete our verification of the ladder CA axioms, we need to show that any ladder headed for the side of another already present can be phase-shifted to guarantee a clean block.

Fig. 8. The two clean blocking collisions

Our solution combines the turns of Figs. 6 - 7 into a two-turn perturbation induced by the static debris of the middle frame in Fig. 9. The top and middle frames show the same horizontal ladder approaching the same vertical one, while the bottom frame shows the result of collision with the debris. The net effect is an advance of the same head one cell horizontally and a change of vertical parity, shifting (h,v) by (-1,1) = (3,1). This action partitions the group Z4 into a subgroup consisting of phases of the form (even, even) and (odd, odd), and another coset comprised of the remaining phases. Since one of the clean blocks in figure 8 belongs to the subgroup, and the other to the complementary coset, it follows that an arbitrary ladder can be phase-shifted to achieve a clean block by applying between 0 and 3 of these shifts. This completes the demonstration.

Fig. 9. A (-1,1) phase shift

Let us conclude with a few additional remarks. First, the inevitable question: are there other ladder CA rules? A number of minor variants of Life without Death admit ladders with similar but slightly different architectures. Four alternatives on the 8-cell Moore neighborhood we know of have the same birth rule, but preclude survival for certain population counts: (i) 8, (ii) 7, (iii) 7 or 8, and (iv) 1 or 3. These slight differences no doubt destabilize many, if not all, of the elementary interactions just described, so it remains an open question whether any of these variants satisfies our axioms. We invite the reader with an insatiable appetite for experimental mathematics to investigate these or other candidates. Another interesting rule has birth with 2 or 5 occupied neighbors, and certain survival. In that case there are diagonal ladders, but we have not investigated the possibilities for turns and other complex collisions. Clearly a ladder CA can be designed to have precisely the desired properties by including sufficiently many states and/or sites in the rule table; the appeal of LwoD and its cousins lies in their mathematical simplicity and their ability to emulate circuits on their own terms.

Finally, we pose an intriguing open question about Life without Death: is there any initial seed that fills the lattice linearly in time with a positive asymptotic density? Experiments from large lattice balls suggest there is, but we know of no way to prove this other than to construct a 'ladder gun' or a space-filler such as Max. This would require far greater ingenuity than the above constructions, but we think there is a good chance that one is possible.

  Back  

  Next

Take me higher...
Intro Soup Recipe Shelf Sink Chef