Life
The most well-known Cellular Automaton, invented by John Conway and popularized in Martin Gardner's ScientificAmerican column starting in October 1970. The game was originally played (i.e., successive generations were produced) byhand with counters, but implementation on a computer greatly increased the ease of exploring patterns.
The LifeAutomaton is run by placing a number of filled cells on a 2-D grid. Each generation thenswitches cells on or off depending on the state of the cells that surround it. The rules are defined as follows. All eightof the cells surrounding the current one are checked to see if they are on or not. Any cells that are on are counted, andthis count is then used to determine what will happen to the current cell.
- 1. Death: if the count is less than 2 or greater than 3, the current cell is switched off.
- 2. Survival: if (a) the count is exactly 2, or (b) the count is exactly 3 and the current cell is on, the current cell is left unchanged.
- 3. Birth: if the current cell is off and the count is exactly 3, the current cell is switched on.
A pattern which does not change from one generation to the next is known as a Still Life 
, and is said to have period1. Conway originally believed that no pattern could produce an infinite number of cells, and offered a $50 prize to anyone whocould find a counterexample before the end of 1970 (Gardner 1983, p. 216). Many counterexamples were subsequently found,including Guns and Puffer Trains .
A Life pattern which has no Father Pattern is known as a Garden of Eden (for obvious biblical reasons). The first such pattern was not found until 1971, and at least 3 are now known. It is not, however, known if a pattern existswhich has a Father Pattern , but no Grandfather Pattern (Gardner 1983, p. 249).
Rather surprisingly, Gosper and J. H. Conway independently showed that Life can be used to generate a UniversalTuring Machine (Berlekamp et al. 1982, Gardner 1983, pp. 250-253).
Similar Cellular Automaton games with different rules are HexLife and HighLife.
See also Cellular Automaton, HashLife, HexLife, HighLifeReferences
``Alife online.'' http://alife.santafe.edu/alife/topics/cas/ca-faq/lifefaq/lifefaq.html. Berlekamp, E. R.; Conway, J. H.; and Guy, R. K. ``What Is Life.'' Ch. 25 in Winning Ways, For Your Mathematical Plays, Vol. 2: Games in Particular. London: Academic Press, 1982. Callahan, P. ``Patterns, Programs, and Links for Conway's Game of Life.'' http://www.cs.jhu.edu/~callahan/lifepage.html. Flammenkamp, A. ``Game of Life.'' http://www.uni-bielefeld.de/~achim/gol.html. ``The Game of Life.'' Math Horizons. p. 9, Spring 1994. Gardner, M. ``The Game of Life, Parts I-III.'' Chs. 20-22 in Wheels, Life, and other Mathematical Amusements. New York: W. H. Freeman, 1983. Hensel, A. ``A Brief Illustrated Glossary of Terms in Conway's Game of Life.''http://www.cs.jhu.edu/~callahan/glossary.html. Hensel, A. ``PC Life Distribution.'' http://www.mindspring.com/~alanh/lifep.zip. Hensel, A. ``Conway's Game of Life.'' Includes a Java applet for the Game of Life. http://www.mindspring.com/~alanh/life/. Koenig, H. ``Game of Life Information.'' http://www.halcyon.com/hkoenig/LifeInfo/LifeInfo.html. Poundstone, W. The Recursive Universe: Cosmic Complexity and the Limits of Scientific Knowledge. New York: Morrow, 1985. Toffoli, T. and Margolus, N. Cellular Automata Machines: A New Environment for Modeling. Cambridge, MA: MIT Press, 1987. Wainwright, R. T. ``LifeLine.'' http://members.aol.com/life1ine/life/lifepage.htm. Wainwright, R. T. LifeLine: A Quarterly Newsletter for Enthusiasts of John Conway's Game of Life. Nos. 1-11, 1971-1973.
- Semisimple Ring
- Semistable
- Sensitivity
- Sentence
- Separating Edge
- Separating Family
- Separation
- Separation of Variables
- Separation Theorem
- Separatrix
- Septendecillion
- Septillion
- Sequence
- Sequency
- Sequency Function
- Sequential Graph
- Series
- Series Expansion
- Series Inversion
- Series Multisection
- Series Reversion
- Serpentine Curve
- Serret-Frenet Formulas
- Set
- Set Difference