Two-gliders Fuse

... ;. 4*. ...««... simplest i l l ; r i . a spark a dirty j.

a reverse fuse

Five fuses

Fuse b in Figure 151 oscillates with a period of 4, giving off sparks that fade quickly. A "dirty fuse," like the one shown in c in Figure 151, leaves clouds of debris behind as it burns. At one point it shoots off a glider. Fuse d in Figure 151, named the "baker" by its discoverer, McClelland, is a confused fuse that bakes a string of stable loaves while it burns. The last three fuses all oscillate with periods of 4, and all four burn with the speed of light.

Fuse e in Figure 151, eventually becomes a clean fuse of period 4, but leaves behind a cloud consisting of three blocks, three beehives, two blinkers, a ship, and four gliders. William Woods calls it a "reverse fuse" because it explodes first, then burns quietly for the rest of its endless life. The harvester, described in the previous chapter, is of course a fuse.

Other unusual fuses are shown in Figure 152. Fuse a, found by Steve Tower, has a period of 8. It leaves behind a trail of beacons. Fuse b abandons a twin pair of boats every four ticks. Orthogonal fuse c, which burns with a speed slower than light, consumes two tubs every 18 ticks, then changes them to traffic lights (four blinkers). It was discovered by Earl Abbe. Wain-

• « a • • •• •• •• •• ••

More fuses wright's fuse d consumes three fenceposts every 12 generations, and turns them into a beehive.

Two fuses of a more complicated nature, discovered by Don Woods, are shown in Figure 153. The cow burns at light speed, with period 8, slowly "chewing its cud" by eating the blocks on either side, bringing them back again, then eating them a second time. The two-glider fuse throws off two gliders every 12 ticks. I resist the impulse to describe two close relatives of fuses, the wicks (infinite in both directions) and the kinkbombs. Kinkbombs come in three varieties: duds, firecrackers, and bombs, as detailed by Mark Horton in the 11th issue of Lifeline.

Figure 153

Two remarkable fuses

There are 102 distinct patterns of bits within a 3 X 3 square (excluding rotations and reflections, but including the patterns consisting of nine bits and no bits). Some of these are polyo-minoes, some not. All the letters of the alphabet in Braille are among the 102. The fates of all 102 are known. Also known are the fates of all polyominoes through the order-7 heptominoes.

Methuselah patterns are those of fewer than 10 bits which do not stabilize until after more than 50 generations. Two examples were given in the previous chapter: The 5-bit ii-pen-tomino and the pi-heptomino of 7 bits. The first generation of the pi-heptomino, by the way, reappears in tick 31, but shifted 9 cells. Because of interaction with its exhaust, in generation 61, it fails to make it as a spaceship.

Other examples of Methuselahs are shown in Figure 154. The first one, a is the smallest known. It becomes the i?-pen-tomino in two ticks, giving it a life of 1,105 generations. Methuselah b stabilizes (six blocks, twelve blinkers, one loaf) after 608 generations, c (the thunderbird) lasts 243 ticks, and d goes to 1,108. The heptomino e stabilizes after 148 ticks, having produced three blocks, a ship, and two gliders. The acorn /, found by Charles Corderman, is the most amazing Methuselah known. It lives for 5,206 generations! When it stabilizes as an "oak" of 633 bits, it has produced numerous gliders, 13 of which escape.

Figure 154

; thunderbird

;ACORN

Methusalehs

The Honeywell group tracked the life histories of the first nine members of the 5-cell crosses, of which the simplest are shown in Figure 155. The first is a portion of an infinite trellis

Figure 155

The five-cell cross series consisting of solid horizontal and vertical rows, two cells apart, that surround an infinity of empty 2x2 squares. Like the infinite trellis, this cross vanishes in one tick. The next cross disappears in 8 ticks. The third ends with many traffic lights in 6 ticks, and the fourth stabilizes after 34 ticks with eight blinkers, having produced a truly spectacular display of fireworks along the way. (Its 19th generation is a beautiful ring of blocks with a checkerboard in the center.) Order-5 and order-7 crosses in this sequence stabilize as four pulsars in 31 and 21 ticks respectively, orders 6 and 8 go to four pulsars and a tub in 36 and 21 ticks respectively, and order-9 ends after 42 ticks with 16 blocks and 8 blinkers.

