Cellular Automata FAQ


[Non-Java version]

Conway's Game of Life FAQ

Collapse all tree nodesExpand all tree nodes
Expand this node
Expand/collapse
Expand this node
Where do I start?
Expand this node
Expand/collapse
Expand this node
Where do I find a simulator for the Game of Life?
There is a comprehensive list of life simulators on Alan Hensel's site.

Expand this node
Expand/collapse
Expand this node
Can I see the Game of Life in action?
Here is a DHTML/JavaScript implementation of Conway's Game of Life:

Paused
Expand this node
Expand/collapse
Expand this node
Where do I find Game of Life patterns?
Contributions by:
  • Alan W. Hensel <alanh@digital.net>
lifep.zip. Claimed to be the best 152 patterns from the first quarter-century of Conway's Game of Life. Note that this collection has no included program.

The weird pattern collection covers rules other than Conway's standard 23/3.

Expand this node
Expand/collapse
Expand this node
Who is interested in Life?
Expand this node
Expand/collapse
Expand this node
Is Martin Gardner's Scientific American article on Conway's life available?
Yes - see here.

References

[Dew87]

[Dew88]

Expand this node
Expand/collapse
Expand this node
Can you do computations with the Game Of Life?
Yes. The Game Of Life was proved to be computation-universal in the classic work [BCG82].
Expand this node
Expand/collapse
Expand this node
Has anyone actually built a computer in the Game Of Life?
Yes.

For example see the Turing machine in the game of life implementation.

Expand this node
Expand/collapse
Expand this node
How do you do computations with the Game of Life?
Contributions by:
  • Chris Langton <cgl@t13.lanl.gov>
The constructive proof that the game of life is capable of supporting universal computation is built around colliding glider streams into one another. colliding glider streams form the basic AND, OR, and NOT gates, out of which one then goes on to engineer a general purpose computer. However, one need not construct a general purpose computer, one could arrange the same computational primitives into a device that computes only a specific function.

One example, computing the logical NOT of a byte, is straightforward. Arrange for a stream of gliders (the input stream) to collide with the output of a glider gun at right-angles in such a way that the gliders in the input stream occur with the same spacing as the gliders coming from the glider gun. Furthermore, time the arrival of gliders in the input stream so that they collide with gliders in the output of the glider gun and annihilate each other. Then, encode the byte you want to compute the logical NOT of in the following way: For every 0 in the input byte, remove a glider from the input stream, for every 1, leave a glider. Thus, the input byte 10110010 will be represented by the glider stream:

glider noglider glider glider noglider noglider glider noglider

where the "nogliders" are spots where gliders in a regular periodic stream of gliders have been removed.

When this stream is collided into the regular stream of gliders coming out of a glider gun, observe what happens. For every 0 in the input byte, the missing glider in the input stream allows a glider from the glider gun to pass, whereas for every 1 in the input byte, a glider in the input stream annihilates the corresponding glider coming from the glider gun. Thus, looking at the output stream from the glider-gun DOWNSTREAM of the collision site, there is a glider (a 1) for every "hole" in the input stream (a 0) and there is a hole (a 0) for every glider (1) in the input stream. Thus, the filtered output of the glider-gun is the logical NOT of the encoded input stream.

And not a universal computer in sight!

By colliding this output stream (call it NOT A if the input steam is A) with another input stream, B, one gets A AND B in the continuation of the input stream B after the collision site. If one collides the downstream portion of the NOT A stream from this latter gate with the output of another glider gun, one obtains A OR B as the continuation of the second glider gun output downstream of the collision.

By hooking up a sequence of AND, OR, and NOT gates built in this way, one can compute any function that can be expressed by these logical operations (a great many functions indeed....;-)

For complex functions, involving many gates, one needs to cross glider streams, redirect glider streams, and so forth. This leads to more complication. However, the basic idea is as sketched out above.

Contributions by:

  • Wentian, Li <wli@cshl.org>
  • McIntosh, Harold V. <mcintosh@redvax1.dgsca.unam.mx>

Using the interaction of glider streams, the Game of Life can be programmed to perform computations. Indeed, it is a universal computer.

References

[BCG82]
[Pou85]
Expand this node
Expand/collapse
Expand this node
Must one use all of the logical gates to perform computations in the Game of Life?

See: [Jay00] The three logical gates AND, OR, NOT are sufficient for all logical functions, but not necessary. not only two basic gates are enough, one basic gate is also enough! for example, gate NAND, which is ``negation of AND,'' can lead to all three previously considered ``basic'' gates:

another example is the NOR (negation of OR):

the relevance to CA/Game of Life is that the requirement for having three logical gates in a CA rule so that it can do all computations can be (two) too much. at least in principle, having one NAND should be enough for constructing all logical functions.

Expand this node
Expand/collapse
Expand this node
Is the Game Of Life reversible?
No. Many states lead to an empty universe - so information is clearly lost during the evolution of the automaton.
Expand this node
Expand/collapse
Expand this node
Garden-of-Eden patterns exist in Conway's Game of Life. Do they exist in other automata?

Harold McIntosh <mcintosh@servidor.unam.mx>

They exist for the great majority of cellular automata, and there is a considerable theory concerning the criteria according to which they exist or not, which in turn is related to the question of whether the automaton is reversible or not.

