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

Life without Death

Let us now show that the ladder CA design principles can be implemented using one of the simplest imaginable two-dimensional rules: Life without Death (LwoD). In this growth model an empty site becomes permanently occupied if 3 of its 8 nearest neighbors in the square lattice are occupied. The remarkable behavior of LwoD is described in our recipes of February 13 and April 24, 1995; essential features have been noted over the years by Packard and Wolfram [16], and by various members of the Life List Internet group devoted to Conway's Game of Life.

From suitable initial seeds one encounters complex dendritic crystal patterns. The dynamics evolve as a pseudo-stochastic mix of three ingredients: (i) chaotic lava, (ii) horizontal and vertical ladders which advance at speed 1/3 by a weaving motion and seem to outrun the surrounding lava, and (iii) parasitic chutes which emerge from the lava but can only shoot along the edges of ladders at speed 2/3. The resulting interactions - for instance, when a chute reaches the end of a ladder it nips it in the bud, and causes a lava eruption - give rise to remarkable self-organization in which very large regions of the growing crystal can be cloned exactly in time. As one indication of LwoD's sensitive dependence on initial conditions, given any finite initial configuration A, one can produce configurations B and C, each consisting of at most 100 cells, such that the crystal grows forever when the sites of B are added, but reaches a fixed point when C is added [5]. Apart from minor variants, we know of no other simple CA rule with this property.

Our objective here is to harness some of the complex phenomenology of LwoD in order to construct the defining elementary collisions of a ladder CA: births, turns, blocks and phase shifts. In Figs. 4 - 9 below we present a series of still frames which document the necessary interactions. We invite the reader to check out our Java LwoD Demos, or to download WinCA or any of several other interactive 2d CA simulators, in order to see the dynamics and confirm the constructions.

To begin, Fig. 4 shows one seed of size 8 which gives birth to a ladder. (The pentomino piece actually spawns a two-sided ladder, and then interaction with the other three cells kills its left branch.) Note that the ladder's horizontal spatial periodicity is 4. In fact, the head cycles through 12 distinct patterns in order to weave its periodic pattern, the last 6 of which are vertical flips of the first 6.

Fig. 4. Birth of a ladder from 8 cells

Recall that a separate killing mechanism is not needed in a ladder CA since ladders can block themselves after 3 turns. Nevertheless, as further evidence of LwoD's sensitive dependence, Fig. 5 shows that its ladders can be stopped by a single well-placed cell!

Fig. 5. A ladder killed by a single cell

Next, Figs. 6 - 7 show two static configurations which cause an LwoD ladder to execute a 90 turn to the right, while otherwise causing only a local disturbance. The turn in Fig. 6 is instructive, since it involves typical instabilities which must be controlled after a collision. The actual ladder turn is caused by the single isolated cell, but without further engineering another ladder would turn to the left and a chute would race back along the lower edge of the incoming horizontal ladder. The 29-cell blob blocks the former effect, and the row of 3 cells stops the latter while causing only a small transient lava flow. Fig. 7 shows a turn which is both more elegant and mysterious: four carefully placed cells induce a brief burst of lava which leads to a right ladder turn without any undesirable side-effects.

Fig. 6. A turn

Fig. 7. Another turn

  Back  

  Next

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