Conway's game of Life

This is a cellular automaton comprising a square lattice of cells, each of which is either live or dead at any given moment in time. Time is discrete: each moment has a definite successor. At any moment, a cell will be live precisely if, at the previous moment:

• it was live and so were 2 or 3 of its neighbours; or
• it was dead but 3 of its neighbours were live;

Thus:

A two-by-two grid of live cells is stable: each live cell has three live neighbours, so lives on, but no dead cell has more than two live neighbours, so none come alive.

A pair of diagonally-adjacent diagonals, of any length greater than 1, likewise form a stable pattern, which may optionally be capped at either end (as shown here at the bottom right end), or at both; indeed, the block may be construed as the special case of length one capped at both ends. The uncapped variant of length two is known (Figure 3, page 819 of Winning Ways) as the tub; that of length three as the barge and that of length four as the long barge; a tub with one end capped is a boat, with both ends capped it is a ship; a barge with one end capped is a long boat and with both ends capped it is a long ship. The above is an even longer boat: I'll call it the very long boat.

↔

A line of three live cells will flip-flop endlessly between horizontal and vertical: the central cell has two live neighbours, so survives; each of the other live cells has only one live neighbour, so dies; but the cells bordering the middle live cell on its other two edges are adjacent to all three live cells, so come alive. This pattern's name is blinker; there is a common pattern of four of them, known as traffic lights, which arises after seven time-steps starting from

→ → → →

The final state here is the result of reflecting the initial state in a diagonal of its bottom right cell and sliding it one cell to the right; consequently, the next two time steps reflect it back again and slide it one cell down; thus, every four time steps, this pattern moves once cell diagonally down and to the right. The two-step transformation is technically a glide-reflection – reflecting in a diagonal that bisects the right edge of the bottom right live cell of the initial position and translating half the length of a cell diagonal parallel to that line – so this pattern is known as a glider.

See below for more examples, some screen-shots of the results from one interesting start-state and an exploration of what happens when gliders collide with one another or with a block. Ham-Hung Soh has written an implementation of the same system using scalable vector graphics (SVG, an XML-based image format).

Despite the simplicity of the rules, this system (which the late John Horton Conway discovered in the 1960s) is sufficiently complex that one can implement a Turing-complete computer in it, if its lattice of cells is infinite (so, presumably, on a large enough grid, you can implement a von Neumann computer). See the book Winning Ways (ISBN 01-12-091102-7, by Berlekamp, Conway and Guy: volume 2, chapter 25) for a vastly more extensive treatment of this toy (from which I selected the examples below); which (page 849) asserts that

It's probable, given a large enough Life space, initially in a random state, that after a long time, intelligent self-reproducing animals will emerge and populate some parts of the space.

The following demo (mostly an exercise in learning how to use ECMAScript and the Document Object Model; the rest of this page is fall-out from the inevitability of playing with it) works with a finite grid of cells: you can have a void over the edge of the grid, or identify edges with one another to form various implicit topologies. The grid of cells it works with can be of any size (but your browser may slow down a lot if it is big): the table below is just a display window onto a patch of the underlying grid. You can move it around the grid, or flip around to see the grid side-ways or reversed; changing the display has no effect on the cellular automaton in the grid. Note that the orientation and offset properties of this display may be changed by scrolling in the display area: for the cyclic topologies, scrolling off the edge of the grid is equivalent to being elsewhere on it, possibly in a changed orientation. Clicking on a cell toggles it: if it was live, it dies; if it was dead it comes alive.

Topologies

In Conway's original formulation, the cellular automaton runs in an infinite two-dimensional plane; however, your computer doesn't have infinite memory and, in any case, the gliders a life run is apt to emit escape and are lost to the rest of the mess. Consequently, this implementation just has one rectangular tile – the Grid above – whose size you can set. At its boundaries we have various options; most of the interesting variation comes by associating one edge with another, so that what's just inside our tile beside one edge sees, just across the edge, whatever's just inside our tile beside the other edge. That way, when a glider crosses one of these edges, it comes back into the grid across the other. Associations of this kind characterize the topologies listed below.