William Gosper, in 1971, found the eater (fishhook), the incredible 7-bit stable form shown with circles in Figure 156. It has the ability to consume an enormous variety of "Life" forms, then quickly repair itself. The first four pictures show the eater about to ingest a glider, blinker, pre-beehive, and a lightweight spaceship. In the fifth picture two eaters are poised to devour one another. This is prevented by their amazing ability to self-repair, so the pattern oscillates with period 3. The last picture shows how two gliders collide to produce an eater on the 13th tick. In recent years eaters of larger size have been discovered, with a variety of bizarre feeding habits.

Figure 156

ai 8o

The eater (circles) and some of its prey

Extensive investigations have been made of different kinds of agars (regular patterns that are infinite in two dimensions), the procrastinators (forms that take more than 50 ticks to become a single simple stable form), and puffer trains. The puffers leave a trail of permanent smoke. Three are shown in Figure 157. The first, discovered by Gosper, is an engine escorted between two lightweight spaceships. It puffs along at half the speed of light until after more than 1,000 ticks it develops a period of 140. Paul Schick discovered an entire family of puffer trains, the simplest of which, shown in b, leaves nothing behind. The pair of mirror-image lightweight spaceships pull alon^ the symmetrical heptomino engine with a period of

248 chapter 22

Figure 157

Puffer trains

12. The switch-engine puffer train c in Figure 157, moves too slowly (one-twelfth the speed of light) to be of much use. It travels diagonally like a glider, eventually producing eight blocks every 288 generations. No escorting spaceships are needed, but without the stabilizing block it's smoke catches up with the engine and destroys it.

The first Garden of Eden pattern, reproduced in Figure 158, was found by Roger Banks in 1971. It required an enormous computer search of all possible predecessor patterns. The confining rectangle (9 x 33) holds 226 bits. The only other Garden of Eden pattern known was found by a French group in 1974, led by J. Hardouin-Duparc, at the University of Bordeaux. It is inside a rectangle of 6 X 122.

Figure 158

Figure 158

A garden of Eden

A garden of Eden

Although any "Life" pattern generates only one successor, the converse is not true. A given pattern may have two or more predecessors. This is why searching for Garden of Eden patterns is so difficult—the computer has to look at all possible predecessors at each backward tick. If the universe eventually turns out to be one monstrous cellular automaton, one may reasonably ask whether there is an initial Garden of Eden state that required a creation because it has no predecessor pattern. By the way, the fact that a "son" of a Garden of Eden pattern may have more than one "father" has led Conway to offer $50 to the first person who can find a pattern that has a father but no grandfather. The existence of such a pattern is still an open question.

The most spectacular of the new developments in "Life" involve gliders and their collisions. Gosper's group found new types of glider guns, more compact spaceship factories produced by glider crashes, and innumerable "Life" forms that eat gliders or reflect them back at different angles. Before its members broke up to go their separate ways, the M.I.T. group managed to complete a 17-minute film about their discoveries that has become a classic.

A pure glider generator is one that generates one or more gliders with no debris left over. Two elegant ones found by the Honeywell group are shown in Figure 159. The biloaf left in four ticks produces two gliders going opposite ways. The 4-8-12 diamond right in 15 ticks forms four gliders headed in four different directions. Half a dozen 5-bit forms turn into a single glider, and more than a hundred 6-bit forms do the same. A search for predecessors of the original Gosper glider gun turned up a pattern of 21 bits that is the smallest known, though it seems possible there may be a way of positioning just four gliders (20 bits) so that they crash and form a gun.

Figure 159

Figure 159

Two glider-generators

Two glider-generators

I mentioned earlier Gosper's way of placing eight guns so that their gliders crash to form a spaceship factory which fires off a middleweight spaceship about every 300 generations. Gosper soon improved this to four guns and one pentadecath-lon. This pattern produces a factory that shoots off lightweight or middleweight spaceships (depending on the timing) every