A quick criterion is that the rule of evolution has to be "balanced" for an automaton to be reversible and thus not have Garden-of-Eden configurations. Life fails this, because many more neighborhoods lead to zeroes than to ones.

A more precise criterion is one called "mutual erasibility" introduced by Edward F. Moore, to be found in books on automata theory.

This state of affairs notwithstanding, several persons have programmed a search for Life GOE's and found some; I think an example is shown in Poundstone's book. So, of course, a Turing machine could undertake a similar calculation. As an aside, note that it is a Minsky register machine which has been shown to be a universal computer in Life, but that some people have tried to make a more traditional Turing Machine using glider streams.

See:

Edward F. Moore, ``Machine models of self-reproduction,'' in A. Burks (ed), Essays on Cellular Automata, University of Illinois Press, Urbana, 1970.

The same volume also contains a discussion (by J. W. Thatcher) of the relation between Turing Machines and Cellular Automata, another topic of recent interest for this newsgroup.

Expand this node
Expand/collapse
Expand this node
What is the smallest known Garden of Eden in the Game Of Life?
It consists of 143 living cells, and fits in a 14x14 bounding box.

You can see it here.

Expand this node
Expand/collapse
Expand this node
Where can I learn about Spaceships in the Game of Life?
Contributions by:
  • Bruce Stangeland<tbest@rrc.chevron.com>

See Spaceships in Conway's Life, by David I. Bell <dbell@pdact.pd.necisa.oz.au>.

Texinfo version of above by Jörg Heitkötter <joke@santafe.edu> in the CA archives at think.com.

There have also been a series of articles on CA that have appeared in Scientific American, in the Computer Recreations section. See, for example: 10/70, 8/88, 8/89, 9/89, and 1/90.

Expand this node
Expand/collapse
Expand this node
Are variable-speed spaceships possible?
Yes - this follows from the existence of construction universality.

Life patterns can construct complex machinery in a vaccuum, destroy it again, and process delay units. It follows that arbitrarily slow spaceships can be constructed.

Expand this node
Expand/collapse
Expand this node
Has a variable-speed spaceship been constructed?
No. At the time of writing, eight distinct space-ship speeds are known.
Expand this node
Expand/collapse
Expand this node
What are the known spaceship speeds?
c/2, c/3, c/4, c/5, 2c/5, c/6, 2c/7 and c/12.
Expand this node
Expand/collapse
Expand this node
Where can I find the meaning of terms like 'spaceships', 'blinkers' and 'beehives'?
In the Life Lexicon.
Expand this node
Expand/collapse
Expand this node
Are self-reproducing organisms possible in the Game Of Life?
Yes. [BCG82] contains the proof that the Game of Life can contain self-reproducing organisms.
Expand this node
Expand/collapse
Expand this node
Has anyone built a self-reproducing organism in the Game Of Life?
No - that challenge still remains.
Expand this node
Expand/collapse
Expand this node
How big is a self-reproducing organism in the Game Of Life likely to be?
That is not known in any detail. We can say that it is not likely to be very small - or it would have been found by now.

On the other hand, any constraction following the approach detailed in [BCG82] is likely to be huge.

Expand this node
Expand/collapse
Expand this node
What published work relates to the Game of Life?
Expand this node
Expand/collapse
Expand this node
What is 3D Life?
Contributions by:
  • Anthony Wesley <awesley@canb.auug.org.au>
  • Harold V. McIntosh <MCINTOSH@unamvm1.dgsca.unam.mx>
  • John Pedersen <jfp@GOEDEL.MATH.USF.EDU.>
There have been a number of attemps at finding a 3D version of Conway's life.

Many of the current attepts can be seen here.

Carter Bays gives a new rule for 3D Life in [Bay92].

Expand this node
Expand/collapse
Expand this node
References
Bay87a
Carter Bays. Candidates for the game of life in three dimensions. Complex Systems, 1(2):373-400, April 1987.

Bay87b
Carter Bays. Patterns for simple cellular automata in a universe of dense packed spheres. Complex Systems, 1(6):853-875, December 1987.

Bay92
Carter Bays. 3D life (?). Complex Systems, 6(5):433-442, 1992.

BB91
Bennett and Bourzutschy. Nature, 350:468, 1991.

BCC89
Bak, Chen, and Creutz. Soc/game of life (??). Nature, 342:780, 1989.

BCG82
Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy. Winning Ways for your Mathematical Plays, volume 2. Academic Press, ISBN 0-12-091152-3, 1982. chapter 25.

Dew87
A. K. Dewdney. The game life aquires some successors in three dimensions. Scientific American, 224(2):112-118, February 1987.

Dew88
A. K. Dewdney. The hodgepodge machine makes waves. Scientific American, 225(8), August 1988.

GV87
H. A. Gutowitz and J. D. Victor. Local structure theory in more than one dimension. Complex Systems, 1:57-68, 1987.

Jay00
E. T. Jaynes. probability theory-the logic of science. unknown, 1900.

Mci90
Harold V. Mcintosh. Wolfram's class IV automata and a good life. Physica D, 45:105-121, 1990.

Pou85
William Poundstone. The Recursive Universe. William Morrow and Company, New York, 1985. ISBN 0-688-03975-8.

SS78
L. S. Schulman and P. E. Seiden. Statistical mechanics of a dynamical system based on conway's game of life. Journal of Statistical Physics, pages 293-314, 1978.