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.
  1. 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).
  2. Achim Flammenkamp has a lot of statistics about the objects produced from a random initial state at: http://www.uni-bielefeld.de/cgi-bin/php/~achim/gol.html
  3. 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: http://www.pentadecathlon.com/LifeInfo/LifeInfo.html
  4. Mark D. Niemiec has lists of possible small still lifes as well as methods for creating many of them from gliders at: http://home.interserv.com/~mniemiec/lifepage.htm
  5. Stephen Silver is the current maintainer of the Life Lexicon, which lists most of the Life terms you're likely to see, at: http://www.cs.jhu.edu/~callahan/lexiconf.htm
  6. The "enclosed block" was designed (9/13/98) by Noam Elkies as the smallest example of one island enclosing another, after H. König. 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.
  7. This definition was first proposed by Mark D. Niemiec.
  8. For an example of water traffic crossing a dam, see: http://www.ils.nwu.edu/~eric/matt.html
  9. There are many good introductions to combinatorial graph theory, for example Chapters 6 and 7 of Introduction to Combinatorial Mathematics by C. L. Liu.
  10. For example, see chapter 23 and problem 23-2 in Introduction to Algorithms by Cormen, Leiserson, and Rivest.
  11. 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).
  12. 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: http://www.mathematik.uni-bielefeld.de/~sillke/PROBLEMS/Twixt_Proof_Draft 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.
  13. 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: http://www.paradise.caltech.edu/~cook/Warehouse/StillLifeLinks.html

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.