60 ticks. Wainwright positioned three "newguns" that generate a middleweight spaceship every 46 generations.

Lifenthusiasts have investigated thousands of ways that gliders and spaceships can collide to produce an incredible variety of stable patterns (including the null pattern of nothing at all), as well as patterns that change, and patterns that produce new gliders and/or spaceships. Figure 160 shows some unusual collisions found by the Waterloo group. On the left is the pattern just before the crash; on the right, the outcome after the indicated number of ticks (t = ticks).

The breeder is one of the most remarkable life forms found by the M.I.T. group; remarkable because its population growth is so rapid. Figure 161 is a photograph of a computer scope that shows the breeder breeding gliders. The little dots are gliders, about 1,000 of them inside the triangular region. The breeder consists of ten puffer trains moving east, their exhaust carefully controlled so that they generate gliders that crash to form guns that instantly spring into action along the horizontal axis. The picture shows the breeder at generation 3,333. Thirty guns are firing northeast at a rate of one glider per tick. The firing rate increases without limit until at about tick 6,500 the number of gliders starts to exceed the age of the breeder. Seeing the breeder in action was one of the most awesome high points of my visit to M.I.T.

When I wrote the previous chapter for the February 1971 issue of Scientific American, I raised the question of whether the rules of "Life" permit the construction of a universal computer. I had the pleasure of reporting the next month that "Life" is indeed universal. Gosper at M.I.T. and Conway at Cambridge independently "universalized" the "Life" space by showing how gliders could be used as pulses to simulate a Turing machine. Exactly how this is done is too complicated to go into here, but you will find it clearly outlined by Conway in the second volume of Winning Ways, the book he coauthored with Elwyn Berlekamp and Richard Guy.

The universality of "Life" means that it is possible in principle to use moving gliders to perform any calculation that can be performed by the most powerful digital computer. For example, one can arrange a formation of glider guns, eaters, and other "Life" forms so that a stream of gliders, with gaps in the right places, will calculate pi, e, the square root of 2, or any other real number to any number of decimal places. Of course, it would be a very inefficient way to do such calculations, nonetheless they are possible if you have a large enough field and sufficient ingenuity to build the needed "machine."

In Winning Ways Conway uses Fermat's last theorem to illus-

START

BECOMES

SIX GLIDERS (t=0)

TUB AND FOUR GLIDERS (t=0)

SIX GLIDERS (t-11)

TUB WITH TAIL (t=11)

'SIX GLIDERS AND ! TA LIGHTWEIGHT SPACESHIP ft=0)I

SEVEN GLIDERS, i TWO BLOCKS, AND A BOAT (t=0)

FLOATILLA OF TWO LIGHT-WEIGHT SPACESHIPS BOUNDING OVERWEIGHT SPACESHIP (t=10) ; j

The breeder trate "Life's" computing power as well as its limitations. A "Life" machine can be constructed that will steadily test the values of the four variables in Fermat's famous formula. The program could be designed to halt, say by fading away, if it found a counterexample to Fermat's conjecture. On the other hand, if the conjecture is true, the "Life" machine will keep searching forever for the right combination of values. We know from un-decidability theory that there is no way to know in advance whether any given problem is solvable, therefore there is no way to know in advance whether any given pattern in "Life" will continue to change or to reach a stable end.

In 1981, in a letter telling me he had found "Life" to be universal, Conway added a note on the back of the envelope. "If

(ask Gosper) gliders can crash to form a pentadecathlon, then I can produce self-replicating machines, and it's undecidable whether a given machine is self-replicating."

I cannot remember if I asked Gosper this question, but at any rate, gliders can crash to form pentadecathlons, and Con way states flatly, in Winning Ways, that self-replicating machines can be constructed in "Life" space. We are not speaking now of moving forms like spaceships, but of machines that will build exact copies of themselves. The original machine may either remain in the space or it can be programmed to self-destruct after it has replicated itself. So far as I know no one has built such a machine, but if Conway is right (his proof has not been published), it is possible to build them.

