Random Recipe

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.

Take me higher...
Introduction to the PSK PSK Search Recent Additions CA Archive CA Links Feedback Appreciated !