Game of Life & Other Cellular Automata: an Introduction

(for non-gurus!)

by Harry Foundalis

Please note: the parent of this page is Conway's Game of Life: a Java Applet with Autodetection of Patterns.

The "Game of Life" is not a game, really. Don't expect to see something played by opponents who try to outwit each other. If you count solitaire as a game, then that's as close as you can get to the kind of thing the Game of Life is. But it's a lot more fun!

"Game of Life" is the name the mathematician John Horton Conway gave to a specific case of what is more generally known as "cellular automata". Don't let the cryptic words fool you! The idea is extremely simple, and can be understood by anybody. Here it is:

The game is played on a board, like the one for chess, or checkers, except that the board extends infinitely in all four directions. There is only one kind of "men", or pebbles, that you ever need to put on the squares of the board, and each square may hold exactly one pebble. So imagine you have an unlimited supply of pebbles, which we'll call cells from now on you'll soon see why and you place a few of them on the board. For example, in the figure that follows we have placed three cells in a row, shown in red color against the black background of the board which we'll call space from now on.

Figure 1. The blinker

Here is how the "game" is played. On each "move" (or: snapshot in time) we decide whether each location of our space is going to acquire a new cell if it is empty, or if it is going to retain or lose the cell if it already has one. If the cell dies, it disappears, and its location becomes black. If it remains alive, or is born in that location, it stays or becomes red. How we decide what is going to happen in each location? We start by counting the eight neighbors of the location (up, down, left, right, and the four diagonal neighbors). If the number of neighbors is 2 or 3 and the location is already occupied by a cell, we say that the cell survives, and stays red in the next time-snapshot. Any other number of neighbors (0, 1, 4, 5, 6, 7, or 8) kills the cell. (No justification for this rule is needed, but if it helps to remember, with 2 or 3 neighbors we can think that the cell has just enough company to supply it with nutrition and remain alive; with fewer neighbors it feels lonely and dies; and with 4 or more neighbors it suffocates from overpopulation and dies again; so, this intuition from biology is what causes the usage of names such as cell, dies, survives, etc.) In addition, a cell is born in an empty location if there are exactly three neighbors around that location. That's it. Two or three neighbors, and the cell survives. Three neighbors, and a cell is born. That's Conway's rule, and is often described succinctly as: S23/B3, where S stands for survives, and B for born.

Figure 1 shows the most common oscillator pattern in the Game of Life, the blinker. Why it is called an oscillator? Click on it, to see how it changes in successive time-snapshots: it switches from horizontal to vertical, and back. This is not a random behavior: its three cells follow Conway's rule. The central cell stays always alive because it always has exactly two neighbors. The other two cells to its sides die, because they have only one neightbor (the central cell). Finally, of all the other locations in space, two can give birth to new cells because they have three neighbors, and that's what causes the blinker to oscillate between the horizontal and vertical position.

Do all cell configurations oscillate like that? Of course not. Most random configurations present a random behavior, a chaotic behavior as it is called, one in which it is not possible to predict what the outcome will be. Figure 2 shows such an initial pattern, called the b-heptomino. Click on it.

Figure 2. A b-heptomino

Did you notice the two purple creatures which escaped to the southwest and southeast? These are called the gliders, and play a very important role in the Game of Life. If you missed them, drag the mouse anywhere within the figure to reset it, and click again once on it to start it anew. (You can use this mode of interaction with all figures in this page.)

