From: howell@grover.llnl.gov (Louis Howell)
Newsgroups: comp.theory.cell-automata
Subject: Life in Life
Date: 9 Oct 92 21:45:36 GMT
Organization: Lawrence Livermore National Laboratory


There was a discussion here a bit over a year ago about constructing
a Turing machine within Conway's Life.  Paul Callahan discussed what
I think is the most promising approach---instead of building a moving
tape head, duplicate the head logic in every cell.  The problem then
reduces to that of implementing a 1D automaton in Life.  In the case
of a Turing machine only one cell, the one corresponding to the
current location of the "head", would change at a time.  This need
not be true in general, however.

Callahan got sidetracked, IMHO, by his desire to avoid starting with
an infinite tape.  He considered building the tape with puffer trains
so that new cells would be built long before they could be reached
by the tape head.  This required slimming down the cell logic so that
cells would be as easy to build as possible.  So far as I know, the
investigation never made it past the theoretical stage.  At least I've
seen nothing more reported here.

I'm curious about whether any more work has been done on the general
question of simulating 1D or 2D cellular automata in Life.  I don't
have a problem with infinite arrays---it seems that designing such a
system in the first place is more interesting than determining if it
can be built up from a finite starting configuration.

In particular, how about implementing the Life rules in Life?  I can
see two ways that this might be done.  The first might be called the
cell-computer idea, similar to Callahans approach to the Turing
machine.  You have an infinite 2D array of identical mechanisms.  To
facilitate the use of glider streams for sending signals you would
probably want this array to be rotated 45 degrees from the base grid,
like the white cells on a chess board.  Each engine would cycle through
the following steps:

  1.  Send own state to East and West neighbors.
  2.  Add signals from E and W with own state (1=live,0=dead).
  3.  Send sum to North and South neighbors.
  4.  Using own sum, own state and sums from N and S, compute new state.

Note that this is similar to the way Life can be implemented on a
SIMD machine like the CM2.  Also note that if an absence of incoming
gliders is interpreted as evidence of dead cells, then a finite array
of cell engines would operate properly until the active region reached
the edge of the array.

The other approach seems like it would be more difficult to build up
from known components, but might run much more quickly if it could be
made to work.  It is to use an infinite crystal---a regular stable
(or oscillating) lattice---which can store state information in
local variations of structure.  Examples could be an infinite array
of sites where blocks may or may not be present, or an infinite
array of blinkers in either one of the two possible phases.  The
system could be constructed so that sites could affect each other's
states through a cellular automaton rule, without breaking down the
regular structure of the lattice.

Thoughts:  Any investigation of either of these approaches would, I
think, be most easily done on a periodic grid.  Implementation of
simpler rules, both in 1D and in 2D, should precede that of the
Life rule.  The cell-computer approach would involve actual design
of the engine, while the crystal approach would probably involve a
search strategy through a space of possible crystals.

Since these crystals would encode state information, they would not
be completely regular.  How then would a search program work?  Have
there been any automated searches for crystals analogous to the
searches for spaceships?  Is there any known way to build up a 2D
crystal from a finite starting configuration, like the 2D array of
gliders generated by the breeder?

Any references to crystals at all?  99% of everything I've seen
about Life deals with configurations with compact support.

Enough questions.  This post is long enough already.

-- 
Louis Howell  (nazgul@llnl.gov)

  "A few sums!" retorted Martens, with a trace of his old spirit.  "A major
navigational change, like the one needed to break us away from the comet
and put us on an orbit to Earth, involves about a hundred thousand separate
calculations.  Even the computer needs several minutes for the job."