Variations on Life
Harold V. McIntosh
State College of Agriculture and Mechanical Arts, my old alma mater?)
wonders whether anyone is interested in variants on Conway's Life,
himself having gotten bored with plain vanilla Life. Well, that sort
of depends on whether you like chocolate, and whether he has found some
<<good>> chocolate. This isn't Howard Johnson's, but let's take a look.
From the earliest days there was a variant called 3-4 Life (named after
its totalistic range within the same Moore neighborhood) whose description
in William Poundstone's "Recursive Universe" contains most of what
appeared in Robert T. Wainwright's "Lifelines." There are many small
interesting artefacts, but it is too easy to get runaway growth; the
return map from mean field theory predicts this.
Another variation was colored Life; with the same basic rules,
offspring can acquire the color of one or more parents in many ways.
The space Lifelines devoted to either of these rules was never more
than a small fraction of what was devoted to regular Life; one can
plausibly conclude that they were the most interesting of all of the
unreported variations which people tried, without arousing too much
further interest.
[Kendall Preston, Jr., and Michael J. B. Duff, "Modern Cellular
Automata: Theory and Applications," Plenum Press, New York, 1984 (ISBN
0-306-41737-5)] have some chapters devoted explicitly to cellular
automata, on a hexagonal lattice, reporting several artifacts including
gliders. There is further reference to some work of Golay, which we
have not examined, it being somewhat inaccesible to us. The mean field
curve of the automata which they mention is consistent with Wolfram's
Class IV and with their being "Life-like."
By going into minute details of rule construction, many variants of
Life can be created; it all depends on what you want. To start,
symmetries, both rotational and reflective, are evidently desirable.
Better still, they limit the number of possibilities; Golay classes are
fewer in number by a factor roughly equal to the size of the symmetry
group.
An attempt can be made to force specific figures to move about (like
gliders); the larger the neighborhood, the more freedom to postulate
the necessary rule. Interestingly, accepting such Life artifacts as
gliders and glider guns, most of the possibilities for the 3x3 Moore
neighborhood are exhausted (it has about 100 Golay classes, out of 512
neighborhoods), even though a certain residual freedom remains. The
hexagonal neighborhoods of Golay, and Preston and Duff, are smaller
(seven cells), so the limitations are much stronger.
A movable object has to be asymmetric; in a square lattice this implies
eight symmetry images --- sixteen if there are two phases. It has to be
checked that the neighborhood accomodates so many distinct asymmetric
figures, although there is no reason that the complete object has to
fit into just one neighborhood. In turn this preempts at least that
many transitions, whose mutual consistency has to be checked. So the
simplest apologetics for Life suggest that it barely made the grade;
but they also point toward variants which could produce alternative
Life.
We are not aware of whether anyone has tried this in three dimensions,
although it evidently does not lead toward totalistic or semitotalistic
rules, if any at all. There would be 48 variants on a fully asymmetric
figure, much ambiguity in the direction in which to expect it to travel
(would it have three phases, to rotate about the axis of motion?), a
huge number of neighborhoods, but a ferocious job of consistency
checking.
Stephen Wolfram was wildly enthusiastic that automata with "gliders"
(which abound) would have "glider guns" (hardly any have been found
outside of Life) from which universal computers could be constructed
(we are still waiting). Anyone who wants a universal computer should
forget about gliders and look at one of the Turing machine simulators,
but all that is another story.
The theory of de Bruijn diagrams and random graphs (as applied to
automata) makes it clear that <<any>> cellular automaton will have
structures of almost any period and translational characteristic. Only
for Wolfram's Class IV can it be expected that significant numbers of
them will "have finite support," which makes it desirable to be able to
predict an automaton's class. On the other hand, the same theory
indicates that gliders and such like are something of a rarity, the
higher the dimension.
As Howard Gutowitz remarks, and we have stated previously, Carter Bays
is the key reference for higher dimensional automata; Christopher
Langton has taken the approach of increasing the number of states. But
then one is headed in the direction of John von Neumann's original work
(with 29 states) and its later simplifications. Using large numbers of
states supposes that they will be chosen to exhibit convenient
properties; indeed von Neumann had essentially seven classes of states
(plus a quiescent state), considering that everything had to operate
equally in four directions. Some propagated signals, some extended
arms, and so on.
So, much of the charm of Conway's game lies in what lay hidden in
binary automata with an extraordinarily simple rule of evolution.
Certainly it is worth looking to see if there are others, but maybe
the point has already been made.
Even so, maybe vanilla Life has not been completely exhausted. Within
recent years, Bill Gosper has found another glider gun, and Dean
Hickerson has found spaceships moving at half the velocity of light.
Life shows several stubborn characteristics which may or may not have
an explanation at some fundamental level. Still lifes and objects of
period two exist in abundance, but artifacts with period three are a
rarity. The two-dimensional Rule 22, which is a cross section of Life,
rigorously lacks (nontrivial) period three structures; and most likely
lacks period 9 as well. On the other hand there is a pronounced
periodicity of three in Life's spatial statistics.
Collisions or interactions which turn a glider ninety degrees are
another extreme rarity; Conway uses such a collision between gliders in
a fundamental way in working up a universal constructor; but the one he
uses is just about the only one there is, and rather complicated to boot.
Collisions of gliders with each other and with other small objects were
much studied in the early days, but it is not clear how much of this
was ever recorded formally. Lifeline contained various summaries; also
reports on data bases that some individuals were compiling, but we do
not know how much of this survives. Trinary glider collisions may
involve so many parameters and such a mess that nobody has ever
attempted to classify them.
There is always a hope that some simple bistable Life objects may be
found. Conway's universal computer and constructor is dependent on
gliders throughout; maybe there is another approach to these same
results. But note that a single glider stream won't keep on moving the
same object (so far as is known) (and multiple streams sometimes do
remarkable things). Or switch it between two forms.
After all this, anyone who has interesting data or insight to
contribute might as well do so. Lifeline lasted three years (an effort
which only those who have tried to write books or to edit newsletters
will fully appreciate), but discoveries continue and ought to be
publicized.
A suggestion to those who want to exchange information: a mailing
address, with zip code and all, will sometimes be rewarded with a
reprint or two; material which can't be sent easily by e-mail.
---
Harold V. McIntosh |Depto. de Aplicacion de Microcomputadoras
mcin...@uapnx1.dgsca.unam.mx |Inst. de Ciencias, UAP, Apdo. Postal 461
MCINTOSH@UNAMVM1 (BITNET) |72000 Puebla, Pue., Mexico