References for Still Life Theory
Although many of the references do not refer explicitly to web pages,
there exists a relevant web page for almost all of them.
John Conway wrote an exposition of Life, including a sketch
of how one might build a universal computer within it, in
Winning Ways For Your Mathematical Plays, Volume 2,
by E. Berlekamp, J. Conway, and R. Guy (Academic Press, 1982).
Achim Flammenkamp has a lot of statistics about the
objects produced from a random initial state at:
H. Koenig has lists of possible small still lifes with constructions
for many, as well as their frequencies of occurrence from a random
initial state at:
Mark D. Niemiec has lists of possible small still lifes as
well as methods for creating many of them from gliders at:
Stephen Silver is the current maintainer of the Life Lexicon,
which lists most of the Life terms you're likely to see, at:
The "enclosed block" was designed (9/13/98) by Noam Elkies
as the smallest example of one island enclosing another, after
The ``fragile four'' is based on a pattern designed (9/27/98)
by Gabriel Nivasch as one of the smallest known of this kind,
after the author.
The ``switch'' was originally found in the early 1970's, either
by Peter Raynham or by David Buckingham.
This definition was first proposed by Mark D. Niemiec.
For an example of water traffic crossing a dam, see:
There are many good introductions to combinatorial graph theory,
for example Chapters 6 and 7 of
Introduction to Combinatorial Mathematics by C. L. Liu.
For example, see chapter 23 and problem 23-2 in
Introduction to Algorithms
by Cormen, Leiserson, and Rivest.
The original proof:
K. Appel, W. Haken, and J. Koch,
Every planar map is four colorable,
Illinois J. Math 21 (1977) 429-567.
And a more recent simpler one:
N. Robertson, D. P. Sanders, P. D. Seymour, and R. Thomas,
A new proof of the four color theorem,
Electronic Research Announcements of the American Mathematical Society
2 (1996) 17-25 (electronic).
Dominic Mazzoni and Kevin Watkins wrote a proof that the problem of
deciding whether a position in the game of Twixt is a winning position
or not is NP-complete, currently available at:
Their proof effectively showed that the problem of determining whether
there is a simple non-crossing path between two given points in a planar
layout of a graph is NP-complete.
Their proof very directly inspired
the proof in Section 5
of the NP-completeness of Switch-Simple Loop.
Local Lattice Languages are presented and discussed in:
K. Lindgren, C. Moore, and M. Nordahl,
Complexity of Two Dimensional Patterns,
Santa Fe Institute Working Paper 97-03-023.
Many of the items here refer to web pages,
which unlike items published on paper and stored in libraries,
can easily change or disappear without notice.
To help ameliorate this,
I will maintain a page of links to the web pages cited above at:
The books shown with pictures above are linked directly to pages at
Amazon.com where you can see
more information about them and even buy them if you like.