Here is a DHTML/JavaScript implementation of Conway's Game of Life:
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 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:
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.
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.
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.
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.
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.
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.
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.
Has a variable-speed spaceship been constructed?
No. At the time of writing, eight distinct space-ship speeds are known.
What are the known spaceship speeds?
c/2, c/3, c/4, c/5, 2c/5, c/6, 2c/7 and c/12.
Where can I find the meaning of terms like 'spaceships', 'blinkers' and 'beehives'?
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.
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.