Conway also asserts in Winning Ways that he has proved that "Life" patterns exist which move steadily in any desired rational direction, recovering their initial forms after a fixed number of moves. As for spaceships (which move without producing smoke), no new ones have been discovered other than those already known to Conway in 1970.

Conway goes on to speculate that if you imagine a sufficiently large broth of randomly placed bits, one would expect that by pure chance self-replicating creatures would arise, and those best adapted to survive would live longer than the others. Interactions with the environment would produce mutations. As in organic evolution, most mutations would be harmful, but some would have survival value. "It's probable," Conway writes, "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."

I would prefer the word "possible" here to "probable," but there is no question that "Life's" analogy with biological evolution on earth is remarkable. One science fantasy writer, the widely read Piers Anthony, plays with this theme in his 1976 novel, Ox. Diagrams of "Life" patterns head each chapter, and the book's plot involves intelligent, sentient beings called "pattern entities" or "sparkle clouds" that have evolved by just the process Conway imagines, in a cellular space of dimensions higher than our spacetime. Their behavior is totally determined by transition rules, but like us they imagine themselves to have free wills. There is an amusing Chapter 11 in which Cal explains the rules of "Life" to Aquilon and she experiments with some simple patterns.

"Try this one," Cal suggests, giving her the /?-pentomino:

"That's similar to the one I just did. You've just tilted it sideways, which makes no topological difference, and added one dot."

"Try it," he repeated.

She tried it, humoring him. But soon it was obvious that the solution was not a simple one. Her numbered patterns grew and changed, taking up more and more of the working area. The problem ceased to be merely intriguing; it became compulsive. Cal well understood this; he had been through it himself. She was oblivious to him now, her hair falling across her face in attractive disarray, teeth biting lips. "What a difference a dot makes!" she muttered.

In Chapter 13 Aquilon, still tracking the pattern's fate, exclaims: "This /2-pentomino is a menace! I'm getting a head ache! It just goes on and on." Gosper once said that to him the most impressive aspect of Conway's game is how it demonstrates the impossibility of predicting the outcome of processes that are rigidly determined by extremely simple rules of change. After Aquilón has learned about gliders and glider guns, she remarks: "If I were a pattern, I'd be very careful where I fired my gliders! That game plays a rough game!"

"It does," Cal replies. "As does all nature."

Much work has been done on variants of "Life": playing by other rules, and on other lattices such as triangular or hexagonal, and in dimensions higher than two. One-dimensional "Life" has also been explored—see the articles by Jonathan Miller and Munemi Miyamoto. "Life" has been investigated on wraparound fields that are cylinders and toruses, and even Moebius surfaces and Klein bottles. Some interesting results have emerged, but nothing compares with "Life" in the combination of richness of interesting forms with such simple transition rules. This is a tribute to Conway's intuition, and to the thoroughness with which he and his friends initially explored hundreds of alternate possibilities, including games with two or more sexes. Attempts have also been made to invent competitive games based on "Life," for two or more players, but so far without memorable results.

"Life" may have some practical uses. There have been attempts to apply it to socioeconomic systems, and a generalization of "Life" has been suggested as an explanation of why some nebulas have spiral arms (see the article by Kenneth Brecher). Arthur Appel and Arthur Stein, at IBM, found a way of applying rules similar to "Life's" in programs designed to identify the hidden edges in computer drawings of solid shapes.

I spoke earlier of the possibility that the universe is a vast cellular automaton, operated by the movements of ultimate particles (perhaps not yet discovered) according to unknown transition rules. Physicists are now searching for a GUT (Grand Unification Theory) that will bring together all the forces of nature into one unified theory based on a gauge structure. As physicist Claudio Rebbi explained in his article on "The Lattice Theory of Quark Confinement" (Scientific American, February 1983), a popular approach is to think of the gauge game as being played by particles on an abstract lattice of four-dimensional cubes—a sort of spacetime "Life." This suggestion was made in 1974 by Kenneth Wilson, and is now known as lattice gauge theory.

The game metaphor for GUT carries with it the implication that the basic particles of the universe (pieces), the fundamental laws (transition rules), and spacetime (board) are not logical necessities. They are simply given. It is folly, as Hume and the positivists have taught us, to ask why they are what they are. Like chess players, physicists should accept the game and enjoy their (endless?) task of trying to guess how it is played, not waste energy speculating on why the game is designed the way it is. Now we are back to Leibniz and his stupendous vision of a transcendent Mind, contemplating all possible games, then choosing for our universe the Game that best suits the Mind's incomprehensible purposes.

BIBLIOGRAPHY

On cellular automata theory:

Theory of Self-Replicating Automata. John von Neumann. University of

Illinois Press, 1966. Computation: Finite and Infinite Machines. Marvin L. Minsky. Prentice-Hall, 1967.

Perceptrons. Marvin Minsky and Seymour Pa pert. MIT Press, 1969. Cellular Automata. Edgar F. Codd. Academic Press, 1968. Theories of Abstract Automata. Michael A. Arbib. Prentice-Hall, 1969. Essays on Cellular Automata. Arthur W. Burks ed. University of Illinois Press, 1970.

On the Game of Life:

"Toward a Mathematical Definition of Life." Gregory J. Chaitin. Part

I, ACM SICACT News, Vol. 4, January 1970, pages 12-18; Part 2, IBM Research Report RC 6919, December 1977.

"The Game of Life: Is It Just a Game?" John Barry. The London Times,

Sunday, June 13, 1971. Lifeline, a newsletter on Life. Robert Wainwright ed. Issues 1 through

II, March 1971 through September 1973. "The Game of Life." Time, January 21, 1974.

"Population Explosion: An Activity Lesson." Donald T. Piele. Mathematics Teacher, October 1974, pages 496—502. "Life Games and Statistical Methods." M. Dresden and D. Wang. Proceedings of the National Academy of Science, Vol. 72, March 1975, pages 956-968.

"Life Line." Carl Helmers. Byte, Vol. 1, September 1975, pages 72-80. "Lifeline." Carl Helmers. Part 2, Byte, October 1975, pages 34—42; Part 3, December 1975, pages 48-55; Part 4, January 1976, pages 32-41.

Ox. Piers Anthony. Avon, 1976. A novel involving Conway's Life and hexaflexagon theory.

"Statistical Mechanics of a Dynamical System Based on Conway's Game of Life." L. E. Schulman and P. E. Seiden. IBM Research Report RC 6802, October 1977.

"Self-Organization of Living Systems." Milan Zeleny. International Journal of General Systems, Vol. 4, 1977, pages 13—28.

"Life with Your Computer." Justin Millium, Judy Reardon, and Peter Smart. Byte, Vol. 3, December 1978, pages 45-50.

"Some Facts of Life." David J. Buckingham. Byte, Vol. 3, December 1978, pages 54-67.

"One-Dimensional Life." Jonathan K. Millen. Byte, Vol. 3, December 1978, pages 68-74.

"An Equilibrium State for a One-Dimensional Life Game." Munemi Miyamoto .Journal of Mathematics of Kyoto University, Vol. 19, 1979, pages 525-540.

"Life Algorithms." Mark D. Niemiec. Byte, Vol. 4, January 1979, pages 90-97.

"Life Can Be Easy." Randy Soderstrom. Byte, Vol. 4, April 1979, pages 166-169.

"The Game of Life." Howard A. Peelle. Recreatiorml Computing, Vol. 7, May—June, 1979, pages 16—27.

"Spirals: Magnificent Mystery." Kenneth Brecher. Science Digest, Spring 1980, page 74ff.

"APL Makes Life Easy (and Vice Versa)." Selby Evans. Byte, Vol. 5, October 1980, pages 192-193.

"Life After Death." Pat Macaluso. Byte, Vol. 6, July 1981, pages 326-333.

"What is Life?" Chapter 25, Winning Ways, Vol. 2. Elwyn Berlekamp, John Conway, and Richard Guy. Academic Press, 1982.

0 0

Post a comment