de Bruijn diagrams

[McIntosh Harold V.-UAP]

Persons who have been following the discussions in this group will recall
that from time to time the issue comes up, of how to accurately foresee the
evolution of a cellular automaton. Whereas this is an intrinsically difficult
subject, there are nevertheless several good techniques available which can be
quite illuminating. Mean Field Theory is one of them, the calculation of Basins
of Attraction as reported in Wuensche and Lesser's recent ATLAS (and reviewed
here at length) is another.

In the course of analyzing the BOA's the topic of de Bruijn diagrams came up,
and indeed one of the topics which users of the LCAU series of cellular
automaton programs have been promised has been an improved treatment of the
Diagrams within these programs. Hopes that that work would be finished by
Christmas have not materialized, but one essential ingredient of the
modification, the Graph Editor, is now fairly advanced within NeXTstep. My
apologies to the one or two persons who have asked for this and are still
waiting.

The purpose of this posting is to announce the completion (and consequently
availability of a summary) of the study of period-2 half-light-velocity
spaceships in Conway's Game of Life that was undertaken a year and a half ago
using de Bruijn diagrams.

Those who read David Bell's excellent series of articles on Life's Space Ships
know that there has been a remarkable series of discoveries of Life artifacts
during the past few years (and still continuing). One of them was the discovery
by Dean Hickerson of period 2 spaceships (Life Enthusiasts will recall that the
usual Life spaceships have a period of 4 and advance by gliding, as do the well
known gliders, but in a different direction and velocity). Dean's discovery
included a much more plentiful family than just the light, medium, and heavy
weight spaceships that have been known since the beginning, which he was able
to organize into a series of tiles and a grammar for them.

Since first discovering de Bruijn diagrams and originally having heard about
Dean's discoveries, it has been an ambition to cast them within the framework
of the diagrams. Unfortunately, diagrams in two dimensions are much more
complicated than in one dimension (and in three are more complicated still)
and it has taken the computer power which we could muster to calculate such
one-generation properties as still lifes, and for rather small patches, at
that.

Having been offered some time on a supercomputer, that seemed to be a good
project to undertake, and the summary of a good year's activity consists in
saying that the the phoenix property was a reasonable two-generation project,
and that shifting one cell every two generations was ambitious but realizable.
As we gradually digested the raw data, our commentaries and analyses of the
results were recorded elsewhere, and eventually ran to about 25 postings (a
bit longer than the analysis of the Atlas).

SO! all those bitsy details aren't going to interest everybody, and one dreads
to think of the bandwidth that would be consumed by posting them. Nevertheless
there have been a few requests for this kind of information, and there may
still be one or two more people interested in seeing it; so the usual offer
applies: send me a complete mailing address (including zip) and you can have
nearly a hundred pages of linkage lists, drawings, and running commentary.

It's a mass of data; those willing to wait can have a more final report, with
programs incorporating the methods. The wait may be fairly long ... .

Harold V. McIntosh |Depto. de Aplicaci'on de Microcomputadoras
mcin...@redvax1.dgsca.unam.mx |Instituto de Ciencias/UAP
mcin...@redvax1.bitnet |Apdo. Postal 461
(+52+22)43-6330 |72000 Puebla, Pue., MEXICO