The Cook Book
Recipe for the week of February 5 - 11
Algorithmic Search for Rare Life Forms: Tim Coe's Snail
- This week we present a remarkable new creature for Conway's Game of
Life, discovered last month by Tim Coe, and announced by Paul Callahan on
his
LifePage. Coe describes his critter, whose capture required six
workstations for the better part of two months, as a c/5 orthogonal
spaceship. I'm not part of the inner circle of Life fanatics, but will
hazard an interpretation of the jargon. Spaceship is synonymous with
glider or bug, a familiar notion here in the Kitchen:
a configuration that travels through space while maintaining its shape,
either exactly, or by cycling through a finite sequence of patterns.
Orthoganal probably means moving in the horizontal or vertical
direction, but that's just a hunch. c/5 denotes one-fifth the 'speed
of light,' c being the fastest that a rule with a given local
neighborhood can possibly propagate (one cell per update in the horizontal
and vertical directions in this nearest-neightbor case). Why is Coe so
proud of his c/5 creation? Presumably because it sets a new record as the
slowest known moving spaceship, advancing only one cell each period-5 cycle.
For this reason, and because of its form, I propose to call it the Snail.
(Of course it also looks like a fish, but then it would swim backwards!)
- For more about the Snail, see Tim Coe's Message
to Callahan. To actually see the thing move, you can get the .lif file
from Callahan's page and load it into one of the dedicated Life simulators,
available for download, that supports that format. Alternatively, if you use
the Kitchen's preferred CA platform, I have put a WinCA experiment
snail.xpt and companion bitmap snail.bmp in my anonymous ftp
directories accessible from the Sink.
- What is the theory behind Coe's computer search? He mentions
that it is based on the backward iterative method of
de Bruijn diagrams, which was described by
Harold McIntosh
a couple of months ago in a post to the Usenet group
comp.theory.cell-automata.
For range 1 CA rules such exhaustive searches are evidently quite productive,
but for many of the longer range dynamics described here in the Kitchen the computation
time of this approach is prohibitive. Then other search strategies are required in
order to find exotic configurations of interest. Using a variety of techniques, my
student Kellie Evans has collected an extensive menagerie of bugs for Larger than
Life that we will describe in a future recipe.
|