Another option is to have an edge be void – as if there were a barren emptiness on the other side of it, whose cells never can become live. As long as your tile is large enough that nothing ever hits it except for gliders, this will simulate Conway's infinite plane fairly faithfully – except for a two by two square block left on the boundary by each glider that tries to leave, which may result in more mess if another glider hits it. Such an edge thus amounts to a true boundary; an edge bound to another behaves locally as if there were no edge, but things can fall off an unbound edge. The descriptions of topologies, below, presume this handling for any edge not bound to a different edge – which only arises in the first three. However, in the interests of more interesting dynamics (after all, this page is a toy) you have a choice of handling of such boundary edges: you can also bind the edge to itself. Where a true boundary behaves as though there is a desert beyond it, an edge bound to itself can behave like a mirror: a cell beside the edge sees itself just across the edge. Alternatively, we can reverse the edge while associating it with itself, so that a cell beside one end sees, across the edge, the cell beside the other end of the edge; on an edge of odd length, the middle cell sees itself just across the edge; on an edge of even length, the two middle cells see each other across the edge. This last is the boundary type called Spin, above (when one of the first three topologies below is selected – the boundary type control is hidden, because it's irrelevant, otherwise), and used by default (when relevant) because I suspect it's more interesting.

The supported topologies are (when boundary type is Desert):

Oasis

The grid is surrounded by barren emptiness in all directions.

Cylinder

There is barren emptiness above and below; but the grid's left edge is identified with its right edge. The result is an endless ribbon that repeats itself, just as an ant walking round a cylinder would come back to where it was before.

Möbius

The Möbius strip is just like the cylinder, but with a twist: the left and right edges are identified with one another, but the top of each is identified with the bottom of the other. Again, we get an endless ribbon that repeats itself, but it's reflected top-to-bottom at each repeat.

Torus

As for the cylinder, the left and right edges are identified with each other (the same way up); at the same time, the top and bottom edges are identified with each other (the same way round). The result is like an inflated tire (or the sort of doughnut with a hole through the middle) from the point of view of an ant crawling around on it: it stretches indefinitely in both directions, but repeats itself in each.

Klein

The Klein bottle is obtained by identifying the left and right edges inverted (as for the Möbius strip) and identifying top and bottom edges without inverting (as for the torus).

Projective

Identifying left with right inverted and top with bottom inverted yields a close relative of the projective plane (a hemispherical shell with opposite points of its boundary identified with one another), aside from oddities at the corner.

Sphere

If we identify the top edge with the left edge and the bottom edge with the right edge, in each case identifying rightwards on the horizontal edge with downwards on the vertical one, the result has the same topology as a sphere ('though the geometry's a bit spiky at the corners).

Example configurations

I'll collect here any interesting patterns I hear about, or discover, for use in the Insert menu above. I doubt my implementation is up to the digital clock someone implemented; but the page there can take you to one that is.

Explosive. This starting pattern takes two steps to get to the same state as arose after one step for the configuration whose results I describe and illustrate below: just five initially live cells suffice to kick off a complex pattern of behaviour, lasting 1103 time-steps.

Glider bomb. This emits four gliders after 91 time-steps; four more at 101 and four more at around time-step 161, leaving a residue which, aside from eight blinkers, becomes static at time-step 177.

After fifteen time-steps, this emits a glider; fifteen further time-steps later it's back to its initial state; thus it emits an endless stream of gliders (on the line across = down + 14 relative to its top left corner; the above initial grid is 36 wide and 9 tall). It is consequently known as the (Gosper, 1970) glider gun.

There is a configuration of 35 active cells, also due to Gosper – three gliders, two 2×2 squares and two minimal pairs of diagonals (six squares each, four in a diagonal square, with a hole in the middle, and one on each end of a diagonal through this middle), all carefully placed in relation to one another – that decays in a few time-steps into this glider gun. You can see it around five minutes into this numberphile interview with JHC.

The Eater. This stable configuration will eat various other things; in particular, an in-coming glider from the bottom left going up and to the right will destroy itself, leaving the eater undamaged.

Beehive. Toggling the dead cell just above or below a corner of the above rectangle (and outside it) yields the honey-farm, a pattern of four beehives, after 17 time-steps (centred on what was the live cell of the beehive adjacent to the cell you toggled). Toggling a dead cell one step further out yields, after one step, what the explosion (above) yields after two.

On one beehive of a honey-farm, toggle a dead cell which would turn the beehive into a honey-farm were it isolated. If you pick a candidate near the honey-farm's centre, the pattern emits one glider (in the direction from the beehive you poked towards the cell you toggled) and the residue annihilates itself after 57 time-steps. A candidate on the perimeter of the farm, in contrast, emits three gliders (two to the right and one to the left of the diagonal from the cell you poked to its live neighbour); after 204 time-steps its residue enters stasis (two blocks, 3/4 of traffic lights and a ship).

Arch. This simple pattern evolves over 173 time-steps through an elegantly symmetric sequence of patterns (reminiscent of Aztec art), ending with two ponds, five blinkers and six blocks. It can arise from highly asymmetric priors, notably including several glider collisions.

