Newsgroups: sci.math, sci.physics, comp.theory.cell-automata
Followup-To: comp.theory.cell-automata
From: hoey@AIC.NRL.Navy.Mil (Dan Hoey)
Date: Wed, 10 Feb 1993 23:37:24 GMT
Subject: Big life and blt life (Re: This Week's Finds...)

When b...@guitar.ucr.edu (John Baez) writes:

> Sorry, I was speaking as a statistical mechanic just then.  What I
> meant was that a random initial configuration will *almost* always
> settle down into a boring configuration that is static except for
> small regions executing periodic motions (in practice I have never
> seen anything except blinkers).  Indeed, I think that in the
> infinite-volume limit my "almost always" could be made precise in
> the sense of probability theory, namely, "with probability 1".
> One has to have seen a number of large-screen displays of Life to
> realize just how depressingly dull the average final state is!
> (With the program I have now, I can get one cell per pixel, for a
> total of about 1000x1000.

I boggle at the spectacle of a physicist talking about a 1000x1000
array as ``large.''  In contrast to John's conjecture, I think there
are some conjectures that for _large_ starting arrays most of the
starting positions never settle down.  But I don't know if anyone has
the computrons to get a handle on typical 1e9 x 1e9 arrays (and I'm
not sure they are large enough to exhibit macroscopic effects).

step...@dogmatix.inmos.co.uk (Stephen Collyer) writes

> Image [sic! joke?] your lattice as a 2D image containing only 2
> values, 1 and 0 which correspond to a cell being occupied or empty.
> Now perform a 2D discrete convolution of the image with the
> following 3 by 3 kernel:
>     1   2  4
>   128 256  8
>    64  32 16
> ...this gives a unique result for each of the 512 different 3 by 3
> image squares (remember each cell can only have 2 values).... feed
> the output from a 3 by 3 convolver into a look-up-table....

But that's profligate for Life.  If you use the kernel

  1 1 1
  1 7 1
  1 1 1

you only need a 16-element table, versus 512 for your kernel.  In
fact, I've seen something much like this method where the (binary)
addition is converted to Boolean operations, and implemented in
bitblts.  I found the algorithm, credited to Byte magazine, on Lisp
machines.  It used about 55 bitblts, but I found out how to cut the
number of bitblts in half by doing horizontal convolution followed by
vertical convolution.

> (Does anyone know where I can get a copy of xlife from)

I don't know if it's the most recent version, but /contrib/xlife.tar.Z
is on export.mit.edu.

r...@ark.abg.sub.org (Ralf Stephan) mentions the puffer train as
a configuration that keeps producing new matter, but that is a
relatively stable configuration, since the matter turns out to be very
regular and static.  When I was talking about positions that don't
settle down, I was talking about truly chaotic positions.  Perhaps the
best definition is positions whose population increases without bound,
but you can't prove it.

This stuff is the topic of comp.theory.cell-automata, which I
recommend to people interested in talking about it.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil