<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<title>LucidLife: Notes on the Life Pattern Archive</title>
<link rel="stylesheet" type="text/css" href="style.css">
</head>
<body>
<h1>Notes on the Life Pattern Archive</h1>
<p>
<i>Alan Hensel -- alhensel (at) mindspring.com</i>
<p><br>
<h2>What is the meaning of LIFE?</h2>
<p>
LIFE is a classic computer game. It was invented by John H. Conway in 1970,
and has entertained many hackers and wasted many years of computer time ever
since. If you're smart and creative, it can be very intellectually
stimulating. It's a simulation game which can generate strange and beautiful
patterns, sometimes in complex and interesting ways. Yet the rules of Life are
delightfully simple:
<p>
<ul>
<li>The game is played on a 2-dimensional grid. Each square, or "cell", can be
either "on" or "off".
<li>If a cell is off and has 3 neighbors (out of 8), it will become alive in
the next clock tick.
<li>If a cell is on and has 2 or 3 neighbors, it survives; otherwise, it dies
on the next clock tick.
</ul>
<p>
For example, consider the following pattern:
<p>
<center><img src="blinker_vertical.gif" width="52" height="52" alt="[Vertical Blinker]"></center>
<p>
Notice that the cells in the middle on either side are off and have 3
neighbors: they will come alive. But the two live cells on the ends each have
just 1 neighbor; they will die of loneliness.
<p>
So the next generation is:
<p>
<center><img src="blinker_horizontal.gif" width="52" height="52" alt="[Horizontal Blinker]"></center>
<p>
<h2>LIFE is like a box of chocolates....</h2>
<p>
Since Life begins as a blank canvas, there is no end to the possible ways to
be creative with it. Variety is the spice of Life!
<p>
It's common to start out by drawing random junk and seeing what it turns into.
You can also draw lines, boxes, your name, etc.
<p>
Some of the patterns in the collection are like puzzles to figure out: How do
they work? And how would anyone create such a thing? For example: Random Gun,
Breeder 1? What happens when you change just one little cell...? OK, that's fun
for a while. You get familiar with the common stuff -- the stable patterns,
the blinkers, the movers and the shakers.
<p>
Then there's the engineering approach: try to invent a pattern that does
something interesting. This is a challenge -- the Game of Life is definitely
not horseshoes or hand grenades! Ever hear of the Butterfly Effect?
<p>
For example, try to create one long, snaking line that remains perfectly
stable. Along the way, you will discover rules, like the offset-by-2 rule...
You'll know what that is when you find it.
<p>
Or you can try to create "billiard table configurations." These are mostly
stable, with just a few cells blinking or bouncing around inside. Here's an
example of a billiard pattern:
<p>
<center><img src="billiard.gif" width="137" height="86" alt="[Billiard Animation]"></center>
<p>
Other patterns involve gliders -- generating them, bouncing them around,
absorbing them, and generally using them for your general amusement. Gliders
look like this:
<p>
<center><img src="glider.gif" width="86" height="86" alt="[Glider]"></center>
<p>
There are other moving objects ("spaceships"). In this pattern collection, I
put them in "aquariums", called "Aquarium xx", where xx is their speed. They
are so hard to create that nearly every one of them had to be found by
computer search programs. No human could possibly be expected to find a unique
new spaceship (try it!). Although, sometimes parts can be recognized and mixed
and matched with other parts, to make hybrid ships and other new stuff.
<p>
If enough spaceship pieces can be correlated, you can form what is called a
"grammar": the pieces are like words in a sentence, which can only go in a
certain sequence according to syntactic rules, and can form spaceships of any
length. In the patterns in LIFEP, most of this redundancy has been omitted and
left for you to discover, because otherwise there would be an infinite number
of patterns. Not good for hard disk space.
<p>
It's easy, though, to play with wicks. Wicks are long stable repetitive
patterns that can "burn" at one end. You can try to go make them go around
corners, branch out, explode a bomb...
<p>
And once you've tried all that, you can go back to the patterns in LIFEP and
gape in amazement!
<p>
You can also set up betting games. For example, pick a gun, then put something
in its line of fire.... One of 3 things must happen:
<p>
<ul>
<li>The gun blasts thru the pattern -- but sometimes only after a long
struggle. The debris sizzles out and the gun is victorious.
<li>The gun is lapped up by the flames.
<li>An "eater" pattern appears, swallowing bullets forever.
</ul>
<p>
Place your bets!
<p>
This is fun with Sawtooth 4. Another good betting game is to put a fleet of
spaceships in the path of some debris (Aquarium 25b is best for this, in my
opinion), and bet how many of them will survive.
<p>
Or, if you're really smart and have some time on your hands, you can ponder
the more intellectual questions, like: Can a pattern in the Life universe be
built that reproduces as though it were really alive? (Exactly what kind of
patterns can be built, anyway? For example, can they be Turing-complete? The
answer to this last one is "yes". Now find the proof. Better yet, write a C
compiler whose target language is Life instead of Assembly!) And how is
entropy in the Life universe related to entropy in our own universe? Can any
of the laws of thermodynamics apply to a universe that does not observe
conservation of mass and energy?
<p>
In the Life universe, is there an irresistible force? The answer is "no",
because otherwise you could oppose two of them. Alright, but is there an
immovable object? That is, can you surround a cell with some kind of "wall"
such that no matter what you put outside the wall, the state of that cell can
never change? That question remains unanswered.
<p>
A pattern that has no predecessor ("father") is called a Garden of Eden
pattern. What is the smallest one? A satisfactory one is in the collection
("Garden of Eden"). Another question: Is there a pattern with a parent but no
grandparent? (This question is trickier than it sounds at first.) In general,
is there a pattern with an immediate predecessor but without an infinite
sequence of ancestors? Is there a stable pattern that is its only predecessor?
<p>
What is the smallest object (measured by number of initial "on" cells) whose
population grows unboundedly? The current record is the Switch Engine, which
starts with only 11 cells. What is the smallest object that grows
quadratically? The current record is Jaws with 150 cells.
<p>
The average density that a random field will settle to, from 1/2 density, is
about 1/(34.83 +/- .02), as measured by Achim Flammenkamp. What is the highest
possible average density of a periodic field? It is conjectured to be 1/2, and
proven to be between 1/2 and 8/13, inclusive. If the maximum is really more
than 1/2, then the growth rate of spacefillers may not really be the max!
<p>
For each positive integer T, what's the largest possible quotient of the
population in gen T divided by the population in gen 0? (For T=1, we can get
arbitrarily close to 3, but can't reach it. For T=2, the upper bound again
seems to be 3, but is unproven.)
<p>
How many distinct 3-glider collisions are there? 4-glider? 5?
<p>
Some yet-unfound but sought-after objects: A c/6 orthogonal spaceship, a c/3
diagonal flipper spaceship, a c/6 knightship (2 up, 1 over in 6 generations).
An oscillator with a natural period of 19, 23, 27, 31, 33, 34, 37, 38, 39, 41,
43, 49, 51, 53, or 57. A way to grow an infinite spiral-shaped object. Some
method for lightspeed fuses (such as in "Wire") to interact with other known
objects, such as glider streams. A glider synthesis for a Cordership, a glider
synthesis for a dart (c/3), or a glider synthesis for the smallest c/4
spaceship.
<p>
It would be interesting to find a collision of a glider with a stable pattern
that leaves the pattern displaced in a certain direction and emits a glider
back. If a few of those were found, then some combination of them might be put
together to create a brand new kind of spaceship -- slow, with variable speed.
<p>
That's the end of my suggestions, but by no means the end of the possible ways
to play the game. Discover your very own "way of Life".
<p><hr><p>
<h2>More Enlightenment</h2>
<ul>
<li>Berlekamp, Conway, and Guy: Winning Ways (for your Mathematical Plays),
Volume 2, (c)1982. ISBN 0-12-091152-3.
<li>Dewdney, A.K.: The Armchair Universe, (c)1988. ISBN 0-7167-1939-8 pbk.
<li>Gardner, Martin: Wheels, Life, and Other Mathematical Amusements, (c)1983.
ISBN 0-7167-1589-9.
<li>Gutowitz, Howard: Cellular Automata: Theory and Experiment, (c)1991. ISBN
0-262-57086-6.
<li>Poundstone, William: The Recursive Universe, (c)1985. ISBN 0-688-03975-8.
<li>Preston, Duff: Modern Cellular Automata
<li>Sigmund, Karl: Games of Life
<li>Wolfram, Stephen: Theory and applications of cellular automata, (c)1986.
ISBN 9971-50-124-4 pbk.
<li>BYTE magazine: Sep 75, Oct 75, Dec 75, Jan 76, Dec 78, Jan 79, Apr 79, Oct
80, Jul 81.
<li>Complex Systems: Bays, Carter: (various articles on 3-D life) Apr 87, Dec
87, Dec 90, Feb 91, Oct 92.
<li>Recreational Computing: May/Jun 79.
<li>Reviews of Modern Physics, Vol. 55: Stephen Wolfram: "Statistical
Mechanics of Cellular Automata."
<li>Scientific American: Oct 70, Nov 70, Jan 71, Feb 71, Mar 71, Apr 71, Nov
71, Jan 72, Dec 75, Mar 84, May 85, Feb 87, Aug 88, Aug 89, Sep 89, Jan 90.
<li>"LifeLine: A Quarterly Newsletter for Enthusiasts of John Conway's Game of
Life", nos. 1-11, 1971-1973. These issues are probably still available. Write
to:
<blockquote>
Robert Wainwright (ed)<br>
LifeLine<br>
12 Longvue Ave.<br>
New Rochelle, NY, 10804<br>
</blockquote>
<li>On the Internet, there is a newsgroup called <a
href="news:comp.ai.alife">comp.ai.alife</a>, and another called <a
href="news:comp.theory.cell-automata">comp.theory.cell-automata</a>. Neither
deal directly with Conway's Game of Life, but with related topics.
<li><a href="http://www.radicaleye.com/lifepage/lifepage.html">Paul Callahan's
Page of Conway's Life Miscellany</a>
<li><a
href="http://dir.yahoo.com/Science/artificial_life/cellular_automata/">Yahoo:
Cellular Automata</a>
</ul>
<p><br><hr><p>
<center>DISCLAIMER</center>
<p>
CONWAY'S GAME OF LIFE DOES NOT DISCRIMINATE ON THE BASIS OF GENDER, RACE,
CREED, NATIONALITY, OR BELLY-BUTTON TYPE. THE GAME OF LIFE IS ENVIRONMENTALLY
SAFE. LIFE PATTERNS ARE 100% RECYCLABLE.
<p>
DO NOT BE INTIMIDATED BY THESE PATTERNS! THEY ARE THE BEST OF THE BEST, AND
YOU CAN FIND JOY IN LIFE WITHOUT MATCHING THEIR QUALITY. IF, HOWEVER, YOU ARE
SO INCLINED, HAVE FUN, BUT BE FOREWARNED THAT IT MAY TAKE MANY HOURS AND SOME
KIND OF GENIUS/NUT.
<p><hr><p><br>
Thanx go out to:
<p>
John Conway, the British mathematician who invented the game;<br>
Dean Hickerson, who not only helped me build this awesome pattern collection,
but also created many of the patterns;<br>
Jon C.R. Bennett and his henchmen at Carnegie-Mellon University; Other pattern
authors (certified geniuses/nuts): Bill Gosper, Dave Buckingham, Mark Niemec,
Hartmut Holzwart, David Bell, Rich Schroeppel, Tim Coe, Dieter Leithner, Achim
Flammenkamp, et al.; And thanks also to everyone else who has contributed
along the way.
</body>
</html>