The mounting block. Emits gliders at t=41 (Identity [-2,-8]) and t=93 (Vertical [-20,-20]@92); the residue settles down at t=148, comprising three blocks and a ship.

  

Loaf, pond and snake (in Figure 3, page 819 of Winning Ways); these stable patterns (particularly the first two of them) arise quite routinely in the residue from other things.

  

Beacon, Clock and Toad (in Figure 4, page 820 of Winning Ways); these all have period two – that is, what they change into changes back into what they started out as right away.

If you leave out every second cell on one long diagonal of an arbitrarily extended ship, and each of the other diagonal's cells adjacent to one of those you kept, but leave the three cells at each capped end alone, you get a pattern called (in Figure 12, page 380 of Winning Ways) the barber's pole; this also has period two. The pattern given here is a fragment of the barber's pole, designed to be pasted repeatedly, at intervals of [5,5]; the bottom right end is correctly capped, but you have to cap the top left end yourself (half-turning the first fragment and off-setting it by [-1,-1] will achieve this for you).

Figure 8: an eight-cycle, some of whose transient states resemble the digit 8 (tilted over onto a diagonal).

Three-cycle.

This has period 14; half way through, it's the same pattern but inverted (either in a horizontal mirror – its symmetric under inversion in a vertical mirror – or half-turned about its mid-point).

Fifteen-cycle.

A little flip-flop in a four-by-four square.