You might be wondering why the colors of the cells change as time passes. The blinker turns cyan after a while, the gliders are purple, and some stable patterns after the b-heptomino evolves turn blue. Colors are our figure's way (or: our program's which runs behind the figures way) of showing that it detected certain patterns. For example, those patterns that remain stable (called still lives in the game's jargon) are shown in deep blue color. Oscillators, such as the blinker, are shown with a color which indicates their period of oscillation, if it is a small number. So, the blinker with a period of two is shown in cyan; an oscillator with period 3 would be shown in green; higher periods would result in hues of yellow and orange. Other unrecognized, active patterns are shown in red. The gliders, which are a very well-known and common creature in the Game of Life are shown in purple. The program which animates the figures needs a few time-steps called epochs, or generations before recognizing and color-coding the various objects, so, in the beginning everything is shown in red.

Oscillators

Let's see a collection of still lives, many of them commonly occurring after a number of chaotic births and deaths of cells in random configurations, and let's give them names. (These names have been more-or-less standardized in the game's jargon.) Figure 3 shows a collection of still lives.

Figure 3. Various still lives

Still lives can be thought of as oscillators of period 1. The blinker, as we saw, is an oscillator of period 2. Are there other oscillators? Yes, they come in various periods, and are often beautifully symmetric. A few of them occur commonly, but most of them are the result of craftsmanship, or search by computer. Let's take a look at a few oscillators.

Figure 4. Some oscillators of period 2, known by name.

Did you click on the oscillators (anywhere within their space) to see them animated? After a short number of time-steps (epochs) they are detected by the figure as oscillators of period 2 and are displayed in cyan color. Did you notice the number "2" on the far left, which turns blue after being animated? That's a still life, made of "snakes" (see Figure 3). One may construct every digit from 0 to 9 in this manner.

The following figures show oscillators of periods 3, 4, 5, 6, 7, 8, and some with higher periods.

Figure 5. Some oscillators of period 3, known by name.

Figure 6. Some oscillators of period 4, known by name.

Figure 7. Some oscillators of period 5, known by name.

Figure 8. Oscillators of periods 6, 7, and 8, known by name.

Figure 9. Oscillators of higher periods, known by name.

Figure 10. Finally, some oscillators of very high periods.

Evidently, one can construct oscillators with practically any period. If you pay close attention to the way some of the higher-period oscillators are constructed, you'll recognize some of their parts. For example, P56 in figure 10 consists of two Kok's galaxies (figure 8) which send back and forth a structure which, at a certain epoch, is a b-heptomino (figure 2); the latter is kept within the bounds of the oscillator by making use of two blocks (figure 3, top line). The toadsucker (again in figure 10) works through two pentadecathlons (or PD's, for short; figure 9) that move a toad (figure 4) left and right. All these higher-period oscillators are the result of ingenious craftsmanship by various people who have examined the Game of Life in the last few decades. The structure of such patterns is extremely sensitive to the last detail: usually, if even one cell is missing, the structure disintegrates into a chaotic pattern. Speaking of which, brings us to the next idea: chaotic behavior.

Vigorous Patterns and Methuselahs

Earlier in this page we mentioned briefly the b-heptomino as an example of a mildly vigorous pattern which lives for a short time, creating a couple of gliders and a bunch of oscillators. Is there anything more vigorous and chaotic than that? Oh, yea! For starters, there is a pattern consisting of only five cells in its initial configuration, which gets to live for 1103 epochs before disintegrating into a predictable arrangement of 6 gliders and several oscillators. Click on figure 11 to watch it in action.

Figure 11. The r-pentomino

The pento- in pentomino comes from pente, the Greek word for five, and that's because it has five cells (arranged in the shape of a lowercase r; likewise, hepta is Greek for seven, which is the number of cells of a b-heptomino). With a suitable search program it can be shown that the r-pentomino is the longest living pattern among all those that start with five cells. Such patterns are often called Methuselahs, from the biblical figure in Jewish mythology who presumably lived longer than any other person. Is the b-heptomino a Methuselah for seven-cell patterns? Not really. That honor goes to a pattern known as acorn, probably because acorns are the tiny seeds of huge oak trees. The acorn keeps thriving for 5206 epochs before disintegrating into a predictable collection (often called the debris of the pattern).

Figure 12. The acorn

The acorn generates over a hundred oscillators, and 13 gliders (the purple little creatures) which escape to the "outer space". It also generates a few more gliders which crash within the other existent patterns (oscillators, active patterns, or occasionally other gliders). If you pay close attention to the way activity develops in the Game of Life, you'll notice a transient pattern of activity which occurs over and over again. It is caused by the pi-heptomino, a pattern of seven cells arranged like a Greek letter pi, which moves for a short time in one direction before dying off. Let's see the pi-heptomino in action, in slow motion.

Figure 13. The pi-heptomino

That's it. That's all the pi-heptomino does. It doesn't generate any gliders, but by being propelled for a short time in the direction the letter pi points to, it "disturbs" other patterns which lay dormant (e.g., oscillators) and invigorates them, potentially causing more activity. This is not, of course, the only mechanism that generates and re-generates activity, just a very commonly occurring one.

Did you notice that the pattern generated by the pi-heptomino is symmetric? This is a general observation for this kind of cellular automata: once we start with a symmetric pattern, we continue with symmetric development forever. Here is another, little-known, symmetric pattern, which shows how much can be caused by so little. I've dubbed it the little bang, (reminiscent of the Big Bang, starting stage of the real universe), for its ability to generate a large number of gliders that keep expanding in space.

Figure 14. The little bang

Our tour of vigorous and long-living patterns would not be complete without mentioning the Methuselah for 9 cells. It's an amazing pattern that develops for 17331 epochs before retiring to predictability. Discovered in 1986 by Andrew Trevorrow using a search program, it's called rabbits, making reference to the well-known ability for prolific multiplication by the lovely mammals. The pattern is shown in figure 15 (in rather fast motion, lest you get bored watching those cells multiplying).

Figure 15. Rabbits

By the way, did you notice that the activity in patterns such as the acorn and rabbits sometimes seems to decelerate, other times seems to accelerate? This is an artifact of the way our program (which runs when you click on each figure) keeps track of the active patterns: when there are lots of them it slows down; when there are few it speeds up, because it stops paying attention to oscillators and other debris. This is an inherent feature of our program -- there is nothing we can do (short of rewriting it from scratch) to make its speed uniform.

Another note on running these figures: If you leave figures in "running" mode, your computer spends part of its computational time and resources for their animation. It's very few resources that are allocated for each figure, but you may notice a slow-down if you leave lots of them running on this page. It's best to stop running each one after you've seen it (just click once on it).

Gliders and Spaceships

What causes a glider to glide? It's the mere repetition of the same five cells, four epochs later, and one step further in a diagonal direction. That is, the five cells of the glider get displaced left-or-right and up-or-down four epochs later. Let's see this in slow motion.

Figure 16. Gliders: the four stages of their motion

Figure 16 shows the four successive steps of a glider which moves in the up-right direction. The orientation of the "corner" of the glider (in stages 1 and 3 in figure 16) tells us in which direction the glider will move.

Gliders are not the only patterns that glide in the Game of Life. They're just the simplest ones. Actually, there is an infinity of gliding objects, collectively called spaceships. Probably the most well-known spaceships after the glider are the three fish, more often called the light-weight, middle-weight, and heavy-weight spaceship. We see them (in that order, from top to bottom) in the figure that follows.

Figure 17. Three fish, or: light-weight spaceship (LWSS), middle-weight spaceship (MWSS), and heavy-weight spaceship (HWSS)

Such creatures may glide not only in isolation, but in whole "schools of fish". The following figure shows two HWSS (heavy-weight spaceships, or "big fish") in-between of which there is a tiny fish, even smaller than a LWSS. This extra-light creature cannot exist in isolation; it needs its bigger companions for support. Built by Hartmut Holzwart.

Figure 18. A school of fish: how about "a child accompanied by its parents"?

While we are still on the subject of marine biology, let us mention that creatures can be both larger, and with varying speeds. The following figure shows various possibilities (due to Tin Coe, David Bell, Hartmut Holzwart, and Dean Hickerson): a rather slow "lobster", a "fish" (with fins and a nice tail) which attacks a "crab". The latter back-steps, with its huge pincers threatening the fish, but because it moves slower the two of them crash against each other. Soon, the lobster joins their debris, producing a seafood salad of various oscillators. Enjoy!

Figure 19. More marine life: a lobster, a huge fish, and a back-stepping crab

Is this all that gliders and other spaceships do? Just sail across space as long as they do not bump on anything else? Not quite; things can be a bit more complex than that. In particular, there are several interesting reactions that can take place between moving objects, provided the objects are precisely put in space. In the following figure we see three well-known reactions, in each of which three gliders collide and create a fish, one each of a LWSS, a MWSS, and a HWSS. The dotted lines are there simply to place a border around the gliders of each reaction. (Borders made in this fashion disappear immediately after the first step.)

Figure 20. Three "reactions", resulting in a LWSS, a MWSS, and a HWSS

Another famous and very simple reaction is the "eating up" of a glider by... what else: an "eater" (one of the still lives shown in the top row of figure 3, otherwise known as "fishhook"). Here it is:

Figure 21. Disappearance of a glider by an eater

It may seem very simple, but you'll see this reaction over and over again, in complex "engines" that work by putting such simple concepts together. Eaters are generally quite resilient to disturbances, not only by gliders, but by various other kinds of patterns.

Gliders can be deflected to any angle along the two diagonal directions in which they move, and even be converted to fish! The latter can be deflected, too. The following figure shows all three of these reactions.

Figure 22. A glider deflected 90 degrees, turns to a fish, which gets deflected, too

Figure 22, above, shows a lone glider (close to the center-right of the figure) which marches towards an oscillator, very similar to the "queen bee shuttle" (see figure 9), except that instead of a pair of blocks the queen bee moves between a pair of eaters. As soon as the glider reaches this structure it gets deflected 90 degrees and starts moving up and left, towards the left "b-heptomino shuttle" (we have seen it again in figure 9). Once there, the glider is turned to a small fish (a LWSS). The fish marches towards the right, and as soon as it reaches the right "b-heptomino shuttle" it gets deflected upwards, starting its jurney to the outer space, never to return (unless you reset the figure that is, by "dragging" with your mouse anywhere on its surface).

Notice that during all these reactions the "parts" which constitute this simple engine remain intact! This is an almost absolute requirement for any engine. If the parts of an engine change in any way, the result has better to be meaningful, or else the engine will cease functioning.

Fish can also be converted back to gliders, when reacting against each other in a headlong collision. The following figure puts these ideas together, having two pairs of lines of gliders being converted to fish, which then crash against each other, producing the same gliders with which the whole thing started, resulting in an infinite loop! Due to Bob Wainwright.

Figure 23. "Double-X": from gliders, to fish, and back again

Guns

Until now, whenever we wanted to have a glider, a fish, etc., we had to insert it wherever needed. The only exceptions were the reactions in figure 20, where some fish were created out of gliders. Is there a way to have any number of gliders or other creatures created repeatedly? The answer is yes, and such engines are called guns. Not only this is possible, but it is also possible to make guns shooting gliders with practically any period. Let us see first a gun that is very similar to the engines we encountered in figure 22.

Figure 24. A glider gun with a period of 46 epochs

Notice that this is very similar to the "deflectors" in figure 22. The gun of the previous figure can be combined with the glider-to-fish converter of figure 22, to make a gun of little fish. Here it is.

Figure 25. A fish gun

Once again, the bottom engine in figure 25 (the glider gun) is the same as the one in figure 24, but shown at a different epoch. Similarly, the engine on the left (the glider-to-fish converter) is the same as the one in figure 22, but at a different epoch in its development.

A small modification in the engine of figure 24 has a dramatic effect: just moving the left block a bit up and stepping the two structures on the left (the ones that look like a C and G) one epoch back in time, tunrs the engine into a bi-directional gun (due to Bill Gosper). Here it is.

Figure 26. A bi-directional glider gun (46 epochs, engine similar to figure 24)

We give below a gun of a different period, lest you think that all guns have a period of forty six. What do you want? Forty seven? All right, forty seven it will be!

Figure 27. The AK47, a period-47 bi-directional gun

The gun in figure 27 (by Richard Schroeppel and Paul Callahan, 1994) takes its name from a real gun, the well-known AK47.

Finally, we give below two rather more complicated guns that shoot in all four directions (both due to David Buckingham, 1991) . The one on the left has a period of 144, while the period of the one on the right is 168. No, their gliders do not create catastrophic debris, although they occasionally crash against each other. Try it!

Figure 28. Two star-guns, of periods 144 (left) and 168 (right)

Is there any smaller star-like gun? I am not aware of one. If yes, what could the smallest one be?

Puffers

Another interesting engine is the so-called puffers. These are creatures that move in one direction, but leave a trail of other structures behind (usually oscillators). In the figure that follows, the puffer creates a trail of blinkers.

Figure 29. A blinker-puffer

In the following variation of figure 29, a HWSS (large fish) eats up the left-over blinkers.

Figure 30. A HWSS eats up the blinkers of the puffer

Want some more exciting object than a mere blinker to be left behind? Below, a puffer made out of a school of fish produces pulsars! (figure 5)

Figure 31. A pulsar-puffer!

An interesting variation of a puffer the trail of which is deleted by something else is one in which the deletion leaves an occasional structure behind. In the following figure, due to David Bell, a school of fish produces a trail of blinkers, which are eaten up by a structure. The deletion is not absolute though, leaving behind a vertical bi-block (figure 3, top row). In the end, the entire pattern can be construed as a very slow puffer of bi-blocks.

Figure 32. A very slow bi-block puffer

Finally, we present below a different kind of puffer: one that leaves behind not a single line of oscillators, but a profusion of still-lives, gliders, and all kinds of other pieces of debris (including occasional pulsars, if you have the patience to wait up to epoch 2217, when the first one is formed). This one is called line puffer. It is due to Hartmut Holzwart and Al Hensel, and because its trail is extremely complex you'll have the option to interact more effectively with the figure. On the top of the figure you see a row of buttons. Click on the play-button: to get the puffer moving, and on the same button later (appearing like this: ) if you want to pause. (Notice: the interface is different now, compared to all the other figures in this page.) The right-most button (the one with the down-pointing triangle, and the magnifying glass on its left) allows you to use a different zoom-level. This is useful because the line puffer grows rightwards and creates ever more intricate patterns, which you may want to look at from close up or from some distance. (We give the default zoom level as 1, meaning that each cell occupies exactly one pixel on your screen, which makes the pattern a bit smaller than zoom level 2, which is what you've been accustomed to in most other figures in this page.) Finally, notice that there are scroll bars in the figure, so you can scroll to the right (for example) and see later parts of the puffer.

Figure 33. Line puffer of width 33: a very dirty fellow

Is the trail produced by line puffer periodic? That is, ignoring gliders that fly off to the outer space, is there a part along the trail of thousands of oscillators that repeats itself? The answer is yes, but you need to run figure 33 for a very long time to see it. (You'll also need a zooming factor of around 1/8 to see at least two parts of the period.) The initial part of the trail looks utterly random.

There are other puffers that you can load through figure 33. First pause the running pattern by clicking on the pause button (), then click on the open-input button () to get the dialog box prompting you with the input pattern to load. Select either Line puf 2 from the list (a variation of the line puffer) or Puffer train (a rather different, but still dirty fellow) to see other puffers.

In case you want to examine the rest of the patterns provided by the open-input button in figure 33, but you are bothered by the width and height of the space, you may go to this page, which allows you to control the dimensions and provides the same functionality as figure 33.

Rakes

Suppose we combine the idea of a gun, with that of a puffer. The result would be a trail that consists not of oscillators, but of spaceships (e.g., gliders). Therefore, a moving trail. Can such a structure exist? You guessed it, it can else we wouldn't include this paragraph, right? and it is called a rake. Here is a simple example.

Figure 34. A dense glider-rake

There can be rakes with various differing attributes: having dense or sparse trails of spaceships, differing directions of spaceship movement, differing speeds, double, triple, or multiple rakes... you name it. What exists is limited only by our imagination, and by the finite amount of time devoted by various explorers in discovering such structures.

The composition of various concepts that we presented so far (as well as other ones that we don't have the space to analyze) can be continued virtually to any desired degree of complexity. As one example, we show below a rake of puffers. That is, what we have is a rake that leaves behind a trail, which consists not of spaceships, but of entire puffers. First, let us see what the puffer looks like, and then we'll see the engine (the rake) that constructs and leaves behind such puffers! Okay, the puffer is called a switch engine, and its creator is Charles Corderman.

Figure 35. Corderman's switch engine (a kind of puffer)

A switch engine, by the way, is believed to be the smallest forever-growing pattern in the Game of Life.

Now, the rake that constructs switch engines and leaves them behind was designed by Helmut Postl, in 1997, and is shown in the following figure.

Figure 36. Postl's switch engine (puffer) rake

Impressive, isn't it? So, Are there any limits? Can we design really anything we want?

It seems that the answer would be, rather unexpectedly, YES! In fact, this is an unqualified YES, one that is given with mathematical certainty. Here is why:

In the year 2000, Paul Rendell constructed a Turing Machine in the Game of Life. A so-called Universal Turing Machine, proposed by the father of modern computer science, the British mathematician Alan Turing in the first half of the 20th century, is the mathematical model of computation: all present-day computers can be shown to have no more computational power than a Universal Turing Machine in the sense that there is no function that can be computed by your personal computer (or a state-of-the-art super-computer) and cannot be computed by a humble Turing Machine. (It is another issue how fast it can be computed; Turing Machines are extremely slow compared to real computers, but then, they are only a model of computation, a tool through which we measure certain facts about computation, not a real instrument we can use to do practical number-crunching work.) According to the so-called Church-Turing Hypothesis, we can never hope to design any "better", or more capable computer than a Turing Machine. This is not because Church and Turing were so proud of their concept of a Turing Machine, but because every effort to build a different model ended up having exactly the computational power of a Turing Machine. So, computer theorists gave up on building new models at some point, and proclaimed that it seems (without proof) that a Universal Turing Machine is the ultimate model of computation. Most researchers in artificial intelligence (AI) and cognitive science, including the author of this text, believe that the human mind, as well, does not have any more computational capabilities than a Universal Turing Machine. (Actually, it is inferior to a Universal Turing Machine in general, in terms of what it can reliably compute, but it is damn good at some computations significant for biological survival; so good, in fact, that we have not been able to even approach the mind's achievements in those areas by present-day software and computers, although we have surpassed it in other areas such as chess-playing that are biologically irrelevant.)

What does all the above mean? Simply put, if we have a Universal Turing Machine, it is like having at our hands any computer, even the most powerful one. As mentioned above, Paul Rendell designed such a Turing Machine by using components (engines) from the Game of Life. (The structure is too large to be included in this introduction.) Now, Rendell's is a specialized Turing Machine, not a Universal one. (Specifically, it is one that duplicates a pattern of zeros and ones.) However, the mere existence of a specialized Turing Machine gives everyone confidence that a Universal one can be constructed, as well. Rendell himself (as well as probably others) is working towards this goal, as far as I know. The conclusion is that in principle (and note please this emphasis) it is possible to construct in the Game of Life patterns that emulate any conceivable computation, including the one of the browser that you use now, and through which you read these lines; including, according to this author's opinion, even the workings of a human mind! Well, in principle, at least.

Back to the main page of the Game of Life