Space-ship. After four steps this has moved two squares to the right, via a glide-reflected form of itself one square to the right after two steps. You can make the horizontal arm of this (the row of four live cells) five or six cells long, moving the trailing diagonal (and back corner) dot appropriately, to get larger variants. (You don't need the back corner dot to make it work, but its cycle puts one there; the longer versions add a dot or two just outside the back corner's long edge of the picture here, likewise irrelevant; but it's these (growing to a third) that prevent longer forms working, without an escort.)

Escort. An over-length version of the space-ship being escorted by two of the longer stable ones.

A pair of towers; this pattern can clearly be extended indefinitely (or shortened) as a zig-zag; as many rows of three as you care for (but at least two of them), separated by blank rows, with caps in these blank rows at alternating ends, just beyond the end, and a block beside each end-row, level with its last block, away from the last cap.

Farewell. Emits a glider and is gone.

… and see the first dozen or so pages of Wining Ways, volume 2 chapter 25, for a vast selection of further examples. Much as I'd love to show you the Gosper group's flip-flop, it's rather big !

If you place two blinkers at right angles to one another, with one's centre on the line of the other with just one cell's space between it and the other's end, the resulting pattern – called Thunderbird – produces thoroughly interesting dynamics. Once it reaches stasis, displaying what has lived how much of the time makes for quite a pretty picture.

There's an arrangement of 13 gliders which, launched correctly, will eventually produce a glider gun. Since some of them are initially in the L form depicted above and others are in the Z form it alternates with, setting it up using the above controls involves pasting in several in L-form, taking one time-step to turn those into the Z-form, then pasting in remainder in L-form. I'll specify each glider as an [orient, across, down] list, for brevity, relative to the top left corner of the final glider gun. The first wave is: [Clock, 9, 4], [Clock, 23, 2], [BL-TR, 15, 10] and [BL-TR, 29, 8]. When you've given those all one time-step, to turn them into Zs, add the second wave: [Vert, 0, 3], [Vert, 34, 1], [BL-TR, 3, 6], [BL-TR, 29, 18], [BL-TR, 37, 4], [Half, 9, 9], [Half, 23, 7], [Half, 20, 11] and [Half, 39, 14].

Pasting a glider gun into a 152 by 84 Klein bottle with its top left corner at grid co-ordinate 20, 20 produces a run in which the ray of gliders wraps round to interfere with itself; thereafter, all new gliders are destroyed along with every third old one. Once the last one to escape such collision when new has passed, new gliders are able to escape again, while the first burst continues rolling round the universe. After about 1830 time-steps the first wave hits the glider-gun and destroys it, though a judiciously placed eater (at 27, 31) can prevent that. Reducing the grid's height to 82 allows the first batch of gliders to clip the end of the gun and destroy it at around time-step 1400 (though it continues doing interesting things until time-step 2528). At height 81 (and, I suspect, other odd heights not too different from this), the first interference between the new and old gliders annihilates all of both; after about 1300 time-steps, the last old glider to escape before interference began has been destroyed and a fresh batch of new gliders escapes, to repeat the story. An 89 by 55 grid likewise produces bursts of gliders, each of which, cycling back round, eats its own tail to produce a gap in between; it does so with a period of 720 cycles. I've observed similar at 197 by 292; one step taller gets the glider gun destroyed like the first case described above.

Apparently it has now been shown that any configuration at all that can arise in life can be arrived at starting from 15 gliders.

Pictures

The images below show the results of starting with the Explosive pattern, above, with its top left corner at position 45 across and 42 down in a 119 wide by 84 tall grid, using its identity orientation. This grid is large enough that the resulting behaviour's only collisions with the boundary are gliders, after these have broken contact with the rest of the pattern, which never touches either the boundary or the two-by-two residues left by the gliders on the boundary. Consequently, in this context, the behaviour is representative of what would happen in an infinite open plane, aside from each glider leaving a two-by-two square residue on the boundary where it tried to leave. After 1003 time steps, aside from the six escaped gliders, the Explosive pattern's decay settles down to four blinkers (each is a row of three cells, alternating between horizontal and vertical) quietly blinking away in the company of a few static fragments. The following images show selected moments in the history leading to that (click on an image to see it at full size):

Time	State	History
189
698
833
1102
Key	dead but about to come alive   live and remaining live   live but about to die   dead and remaining dead   barren	has never been live   has been live once   has been live two or three times   has been live four to seven times   has been live eight to fifteen times   has been live sixteen to 31 times   has been live 32 to 63 times   has been live 64 to 127 times   has been live 128 to 255 times   has been live 256 to 511 times   has been live at least 512 times

At time-step 189, the fifth gliders to escape comes into being: if you look carefully, you'll see it at the top of the left-most active region. You can also identify its start position by looking back along its trajectory, as revealed by the later images. At time-step 698 the last glider to escape is just being born; at time-step 833 it hits the boundary of the Oasis test grid used. After that, the remaining activity is self-contained and eventually attains stasis at time-step 1103; the transition to stasis is shown above.

Glider-glider scattering

What happens when two gliders collide ? It depends on their phase and relative position. At any given moment, a glider has one trailing live cell sharing only a corner with one other and four that are joined edge-to-edge; these four take shapes we can loosely identify with J, Z, L and S; the illustration above starts with J, goes to Z and ends as L; it would become S at the next time-step. Since gliders cycle J-Z-L-S endlessly, their position in the cycle – or phase – can be described, at any moment, by one letter; though this varies with each time-step, two gliders will always be the same number of steps apart in the cycle, so we can describe the phase of one relative to the other as one step behind, one step ahead, in sync or two steps different (either behind or ahead).

In order to collide at all, two gliders must be going in different directions. They can either be going in opposite directions for a head-on collision or be travelling crossing paths, on diagonals at right angles to one another. For the head-on collision their relative position can be described by the off-set, if any, between their lines of flight; the only other variables are their phases. Every two time-steps they get one cell closer together along the diagonal they travel, so differences in initial separation only change their phases at the time of meeting. For the crossing collision there is more to vary. We can eliminate some of the variation by rotating the display so that both are travelling to the right (one downwards, the other up); if the upper one is further to the right than the lower one we can reflect in a horizontal mirror; so that we only need to consider cases where the lower glider is level with or ahead of the upper one. If the lower one is more than five squares to the right of the upper one they shan't collide at all (the glider always sits inside a square of side three, so one might expect four to suffice, but when out of phase they take their right-wards step at different moments). Since each moves vertically towards the other by one cell every four time-steps, the only relevance of their vertical separation, aside from delaying the moment of collision, is whether it is odd or even (since this won't change).

In the following, a glider was launched from the upper left and allowed to run for up to three steps before a second glider was introduced, reflected in BL-TR for the head-on collision or rotated one step anti-clockwise for the crossing. The tables below show the first glider's position when the second was added and record the consequences at the initial position of the second glider's top left corner. The bottom right corner records its [across,down] co-ordinates; those of the top left are always [0,0]. Consequences are recorded in a short-form: M@23 = mounting-block at t=23, A@13 = arch at t=13, each with the subsequent history implicit therein; a11 = total annihilation at t=11, s17, residue = stasis at t=17 leaving the indicated residue, in which a numeric prefix (> 2) on a letter indicates number of copies of the figure and individual figures are:

b

block,

e

eater,

f

honey-Farm,

g

glider,

h

beeHive,

k

blinKer,

l

loaf,

o

boat,

p

pond,

s

ship,

t

traffic lights and

u

tUb.

Written by Eddy.