From ca-request@Think.COM  Thu Jan 28 23:28:41 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Thu, 28 Jan 88 23:28:41 EST
Received: by ucbvax.Berkeley.EDU (5.58/1.26)
	id AA14267; Thu, 28 Jan 88 01:08:55 PST
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 27 Jan 88 04:40:45 GMT
From: imagine!pawl19.pawl.rpi.edu!hiebeler@itsgw.rpi.edu  (David E. Hiebeler)
Organization: RPI CS Dept., Cellular Automata Development Group
Subject: Fast way to update grids
Message-Id: <255@imagine.PAWL.RPI.EDU>
Sender: ca-request@Think.COM
To: ca@Think.COM


	I've been working on a project for some time now which reads in an
algorithm, and writes a C program to run some 2-D automata.  It's coming
along pretty well now, but now I'd like to get some input from people 'out
there.'
	Basically, I'm looking for a fast (the fastest?) way of updating
grids, where each cell has to look at an arbitrary number of its neighbors.
I've seen some fast life-programs, but often they took advantage of particular
quirks of the the rules of Life.
	I need some method more general.  I've tried the simple method,
storing the grid in an array, and simply using 2 indices to cover the grid,
and each cell stores its new value in a 2nd copy of the grid.  Say you have 5
neighbors, then each cell requires 5 things like "grid[x][y+1]" for example
to get the value of its south neighbor.
	I tried a field of linked nodes; i defined a whole bunch of structs,
and each cell had a value, plus the structure contained pointers to all of
its neighbors.  So the south neighbor might be (cell.south).value for example.
	Both methods ran at about the same speed (this was on a Sequent
Balance 21000, using C).
 
	Does anyone out there have some useful tips on what I can do to
speed up the program?  Any comments would be greatly appreciated...
  Thanks,
Dave Hiebeler    Internet: hiebeler@csv.rpi.edu (preferred address)
R.D. Box 225A              hiebeler@b21.cs.rpi.edu
Chatham, NY 12037          userfrzk%mts.rpi.edu@itsgw.rpi.edu
                 Bitnet:   userfrzk@rpitsmts.bitnet

----
David Hiebeler       hiebeler@csv.rpi.edu
Troy, NY            "Wo bu jidow wo tzai
                     shua shumua"

From ca-request@Think.COM  Fri Jan 29 05:33:10 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Fri, 29 Jan 88 05:33:10 EST
Received: by ucbvax.Berkeley.EDU (5.58/1.26)
	id AA12393; Fri, 29 Jan 88 01:54:59 PST
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 27 Jan 88 14:47:46 GMT
From: mcvax!jurjen@uunet.uu.net  (Jurjen N.E. Bos)
Organization: CWI, Amsterdam
Subject: Re: Fast way to update grids
Message-Id: <7496@boring.cwi.nl>
References: <255@imagine.PAWL.RPI.EDU>
Sender: ca-request@Think.COM
To: ca@Think.COM

I implemented life once using this method:
Keep track of all cells that changed state last generation.
The only changes that can occur during the current generation will be
in the direct neighbourhood of those cells. You do this:
- copy the list of changed cells
- for each cell in this list:
-   record the changes caused by this cell
-     in the list of changed cells
-     on screen
-     in the array of cells
- increment generation counter.

This algorithm beats any life implementation I ever saw as long as
the number of changes is very small (one or two gliders) and becomes
gradually more slowly as the number of cells increases.

Jurjen Bos.
"Never imagine yourself not to be otherwise than what it might appear to
others that what you were or might have been was not otherwise than what
you had been would have appeared to them to be otherwise."

From @relay.cs.net:DAVIS@blue.sdr.slb.com  Wed Feb  3 06:40:06 1988
Received: from RELAY.CS.NET by Think.COM; Wed, 3 Feb 88 06:40:06 EST
Message-Id: <8802031140.AA05869@Think.COM>
Received: from relay2.cs.net by RELAY.CS.NET id aa07168; 2 Feb 88 7:30 EST
Received: from sdr.slb.com by RELAY.CS.NET id ab01279; 2 Feb 88 7:20 EST
Date: Tue, 2 Feb 88 06:27 EDT
From: DAVIS@blue.sdr.slb.com
Subject: sign on
To: ca@Think.COM
X-Vms-To: MRGATE::M_SDR::IN%"ca@think.com"


	Please add th following address to the Cellular automata distribution
	list

	ca%m_scrvx1%sdr.slb.com

	Please comfirm receipt,

	with thanks and best wishes,
	
	Paul Davis,
	Schlumberger Cambridge Research
	PO Box 153
	Cambrdige
	England

	+44 223 325282

From ca-request@Think.COM  Fri Feb 12 20:19:17 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Fri, 12 Feb 88 20:19:17 EST
Received: by ucbvax.Berkeley.EDU (5.58/1.26)
	id AA08639; Fri, 12 Feb 88 17:06:21 PST
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 12 Feb 88 20:47:38 GMT
From: dl2n+@andrew.cmu.edu  (Daniel Edward Lovinger)
Organization: Carnegie Mellon University
Subject: Reverse Generations
Message-Id: <cW4qVey00Xo-ZxM0SI@andrew.cmu.edu>
Sender: ca-request@Think.COM
To: ca@Think.COM


Does anyone have a method of generating life patterns in reverse, i.e. 
deriving the father pattern from the son pattern? Any help would be 
appreciated. This is just about the final step in the completion of a 
mega-Life simulator here at CMU, bu so far I have had no luck. Thanks!

-------------------------
Daniel E. Lovinger            dl2n@andrew.cmu.edu
Physics Major                 R746DL2N@VB.CC.CMU.EDU  
                              def: Andrew - n. An Alpha test system from IBM
Carnegie Mellon University                       Draw your own conclusions

Disclaimer: for 17K per year to go to this place, I should be able to
            say anything!

And furth.....<ms> Segmentation fault (core dumped)

From ca-request@Think.COM  Sat Feb 13 00:10:56 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Sat, 13 Feb 88 00:10:56 EST
Received: by ucbvax.Berkeley.EDU (5.58/1.26)
	id AA13043; Fri, 12 Feb 88 20:49:55 PST
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 13 Feb 88 01:59:10 GMT
From: jk3k+@andrew.cmu.edu  (Joseph G. Keane)
Organization: Carnegie Mellon University
Subject: Re: Reverse Generations
Message-Id: <gW4v5iy00WAIyjU0ec@andrew.cmu.edu>
References: <cW4qVey00Xo-ZxM0SI@andrew.cmu.edu>
Sender: ca-request@Think.COM
To: ca@Think.COM

There exist `orphan' generations, i.e., those which have no possible
parent.  So any reverse algorithm can't work all the time.

--Joe (fellow Andrew user)

From wayner@svax.cs.cornell.edu  Sat Feb 13 08:52:49 1988
Received: from cu-arpa.cs.cornell.edu by Think.COM; Sat, 13 Feb 88 08:52:49 EST
Received: from svax.cs.cornell.edu by cu-arpa.cs.cornell.edu (5.54/4.30)
	id AA06972; Sat, 13 Feb 88 08:53:11 EST
Date: Sat, 13 Feb 88 08:53:05 EST
From: wayner@svax.cs.cornell.edu (Peter Wayner)
Message-Id: <8802131353.AA19560@svax.cs.cornell.edu>
Received: by svax.cs.cornell.edu (5.54/4.30)
	id AA19560; Sat, 13 Feb 88 08:53:05 EST
To: ca@Think.COM

A related paper?

I think the following paper gives an algorithm for finding
the n-th generation of a configuration without going
through the n-1 generations in between. It might give
some insight into moving backwards.

Gosper, William, "Exploiting Regularities in Large Cellular
     Spaces," Physica-D, no. 10, pp. 75-80, North Holland, 1984.


In general, a backwards algorithm must be able to select from
a variety of paths. For instance, the following four patterns
generate the same final state:

   **      *      *    **
    *     **      **   *

It should be easy to see that if there are 'orphan' generations
or 'Garden of Eden' states than there must be forks going backwards.
A counting argument suffices for finite spaces.

-Peter Wayner
(wayner@svax.cs.cornell.edu   or wayner@crnlcs.bitnet)

From wayner@svax.cs.cornell.edu  Sat Feb 13 10:54:23 1988
Received: from cu-arpa.cs.cornell.edu by Think.COM; Sat, 13 Feb 88 10:54:23 EST
Received: from svax.cs.cornell.edu by cu-arpa.cs.cornell.edu (5.54/4.30)
	id AA06979; Sat, 13 Feb 88 09:00:06 EST
Date: Sat, 13 Feb 88 09:00:00 EST
From: wayner@svax.cs.cornell.edu (Peter Wayner)
Message-Id: <8802131400.AA19578@svax.cs.cornell.edu>
Received: by svax.cs.cornell.edu (5.54/4.30)
	id AA19578; Sat, 13 Feb 88 09:00:00 EST
To: ca@Think.COM
Subject: A related paper

A related paper?

I think the following paper gives an algorithm for finding
the n-th generation of a configuration without going
through the n-1 generations in between. It might give
some insight into moving backwards.

Gosper, William, "Exploiting Regularities in Large Cellular
     Spaces," Physica-D, no. 10, pp. 75-80, North Holland, 1984.


In general, a backwards algorithm must be able to select from
a variety of paths. For instance, the following four patterns
generate the same final state:


   **      *      *    **
    *     **      **   *

It should be easy to see that if there are 'orphan' generations
or 'Garden of Eden' states than there must be forks going backwards.
A counting argument suffices for finite spaces.

-Peter Wayner
(wayner@svax.cs.cornell.edu   or wayner@crnlcs.bitnet)


From ca-request@Think.COM  Sat Feb 13 13:40:40 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Sat, 13 Feb 88 13:40:40 EST
Received: by ucbvax.Berkeley.EDU (5.58/1.26)
	id AA24455; Sat, 13 Feb 88 10:18:54 PST
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 13 Feb 88 09:26:48 GMT
From: brandx.rutgers.edu!webber@TOPAZ.RUTGERS.EDU  (Webber)
Organization: Rutgers Univ., New Brunswick, N.J.
Subject: Re: Reverse Generations
Message-Id: <825@brandx.rutgers.edu>
References: <cW4qVey00Xo-ZxM0SI@andrew.cmu.edu>
Sender: ca-request@Think.COM
To: ca@Think.COM

In article <cW4qVey00Xo-ZxM0SI@andrew.cmu.edu>, dl2n+@andrew.cmu.edu (Daniel Edward Lovinger) writes:
> 
> Does anyone have a method of generating life patterns in reverse, i.e. 
> deriving the father pattern from the son pattern? Any help would be 
> appreciated. This is just about the final step in the completion of a 
> mega-Life simulator here at CMU, bu so far I have had no luck. Thanks!

Trying to deduce the father pattern from the child looks like an np-complete
problem to me.

However, storing a history of patterns isn't all that bad.  The simplest
compaction would be to run length code the previous values of each cell.
Looking for cycles in the run length code would probably keep things
tight enough for most people's tastes.

---- BOB (webber@athos.rutgers.edu ; rutgers!athos.rutgers.edu!webber)

From ca-request@Think.COM  Sat Feb 13 22:40:40 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Sat, 13 Feb 88 22:40:40 EST
Received: by ucbvax.Berkeley.EDU (5.58/1.26)
	id AA02159; Sat, 13 Feb 88 19:23:28 PST
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 13 Feb 88 19:16:45 GMT
From: jellinghaus-robert@YALE-ZOO.ARPA  (Rob Jellinghaus)
Organization: Yale University Computer Science Dept, New Haven CT
Subject: Re: Reverse Generations
Message-Id: <23083@yale-celray.yale.UUCP>
References: <cW4qVey00Xo-ZxM0SI@andrew.cmu.edu>
Sender: ca-request@Think.COM
To: ca@Think.COM

In article <cW4qVey00Xo-ZxM0SI@andrew.cmu.edu> dl2n+@andrew.cmu.edu (Daniel Edward Lovinger) writes:
>Does anyone have a method of generating life patterns in reverse, i.e.
>deriving the father pattern from the son pattern? Any help would be
>appreciated. This is just about the final step in the completion of a
>mega-Life simulator here at CMU, bu so far I have had no luck. Thanks!

I don't know how possible this is.  There are known to be "Garden of
Eden" patterns in Life; that is, there are patterns for which there
is NO possible predecessor (i.e. they can never appear in the course
of a Life game; they have to have been originally created).

Also, there are many possible parentages for a certain ending config-
uration.  Consider an empty board; it may have been empty in the
previous generation, or have had a sparse arrangement of cells, or
have been chock-full of cells to the point where everything died at
once.  There is a definite "Arrow of Time" aspect to the game; going
forward it's deterministic, but going backwards, not so.

>Daniel E. Lovinger            dl2n@andrew.cmu.edu
>Physics Major                 R746DL2N@VB.CC.CMU.EDU
>                              def: Andrew - n. An Alpha test system from IBM
>Carnegie Mellon University                       Draw your own conclusions
>
>Disclaimer: for 17K per year to go to this place, I should be able to
>            say anything!
>
>And furth.....<ms> Segmentation fault (core dumped)

Rob Jellinghaus                | "This is not a RENTAL car...
jellinghaus@yale.edu           |  this is PRIVATELY owned!!"
ROBERTJ@{yalecs,yalevm}.BITNET |
!..!ihnp4!hsi!yale!jellinghaus |               -- _True Stories_

From ca-request@Think.COM  Tue Feb 16 09:42:38 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Tue, 16 Feb 88 09:42:38 EST
Received: by ucbvax.Berkeley.EDU (5.58/1.26)
	id AA23109; Tue, 16 Feb 88 06:33:07 PST
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 15 Feb 88 16:47:21 GMT
From: slb-sdr!dietz@YALE-ZOO.ARPA  (Paul Dietz)
Organization: Schlumberger-Doll Research, Ridgefield, CT
Subject: Re: Reverse Generations
Message-Id: <439@slb-sdr.UUCP>
References: <cW4qVey00Xo-ZxM0SI@andrew.cmu.edu>
Sender: ca-request@Think.COM
To: ca@Think.COM

Daniel E. Lovinger (dl2n@andrew.cmu.edu) asked if there is an algorithm for
reversing life generations.  Joseph G. Keane (jk3k+@andrew.cmu.edu) responded
there are orphan generations which have no predecessors.  webber@athos.rutgers
.edu (Bob Webber) said it looks NP-complete.

Actually, it's not obvious to me that it's even decidable.  One can
construct 2-d cellular automata (using more complicated rules and cell
states than for Life) for which the "orphan" problem is undecidable,
using "valcomps".

Find some universal turing machine.  Design a 2-d cellular automaton that
checks a list of strings to see if they represent successive configurations
of this TM.  This can be done in one generation.  If the list of states is a
valid computation ending in an accepting state, the 2-d cellular automaton
erases everything except the input string.  Otherwise, it leaves some garbage
around the point where an error was detected.  This way, a configuration
consisting only of a particular input string with no other garbage has a
predecessor iff the universal TM accepts the string.  This would solve the
halting problem.

The important point here is that a configuration can be nonrecursively
larger than its successor, so enumeration algorithms cannot be guaranteed
to find predecessors.

	Paul F. Dietz
	dietz@sdr.slb.com

From ca-request@Think.COM  Tue Feb 16 16:42:26 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Tue, 16 Feb 88 16:42:26 EST
Received: by ucbvax.Berkeley.EDU (5.58/1.26)
	id AA00376; Tue, 16 Feb 88 13:14:31 PST
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 16 Feb 88 19:32:57 GMT
From: metcalf-christopher@yale-zoo.arpa  (Chris Metcalf)
Organization: Yale University Computer Science Dept, New Haven CT
Subject: Re: Reverse Generations
Message-Id: <23289@yale-celray.yale.UUCP>
References: <cW4qVey00Xo-ZxM0SI@andrew.cmu.edu>, <825@brandx.rutgers.edu>
Sender: ca-request@Think.COM
To: ca@Think.COM

In article <825@brandx.rutgers.edu> webber@brandx.rutgers.edu (Webber) writes:
>Trying to deduce the father pattern from the child looks like an np-complete
>problem to me.
>---- BOB (webber@athos.rutgers.edu ; rutgers!athos.rutgers.edu!webber)

Please be careful when using technical terms.  NP-complete does not mean
"impossible to solve". Categories of complexity include:

	P		solvable in polynomial time
	NP		non-deterministc polynomial time; i.e., you can
			prove that a guess is correct in polynomial time.
	NP-complete	any problem in NP can be reduced to an NP-complete
			problem (notice, if you can show any NP-complete
			problem to be in P, then NP equals P).
	NP-hard		the class of problems which anything in NP can be
			reduced to (though not necessarily in NP).  If such a
			problem is not in NP you may not be able to show that
			a given guess is correct in polynomial time.
	incomputable	i.e., the halting problem--computing whether a
			given program with certain inputs will terminate.
	ambiguous	problem for which there is no answer, or for which
			there are many answers.

So, the Life problem is merely ambiguous.


Michael S. Littman (MSL) [->               "An evening without chocolate...
...!{ihnp4!hsi,decvax}!yale!mlittman          is like an afternoon without
mlittman@yale.arpa, or @yalecs.BITNET       chocolate- only later!"

and

metcalf@yale.edu               Chris Metcalf            ...!decvax!yale!metcalf
metcalf@yalecs.BITNET                                ...!ihnp4!hsi!yale!metcalf

From bard@theory.lcs.mit.edu  Tue Feb 16 22:04:11 1988
Received: from THEORY.LCS.MIT.EDU by Think.COM; Tue, 16 Feb 88 22:04:11 EST
Received: from RAVEN.LCS.MIT.EDU by THEORY.LCS.MIT.EDU (4.12/4.7); Tue, 16 Feb 88 22:04:45 est
Received: by RAVEN.LCS.MIT.EDU (4.12/4.7); Tue, 16 Feb 88 22:04:40 est
Date: Tue, 16 Feb 88 22:04:40 est
From: Bard Bloom <bard@theory.lcs.mit.edu>
Message-Id: <8802170304.AA07524@RAVEN.LCS.MIT.EDU>
To: ca@Think.COM, metcalf-christopher@yale-zoo.arpa
In-Reply-To: (Chris Metcalf's message of 16 Feb 88 19:32:57 GMT <23289@yale-celray.yale.UUCP>
Subject: Reverse Generations



>>In article <825@brandx.rutgers.edu> webber@brandx.rutgers.edu (Webber) writes:
>>Trying to deduce the father pattern from the child looks like an np-complete
>>problem to me.
> Please be careful when using technical terms.  NP-complete does not mean
> "impossible to solve". Categories of complexity include:
> [ defines P, NP, NP-complete, etc. ...]
> So, the Life problem is merely ambiguous.

(My credentials: I am a grad student in theory of computation at MIT, and have
survived Mike Sipser's advanced complexity theory course.  Probably I know
what NP and friends are.)

I think that the original poster was right.  I interpret the question as,
  "Given a pattern P, return a pattern F which turns into P in one generation."

Now, it's hard to think about nondeterministic functions, so let's consider
the decision problem:
  "Given a pattern P, decide if there is some pattern F which turns 
  into P in one step."
This way, we don't care how many of them there are, because we don't have to
return one.  

This is probably a classical NP problem.  Say that P fits inside a NxN
square.  I seem to remember from somewhere that, if P has a predecessor, it
must fit within an (N+2)x(N+2) square.  The nondeterministic program guesses
what that pattern is, and checks it by running it one generation.   This is
obviously NP.

If you define the function computed by a nondeterministic machine in some
reasonable way (e.g., the leftmost value in the computation tree), then the
first problem is NP with a similar program.  The consensus among the
complexity community is that all such definitions are gross, so they don't
talk about them much.

I don't want to try to prove it NP-complete, but it has the feel of an
NP-complete problem.  

-- Bard

From metcalf-christopher@yale.arpa  Wed Feb 17 00:32:13 1988
Received: from SUNED.ZOO.CS.YALE.EDU ([128.36.0.19]) by Think.COM; Wed, 17 Feb 88 00:32:13 EST
Received: by SUNED.ZOO.CS.YALE.EDU; Wed, 17 Feb 88 00:23:38 EST
Date: Wed, 17 Feb 88 00:23:38 EST
From: Chris Metcalf <metcalf-christopher@yale.arpa>
Message-Id: <8802170523.AA17596@SUNED.ZOO.CS.YALE.EDU>
Received: by yale-zoo-suned (yale-zoo-suned) 
          via WIMP-MAIL (Version 1.3/1.5) ; Wed Feb 17 00:23:34
To: bard@theory.lcs.mit.edu, ca@Think.COM
Subject: Re:  Reverse Generations
Cc: littman-michael@yale.arpa

Yes, the decidability question is NP.  So is finding a possible
parent.  I replied as I did assuming that the original poster meant
literally "finding the father generation is np-complete" instead of
"finding *a* father...".  I think I've just heard np-complete misused
once too often and seeing it again decided to post---no doubt I should
have given the original poster the benefit of the doubt.

I'm interested to notice someone at think.com as the Cc: of this; I
spent last summer working at TMC myself.  Hello!

Chris


From ca-request@Think.COM  Wed Feb 17 09:45:40 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Wed, 17 Feb 88 09:45:40 EST
Received: by ucbvax.Berkeley.EDU (5.58/1.26)
	id AA22324; Wed, 17 Feb 88 06:40:51 PST
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 17 Feb 88 09:28:36 GMT
From: aramis.rutgers.edu!athos.rutgers.edu!webber@rutgers.edu  (Bob Webber)
Organization: Rutgers Univ., New Brunswick, N.J.
Subject: Re: Reverse Generations
Message-Id: <879@athos.rutgers.edu>
References: <cW4qVey00Xo-ZxM0SI@andrew.cmu.edu>, <825@brandx.rutgers.edu>, <23289@yale-celray.yale.UUCP>
Sender: ca-request@Think.COM
To: ca@Think.COM

In article <23289@yale-celray.yale.UUCP>, metcalf-christopher@CS.YALE.EDU (Chris Metcalf) writes:
> In article <825@brandx.rutgers.edu> webber@brandx.rutgers.edu (Webber) writes:
> >Trying to deduce the father pattern from the child looks like an np-complete
> >problem to me.
> >---- BOB (webber@athos.rutgers.edu ; rutgers!athos.rutgers.edu!webber)
> 
> Please be careful when using technical terms.  NP-complete does not mean
> "impossible to solve". Categories of complexity include:

I assure you I know what NP-complete means.  While NP-complete
certainly does not mean impossible, it is generally a good heuristic
indicating exceptional complexity.  However, even an algorithm that
ran in time proportion to the cube of the size of a life configuration
would be of minimal use to the original questioner.  I still stand by
my conjecture that the problem is NP-complete, but I will also concede
that at the moment it is but a conjecture.  Another poster has hypothesized
that a simple enumeration algorithm may be insufficient.  I think a
simple enumeration is sufficient, but grant that I can't prove that it
is any more than that poster could prove that it isn't.  At the moment,
vis a vis the discussion that has appreared so far in this list, the
problem is open.

> 	ambiguous	problem for which there is no answer, or for which
> 			there are many answers.
> 
>> So, the Life problem is merely ambiguous.

The fact that there is sometimes more than one ``shortest'' path in a 
graph does not mean that one cannot analyze the cost of finding a path
for which there are none shorter.

---- BOB (webber@athos.rutgers.edu ; rutgers!athos.rutgers.edu!webber)

From wayner@svax.cs.cornell.edu  Wed Feb 17 12:28:23 1988
Received: from cu-arpa.cs.cornell.edu by Think.COM; Wed, 17 Feb 88 12:28:23 EST
Received: from svax.cs.cornell.edu by cu-arpa.cs.cornell.edu (5.54/4.30)
	id AA22545; Wed, 17 Feb 88 12:28:46 EST
Date: Wed, 17 Feb 88 12:28:36 EST
From: wayner@svax.cs.cornell.edu (Peter Wayner)
Message-Id: <8802171728.AA04624@svax.cs.cornell.edu>
Received: by svax.cs.cornell.edu (5.54/4.30)
	id AA04624; Wed, 17 Feb 88 12:28:36 EST
To: ca@Think.COM
Subject: Another non-determanent path...


There are, in reality, an infinite and uncountable number of states that
could precede any non-garden of eden state. Say there is a given pattern
f that results in g. Bound f. Outside of these boundaries there can be 
any combination of randomly distributed cells that will die as f evolves
to g without affecting the process.

A canonical evolution:
     --------------                  -------------
     I            I                  I           I
     I      f     I          =>      I     g     I
     I            I                  I           I
     --------------                  -------------
  
  ..........   
     
 One of the uncountable trivial cases:
     
     *   *   
             *   <- cells that
       *            will die.
     --------------                  -------------
     I            I                  I           I
     I      f     I          =>      I     g     I
     I            I                  I           I
     --------------                  -------------  
     
      *    *  *
      
        *    *
	
    *
     
     
     
     
     
In a bounded universe, like a torus. there are only a finite number of these
states. 

-Peter Wayner
(wayner@svax.cs.cornell.edu   or wayner@crnlcs.bitnet)

From @relay.cs.net:DJS%UTRC@utrcgw.utc.com  Thu Feb 18 11:55:15 1988
Received: from RELAY.CS.NET by Think.COM; Thu, 18 Feb 88 11:55:15 EST
Message-Id: <8802181655.AA00771@Think.COM>
Received: from relay2.cs.net by RELAY.CS.NET id aa10496; 18 Feb 88 10:30 EST
Received: from utrcgw.utc.com by RELAY.CS.NET id aa15770; 18 Feb 88 10:23 EST
Date: Thu, 18 Feb 88 09:15 EST
From: DJS%UTRC@utrcgw.utc.com
Subject: Reverse Generations
To: CA@Think.COM
X-Vms-To: UTRCGW::IN%"CA@Think.com"


	I believe that the purpose of the question that originally started 
this discussion of reversing the flow of time in Life was intended to produce
suggestions for a useful CA tool. If this is correct, it would seem reasonable
to me to try to restrict the problem.

Two suggestions for a restricted form of the problem:

	Find a minimal (smallest number of living cells) pattern which 
could have generated the current pattern in one generation.

or

	Find any parent pattern that does not contain living cells more than
two cells away from any living cell in the current pattern (This restriction 
is intended to eliminate parent cells which do not affect the current pattern.)

	Although these problems may still be too difficult, they are still a
step in the right direction  -  trying to define a useful tool for analyzing
patterns in Life. 

						David Sirag
					United Technologies Research Center


From ca-request@Think.COM  Fri Feb 19 03:08:09 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Fri, 19 Feb 88 03:08:09 EST
Received: by ucbvax.Berkeley.EDU (5.58/1.26)
	id AA07979; Thu, 18 Feb 88 22:02:44 PST
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 19 Feb 88 04:25:03 GMT
From: clong@topaz.rutgers.edu  (Chris Long)
Organization: Rutgers Univ., New Brunswick, N.J.
Subject: Core Wars
Message-Id: <18164@topaz.rutgers.edu>
Sender: ca-request@Think.COM
To: ca@Think.COM

I'm currently entered in a Core Wars contest and am trying to look
up any relevant background info on it.  If anyone could refer me 
to articles I would be eternally grateful.  I remember two
Scientific American articles distinctly, but can't think of
the issues.
-- 

Chris Long
Rutgers University
New Brunswick, NJ

From ca-request@Think.COM  Fri Feb 19 03:11:05 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Fri, 19 Feb 88 03:11:05 EST
Received: by ucbvax.Berkeley.EDU (5.58/1.26)
	id AA08139; Thu, 18 Feb 88 22:09:28 PST
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 19 Feb 88 04:28:10 GMT
From: clong@topaz.rutgers.edu  (Chris Long)
Organization: Rutgers Univ., New Brunswick, N.J.
Subject: Uncountable Parents
Message-Id: <18165@topaz.rutgers.edu>
References: <8802171728.AA04624@svax.cs.cornell.edu>
Sender: ca-request@Think.COM
To: ca@Think.COM

In article <8802171728.AA04624@svax.cs.cornell.edu>, Peter Wayner writes:

> There are, in reality, an infinite and uncountable number of states that
> could precede any non-garden of eden state. Say there is a given pattern
> f that results in g. Bound f. Outside of these boundaries there can be 
> any combination of randomly distributed cells that will die as f evolves
> to g without affecting the process.

What if f isn't bounded?  I believe there may actually be some states
that have unique parents.

A more rigorous proof of uncountability:

Take any real number z from (0,1) expressed in binary notation.  If z
has two such expressions then pick the expression that terminates in
all 1's.

We place cells in the plane according to the following rule:

If the nth decimal place of z is 1, then place a cell at (2n,0).

This clearly gives an uncountable number of parents to the empty plane.
-- 

Chris Long
Rutgers University
New Brunswick, NJ

From bard@theory.lcs.mit.edu  Fri Feb 19 10:00:26 1988
Received: from THEORY.LCS.MIT.EDU by Think.COM; Fri, 19 Feb 88 10:00:26 EST
Received: from RAVEN.LCS.MIT.EDU by THEORY.LCS.MIT.EDU (4.12/4.7); Fri, 19 Feb 88 09:28:14 est
Received: by RAVEN.LCS.MIT.EDU (4.12/4.7); Fri, 19 Feb 88 09:28:08 est
Date: Fri, 19 Feb 88 09:28:08 est
Message-Id: <8802191428.AA02241@RAVEN.LCS.MIT.EDU>
To: ca@Think.COM
From: bard@theory.lcs.mit.edu
Sender: bard@theory.lcs.mit.edu
Subject: Finite and Infinite Parents


  While we're on this topic, has anyone tried to prove this:

GUESS 1:
  If P is an NxN pattern in Life with a finite ancestor, P has an (Nx2)x(Nx2)
ancestor?

  Off hand, I don't see how to prove it.  I could imagine a pattern which
requires some border cells to create.   Then you need to kill off the border
cells and make sure they don't reproduce, so you need some more cells outside
the border.  And so on.  

  In the worst case, it might not stop.  So, e.g., you might have a "garden
of Eden" state which can't be reached from any finite configuration, but
could be reached from some infinite one.  That sounds unlikely:

GUESS 2:
  If P is a finite Life pattern with an infinite ancestor, then P has
a finite ancestor.

Anyone tried these proofs?

-- Bard


From ca-request@Think.COM  Fri Feb 19 16:00:45 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Fri, 19 Feb 88 16:00:45 EST
Received: by ucbvax.Berkeley.EDU (5.58/1.26)
	id AA26550; Fri, 19 Feb 88 12:23:27 PST
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 19 Feb 88 16:57:41 GMT
From: irizarry@tcgould.tn.cornell.edu  (Gil Irizarry)
Organization: Cornell Theory Center, Cornell University, Ithaca NY
Subject: Re: Core Wars
Message-Id: <3784@batcomputer.tn.cornell.edu>
References: <18164@topaz.rutgers.edu>
Sender: ca-request@Think.COM
To: ca@Think.COM

In article <18164@topaz.rutgers.edu> clong@topaz.rutgers.edu (Chris Long) writes:
>I'm currently entered in a Core Wars contest and am trying to look
>up any relevant background info on it.  If anyone could refer me 
>to articles I would be eternally grateful.  I remember two
>Scientific American articles distinctly, but can't think of
>the issues.
>-- 
>
>Chris Long
>Rutgers University
>New Brunswick, NJ

I don't remember the exact issues either.  However, I do know that they were
not articles per se, but features in Dewdney's Computer Recreation column.
Also, I believe they appeared in '86.  Sci Am prints an index of the year's 
articles and columns in the Dec issue of each year.

Gil Irizarry 
irizarry@tcgould.tn.cornell.edu

 

-- 
Gil Irizarry					BS CS '89
irizarry@tcgould.tn.cornell.edu	<- USEnet 	Cornell University  
irizarry@cnrlthry.bitnet        <- Bitnet	 
xady@crnlvax5.bitnet		<- Bitnet	Space: the dream lives on... 

From pom%under.s1.gov@mordor.s1.gov  Fri Feb 19 19:58:37 1988
Received: from under.s1.gov by Think.COM; Fri, 19 Feb 88 19:58:37 EST
Received: by under.s1.gov id AA11776; Fri, 19 Feb 88 16:58:47 PST
	id AA11776; Fri, 19 Feb 88 16:58:47 PST
Date: Fri, 19 Feb 88 16:58:47 PST
From: pom%under.s1.gov@mordor.s1.gov
Message-Id: <8802200058.AA11776@under.s1.gov>
To: CA@Think.COM
Subject: 


 re: Core Wars
		Assuming that partial info is better then nothing -
		here is a fragment - of an info:

	3. Mark Clarkson, International Core War Society, Wichita,
	KS.

		Core Wars, as publicized by K. Dewdny in *Scientific
		American*, is a game in which two or more programs compete for
		the same processor and/or memory space.  Each tries to trick the
		processor into reading its instructions and those of no other
		programs or tries to find and overwrite the memory locations in
		which the instructions of other programs are stored.

	
		Peter ( pom )


From ca-request@Think.COM  Sat Feb 20 01:45:11 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Sat, 20 Feb 88 01:45:11 EST
Received: by ucbvax.Berkeley.EDU (5.58/1.26)
	id AA08026; Fri, 19 Feb 88 22:45:17 PST
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 19 Feb 88 15:44:58 GMT
From: mtune!codas!killer!pollux!ti-csl!mips!mmeyer@rutgers.edu  (Mark Meyer)
Organization: TI Computer Science Center, Dallas
Subject: Re: Another non-determanent path...
Message-Id: <42697@ti-csl.CSNET>
References: <8802171728.AA04624@svax.cs.cornell.edu>
Sender: ca-request@Think.COM
To: ca@Think.COM

In article <8802171728.AA04624@svax.cs.cornell.edu> wayner@SVAX.CS.CORNELL.EDU (Peter Wayner) writes:

>There are, in reality, an infinite and uncountable number of states that
>could precede any non-garden of eden state.

	Technically :-), the number of possible parent generations is
countably, not uncountably, infinite.

>-Peter Wayner
>(wayner@svax.cs.cornell.edu   or wayner@crnlcs.bitnet)

--
Mark Meyer          USENET: {ut-sally!im4u,convex!smu,sun!texsun}!ti-csl!mmeyer
Texas Instruments, Inc.                                   CSNET : mmeyer@TI-CSL
(SET! TI-RESPONSIBLE-FOR-MSG? #!FALSE)
             If you are on the "leading edge", you are holding the knife wrong.

From bard@theory.lcs.mit.edu  Sat Feb 20 12:07:51 1988
Received: from THEORY.LCS.MIT.EDU by Think.COM; Sat, 20 Feb 88 12:07:51 EST
Received: from RAVEN.LCS.MIT.EDU by THEORY.LCS.MIT.EDU (4.12/4.7); Sat, 20 Feb 88 12:08:21 est
Received: by RAVEN.LCS.MIT.EDU (4.12/4.7); Sat, 20 Feb 88 12:08:17 est
Date: Sat, 20 Feb 88 12:08:17 est
From: Bard Bloom <bard@theory.lcs.mit.edu>
Message-Id: <8802201708.AA04218@RAVEN.LCS.MIT.EDU>
To: ca@Think.COM
In-Reply-To: (Mark Meyer's message of 19 Feb 88 15:44:58 GMT <42697@ti-csl.CSNET>
Subject: Another non-determanent path...


> >There are, in reality, an infinite and uncountable number of states that
> >could precede any non-garden of eden state.
> 
> 	Technically :-), the number of possible parent generations is
> countably, not uncountably, infinite.
> 

Both are correct

The first writer is considering states of the entire plane, which may have an
infinite number of living cells.  For example, every configuration at which 
all the living cells have both coordinates even is a predecessor of the empty
plane; there are omega even-even cells, and so 2^omega (uncountably many)
configurations. 

The second is considering only configurations in which there are a finite
number of living cells.  There are only a countable number of such
configurations, and a fortiori only a countable number of them can be
ancestors of a given configuration.

-- Bard the set-theory gargoyle

From ca-request@Think.COM  Sat Feb 20 20:23:37 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Sat, 20 Feb 88 20:23:37 EST
Received: by ucbvax.Berkeley.EDU (5.58/1.26)
	id AA26158; Sat, 20 Feb 88 16:59:25 PST
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 18 Feb 88 16:31:12 GMT
From: mcvax!diku!torbenm@uunet.uu.net  (Torben Mogensen)
Organization: DIKU, U of Copenhagen, DK
Subject: Re: Re: Reverse Generations
Message-Id: <3677@diku.dk>
References: <cW4qVey00Xo-ZxM0SI@andrew.cmu.edu>, <23083@yale-celray.yale.UUCP>
Sender: ca-request@Think.COM
To: ca@Think.COM

In article <23083@yale-celray.yale.UUCP> jellinghaus-robert@CS.YALE.EDU (Rob Jellinghaus) writes:
In article <cW4qVey00Xo-ZxM0SI@andrew.cmu.edu> dl2n+@andrew.cmu.edu (Daniel Edward Lovinger) writes:
>Does anyone have a method of generating life patterns in reverse, i.e.
>deriving the father pattern from the son pattern? Any help would be
>appreciated. This is just about the final step in the completion of a
>mega-Life simulator here at CMU, bu so far I have had no luck. Thanks!

>Daniel E. Lovinger            dl2n@andrew.cmu.edu

I have tried to use the respond facility to send this reply
directly to Daniel, but a friend told me that this is
notoriously unreliable, so I now post it as a follow-up:


There are serious problems generating inverse life generations.
I will list some of these and give some ideas of how to do it
in a reasonable way.

Problems:

    1.  There may be many possible solutions (even infinitely many).

    2.  The smallest solution may be arbitrarily larger than the input.

    3.  There may be no solutions.

    4.  Even restricting solutions to a limited size, finding the set
        of solutions requires exponential time (2 ^ (length+width)).

I studied the problem some time ago and found an algorithm that
works reasonably fast on small patterns and gives the set of
all solutions of a limited size.  It uses comparisons of binary
numbers, logical operations and shifts only.  It works like
this:

    1.  Construct the set B of all 3x3 configurations that would leave
        the central cell blank after one generation, and another (L) for
        the configurations that would give a life cell.  The configu-
        rations should each be represented as 3 words of bit-patterns.

    2.  Start with the centre of the pattern you want to find the
        predecessor of.  If this is blank let the set of partial
        solutions be the set B, otherwise the set L.

    3.  Now go to the neighbour of this cell and depending on its value
        choose either B or L.  Call this set S.  For each element in the
        set of partial solutions and each element in S do:  shift the
        pattern from S so its centre is over the point in the partial
        solution that corresponds to the neighbour.  If the pattern
        from S and the partial solution agree on their overlapping area
        (mask out the other bits and compare) include the combined (or'ed)
        pattern in the new set of partial solutions, otherwise don't.

    4.  Continue adding cells to the set of partial solutions by
        repeating step 3 for neighbouring cells, going around in a
        spiral:

                        7  8  9 10
                        6  1  2 11
                        5  4  3 12
                                13

When you have done this for all the cells in the pattern, all
the partial solutions that have an empty border are possible
predecessors to that pattern.  For the rest you can continue
spiralling as long as you like getting bigger solutions each
time a pattern has an empty border.
    If at any time the set of partial solutions become empty,
there are no (more) solutions.  This is however extremely
unlikely, the usual case being a number of number of partial
solutions proportional to 2 ^ (length+width).
    A small example will propably be helpful at this point:

Given a pattern

                        01
                        10

that we want to find predecessors for, and using reduced
versions of the sets B and L:

   000  100  100  111  010  000  010  000
B: 000  000  000  110  101  011  100  001
   000  000  001  100  010  000  000  010

   101  111  100  010  100  110  000  001
L: 000  000  001  010  010  100  111  010
   010  000  001  010  001  000  000  100


For the initial point we choose the top left corner, which is
blank, so the set of partial solutions become B.
    Now we try to add the top right corner.  There are 36
combinations we have to compare, a few examples are:


   000     010
   000 and 010   do not agree in their overlap
   000     010

   111     110                                          1110
   110 and 100  agree, giving the new partial solution  1100
   100     000                                          1000

in total the new partial solutions are:

1110  0000  0100  0001
1100  0111  1001  0010
1000  0000  0001  0100

now, trying to add the bottom right (blank) corner we get:

1110  1110  0001
1100  1100  0010
1000  1000  0100
 000   001   000

and then adding the bottom left (life) corner:

1110  1110  0001
1100  1100  0010
1000  1000  0100
0000  0001  1000

since we have no partial solution with blank border we must
continue outwards using B, starting with bottom left:

 1110   1110   0001
11100  11100  00010
11000  11000  00100
10000  10001  01000

when we have completed a full revolution we have one partial
solution with blank border (plus some without):

000000
000010
000100
001000
010000
000000

this is thus a valid predecessor to

  01
  10

The time used to find predecessors is in addition to the size
of the pattern also dependent on the denseness of the pattern,
as this will affect the number of partial solutions. A large
number of life cells will reduce this number as L has 140 elements
compared to 372 for B.


                                Torben Mogensen
                                Institute of Datalogy
                                University of Copenhagen

From ca-request@Think.COM  Sun Feb 21 17:39:27 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Sun, 21 Feb 88 17:39:27 EST
Received: by ucbvax.Berkeley.EDU (5.58/1.26)
	id AA08188; Sun, 21 Feb 88 13:26:02 PST
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 20 Feb 88 19:27:26 GMT
From: imagine!pawl4.pawl.rpi.edu!hiebeler@itsgw.rpi.edu  (David E. Hiebeler)
Organization: RPI CS Dept., Rensselaer Cellular Automata Development Group
Subject: hexagonal (triangular) grids
Message-Id: <397@imagine.PAWL.RPI.EDU>
Sender: ca-request@Think.COM
To: ca@Think.COM


	Howdy; I see there's _finally_ a little traffic in this group.
So, I might as well say something. :-)
	Lately, I've been fiddling with hexagonal grids a little.  I'm using
2-D automata for simulating diffusion, and crystal growth to fulfill some
chemistry requirements here.  Anyways, I just implemented hexagonal grids
on the automata-program myself and 2 others here wrote, using a method mentioned
in the article "Numerical Simulations of Hydrodynamics with Lattice Gas
Automata in Two Dimensions" by Dominique d'Humieres and Pierre Lallemand,
in _Complex Systems_ vol. 1 #4 (page 610), where they map a hexagonal grid
to a rectangular grid by assigning the 6 neighbors depending on whether the
cell being treated is on an even or odd line of the grid:

                        6 5
                         \|
  even lines:           1- -4
                         /|
                        2 3

                          6 5
                          |/
   odd lines:           1- -4
                          |\
                          2 3

  This works pretty well.  I think my implementation of the FHP model of
diffusion is working, and i've also experimented with making things that
look kind of like snowflakes.
    I'm just curious, has anyone done much with FHP, or other interesting
stuff on a hex grid?  I'm kind of curious to see a reasonable explanation
of why a hex grid is so much better than a rectangular grid for simulating
the Navier-Stokes equation.  All the articles say that this is the case, but
I have yet to see _why_.


	On another note, this automata program we're working on here is
getting better.  It allows you define neighbors and include already-defined
libraries of neighbors, declare and use global variables, execute extra
statements between the regular time-steps of the simulation, and in general
do all the regular stuff you'd do with 2-D automata.  You define the actual
transition-function as a C procedure, and what happens is our program reads
in your file, processes the neighbor-definitions and function and everything
else, and writes a complete C program which runs in parallel on a Sequent
Balance 21000.  Some people have expressed interest in the program, and I
haven't forgotten about you.  I'm still adding to it (trying to make it run
faster is a big problem now), and also I guess sticking in a flag to allow
it to write programs that run on sequential unix machines.  So I'll be sending
it out to those who asked, but I'm still not sure just how soon.

--Dave Hiebeler         Internet: hiebeler@csv.rpi.edu
  R.D. Box 225A                   hiebeler@b21.cs.rpi.edu
  Chatham, NY 12037               userfrzk%mts.rpi.edu@itsgw.rpi.edu
                        Bitnet:   USERFRZK@RPITSMTS.BITNET

From trainor@cs.ucla.edu  Sun Feb 21 19:46:27 1988
Received: from lanai.cs.ucla.edu by Think.COM; Sun, 21 Feb 88 19:46:27 EST
Return-Path: <trainor@CS.UCLA.EDU>
Received: from LocalHost.ARPA by lanai.cs.ucla.edu (Sendmail 5.58.2/1.14)
	id AA01471; Sun, 21 Feb 88 16:46:52 PST
Message-Id: <8802220046.AA01471@lanai.cs.ucla.edu>
To: hiebeler@csv.rpi.edu (David E. Hiebeler)
Cc: ca@Think.COM, trainor@cs.ucla.edu
Subject: Re: hexagonal (triangular) grids 
In-Reply-To: Your message of 20 Feb 88 19:27:26 +0000.
             <397@imagine.PAWL.RPI.EDU> 
Date: Sun, 21 Feb 88 16:46:51 PST
From: Vulture of Light <trainor@cs.ucla.edu>


>    I'm just curious, has anyone done much with FHP, or other interesting
>stuff on a hex grid?  I'm kind of curious to see a reasonable explanation
>of why a hex grid is so much better than a rectangular grid for simulating
>the Navier-Stokes equation.  All the articles say that this is the case, but
>I have yet to see _why_.

Maybe we need some debate!  How many people believe in the Navier-Stokes
equations?  How many think the CA models are *better*?  From Wolfram's
invited paper ``Cellular Automaton Supercomputing*'' at the Frontiers of
Massively Parallel Scientific Computation symposium (NASA conference
publication 2478): 

        ``Just like a real fluid, however, the cellular automaton model
        contains definite high-order corrections, not included in the
        Navier-Stokes equations.  In addition, analytical methods
        provide only approximate values for parameters such as
        viscosity; accurate values must be obtained from explicit
        computer simulations.''

douglas trainor

PS: Can someone pretty please send me their FHP code?

--------
* Also to appear in ``High Speed Computing:  Scientific Applications and
  Algorithm Design, edited by Robert B. Willhelmson, (Univ. of Illinois
  Press, 1987).


From ca-request@Think.COM  Mon Feb 22 12:33:48 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Mon, 22 Feb 88 12:33:48 EST
Received: by ucbvax.Berkeley.EDU (5.58/1.26)
	id AA26335; Mon, 22 Feb 88 08:54:24 PST
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 22 Feb 88 00:27:47 GMT
From: imagine!pawl3.pawl.rpi.edu!hiebeler@itsgw.rpi.edu  (David E. Hiebeler)
Organization: RPI CS Dept., Rensselaer Cellular Automata Development Group
Subject: re: reversibility
Message-Id: <402@imagine.PAWL.RPI.EDU>
Sender: ca-request@Think.COM
To: ca@Think.COM


	The book _Cellular Automata Machines: A New Environment for Modeling_,
by T. Toffoli and N. Margolus, has a bit of discussion about reversibility.
Chapt. 14 is called "Reversibility and Randomness".  
	There is not a great deal devoted to it, but between that and another
chapter, they mention some features of reversible rules, and construct a
second-order rule which is reversible.
	It's an excellent introductory book on the subject of cellular automata
and modeling; there are _many_ examples, and even code for a lot of them
(written in Forth [:-)] because the CAM-6 machine built by the information-
mechanics group at MIT uses that language; but still it's easy to understand
even if you don't know Forth).
  -
 Dave Hiebeler     Internet:  hiebeler@csv.rpi.edu
 R.D. Box 225A                hiebeler%mts.rpi.edu@itsgw.rpi.edu
 Chatham, NY 12037   Bitnet:  USERFRZK@RPITSMTS.BITNET

From ca-request@Think.COM  Mon Feb 22 14:49:52 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Mon, 22 Feb 88 12:33:48 EST
Received: by ucbvax.Berkeley.EDU (5.58/1.26)
	id AA26335; Mon, 22 Feb 88 08:54:24 PST
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 22 Feb 88 00:27:47 GMT
From: imagine!pawl3.pawl.rpi.edu!hiebeler@itsgw.rpi.edu  (David E. Hiebeler)
Organization: RPI CS Dept., Rensselaer Cellular Automata Development Group
Subject: re: reversibility
Message-Id: <402@imagine.PAWL.RPI.EDU>
Sender: ca-request@Think.COM
To: ca@Think.COM


	The book _Cellular Automata Machines: A New Environment for Modeling_,
by T. Toffoli and N. Margolus, has a bit of discussion about reversibility.
Chapt. 14 is called "Reversibility and Randomness".  
	There is not a great deal devoted to it, but between that and another
chapter, they mention some features of reversible rules, and construct a
second-order rule which is reversible.
	It's an excellent introductory book on the subject of cellular automata
and modeling; there are _many_ examples, and even code for a lot of them
(written in Forth [:-)] because the CAM-6 machine built by the information-
mechanics group at MIT uses that language; but still it's easy to understand
even if you don't know Forth).
  -
 Dave Hiebeler     Internet:  hiebeler@csv.rpi.edu
 R.D. Box 225A                hiebeler%mts.rpi.edu@itsgw.rpi.edu
 Chatham, NY 12037   Bitnet:  USERFRZK@RPITSMTS.BITNET

From @relay.cs.net:DAVIS@scrvx2.sdr.slb.com  Mon Feb 22 18:28:19 1988
Received: from RELAY.CS.NET by Think.COM; Mon, 22 Feb 88 18:28:19 EST
Message-Id: <8802222328.AA01920@Think.COM>
Received: from relay2.cs.net by RELAY.CS.NET id ab19125; 22 Feb 88 17:36 EST
Received: from sdr.slb.com by RELAY.CS.NET id ae12918; 22 Feb 88 17:26 EST
Date: Mon, 22 Feb 88 17:07 EDT
From: DAVIS@scrvx2.sdr.slb.com
Subject: Navier-Stokes and CA
To: ca@Think.COM
X-Vms-To: MRGATE::M_SDR::IN%"ca@think.com"


	At last - I might be able to justify my subscription to
	this group to my employers !! I refer of course to the
	appearance of Fluid Mechanics on this medium, and the impending
	discussion of different modelling methods.

	We have some people here doing traditional differential
	equation modelling of turbulence, fluid flow and the like,
	and continually burning up the CPU time in the process. I
	have a keen (if armchair) interest in CA, and it has always
	seemed to me that they represent a better way of modelling
	what is essentially a discreet phenomenon anyway.

	So - tell me gentlefolk: why should we be using CA's for
	this stuff (as in justifying it to Newtonian traditionalists
	who can still apply Maximum Entropy, Catastophe Theory and
	Non-linear dynamics to their work) ? Where do we begin ?
	Will a CA approach on a regular sequential machine be faster
	or slower than the DE approach ? What hardware is there that
	is pretty cheap and available for this sort of stuff ?

	These seem like a pretty good bunch of qeuries for starters...

	replies to the group or to me at:

	davis%m_blue%sdr.slb.com@relay.csnet

	Paul Davis

From @relay.cs.net:DJS%UTRC@utrcgw.utc.com  Mon Feb 22 18:37:43 1988
Received: from RELAY.CS.NET by Think.COM; Mon, 22 Feb 88 18:37:43 EST
Message-Id: <8802222337.AA01998@Think.COM>
Received: from relay2.cs.net by RELAY.CS.NET id ad18214; 22 Feb 88 16:40 EST
Received: from utrcgw.utc.com by RELAY.CS.NET id ad12319; 22 Feb 88 16:28 EST
Date: Mon, 22 Feb 88 16:20 EST
From: DJS%UTRC@utrcgw.utc.com
Subject: Triangular Grids
To: ca@Think.COM
X-Vms-To: UTRCGW::IN%"ca@think.com"


	I am no expert on the subject, but a reason that I have
heard for preferring triangular grids for simulating physical systems
is that these triangular systems permit the transfer of energy from 
one dimension to the other. It would seem to me that this might apply
to other physical properties as well. I think this property is 
discussed in literature from Thinking Machines Inc. and possibly
in other articles in Complex Systems.

				David Sirag
				United Technologies Research Center

From wayner@svax.cs.cornell.edu  Mon Feb 22 20:15:29 1988
Received: from cu-arpa.cs.cornell.edu by Think.COM; Mon, 22 Feb 88 20:15:29 EST
Received: from svax.cs.cornell.edu by cu-arpa.cs.cornell.edu (5.54/4.30)
	id AA02567; Mon, 22 Feb 88 20:15:53 EST
Date: Mon, 22 Feb 88 20:15:43 EST
From: wayner@svax.cs.cornell.edu (Peter Wayner)
Message-Id: <8802230115.AA09725@svax.cs.cornell.edu>
Received: by svax.cs.cornell.edu (5.54/4.30)
	id AA09725; Mon, 22 Feb 88 20:15:43 EST
To: ca@Think.COM
Subject: Differential Equations versus Cellular Automata


Well in absolute terms, every differential equation solved with 
numerical methods on a computer with n bits of precision
is just a cellular automaton with 2^n states per cell and an
update rule based on the difference equation. So numerical
methods are just a subset of cellular automata solutions. 

On the other hand, any fairly non-linear CA model should be 
impossible to represent with numerical methods and differential
equations.  I would guess that DE models are a proper subset of CA
models. 

This is a distinction made for mathematicians not engineers. In
reality, differential equations are much easier to tune and 
control than CA models because they contain so much more information 
and flexibility. On the other hand, they require endless amounts
of real arithmetic. A simple CA model for fluid flow can use
much less than 100 gates for computation. This is a big
saving in computational complexity. 

There is something unsatisfying about simulating millions
of atoms bouncing about with millions of bits bouncing about.
Unfortunately, the differential equations won't yield a
closed form solution for anything more interesting than lamilar
flow down a pipe so numerical methods are often all
classical mathematics can offer. 

Aside from questions of accuracy, the differences are many
matters of taste and style. Most CA's are simple enough
for a second grader to visualize. Their richness often remains
unrecognized because of their simplicity. Differential
Equations are modifications of Newton's
assertion that force equals change in momentum. Solving
them, however, requires a college level education. This 
high level of discourse often obscures the simplicity
of the  model's first principles. 

I would not like to discard classical DE-based
physics for CA's. A classical solution of water
flowing through a pipe is much more elegant than
millions of bits swarming about a wing. Using
CA models that reduce to the classical DE might
have many computational advantages if accuracy
can be verified. 

Peter Wayner
(wayner@svax.cs.cornell.edu)

From @cunyvm.cuny.edu:031976@DOLUNI1.BITNET  Mon Feb 22 20:42:00 1988
Received: from CUNYVM.CUNY.EDU by Think.COM; Mon, 22 Feb 88 20:42:00 EST
Message-Id: <8802230142.AA02554@Think.COM>
Received: from DOLUNI1.BITNET by CUNYVM.CUNY.EDU ; Mon, 22 Feb 88 20:41:19 EST
Date: Tue, 23 Feb 88 02:33:59 CET
To: ca@Think.COM
From: 031976%DOLUNI1.BITNET@cunyvm.cuny.edu
Comment: CROSSNET mail via SMTP@INTERBIT
Subject: lattice gas automata


   I'm just writing a fortran program for the FHP lattice gas automata
model and I've noticed that the discussion on this subject is going on.
In principle I believe that the great benefit of this method is that is
exact.One can forget about round-off errors or the instability of finite
difference codes.The information is packed in integer words ( bit-cell
simulation ) and one cares about the updating (collision and propagation)
of the quasi-particles moving on the hexagonal grid (which is nessesary
in order to preserve the isotropy of  a Tijkl tensor-actually is the
simplest case).{A nice general reference on the lattice gas automata
which also discuss extensively the isotropy of tensors is the following:
S.Wolfram, J.Stat. Phys, vol 45,nos 3/4,1986,p.471.}
After coarse graining one can get the macroscopic velocity profile of the
fluid.Also everything goes faster(vector or parallel computing).
There are many experiments in the literatur using lattice gas methods
(von Karman street, Pipe flow, Helmholz-Kelvin instability u.s.w).
 By the way does anyone have in mind any method for
optimizing Boolean functions?
----------------------|
Ch.Kougias            |
031976%doluni1.bitnet |
Un. Oldenburg         |
FB-Physik             |
F.R.G.                |
----------------------|

From bmb@Aquinas.Think.COM  Mon Feb 22 20:49:28 1988
Received: from sauron.think.com by Think.COM; Mon, 22 Feb 88 20:49:28 EST
Received: from LIOBA.THINK.COM by sauron.think.com; Mon, 22 Feb 88 20:49:23 EST
Date: Mon, 22 Feb 88 20:50 EST
From: Bruce Boghosian <bmb@Aquinas.Think.COM>
Subject: hexagonal (triangular) grids
To: hiebeler@csv.rpi.edu
Cc: ca@Think.COM
In-Reply-To: <397@imagine.PAWL.RPI.EDU>
Message-Id: <880222205042.3.BMB@LIOBA.THINK.COM>

    Date: 20 Feb 88 19:27:26 GMT
    From: imagine!pawl4.pawl.rpi.edu!hiebeler@itsgw.rpi.edu  (David E. Hiebeler)
    Organization: RPI CS Dept., Rensselaer Cellular Automata Development Group
    Subject: hexagonal (triangular) grids
    To: ca@Think.COM

    ...

	I'm just curious, has anyone done much with FHP, or other interesting
    stuff on a hex grid?  I'm kind of curious to see a reasonable explanation
    of why a hex grid is so much better than a rectangular grid for simulating
    the Navier-Stokes equation.  All the articles say that this is the case, but
    I have yet to see _why_.

    ...

    --Dave Hiebeler

I'll give a quick (admittedly sketchy) explanation of why one needs a
triangular lattice in 2D.  For details, see e.g. Stephen Wolfram's article
in J. Stat. Phys., Vol. 45 (1986), pp. 471-526.

In words, the basic idea is this:  We have "microscopic" dynamics (the CA)
on some kind of regular grid.  We average it (using local spatial averages)
to get "hydrodynamic" quantities, such as fluid density, fluid velocity,
etc.  Whereas the microscopic particle dynamics are obviously anisotropic
(individual particle velocities obviously lie along the discrete grid
directions), we want the macroscopic dynamics to be totally isotropic.
That is, we don't want the fluid to "know" that there are preferred
directions on the underlying lattice.  For example, if we use CA fluids to
study channel flow, it shouldn't matter how the lattice directions are
oriented with respect to the channel walls (i.e. parallel, perpendicular,
or at some random angle).  In 2D it can be shown that the required isotropy
is obtained with a triangular lattice, but not with a square one. 
 
In the analysis that leads from the CA rule to the fluid equation for a
generic lattice gas, the result is something of the form:

partial u_i
----------- + g(n) u_j del_j u_i = - grad_i p + C_{ijkl} del_j del_k u_l,
 partial t

where I have used a nonstandard (but obvious) notation, where u_i is the
i'th component of fluid velocity, where p is the pressure, and where g(n)
is a known function of the density n.

Now g(n) is not there in the real Navier-Stokes equation, and its presence
voids the Galilean invariance of the above equation (this should not be
surprising because there is a preferred reference frame -- that for which
the lattice is at rest).  Nevertheless, for incompressible flow, n (and
hence g(n)) is constant, so that a simple rescaling of the variables in the
above equation will get rid of this unwanted constant factor.

More troublesome is the term with the fourth rank tensor on the right-hand
side where the viscous term should be.  The actual form of the tensor
C_{ijkl} depends only on the lattice used.  In particular, it has the
symmetry properties of that lattice.  For example, if one uses a square
lattice, then C will be invariant under rotation by 90 degrees; if one uses
a triangular lattice, then C will be invariant under rotation by 60
degrees, etc.

Now let us suppose that C were an isotropic tensor.  In 2D, a general
isotropic tensor is given by

C_{ijkl} =   mu  delta_{jk} delta_{il}
           + nu  delta_{jl} delta_{ik}
           + rho delta_{ij} delta_{kl},

where delta denotes the Kronecker delta in 2D.  Then the term involving C
in our fluid equation would become:

mu del^2 u_i + (nu del_i + rho del_i) (del_j u_j).

Now the second term vanishes in the incompressible limit because del_j u_j
= 0, and the first term is exactly the viscous term that we want.  So we
conclude that if the tensor C were isotropic, then we would get the
incompressible Navier-Stokes equation, as desired.

So the question boils down to the following:  What sort of symmetry
property is required to guarantee the isotropy of a fourth rank tensor in
2D?  It turns out that symmetry under 90 degree rotation is NOT sufficient
for this (if you think about it, you can write down anisotropic fourth rank
tensors that are invariant under 90 degree rotation), but that symmetry
under rotation by 60 degrees is.  That is why everybody uses a hexagonal
lattice.

To see another different example of the same sort of phenomenon, note that
the diffusion tensor is a second rank tensor.  It turns out that invariance
under 90 degree rotation IS sufficient to guarantee the isotropy of a
second rank tensor in 2D.  That is why it is possible to have isotropic 2D
diffusion equation simulations using CA on a 2D grid.

Incidentally, we (here at TMC) have tried studying channel flow with the
hexagonal lattice gas with the lattice oriented at varying angles with
respect to the channel, and we have found that the orientation really does
make no difference whatsoever.

Finally, note that this is the reason that a 3D version of the CA fluid is
so difficult.  In 3D, icosahedral symmetry is required to guarantee the
isotropy of a fourth rank tensor.  Alas, there is no regular lattice with
this symmetry in 3D.  In 4D, however, there IS a regular lattice with the
required symmetry, and the most promising 3D work to date has done the CA
on this 4D lattice and then projected the flow back down to 3D.

Bruce M. Boghosian
Thinking Machines Corporation
(bmb@think.com)


From cgl%raven@lanl.gov  Tue Feb 23 12:05:55 1988
Received: from LANL.GOV (beta.lanl.gov) by Think.COM; Tue, 23 Feb 88 12:05:55 EST
Received: by LANL.GOV (5.54/1.14)
	id AA09802; Tue, 23 Feb 88 10:06:17 MST
Received: by raven.lanl.gov.ARPA (3.2/5.17)
	id AA14870; Tue, 23 Feb 88 10:00:12 MST
Date: Tue, 23 Feb 88 10:00:12 MST
From: cgl%raven@lanl.gov (Chris Langton)
Message-Id: <8802231700.AA14870@raven.lanl.gov.ARPA>
To: ca@Think.COM
Subject: Lattice gas article...

There is a good overview of discrete-fluids/lattice-gases in the most recent
"Los Alamos Science" (#15) - a special issue devoted to Stanislaw Ulam (as
you may know, Ulam suggested a cellular automaton approach to von Neumann as 
an alternative to his kinetic model of self-reproduction.) The lattice-gas
article is written by Brosl Hasslacher (the "H" of the FHP model) and his
collaborators here at Los Alamos. Some of the questions at issue here - such
as the reason for using a hex-lattice and techniques for 3D simulations - are
covered nicely. There are also color photos of 2- and 3-D flow. The issue also 
has many other worthwhile articles, especially one by David Campbell - director
of the Center for Nonlinear Studies - on nonlinear science, its paradigms, and
techniques. Best of all, "Los Alamos Science" is available free of charge - 
while supplies last - by writing to:

		  Dixie McDonald - Circulation Manager
                  "Los Alamos Science"
                  MS M708
                  Los Alamos National Laboratory
                  Los Alamos, New Mexico
                  87545
                  
                  Phone: 505-667-1447
 
                  
 Chris Langton  
 Center for Nonlinear Studies		phone: 505-665-0059
 MS B258				email: cgl@lanl.gov
 LANL
 Los Alamos, NM 87545               
                  

From wayner@svax.cs.cornell.edu  Tue Feb 23 13:18:57 1988
Received: from cu-arpa.cs.cornell.edu by Think.COM; Tue, 23 Feb 88 13:18:57 EST
Received: from svax.cs.cornell.edu by cu-arpa.cs.cornell.edu (5.54/4.30)
	id AA05105; Tue, 23 Feb 88 13:05:23 EST
Date: Tue, 23 Feb 88 13:05:14 EST
From: wayner@svax.cs.cornell.edu (Peter Wayner)
Message-Id: <8802231805.AA19802@svax.cs.cornell.edu>
Received: by svax.cs.cornell.edu (5.54/4.30)
	id AA19802; Tue, 23 Feb 88 13:05:14 EST
To: ca@Think.COM
Subject: "Fairly Non-linear CAs"


Sean Smith of CMU writes:

Stephen Omohundro's "Modelling Cellular
Automata with PDE's" (Physica 10D (1984) 128-134).
 
begins with the abstract:

"A system of 10 coupled nonlinear pde's is exhibited which simulates an
arbitrary two-dminesnional, nine-neighbor, square lattice ca."

In this case, it would seems as if nine-neighbor, square lattice
CA's are equivalent to differential equations. I would guess that
the technique can be generalized. 

-Peter Wayner
(wayner@svax.cs.cornell.edu

From wayner@svax.cs.cornell.edu  Tue Feb 23 13:48:00 1988
Received: from cu-arpa.cs.cornell.edu by Think.COM; Tue, 23 Feb 88 13:48:00 EST
Received: from svax.cs.cornell.edu by cu-arpa.cs.cornell.edu (5.54/4.30)
	id AA05255; Tue, 23 Feb 88 13:48:21 EST
Date: Tue, 23 Feb 88 13:48:08 EST
From: wayner@svax.cs.cornell.edu (Peter Wayner)
Message-Id: <8802231848.AA20776@svax.cs.cornell.edu>
Received: by svax.cs.cornell.edu (5.54/4.30)
	id AA20776; Tue, 23 Feb 88 13:48:08 EST
To: ca@Think.COM
Subject: "Fairly Non-linear CAs"


In response to my earlier posting, Sean Smith of CMU writes:

Stephen Omohundro's "Modelling Cellular
Automata with PDE's" (Physica 10D (1984) 128-134).
 
begins with the abstract:

"A system of 10 coupled nonlinear pde's is exhibited which simulates an
arbitrary two-dminesnional, nine-neighbor, square lattice ca."

In this case, it would seems as if nine-neighbor, square lattice
CA's are equivalent to differential equations. I would guess that
the technique can be generalized. 

-Peter Wayner
(wayner@svax.cs.cornell.edu
-------

From cgl%raven@lanl.gov  Tue Feb 23 14:49:09 1988
Received: from LANL.GOV (beta.lanl.gov) by Think.COM; Tue, 23 Feb 88 14:49:09 EST
Received: by LANL.GOV (5.54/1.14)
	id AA18900; Tue, 23 Feb 88 12:49:37 MST
Received: by raven.lanl.gov.ARPA (3.2/5.17)
	id AA15187; Tue, 23 Feb 88 12:43:29 MST
Date: Tue, 23 Feb 88 12:43:29 MST
From: cgl%raven@lanl.gov (Chris Langton)
Message-Id: <8802231943.AA15187@raven.lanl.gov.ARPA>
To: CA@Think.COM
Subject: equivalence of CA's and pde's...

Peter Wayner writes:

(quoting Omohundro's abstract in Physica 10D)

>> "A system of 10 coupled nonlinear pde's is exhibited which simulates an
>>  arbitrary two-dminesnional, nine-neighbor, square lattice ca."

>In this case, it would seems as if nine-neighbor, square lattice
>CA's are equivalent to differential equations. I would guess that
>the technique can be generalized.

  Peter, I think you are overstating the conclusion. Embedding a CA 
in a set of pde's just shows that the pde's are as powerful as an
arbitrary 2D, nine-neighbor, square lattice CA. Since we know that
such a CA can support universal computation, this means that the 
system of 10 pde's can, a-fortiori, support universal computation as well.

However, stepping outside of the realm of formal computation, I don't
think that Omohundro's embedding shows that CA's are "equivalent" to
pde's. In his system, Omohundro forces "discrete" states on what is in 
reality a continuous system. Furthermore, systems of DE's often relate 
rates of change of GLOBAL variables, such as concentrations of reagents 
and so forth, and although it might be possible to model similiar systems 
LOCALLY in CA, I'm not sure that "equivalence" is the right term to use.
Omohundro's result shows that pde's can support universal computation, so 
pde's can do anything that CA's can do, but can CA's do anything that pde's 
can do? His result doesn't show that. That would require the opposite 
embedding: embed an arbitrary system of pde's in a CA. I have not seen such
an embedding, and I'm a little skeptical that it can be done.

Chris Langton
Center for Nonlinear Studies		phone: 505-665-0059
MS B258					email: cgl@lanl.gov
Los Alamos National Laboratory
Los Alamos, NM 87545

From ca-request@Think.COM  Tue Feb 23 17:57:58 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Tue, 23 Feb 88 17:57:58 EST
Received: by ucbvax.Berkeley.EDU (5.58/1.26)
	id AA25534; Tue, 23 Feb 88 12:35:32 PST
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 23 Feb 88 10:18:35 GMT
From: imagine!pawl23.pawl.rpi.edu!puswad@itsgw.rpi.edu  (Mark-Jason Dominus)
Organization: Rensselaer Cellular Automaton Development Group
Subject: Re: Finite and Infinite Parents
Message-Id: <410@imagine.PAWL.RPI.EDU>
Sender: ca-request@Think.COM
To: ca@Think.COM



 While we're on the subject, here's something interesting:
  If a life pattern has only a finite number of parents, then it posesses
no translational symmetry.  (i.e., it is not periodic)

  Dunno whether it's obvious or not, but if it's not, some of y'all may
have fun thinking about it.
-------------------------------------------------------------------------------
  |   |   |   | 1 | 1 | 0 | 1 | * | 0 | $ | 1 | 0 | 0 | * | 1 | 1 | $ |   |   |
-------------------------------------------------------------------------------
"Turing Machine tape is strongly reminiscent of toilet paper."  

USERFG8M@rpitsmts.BITNET             puswad@pawl.rpi.EDU
USERFG8M%rpitsmts@itsgw.rpi.EDU      dominusm@b21.cs.rpi.EDU  <-- Preferred

                         Ceci n'est pas une pipe |
-------------------------------------------------------------------------------

From ca-request@Think.COM  Fri Feb 26 12:06:18 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Fri, 26 Feb 88 12:06:18 EST
Received: by ucbvax.Berkeley.EDU (5.58/1.26)
	id AA26916; Fri, 26 Feb 88 08:10:32 PST
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 23 Feb 88 16:00:25 GMT
From: steinmetz!galen!leue@uunet.uu.net
Organization: General Electric Research & Devleopment
Subject: Pederson's Worm (Hexagonal Grids)
Message-Id: <9655@steinmetz.steinmetz.UUCP>
Sender: ca-request@Think.COM
To: ca@Think.COM

A recent posting asking about hexagonal (and triangular) grids reminded me of 
something I saw running a long time ago.  I think it was called "Pederson's
Worm" (or something like that) and was definitely a cellular automaton living
in a trangular grid.  The "actors" were "worms" which grew by adding segments
aligned with the grid.  There were (countably infinite?) different rules 
that could be used to define a worm, e.g., add a segment, then turn 30
degrees left unless that was blocked, in which case turn 30 degrees right, 
and so on.  I seem to remember some speculation about whether all worms
eventually died or not.

I also seem to remember that some vendor, prehaps Electronic Arts, published
a commerical version for PC's called "Worms!" (great name).  If anyone
can remember a citation for the original work, I'd be grateful.

-Bill
leue@ge-crd.arpa
uunet!steinmetz!nmr!leue

From cgl%raven@lanl.gov  Fri Feb 26 13:00:14 1988
Received: from LANL.GOV (beta.lanl.gov) by Think.COM; Fri, 26 Feb 88 13:00:14 EST
Received: by LANL.GOV (5.54/1.14)
	id AA26943; Fri, 26 Feb 88 11:00:30 MST
Received: by raven.lanl.gov.ARPA (3.2/5.17)
	id AA18420; Fri, 26 Feb 88 10:53:53 MST
Date: Fri, 26 Feb 88 10:53:53 MST
From: cgl%raven@lanl.gov (Chris Langton)
Message-Id: <8802261753.AA18420@raven.lanl.gov.ARPA>
To: ca@Think.COM
Subject: Paterson's Worm...

Martin Gardner did a "Mathematical Games" column on Paterson's worm. I have
a xerox of the article, but unfortunately I didn't note which issue it came 
from. It should be locatable in the SCI AM index volumes though. The title
is "Fantastic patterns traced by programmed `worms'". It is based on an MIT
AI-lab memo by Michael Beeler which was at one time available from the AI 
lab. Apparently John "Life" Conway had a hand in thinking up the scenario 
as well.I tried to obtain it a while back, but no luck. If anyone has - or 
can check into the availability of - that memo I'd very much like to have 
a copy of it. I'd also like to know of any running version. I'm building
up an archive/library of articles and software pertaining to the simulation
of living systems. 


Chris Langton
Center for Nonlinear Studies			Phone: 505-665-0059
MS B258						email: cgl@lanl.gov
Los Alamos National Laboratory
Los Alamos, NM 87545

From ca-request@Think.COM  Sun Feb 28 19:28:27 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Sun, 28 Feb 88 19:28:27 EST
Received: by ucbvax.Berkeley.EDU (5.58/1.26)
	id AA21440; Sun, 28 Feb 88 16:03:21 PST
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 28 Feb 88 22:25:52 GMT
From: lnd@bu-cs.bu.edu  (Leonid Levin)
Organization: Boston U. Comp. Sci.
Subject: Small fast Universal Turing Machines.
Message-Id: <20254@bu-cs.BU.EDU>
Sender: ca-request@Think.COM
To: ca@Think.COM

I am interested in small universal Turing Machines with a polynomial time
overhead.  I discovered that many best known small UTM's simulate only those TM
working in unary (of course a binary TM may be translated to unary but the
overhead gets exponential). I would be grateful for any information.
	My e-mail address is: lnd@bu-cs.bu.edu .

From ca-request@Think.COM  Wed Mar  9 01:21:56 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Wed, 9 Mar 88 01:21:56 EST
Received: by ucbvax.Berkeley.EDU (5.58/1.26)
	id AA12428; Tue, 8 Mar 88 21:36:47 PST
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 8 Mar 88 07:15:38 GMT
From: ihnp4!att-ih!alberta!franco@ucbvax.berkeley.edu  (Franco Carlacci)
Organization: U. of Alberta, Edmonton, AB
Subject: Limit sets of CA
Message-Id: <1117@pembina.UUCP>
Sender: ca-request@Think.COM
To: ca@Think.COM

In one of his early papers, S Wolfram postulated that the problem
of determining whether or not the limit set of a CA contains only the
null configuration was undecidable. In a report from the U. of.
Waterloo, K. Culik et. al. showed that the problem was indeed undecidable
for CA of dimension  >1. For linear CA they conjectured that the problem was
decidable. I'd like to know if any more work has been done on that problem.
 Also, If any one has a reprint of the paper by L.P. Hurd entitled
"Formal Language Characterizations of Cellular Automaton limit sets" that they
are willing to part with, please e-mail me a response. ( We don't
have the journal "Complex Systems").

                 Thanks in advance
                                          Franco
 

From @cunyvm.cuny.edu:096415@DOLUNI1.BITNET  Fri Mar 11 06:18:42 1988
Received: from CUNYVM.CUNY.EDU by Think.COM; Fri, 11 Mar 88 06:18:42 EST
Message-Id: <8803111118.AA03039@Think.COM>
Received: from DOLUNI1.BITNET by CUNYVM.CUNY.EDU ; Fri, 11 Mar 88 06:06:06 EST
Date: Fri, 11 Mar 88 12:03:55 CET
To: CA@Think.COM
From: 096415%DOLUNI1.BITNET@cunyvm.cuny.edu
Comment: CROSSNET mail via SMTP@INTERBIT

Date: 11 March 1988, 12:01:44 CET
From: 096415   at DOLUNI1
To:   CA at THINK


HELP

























From ca-request@Think.COM  Sat Mar 12 10:35:39 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Sat, 12 Mar 88 10:35:39 EST
Received: by ucbvax.Berkeley.EDU (5.58/1.26)
	id AA08617; Sat, 12 Mar 88 07:27:14 PST
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 10 Mar 88 05:52:49 GMT
From: simon@gargoyle.uchicago.edu  (Janos Simon)
Organization: U of Chicago - Computer Science
Subject: Re: Limit sets of CA
Message-Id: <956@gargoyle.UChicago.EDU>
References: <1117@pembina.UUCP>
Sender: ca-request@Think.COM
To: ca@Think.COM


Exactly what is the problem that was proven undecidable? 

From ca-request@Think.COM  Mon Mar 14 06:07:16 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Mon, 14 Mar 88 06:07:16 EST
Received: by ucbvax.Berkeley.EDU (5.58/1.26)
	id AA23504; Mon, 14 Mar 88 02:52:14 PST
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 14 Mar 88 07:42:05 GMT
From: imagine!pawl11.pawl.rpi.edu!hiebeler@itsgw.rpi.edu  (David E. Hiebeler)
Organization: RPI CS Dept., Rensselaer Cellular Automata Development Group
Subject: crystal formation with CA
Message-Id: <522@imagine.PAWL.RPI.EDU>
Sender: ca-request@Think.COM
To: ca@Think.COM


	Well, thanks to everyone who responded to my query about advantages
of hexagonal(triangular) grids over rectangular grids when it comes to 
doing fluid flow...

	Now, I'm looking for some more info.  I'm doing some stuff with CA
applied to modelling crystal formation (I'm doing this as sort of a joint
project with the CS Dept and the Chemistry Dept here), and I'm testing out
some ideas that my advisor & I came up with...anyways, I'm looking for 
useful pointers to info about the subject.  

	So far, about all I've seen are the book _Cellular Automata
Machines_, by Toffoli & Margolus, and an article by N. Packard titled
"Lattice models for solidification and aggregation" which is in S. Wolfram's
book "Theory and Applications of Cellular Automata".

	The model in Toffoli & Margolus's book was extremely easy to
implement.  Packard's uses a continuous variable at each site, which I
guess I can fake by using the 8 bits/cell that I currently have (though
I haven't done that yet).

	But anyways, I would _really_ like to find some more articles about
the subject, or hear some thoughts about it from anyone out there.
  "xie xie ni men"   (thanks! (mandarin chinese))

--Dave Hiebeler    Internet: hiebeler@csv.rpi.edu  <-- preferred address
  R.D. Box 225A              userfrzk%mts.rpi.edu@itsgw.rpi.edu
  Chatham, NY 12037  Bitnet: USERFRZK@RPITSMTS.BITNET

From @cornellc.ccs.cornell.edu:BECKER@HUMBER.BITNET  Sat Apr  2 16:04:25 1988
Received: from CORNELLC.CCS.CORNELL.EDU by Think.COM; Sat, 2 Apr 88 16:04:25 EST
Message-Id: <8804022104.AA14421@Think.COM>
Received: from HUMBER.BITNET by CORNELLC.CCS.CORNELL.EDU ; Sat, 02 Apr 88 15:22:02 EST
Received: by HUMBER (Mailer X1.25) id 1826; Sat, 02 Apr 88 15:17:19 EST
Date:         Sat, 02 Apr 88 15:14:39 EST
From: Bruce Becker <BECKER%HUMBER.BITNET@cornellc.ccs.cornell.edu>
Subject:      Where is the discussion?...
To: Cellular Automata <CA@Think.COM>

I haven't heard any communication from this group for a while, and I hope to
stir some up! ... That is if the group still exists, for which this is also
a test...
I'll add more to the discussion, if there turns out to be one.

Comments?      - Cheers, Bruce Becker     Humber College     Etobicoke, Ont.

From @cunyvm.cuny.edu:BRC5641@TNTECH.BITNET  Sat Apr  2 18:43:28 1988
Received: from CUNYVM.CUNY.EDU by Think.COM; Sat, 2 Apr 88 18:43:28 EST
Message-Id: <8804022343.AA14861@Think.COM>
Received: from TNTECH.BITNET by CUNYVM.CUNY.EDU (IBM VM SMTP R1.1) with BSMTP id 3472; Sat, 02 Apr 88 18:23:52 EST
Date:     Sat, 2 Apr 88 15:47 CST
From: <BRC5641%TNTECH.BITNET@cunyvm.cuny.edu>
Subject:  Core Wars Info
To: ca@Think.COM
X-Original-To:  ca@think.com

Someone was asking about the Core Wars recently. Dewdney has written a new
book called "The Armchair Universe" which is a collection of his Scientific
American Columns from 1984 to 87. He has a chapter on Core Wars and also
gives the following useful addresses:

Newsletter      The Core War Newsletter
                William R. Buckley, Editor
                5712 Kern Drive
                Huntington Beach, Calif.  92649

Organization    International Core War Society
                Mark Clarkson
                8619 Wassall Street
                Wichita, Kans.  67210

Software        William R. Buckley (address as above)
                (Core War for IBM PC)

                Mark A. Durham
                8282 Cambridge Street #507
                Houston, Tex.  77054
                (Core War for Amiga)

To write Core War programs one must adhere to the "Core War Standards,"
available from Mark Clarkson above. This document precisely describes the
syntax and semantics of Redcode programs.

Hope this helps.

Bruce Copeland
Center for Manufacturing Research
Tennessee Technological University

From @cunyvm.cuny.edu:BRC5641@TNTECH.BITNET  Sat Apr  2 18:55:09 1988
Received: from CUNYVM.CUNY.EDU by Think.COM; Sat, 2 Apr 88 18:55:09 EST
Message-Id: <8804022355.AA14884@Think.COM>
Received: from TNTECH.BITNET by CUNYVM.CUNY.EDU (IBM VM SMTP R1.1) with BSMTP id 3472; Sat, 02 Apr 88 18:23:52 EST
Date:     Sat, 2 Apr 88 15:47 CST
From: <BRC5641%TNTECH.BITNET@cunyvm.cuny.edu>
Subject:  Core Wars Info
To: ca@Think.COM
X-Original-To:  ca@think.com

Someone was asking about the Core Wars recently. Dewdney has written a new
book called "The Armchair Universe" which is a collection of his Scientific
American Columns from 1984 to 87. He has a chapter on Core Wars and also
gives the following useful addresses:

Newsletter      The Core War Newsletter
                William R. Buckley, Editor
                5712 Kern Drive
                Huntington Beach, Calif.  92649

Organization    International Core War Society
                Mark Clarkson
                8619 Wassall Street
                Wichita, Kans.  67210

Software        William R. Buckley (address as above)
                (Core War for IBM PC)

                Mark A. Durham
                8282 Cambridge Street #507
                Houston, Tex.  77054
                (Core War for Amiga)

To write Core War programs one must adhere to the "Core War Standards,"
available from Mark Clarkson above. This document precisely describes the
syntax and semantics of Redcode programs.

Hope this helps.

Bruce Copeland
Center for Manufacturing Research
Tennessee Technological University

From ca-request@Think.COM  Sun Apr  3 23:27:52 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Sun, 3 Apr 88 23:27:52 EDT
Received: by ucbvax.Berkeley.EDU (5.59/1.26)
	id AA08120; Sun, 3 Apr 88 10:11:06 PDT
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 3 Apr 88 00:20:45 GMT
From: pasteur!agate!saturn!ucscb.UCSC.EDU!spcecdt@ucbvax.berkeley.edu  (Space Cadet)
Organization: University of California, Santa Cruz; CATS
Subject: linear automata
Message-Id: <2595@saturn.ucsc.edu>
Sender: ca-request@Think.COM
To: ca@Think.COM

I have posted a linear cellular automata program in comp.binaries.ibm.pc.
It is somewhat limited in its versatility, but is quite fast and at least
produces an interesting display!  :)
--
> John H. DuBois III # spcecdt@ucscb.ucsc.EDU  ...!ucbvax!ucscc!ucscb!spcecdt <

From cgl%raven@lanl.gov  Mon Apr  4 23:47:29 1988
Received: from LANL.GOV (beta.lanl.gov) by Think.COM; Mon, 4 Apr 88 23:47:29 EDT
Received: by LANL.GOV (5.54/1.14)
	id AA00851; Mon, 4 Apr 88 21:47:41 MDT
Received: by raven.lanl.gov.ARPA (3.2/5.17)
	id AA00359; Mon, 4 Apr 88 21:45:20 MDT
Date: Mon, 4 Apr 88 21:45:20 MDT
From: cgl%raven@lanl.gov (Chris Langton)
Message-Id: <8804050345.AA00359@raven.lanl.gov.ARPA>
To: ca@Think.COM
Subject: Daughter of Patterson's Worm....

Patrick Greussal was kind enough to send me a copy of the original MIT
AI memo (#290) on Patterson's Worm. I would be happy to send out copies
to anyone who would like one. 

When we get our scanner, I'll be able to convert arbitrary hard-copies 
to ASCII files and send `em by email! Ain't technology grand! Now we 
have inverse laser-printers! I love it!


Chris Langton

Center for Nonlinear Studies		Phone: 505-665-0059
MS B258					Email: cgl@LANL.GOV
Los Alamos National Laboratory
Los Alamos, New Mexico
87545


From ca-request@Think.COM  Wed Apr  6 21:36:39 1988
Received: from ucbvax.berkeley.edu by Think.COM; Wed, 6 Apr 88 21:36:39 EDT
Received: by ucbvax.berkeley.edu (5.59/1.26)
	id AA06620; Wed, 6 Apr 88 05:00:40 PDT
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 5 Apr 88 14:11:11 GMT
From: amelia!wk05!pulliam@AMES.ARC.NASA.GOV  (Thomas H. Pulliam)
Organization: NASA Ames Research
Subject: crystal growth
Message-Id: <436@amelia.nas.nasa.gov>
Sender: ca-request@Think.COM
To: ca@Think.COM


      I'm looking for references to crystal growth using CA.  Could anyone
help me?  In particular, low gravity crystal growth has resulted in fractal
strucutres.  If anyone has info in that area I would be grateful.




Blue Whales with Peace and Farewell.

     Tom Pulliam x6417    pulliam@wk05 or pulliam@ames-nas

From ca-request@Think.COM  Thu Apr  7 18:26:36 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Thu, 7 Apr 88 18:26:36 EDT
Received: by ucbvax.Berkeley.EDU (5.59/1.26)
	id AA00500; Thu, 7 Apr 88 15:16:36 PDT
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 6 Apr 88 15:21:09 GMT
From: steinmetz!galen!leue@uunet.uu.net
Organization: General Electric Research & Devlopment
Subject: Re: Patterson's Worm
Message-Id: <10288@steinmetz.steinmetz.ge.com>
Sender: ca-request@Think.COM
To: ca@Think.COM

Recently, cgl%raven.lanl.gov.arpa posted a message indicating that he
could mail copies of the original MIT article on Patterson's Worm.  My
mailer is too dumb to reach that address :-), so I'll post the request
here.  Yes, I'd really like to get a copy.  My mailing address is:
	Bill Leue
	General Electric Research & Development Center
	Building K1, Room NMR-135
	1 River Rd.
	Schenectady, NY 12301
Many thanks!
-Bill Leue
leue@ge-crd.arpa
uunet!steinmetz!nmr!leue

From ca-request@Think.COM  Fri Apr  8 21:55:56 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Fri, 8 Apr 88 21:55:56 EDT
Received: by ucbvax.Berkeley.EDU (5.59/1.26)
	id AA21368; Wed, 6 Apr 88 23:36:21 PDT
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 5 Apr 88 08:17:17 GMT
From: imagine!pawl20.pawl.rpi.edu!puswad@itsgw.rpi.edu  (Mark-Jason Dominus)
Organization: Rensselaer Cellular Automaton Development Group
Subject: Philosophical cellular automaton questions we all should be worrying about
Message-Id: <617@imagine.PAWL.RPI.EDU>
Sender: ca-request@Think.COM
To: ca@Think.COM


  Are cellular automata a useful, general simulation and modelling technique?
We know that we can simulate at least these types of processes:
   Heat transfer
   Gas & Fluid diffusion
   Gas & Fluid flow
   Crystal growth & protein aglommeration

There are all things that have been done with CAs a zillion times and are still
being done.  Are these problems fundamentally suited to CA simulation in some
way?  What way is that?  And are there problems which seem completely unap-
proachable by CA methods, regardless of the size of the computer we use?

  I said once that CAs could simulate anything in the universe.  My reasoning
was this way:  

   1:  CAs can model anything that partial differential equations can,
because they work on the same principles:

	a:  That what is happening here and now only depends on what happened 
nearby a little while ago, and long ago, far away things can be ignored.  In
the CA, this arises because of the localizedness of transition functions; in
the DE it arises because of the way derivatives work and because of continuity. 
Really, this is what continuity means.
	b:  Physical laws work the same way everywhere.  We can chuck even this
assumption from either a CA or a DE model, though, by making a nonuniform
transition function in one case or different DEs in different places in the
other case.

   2:  PDEs can model anything, because they are a simple, straightforward way
of describing the way things change.  Period.  If you can describe the way
something changes, what else is there to know about it?  I can't think of
anything.  Certainly they've done a good job so far.

If (1) and (2) are correct, then anything can be modeled with cellular automata.


  There is one difference, and it may be very, very important:  Cellular
automata are discrete models, not continuous ones.  Consider a fluid flow
model.  Maybe there's turbulence.  Maybe the whirlpools and eddies break into
smaller whirlpools and eddies, and smaller, and so on.  Now, they can't do that
for ever, because there's a lower bound on the size of an eddy.  If we can
carry out a CA simulation with a site representing an area about the size of
a water molecule, we may be all right.  At least then we won't scrub out any
detail.  Great.  Now we have to compute billions of sites for billions of
steps.  Maybe more.  

  A differential equation won't have that problem as much; at least not in
the same way.  Differential equations operate in a continuous space, and so
can deal with arbitrarily small eddies.  Here the problem is just the opposite:
The DE's eddies are too small.  Any manageable DE for fluid flow is going to
have to depend on self-similarity to work, otherwise the dtail gets to great
to be manageable.  So the DE model is going to represent fluid flow with 
infinitesimal molecules, infinite detail.  Also wrong.

  How can we expect to develop a fluid flow model that walks the thin line
between infinite detail and insufficient detail?  Is the only answer more
computer power?

  Maybe cellular automata aren't really fundamentally connected to the way the
universe does its business.  After all, when we want to do three-dimensional
fluid flow simulation, we have to do it in four dimensions and look at the 
shadow.  The universe doesn't need four dimensions.  The universe couldn't
care less about the symmetry group of an icosahedron being necessary for iso-
tropy and the fact that icosahedra don't tile threespace.  The universe doesn't
even know what an icosahedron is. It has to be some awful artifact of our sim-
ulation processes.  What went wrong?  Is it the fact that we're using a dis-
crete model of something that really isn't discrete, or is it something else?
Let's hope it's something else, because otherwise all we have is a kludge.
Maybe a kludge that works okay some of the time, but still a kludge.

  Kludge.  Consider gas diffusion.  There are a couple of ways of modelling
it.  We can use DEs: 

     dp          2
   - --  =  K del  p
     dt

  Or we can use CAs:

      Square grid, Margolus neighborhoods.  1 bit / cell. Repeat forever:
      1) Put origin at (0,0). 2) Rotate each Margolus block 90 degrees
      clockwise or counterclockwise, randomly chosen for each block. 
      3) Put origin at (1,1). 4) Rotate each Margolus block 90 degrees
      clockwise or counterclockwise, randomly chosen for each block. 

  The DE gives us a model of an infinitely fine, infinitely dispersable
fluid.  If we start with a drop of gas in a vacuum, it tells us that that gas
spreads out smoothly and continuously, its density getting arbitrarily low,
which is wrong.  Gas density isn't continuous, it's discrete, quantized in
units of 1 molecule / unit volume, but the DE doesn't know that.

  The CA gives us a model which is nicer in some ways; the density quantization
is there, anyway.  In fact, you can even show that the model produced satisfies
the DE if you stand a long way away so that the gas looks very fine and very
dispersable.

  You can even caluclate the value of K for the simulated fluid.

  K?

  Goodness gracious, this model has an innate diffusion constant.  And there's
no way to change it.  If you want to simulate oil spreading on a plate instead
of sugar dissolving in water, you're out of luck.  The mean free path of the
molecules is fixed, too, and you can forget about talking about matters of
fundamental importance like "momentum" and "kinetic energy".

  Even ignoring all that, we still have the problem that there isn't enough
detail.  To do a good simulation, we'd have to have millions of sites and let
it run for a long, long time.  Again, the two models fail in opposite ways.
the DE is to smooth, the CA is too bumpy.

  How can we solve these problems?  Artificiality, lack of detail, hypersmooth-
ness, peculiar mathematical artifacts like the fact that you can do an 
isotropic diffusion model on a square grid but not an isotropic fluid flow
model.  Where do these artifacts come from?  How can we eliminate them?
What if we can't?

  Are there processes we can model that won't give us these problems?
Are there processes we want to model that will be up to their necks in these
problems, so much so that they're impossible to use?  We must understand
what makes these things happen, so we can minimize the effects or at least
know when it'll be hopeless to try.  Otherwise, cellular automaton modelling
will only be a toy.
-------------------------------------------------------------------------------
puswad@pawl.rpi.EDU puswad@pawl.rpi.EDU puswad@pawl.rpi.EDU puswad@pawl.rpi.EDU
        "Oy Gevalt!  With a signature like that, who needs an article?"
-------------------------------------------------------------------------------

From ca-request@Think.COM  Fri Apr  8 23:07:06 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Fri, 8 Apr 88 23:07:06 EDT
Received: by ucbvax.Berkeley.EDU (5.59/1.26)
	id AA03659; Fri, 8 Apr 88 19:32:56 PDT
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 8 Apr 88 23:39:47 GMT
From: ukma!brian@husc6.harvard.edu  (Brian Sturgill)
Organization: U of Ky, Math. Sciences, Lexington KY
Subject: Life
Message-Id: <8868@e.ms.uky.edu>
Sender: ca-request@Think.COM
To: ca@Think.COM

I am looking for references to alternate rules for the birth and death
of cells in the game Life.

Brian
-------------------
           Brian Sturgill          System Manager
   University of Kentucky Departments of Mathematical Sciences
        brian@ms.uky.edu                brian@ms.uky.csnet
        {uunet,cbosgd}!ukma!brian       brian@UKMA.BITNET

From ca-request@Think.COM  Sun Apr 10 02:59:55 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Sun, 10 Apr 88 02:59:55 EDT
Received: by ucbvax.Berkeley.EDU (5.59/1.28)
	id AA27072; Sat, 9 Apr 88 18:39:53 PDT
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 9 Apr 88 18:28:37 GMT
From: jb7m+@andrew.cmu.edu  (Jon C. R. Bennett)
Organization: Carnegie Mellon University
Subject: life code requested
Message-Id: <sWLapJy00WAB459EZt@andrew.cmu.edu>
Sender: ca-request@Think.COM
To: ca@Think.COM

I have been told that there was a posting of some very fast life
code/algorithim on this board, and I would be very grateful if someone who has
it lying around, or the original poster could send it to me. I am curently
working on an ATK (andrew toolkit) version of life and would like it to run a
bit faster then the version that I currently have.

Thanks in advance

Jon Bennett

jcrb@vega.fac.cs.cmu.edu
jb7m@andrew.cmu.edu

From ca-request@Think.COM  Sun Apr 10 12:32:13 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Sun, 10 Apr 88 12:32:13 EDT
Received: by ucbvax.Berkeley.EDU (5.59/1.28)
	id AA08463; Sun, 10 Apr 88 05:24:12 PDT
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 10 Apr 88 05:53:56 GMT
From: well!wcalvin@lll-lcc.llnl.gov  (William Calvin)
Organization: Whole Earth 'Lectronic Link, Sausalito, CA
Subject: Re: Life
Message-Id: <5653@well.UUCP>
References: <8868@e.ms.uky.edu>
Sender: ca-request@Think.COM
To: ca@Think.COM


See the book by William Poundhouse, THE RECURSIVE UNIVERSE (Wm. Morrow
1985).

  William H. Calvin   UUCP:  ucbvax!well!wcalvin
  Univ. of Washington BITNET:   wcalvin@uwalocke
  Biology NJ-15       ARPA: lll-crg!well!wcalvin
  Seattle WA 98195    206/328-1192  206/543-1648

From n@tiger.ccsr.uiuc.edu  Sun Apr 10 15:08:28 1988
Received: from uxc.cso.uiuc.edu by Think.COM; Sun, 10 Apr 88 15:08:28 EDT
Received: from tiger.ccsr.uiuc.edu
	by uxc.cso.uiuc.edu with SMTP (UIUC-5.52/9.7)
	id AA24896; Sun, 10 Apr 88 14:09:26 CDT
Received: by tiger.ccsr.uiuc.edu (3.2/9.7)
	id AA02921; Sun, 10 Apr 88 14:13:20 CDT
Date: Sun, 10 Apr 88 14:13:20 CDT
From: n@tiger.ccsr.uiuc.edu (Norman H. Packard)
Message-Id: <8804101913.AA02921@tiger.ccsr.uiuc.edu>
To: ca@Think.COM
Subject: ca crystal growth


A request came my way (forwarded by Wolfram) for ca crystal growth.
I have a paper on the subject, and would be glad to send it to whoever
wants to read it.  My model is actually not, strictly speaking a cellular
automaton, because it uses both discrete and continuous variables at
each lattice site.

The request listed an address of pulliam@ames-nas, but a message to there
got bounced back to me.  There were some alternatives, but I have lost 
them.

	Norman Packard




From ca-request@Think.COM  Mon Apr 11 01:16:48 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Mon, 11 Apr 88 01:16:48 EDT
Received: by ucbvax.Berkeley.EDU (5.59/1.28)
	id AA19436; Sun, 10 Apr 88 21:33:14 PDT
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 10 Apr 88 22:58:36 GMT
From: rochester!ritcv!jdb9608@rutgers.edu  (J. David Beutel)
Organization: Rochester Institute of Technology, Rochester, NY
Subject: Re: Life
Message-Id: <366@ritcv.UUCP>
References: <8868@e.ms.uky.edu>, <5653@well.UUCP>
Sender: ca-request@Think.COM
To: ca@Think.COM


   I tried to mail, but it was returned.  I thought perhaps this would
be of general interest anyway.  Look out; it's long!


Subject: Returned mail: Host unknown
550 PT.CS.CMU.EDU!andrew.cmu.edu!jb7m+... Host unknown
Subject: Re: life code requested
Newsgroups: comp.theory.cell-automata
In-Reply-To: <sWLapJy00WAB459EZt@andrew.cmu.edu>

There was *alot* of discussion about life in the rec.games.programmer
newsgroup.  Here is what I saved of it:


+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Article 50 of rec.games.programmer:
>From: saponara@batcomputer.tn.cornell.edu (John Saponara)
Newsgroups: rec.games.programmer
Subject: Re: need rules for life
Date: 18 Jan 88 17:00:52 GMT
Summary: Rules, more rules, sources, and a cool object to try out

I had the same problem of non-delivery to the person requesting Life rules,
so here goes (excuse the repetition - it'll get more interesting in a moment):

On a square grid each square is in one of two states, alive or dead.
Simultaneously during one generation (i.e. one move) you check all squares.
If the square is alive, it stays alive to the next generation if touched by
2 or 3 other live squares.  "Touched by" means the 8 squares adjacent to
the square.  If the live square is touched by <=1 or >=4 live squares, then
it turns into a dead square at the beginning of the next generation.  If a
dead square is touched by exactly 3 live squares, it turns into a live square
the next generation; otherwise it stays dead.  Typically, live squares are
represented by "O"'s on the screen.

A lively variant is 3/4 Life, where living squares survive if touched by 3 or
4 other live squares only, and dead squares turn alive if touched by 3 or 4
live squares.  Things tend to be very unstable - regular Life seems to have a
lot more of interest to it.

Sources: Mathematical Games in old "Scientific American"s by Martin Gardner
have a lot of info. I recall the issues are during 1971 and 1972 - about 3 or
4 issues altogether.  Gardner's book "Wheels, Life, and Other Mathematical
Recreations" (or something like that) collects this info in one spot, I
believe.  "Scientific American"'s present column Computer Recreations had an
article about Life on a 3D grid which was pretty cool (the issue was Feb. 87).
The inventor of Life, John Horton Conway, is co-author of "Winning Ways", an
amazing 2 volume set of books on all kinds of games, including Life.  The best
part is when he describes how you could use objects from Life to actually make
a computer (gliders sent off as data streams, with various collisions to
perform AND and OR and NEGATE operations; blocks hit by gliders simulate
memory.  Fascinating theory, showing that you can map any unproved theory to
a Life setup.  For example, you could program a Life computer to attempt to
solve Fermat's Last Theorem, and if a solution was found have the computer
destroy itself.  In this way, all unsolved problems can be mapped to one
overarching problem: given a particular setup in Life, can you predict whether
the final outcome will be having some objects left or having no life left?
If this problem could be solved, then all problem which could be programmed
could be solved (which basically means to me that you can't solve this
problem).  Interesting stuff!)

I also have the complete collection of LifeLines by Robert Wainwright, a journal
which ran for about 11 issues in the early 70's that recorded a massive amount
of information on Life.  One of the quickest tidbits to pass on to you all is
this object:

..O......
....O....
.OO..OOO.

This is known as the acorn, which takes an amazing 5209 generations to settle
down, and yields 34 blocks, 8 boats, 24 beehives, 2 ships, 5 loaves, 2 ponds,
2 barges, 1+3/4 honeyfarms, 22 blinkers, 4+3/4 traffic lights, 13 gliders,
plus an unnamed object.  Makes the "R" pentomino look pretty wimpy.

Anyway, that's about all I'd like to pass on: have a happy Life!

Eric Haines


Article 60 of rec.games.programmer:
>From: saponara@batcomputer.tn.cornell.edu (John Saponara)
Newsgroups: rec.games.programmer
Subject: Re: need rules for life
Date: 21 Jan 88 16:48:06 GMT
Reply-To: saponara@tcgould.tn.cornell.edu (Eric Haines, actually)


The fastest algorithm I know for Life is one I wrote up long ago.  Here's
the description for it - hope it makes sense to you all.  It's an interesting
approach (and a memory hog), but it get rid of all those "check the surrounding
8 cells" tests every generation.

Eric Haines

		 A standard Life algorithm is to look through the grid, get a
	    list of births and deaths, then change these locations on the
	    grid (we need lists so that all changes can happen simultaneously).
	    This is pretty fast, but we have to calculate the sum of eight
	    neighbors for each cell each generation--a lot of calculations!
	    The advantage of this algorithm is that the birth and death lists
	    are pretty short and only one grid list has to be maintained.

		 The kernel of the fastest algorithm I know is to look at the
	    Life grid in terms of both which cells are dead and alive and how
	    these cells affect the grid. The method is to take an initial grid,
	    such as:

		 0 0 0 0 0
		 0 0 1 0 0
		 0 0 1 0 0
		 0 0 1 0 0
		 0 0 0 0 0
	   
	   where 1's represent live cells. In this case the grid contains a
	   blinker. To set up for the algorithm, start with this original grid,
	   which I'll call the "data field", and a new grid initialized to
	   zeros, which I call a "neighbor field". Start with a search for
	   1's on the data field. Whenever a 1 is found, put 1's in all the
	   neighboring positions on the neighbor field. In our example, this
	   leads to:

		 0 0 0 0 0			0 1 1 1 0
		 0 0 1 0 0			0 2 1 2 0
		 0 0 1 0 0   <-data field	0 3 2 3 0   <-neighbor field
		 0 0 1 0 0			0 2 1 2 0
		 0 0 0 0 0			0 1 1 1 0
	   
	   Now the algorithm begins. The steps are:

	   1.  Search through the data field.
	       A.  If the data square is 1, check the neighbor field.
		   ii. If the neighbor square is < 2 or > 3, a death occurs:
		       - Save the location of the square on a "morgue list".
	       B.  If the data square is 0, check the neighbor field.
		   i.  If the neighbor square is 3, a birth occurs:
		       - Save the location of the square on a "nursery list".
	   2.  Bury the dead--for each location on the morgue list:
	       - Change the data field location to a 0.
	       - Subtract 1 from the 8 neighbors on the neighbor field.
	   3.  Bear children--for each location on the nursery list:
	       - Change the data field location to a 1.
	       - Add 1 to the 8 neighboring locations on the neighbor field.
	   {The order of steps 2 & 3 is unimportant}

	   Label the columns from left to right 1-5 and rows from top to bottom
	   1-5 in our example. Step 1 then gives:

		 Morgue list:
		 death at row 2, column 3, at data=1 and neighbor=1 ( < 2 ).
		 death at row 4, column 3, at data=1 and neighbor=1 ( < 2 ).

		 Nursery list:
		 birth at row 3, column 2, as data=0 and neighbor=3.
		 birth at row 3, column 4, as data=0 and neighbor=3.

		 (Survival at row 3, column 3, as neighbor=2)

	   Step 2 changes the fields as shown:

		 0 0 0 0 0			0 0 0 0 0
		 0 0 0 0 0			0 1 1 1 0
		 0 0 1 0 0   <-data field	0 1 0 1 0   <-neighbor field
		 0 0 0 0 0			0 1 1 1 0
		 0 0 0 0 0			0 0 0 0 0
		
	   Step 3 then makes these changes:

		 0 0 0 0 0			0 0 0 0 0
		 0 0 0 0 0			1 2 3 2 1
		 0 1 1 1 0   <-data field	1 1 2 1 1   <-neighbor field
		 0 0 0 0 0			1 2 3 2 1
		 0 0 0 0 0			0 0 0 0 0
	   
	   We now have a new generation, and are ready for some simple
	   compares for our next determination of deaths and births.

	   Expressing this in a more orderly way, we get:

	   x and y are the grid dimensions.

	   dimension cells(x,y), neighbor(x,y)

	   dimension morgue(x*y,2)	{both lists could be smaller}
	   dimension nursery(x*y,2)

	   sl = 2 {lowest survival level: if # neighbors < sl, cell dies}
	   su = 3 {highest survival level: if # neighbors > su, cell dies}
	   bl = 3 {lowest birth level: if # neighbors < bl, cell is not born}
	   bu = 3 {highest birth level: if # neighbors > bu, cell is not born}

	   {for 3/4 life, the above values are 3,4,3,4}

	   {create neighbor field - just do Step 3 for initial point list}

	   {repeat the following for each generation}
	   mtot <- 1
	   ntot <- 1
	   for i = 1 to x
	       for j = 1 to y
		   { the following test can be simplified by a simple look
		     up list }
		   if cells(i,j) = 1
		       then if neighbor(i,j) < dl or neighbor(i,j) > du
			   morgue(mtot,1) <- i
			   morgue(mtot,2) <- j
			   mtot <- mtot + 1
		   if cells(i,j) = 0
		       then if neighbor(i,j) >= bl and neighbor(i,j) <= bu
			   nursery(ntot,1) <- i
			   nursery(ntot,2) <- j
			   ntot <- ntot + 1
	
	    for p = 1 to mtot
		i <- morgue(p,1)
		j <- morgue(p,2)
		cells(i,j) <- 0
		for l = i-1 to i+1
		    for m = j-1 to j+1
			neighbor(l,m) <- neighbor(l,m) - 1

		neighbor(i,j) <- neighbor(i,j) + 1
	    
	    for q = 1 to ntot
		i <- nursery(q,1)
		j <- nursery(q,2)
		cells(i,j) <- 0
		for l = i-1 to i+1
		    for m = j-1 to j+1
			neighbor(l,m) <- neighbor(l,m) + 1

		neighbor(i,j) <- neighbor(i,j) - 1

	   end of generation.

	        This algorithm is much more efficient than the standard Life
	   program. In the standard Life program, Step 1 requires that we sum
	   up the eight neighbors for all grid locations each generation. In
	   our new algorithm, we calculate once the effect of neighbors by
	   creating the neighbor field. Now all we have to do is check the
	   contents of the location on the neighbor field to see what affect
	   its neighbors are having on it. Updating the neighbor field
	   admittedly takes longer than standard Life program's method of
	   simply changing the data field. However, there are so few births
	   and deaths in comparison to the overall grid size that this method
	   is much faster in practice. The other minus is the size of the
	   nursery and morgue lists, though in practice these don't have to
	   be the same length as the the number of grid squares.

	       Anywell, thought you'd be interested in this algorithm. What I
	   thought was interesting about it is that it reflects a much
	   different way of thinking about Life. Instead of just discrete
	   points, we also keep track of influences and effects of neighbors.
	   These fields are just a different way to view things: instead of
	   seeing the objects (which are not recorded in the neighbor field),
	   we see the influence of the objects on the next generation.


	   p.s. another, more mundane, speedup is to keep track of how many
	   objects are in each row and column. You then check these at the
	   beginning of each generation to find an upper and lower bound for
	   the rows and columns. That is, you find the lowest non-zero and
	   subtract 1, and highest non-zero and add 1 to obtain the area of
	   interest.

	   Another speed-up is to simply have a list which represent the
	   test conditions, i.e. instead of:
		       then if neighbor(i,j) < dl or neighbor(i,j) > du
	   do:
		dimension death_cond(0..8) = [ 0 0 1 1 0 0 0 0 0 ]
	   {one's represent the conditions under which a live cell survives}

	   and test:
		       then if death_cond( neighbor(i,j) ) == 0
	    
	   Usually the extra array access is quicker than two 'if' tests.  This
	   also makes for a more flexible Life testbed: you could easily try
	   conditions like "a cell survives if touched by 1, 3, or 5 other
	   cells" - this would simply be [ 0 1 0 1 0 1 0 0 0 ].


>From rochester!cornell!batcomputer!saponara Tue Jan 26 11:17:41 EST 1988
Article 75 of rec.games.programmer:
Newsgroups: rec.games.programmer
Subject: Re: need rules for life, continued
Reply-To: saponara@tcgould.tn.cornell.edu (Eric Haines)
Summary: various and sundry


Do y'all have the issues of "Lifeline" by Robert Wainwright?  This was a little
journal devoted entirely to Life, with some fantastic creations (my favorite
is the puffer train whose exhaust turns into glider guns - the train actually
leaves a line of glider guns which then produce gliders!)  These are a great
resource for objects and I'd love to pass them on to fellow Lifenthusiasts.  If
there is enough interest, I will try to contact Wainwright's family (I believe
Robert died - does anyone know for sure?) and see if I can run off a reprint
for the price of xeroxing and mailing.  There're 142 pages of solid info on
Life.  Given the continuing interest, it seems worth a reissue.

What sources for Life info do you all have other than "Scientific American",
"Winning Ways", Martin Gardner books, and "The Recursive Universe" (and
derivative articles that say mostly the same thing)?  I'm interested in
any new info any might have to share.

After seeing some articles on competition in a Life setting:  have you ever
heard of the two-person life game?  I think I first saw it in the ancient
"101 Basic Computer Games" by David Ahl.  The gist is that you start with a
board of, say, 5x5 dimensions.  Each player marks 5 cells initially with
his own color.  Then a generation is ticked off, and each player can then
change any empty cell to his own color.  Another generation ticks off, etc,
until either everything dies (draw, or, to my way of thinking, both sides lose)
or all tokens are of one color (regardless of whether the final configuration
could survive, even with more planting).  The only change to Life rules are
that a birth takes place under the normal "touched by 3" rules, with the color
being determined by the majority color which touches.

All for now,

.0.....
...0...		the "acorn" - try it out!
00..000

Eric Haines (not John Saponara)


Article 77 of rec.games.programmer:
>From: johnf@apollo.uucp (John Francis)
Newsgroups: rec.games.programmer
Subject: life programmming  (LONG)
Date: 25 Jan 88 21:25:00 GMT


 Aaah, LIFE!  The program that used up the most non-productive CPU
cycles until the Mandelbrot set became popular :-).

I have been writing LIFE programs for a very long time. In fact, I
wrote the first one ever!  I was a student at Cambridge University
when John Conway was developing the game, and I happened to stroll
in to the Mathematics common room when he was tracking the fate of
the 'r' pentomino (using a 'go' board & counters).  This seemed to
me to be a task ideally suited for a computer,  so I headed off to
the Institute of Theoretical Astronomy, where there was an IBM 360
Model 44 with a lot of free time on it.  I wrote a quick-and-dirty
program, and tracked the 'r' pentomino for 250 generations. On the
following morning, when I dropped 250 pages of line-printer output
in front of Conway, he called me something impolite!   I later ran
the program to track the 'r' pentomino further, but gave up around
generation 1000 (I was using a fairly small fixed-size universe).
If only I had made that array a little larger, I would probably be
immortalized in LIFE history (for those of you who don't know, the
'r' pentomino stabilises at generation 1103).
Since then I have written LIFE programs for a wide variety of CPUs
and display systems, including one for the DEC GT40 (a PDP-11/05 &
a graphics display screen). I was very proud of this one - it kept
track of a population of up to 2500 - 3000 live cells on a machine
with only 8K bytes of memory, with a 32K x 32K universe.

 So much for my credentials.  What tips do I have for those of you
who want to write your own LIFE programs?  Read on : -

 o  Don't store the board as a fixed-size array - use some sort of
    linked-list scheme.  The one I tend to use is a list of active
    rows, with each row header pointing to a list of active cells.
    If you work on a machine with limited physical memory then use
    two different schemes - bidirectional linked lists for the bit
    of the world you are currently processing,  but a more compact
    scheme for scanlines above and below the region of interest.

    This not only saves memory - it also saves CPU time, since you
    don't have to look at those vast areas of empty space.

 o  Don't just store 'on/off' information for cells - save all the
    'neighbourhood' information you calculate as well. This allows
    you to only spend CPU time computing what has changed,  rather
    than recomputing static areas of the board.

The following algorithm is not (quite) the most efficient one that
I know of, but is is far easier to explain than any of the others.
(the description does not address problems introduced by using the
two-level storage scheme, at that would complicate it too much).

Each 'cell' contains a numeric field, and three flags. These could
all be squeezed into a single byte, but unless you are prepared to
have a universe of only 256 x 256 you will want to use 16 bits for
coordinates, so use the sign bit of 2 different bytes for 2 of the
flags, place the numeric field in the rest of one of these bytes &
the third flag in the rest of the other byte. This allows a packet
of coordinate, numeric field and 3 flags to fit nicely in 32 bits,
and  allows 2 of the flags to be tested very efficiently. (In fact
the two flags in the second byte are really one three-state flag).
This will be represented below in the shorthand form 'f:n,t', with
f being the first flag (0 or 1), n the numeric field, and t the 3-
state variable (+, -, or 0).

The 'neighbourhood' I use looks like this :

                  . . . . .
                  . 2 2 2 .
                  . 2 1 2 .
                  . 2 2 2 .
                  . . . . .

In other words for each 'live' cell I add one to the numeric field
for that cell, and two to that each of the eight adjacent cells.


Step 0: (Initial board setup).
        Initialize each of the starting live locations to 0:0,+
        (and anything else allocated to 1:0,0) then skip to Step 2.

Step 1: (Births & Deaths)
        Scan for cells with a '0' value of f. If you find one then
        set the tri-state variable for that cell as follows, based
        on the numeric field for the cell:      [use table-lookup]

            old n           new t       comments
            =====           =====       ========
            0,2,4             0         No change
            1,3               -         Death by isolation
            5                 0         Survival
            6                 +         Birth
            7,9,11,13,15,17   -         Death by overcrowding
            8,10,12,14,16     0         No change

        In all cases, set the f flag to 1.

Step 2: (Neighbourhood adjustment)
        Scan for cells with a tri-state value of '+' or '-'. If
        you find one then:
            Set the f flag to '0' for this cell and the 8 adjacents,
            and then either add (if t is +) or subtract (if t is -)
            the neighbourhood values from the numeric fields.

            Update the display screen appropriately.

        In all cases, set the t flag to 0

    If no candidate cells were found in Step 2 then stop, otherwise
    repeat entire process from Step 1 ad infinitum (or ad nauseam :-).


Obvious optimizations are to keep an 'f' flag with each row, (set to
zero if any of the cells on this row has an 'f' flag of zero) and to
use this flag to skip over entire rows where nothing is changing.


This algorithm should knock spots off anything but the most sophisticated
life programs.  Feel free to use it, but it would be appreciated if you
could put a credit line in your source code.
This is getting long so I'll stop now, and post another article with the
rest of what I have to say. Let me know how you get on.

                John Francis        (...!apollo!johnf).


-- 
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
                                          __________
                                         ___    ___
                                        __________      11011011
         Kent for President            ___    ___ 
                                      ___    ___     jdb9608@ritcv.UUCP
                                     ___    ___      jdb9608@ritvax.BITNET

From ca-request@Think.COM  Mon Apr 11 09:00:22 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Mon, 11 Apr 88 09:00:22 EDT
Received: by ucbvax.Berkeley.EDU (5.59/1.28)
	id AA23290; Mon, 11 Apr 88 03:36:57 PDT
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 11 Apr 88 07:56:26 GMT
From: pepper!cmcmanis@sun.com  (Chuck McManis)
Organization: Sun Microsystems, Mountain View
Subject: Re: Life
Message-Id: <49003@sun.uucp>
References: <8868@e.ms.uky.edu>
Sender: ca-request@Think.COM
To: ca@Think.COM

In article <8868@e.ms.uky.edu> brian@ms.uky.edu (Brian Sturgill) writes:
>I am looking for references to alternate rules for the birth and death
>of cells in the game Life.

I have been working on an implementation of Life for the Amiga that includes
custom rules in both single and double species environments. It isn't done
yet (RSN) but if you are interested send me some mail.

--Chuck McManis
uucp: {anywhere}!sun!cmcmanis   BIX: cmcmanis  ARPAnet: cmcmanis@sun.com
These opinions are my own and no one elses, but you knew that didn't you.

From ca-request@Think.COM  Mon Apr 11 20:07:04 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Mon, 11 Apr 88 20:07:04 EDT
Received: by ucbvax.Berkeley.EDU (5.59/1.28)
	id AA05705; Mon, 11 Apr 88 15:48:58 PDT
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 11 Apr 88 19:49:24 GMT
From: jb7m+@andrew.cmu.edu  (Jon C. R. Bennett)
Organization: Carnegie Mellon University
Subject: Re: Life
Message-Id: <YWMGB4y00Uo5Q1wl5Q@andrew.cmu.edu>
References: <8868@e.ms.uky.edu>
Sender: ca-request@Think.COM
To: ca@Think.COM

Here are a few that I know of as good rules....

34/34
1234/3 - patterns "crystalize"
12345/45 - patterns become contained
12345/4 - same as above, but settles VERY quickly
5/12 - floor tile patterns... Variations of this tend to be interesting as well.
/2 - most patterns expand indefinitely, some interesting ones. Fast gliders.

the format for that is  live/born i.e. 5/12 is born on a 1 or a 2 lives on a 5

Have fun

Jon Bennett

From hag%hawk@lanl.gov  Tue Apr 12 00:53:32 1988
Received: from LANL.GOV (beta.lanl.gov) by Think.COM; Tue, 12 Apr 88 00:53:32 EDT
Received: by LANL.GOV (5.54/1.14)
	id AA15469; Mon, 11 Apr 88 22:54:51 MDT
Received: by hawk.lanl.gov.ARPA (3.2/5.17)
	id AA09874; Mon, 11 Apr 88 22:54:31 MDT
Date: Mon, 11 Apr 88 22:54:31 MDT
From: hag%hawk@lanl.gov (Howard A. Guttowitz)
Message-Id: <8804120454.AA09874@hawk.lanl.gov.ARPA>
To: CA@Think.COM
Subject: Life

Some may be interested in analytical work on the Game of Life.
The Grand-dad paper is Shulman and Seiden "A dynamical system based
on the Game of Life" (or words to that effect) Journal of Statistical
Physics 1978. Their work is extended in "Local Structure Theory
in More Than One Dimension" Gutowitz and Victor , Complex Systems
Volume 1, number 1. Also a preprint which treats the statistical
mechanics of analogs of Life on the 2-D hex lattice may be had
by writing to H. Gutowitz, Laboratory of Mathematical Physics,
Rockefeller University, 1230 York Ave. NY, NY 10021-6399.

                       hag%hawk@lanl.gov


From ca-request@Think.COM  Wed Apr 13 01:48:10 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Wed, 13 Apr 88 01:48:10 EDT
Received: by ucbvax.Berkeley.EDU (5.59/1.28)
	id AA28439; Tue, 12 Apr 88 14:21:32 PDT
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 12 Apr 88 17:22:06 GMT
From: saponara@tcgould.tn.cornell.edu  (John Saponara)
Organization: Cornell Theory Center, Cornell University, Ithaca NY
Subject: Life and Lifeline
Message-Id: <4392@batcomputer.tn.cornell.edu>
Sender: ca-request@Think.COM
To: ca@Think.COM

Posted originally on rec.games.programmer - thought you all might be
interested, too:

A few months ago I offered to pass on my old issues of Lifeline.  At the
same time, I found Robert T. Wainwright's address in _The Recursive
Universe_.  Yesterday I heard from him, and it turns out that he still
sells the back issues of LIFELINE, the journal about Life from the
early 1970's.

The complete set (issues 1-11, 128 jam-packed pages) is $13 plus $2 for
postage.  Write him at:

	Robert T. Wainwright
	12 Longue Vue Avenue
	New Rochelle, NY  10804

If you have any interest in the game, this info is de rigeur - truly wonderful
stuff.  My favorite being the puffer trains whose exhaust combine into a row
of glider guns - awe inspiring.

Eric Haines

From ca-request@Think.COM  Wed Apr 13 21:35:30 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Wed, 13 Apr 88 21:35:30 EDT
Received: by ucbvax.Berkeley.EDU (5.59/1.28)
	id AA15212; Wed, 13 Apr 88 07:02:11 PDT
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 13 Apr 88 04:58:32 GMT
From: imagine!pawl1.pawl.rpi.edu!hiebeler@itsgw.rpi.edu  (David E. Hiebeler)
Organization: RPI Computer Science Dept.
Subject: Intro to FHP hexagonal lattice-gas rule
Message-Id: <653@imagine.PAWL.RPI.EDU>
Sender: ca-request@Think.COM
To: ca@Think.COM


Some time ago, someone posted something asking for some FHP source-code.
While I do have the actual source-code to a version of FHP that I implemented,
I figured that the summary of collisions might be more useful and easy to
read (though this is not necessarily so...)
  So anyways, here is a summary of all of the collisions that I put into the
version of I have running here.  All collisions were taken from the article
"Lattice Gas Hydrodynamics in Two and Three Dimensions", by Frisch,
d'Humieres, Hasslacher, Lallemand, Pomeau, and Rivet, which was published in
_Complex Systems_, vol 1 no 4 (August 1987), pp 649-707;  the exception to
this are the particle-wall collisions, which I made up myself.
  The model uses 8 bits/cell, and runs on a hexagonal grid (how you choose
to implement the hexagonal grid is arbitrary) -- 6 bits for moving particles,
one bit for the presence or non-presence of a particle moving in each of the
6 directions; 1 bit for the possible presence of a "rest" particle with 0
velocity (but which may be struck by other particles and move away); 1 bit
for "permanent" particles, or "wall" particles, which never move.
  In the following diagrams, 'o' represents a rest particle, 'X' represents
a wall particle, and there are 6 possible other particles, moving in each
of 6 possible directions.  A cell that has one particle moving in each of
the 6 directions would be shown as:

     6     5
       \ /        The '.' in the middle is nothing, just there to show
    1 --.-- 4     where the center of the picture is.
       / \         And I've arbitrarily labeled the 6 directions.
     2     3

-------
Summary of FHP lattice-gas model as implemented by D. Hiebeler on the
Sequent Balance 21000, using the _autogrid_ cellular automata processor
written by D. Hiebeler, G. Kyriazis, and M.J. Dominus.

2-particle collisions:

                \            /
  --.--    ==>   .    or    .
                  \        /

                  /
  --o      ==>   .
                  \

   \
    .      ==>   o--
   /

3-particle collisions:

   \              /
    .--    ==> --.
   /              \

                \
 --.--     ==>   .
  /             / \

                  /
 --.--     ==>   .
    \           / \

4-particle collisions:

  \ /             /           \
   .       ==> --.--    or   --.--
  / \           /               \

particle-wall collisions:

   \            \
    X      ==>   X


   \X            X
    X      ==>   X
    X           /X

   \              /
   XXX     ==>  XXX

These all have rotational equivalents as well.
Any transitions which are not shown follow the identity transition, i.e.
they don't change.
------
What was shown here was the COLLISION phase of the FHP model.  When you
run the simulation, you alternate between COLLISION phases and PROPAGATION
phases.  During the C-phase, you change the state of a cell according to
the current state of the cell, as shown above.  During the P-phase, you
propagate the particles, that is, the particles actually move along the
lines of the lattice.  So after two steps, for example, a particle will
have moved one position on the lattice (unless it's a rest particle).
------
This is really fairly straightforward to program.   Let me make a note
about the wall/particle collisions, since I don't know how standard my
method is.  To determine which way a particle should bounce off a wall,
for example if a particle is coming in from direction 6: I check to see
if the neighbor along direction 1 has a wall and if the neighbor along
direction 5 has a wall.  If both do, or neither does, than the particle
will bounce back from whence it came, as this is either an isolated wall
particle, or is a corner-piece (whether inside or outside of a corner doesn't
matter).  If 1 has a wall, and 5 doesn't, then the particle will bounce
off in direction 5, and vice-versa.  Anyways, it works, and it gives you
fairly decent specular reflections.
------
So far, all I've done with this is simulate fluid-flow around a straight
wall.  I have a steady input of particles from the left, most of them moving
to the right (but with a very tiny fraction of them moving in directions 3
and 5, the exact number picked randomly).  I do indeed get what I've seen
called "Karman streets" or some turbulence, behind the wall.
The nifty thing about this model is that to simulate fluid-flow around a
jet's nose, or around a square, for example, all I have to do is draw the
object.  The code does not need to be changed in any way.
------
Anyways, I hope that was at least remotely interesting to someone.
I'm doing all this as part of some work I'm doing between the Computer
Science and Chemistry departments here, with lattice-gas models and their
many applications, such as fluid-flow, crystal-formation, etc...  I run
the simulations on a 16-processor Sequent Balance 21000, where I wrote a
generalized cellular automata processor that reads in a CA algorithm and
writes a parallel C program for you to run the simulation.

  If someone wants to see the actual C code, send a message.  If lots of
people actually want to see it (like more than 2 B-) ) I'll post it.
This group really needs some traffic anyways.

-Dave Hiebeler       Internet: hiebeler@csv.rpi.edu  <-- preferred address
 R.D. Box 225A                 userfrzk%mts.rpi.edu@itsgw.rpi.edu
 Chatham, NY 12037     Bitnet: USERFRZK@RPITSMTS.BITNET

From ca-request@Think.COM  Sun Apr 17 19:17:43 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Sun, 17 Apr 88 19:17:43 EDT
Received: by ucbvax.Berkeley.EDU (5.59/1.28)
	id AA06890; Sun, 17 Apr 88 02:55:06 PDT
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 17 Apr 88 01:44:17 GMT
From: agate!saturn!ucscb.UCSC.EDU!spcecdt@ucbvax.berkeley.edu  (Space Cadet)
Organization: University of California, Santa Cruz; CATS
Subject: Linear cellular automata
Message-Id: <2856@saturn.ucsc.edu>
Sender: ca-request@Think.COM
To: ca@Think.COM

I have posted another linear cellular automata program to comp.binaries.ibm.pc
It is much more general than the one I posted previously, though at the cost
of color graphics  :)   It uses characters to represent cells, instead of 
colored pixels.  Source is included in the arc file and it will also compile
under BSD.
--
> John H. DuBois III # spcecdt@ucscb.ucsc.EDU  ...!ucbvax!ucscc!ucscb!spcecdt <

From ca-request@Think.COM  Tue Apr 19 10:33:46 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Tue, 19 Apr 88 10:33:46 EDT
Received: by ucbvax.Berkeley.EDU (5.59/1.28)
	id AA08696; Tue, 19 Apr 88 00:51:49 PDT
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 18 Apr 88 16:24:57 GMT
From: tikal!phred!daveh@beaver.cs.washington.edu  (Dave Hampton)
Organization: Research Div, Physio-Control Corp.
Subject: Cardiac Function
Message-Id: <2165@phred.UUCP>
Sender: ca-request@Think.COM
To: ca@Think.COM


     We have recently begun to work on a finite-element model of the heart,
reconstructed from CT scans.  We would like to use this model to explore
the origins of circulating currents which can cause fibrillation in humans.
As an approach, it would be nice to attach a simple rule to each element
which will simulate the excitable properties of the normal and ischemic tissues.
I have a paper done some years back by Moe which explores
this idea, but, being new to cellular automata, need some additional sources
of information.

     I'm looking for pointers to two items in particular:

     1)  Good, current, general texts on Cellular Automata, and
     2)  Papers which discuss it's use in modelling electrical potential
  at a point above a plane surface of moving charges.

     Any suggestions via e-mail would be appreciated.  If there is
any general interest, I will be happy to summarize replies to the net.

     Dave Hampton

-- 
Reply to:  uiucuxc!tikal!phred!daveh {Dave Hampton}
Addr:      Research Division, Physio-Control Corp.
           P.O. Box 97006
           Redmond, WA  98073-9706

From ca-request@Think.COM  Wed Apr 20 21:47:42 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Wed, 20 Apr 88 21:47:42 EDT
Received: by ucbvax.Berkeley.EDU (5.59/1.28)
	id AA19518; Wed, 20 Apr 88 18:46:49 PDT
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 10 Apr 88 23:30:10 GMT
From: trwrb!felix!ccicpg!cci632!ritcsh!ritcv!jdb9608@ucbvax.berkeley.edu  (J. David Beutel)
Organization: Rochester Institute of Technology, Rochester, NY
Subject: Re: Rules of Life
Message-Id: <368@ritcv.UUCP>
Sender: ca-request@Think.COM
To: ca@Think.COM

I read this just after I posted that big life message.

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

From rochester!cornell!batcomputer!saponara Sun Apr 10 18:15:06 EST 1988
Article 152 of rec.games.programmer:
Newsgroups: rec.games.programmer
Subject: Life and Lifeline
Reply-To: saponara@tcgould.tn.cornell.edu (Eric Haines)
Lines: 18
Summary: It's still available!

A few months ago I offered to pass on my old issues of Lifeline.  At the
same time, I found Robert T. Wainwright's address in _The Recursive
Universe_.  Yesterday I heard from him, and it turns out that he still
sells the back issues of LIFELINE, the journal about Life from the
early 1970's.

The complete set (issues 1-11, 128 jam-packed pages) is $13 plus $2 for
postage.  Write him at:

	Robert T. Wainwright
	12 Longue Vue Avenue
	New Rochelle, NY  10804

If you have any interest in the game, this info is de rigeur - truly wonderful
stuff.  My favorite being the puffer trains whose exhaust combine into a row
of glider guns - awe inspiring.

Eric Haines


++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
                                          __________
                                         ___    ___
                                        __________      11011011
         Kent for President            ___    ___ 
                                      ___    ___     jdb9608@ritcv.UUCP
                                     ___    ___      jdb9608@ritvax.BITNET

From ca-request@Think.COM  Thu Apr 21 19:18:49 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Thu, 21 Apr 88 19:18:49 EDT
Received: by ucbvax.Berkeley.EDU (5.59/1.28)
	id AA05838; Thu, 21 Apr 88 08:54:26 PDT
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 21 Apr 88 05:01:04 GMT
From: imagine!pawl4.pawl.rpi.edu!hiebeler@itsgw.rpi.edu  (David E. Hiebeler)
Organization: RPI Computer Science Dept.
Subject: Ugly C code, to do FHP lattice-gas
Message-Id: <744@imagine.PAWL.RPI.EDU>
Sender: ca-request@Think.COM
To: ca@Think.COM


	Well, I got a bunch of responses to my article about basic rules
to implement the FHP lattice-gas model, asking to see the actual C code.
	I was kinda reluctant to let anyone see the code, because it's about
3-rd grade mentality as far as C goes.  Now, before I get a dozen flames
telling me that switch statements are faster than all those if-statements,
let me tell you -- I tried it with switch-statements, and it did go a bit
faster but not a great deal.
	There are 2 files -- the neighbor-definitions for a hexagonal grid,
and the rule-file itself (which is called "fluid3.bc"). They are intended
to be run through this cellular-automata processor myself and 2 other people
here at RPI wrote on a Sequent Balance 21000 here.  However, it's mostly
C code, and the things that are specific to our program are obvious and
commented.
	I've run the simulation usually on a 512x256 grid, which is
sufficient to get the general idea of what's going on, and occasionally
on a 1024x512 grid.  To display the results of the fluid flow, I average
the velocies of small blocks of particles (the size of the blocks I average
over is specified by the user).  If there's interest, I'll leave a data-
file or 2, also a couple of rasters, somewhere for anonymous FTP.  They're
by no means professional quality, my program may very well still have bugs,
but if you want to see them, let me know.
  Sorry, people who don't want to see this, but it's not as if you have to
wade through dozens of source-code postings, eh?  Anyways, here it is:

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
This is the "hex8" file.
Define a rectangular-grid implementation of a hexagonal or triangular grid.
Based upon an article in Complex Systems journal,
 implemented by Dave Hiebeler with the 'autogrid' cellular automata processor
 on a Sequent Balance 21000.

/* even or odd row of grid? */
#define even ((y%2)==0)
#define odd ((y%2)==1)
/* define x-1, x+1, y-1, and y+1 with wraparound */
#define ym (y-1+YSIZE)%YSIZE
#define yp (y+1)%YSIZE
#define xm (x-1+XSIZE)%XSIZE
#define xp (x+1)%XSIZE
/* define x-2, x+2, y-2, y+2 with wraparound */
#define ymm (y-2+YSIZE)%YSIZE
#define ypp (y+2)%YSIZE
#define xmm (x-2+XSIZE)%XSIZE
#define xpp (x+2)%XSIZE

/* define the 6 neighbors and the current cell */
/* Oh -- one note -- the '8's mean that these are 8-bit neighbors */
/* That's kind of an artifact of our cell_automata processor that
   will probably be taken out of the next version, as it's kinda useless */
%define center8 8 grid[src][x][y]
%define one8 8 grid[src][xm][y]
%define two8 8 even ? grid[src][xm][yp] : grid[src][x][yp]
%define three8 8 even ? grid[src][x][yp] : grid[src][xp][yp]
%define four8 8 grid[src][xp][y]
%define five8 8 even ? grid[src][x][ym] : grid[src][xp][ym]
%define six8 8 even ? grid[src][xm][ym] : grid[src][x][ym]

/* also define the 2-away neighbors */
%define farone8 8 grid[src][xmm][y]
%define fartwo8 8 grid[src][xm][ypp]
%define farthree8 8 grid[src][xp][ypp]
%define farfour8 8 grid[src][xpp][y]
%define farfive8 8 grid[src][xp][ymm]
%define farsix8 8 grid[src][xm][ymm]

END OF hex8
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
START OF fluid3.bc

This is the "fluid3.bc" file
FHP lattice-gas model
--implemented by Dave Hiebeler, March 1988
/* include the hexagonal neighbor definitions */
%include hex8

/* Declare a global phase-variable */
%declare phase
/* Declare global var which is the probability of a particle entering from
   the left edge */
%declare prob

/* Arbitrary definitions of what the particular bits in a cell represent.
 * Here, bits 1-6 represent the presence of a particle moving in one of the
 * 6 possible directions; bit 7 represents a rest-particle, and bit 8
 * represents a permanent particle, or wall-particle. */
#define ONE 0x01
#define TWO 0x02
#define THREE 0x04
#define FOUR 0x08
#define FIVE 0x10
#define SIX 0x20
#define REST 0x40
#define WALL 0x80
/* Define some useful macros which say if a particle is coming in from a
 * particular direction */
#define IN_ONE (one8&FOUR)
#define IN_TWO (two8&FIVE)
#define IN_THREE (three8&SIX)
#define IN_FOUR (four8&ONE)
#define IN_FIVE (five8&TWO)
#define IN_SIX (six8&THREE)

/* List which of the defined neighbors will actually be used in this rule */
%rulelist
	center8
	one8
	two8
	three8
	four8
	five8
	six8
%listend

/* Perform necessary initializations, such as seeding the random-# generator
 * and prompting the user for the probability of particles entering on the
 * left */
%init
{
long rseed;

printf("Enter a long int as a random # seed: ");
scanf("%ld",&rseed);
srandom(rseed);
printf("enter probability of left-particle existing: ");
scanf("%d",&prob);
}
%endinit

/* Extra statements that are executed between each time-step.  Here, all
 * that needs to be done, is changing the phase-variable so that it
 * alternates 0--1--0--1--0 during the simulation. */
%extra
	phase = 1-phase;
%endextra

/* Here we go.  Everything after here is the actual rule, or transition-
 * function */
%rule
{
int count,temp;

    if (phase==0) {  /* collision phase */
	if (!center8) return(0);  /* current cell is empty, return empty */
	/* Count how many neighbors are alive */
	count = ((!!(center8&ONE))+(!!(center8&TWO))+(!!(center8&THREE))+(!!(center8&FOUR))+(!!(center8&FIVE))+(!!(center8&SIX)));

/* Collision of two opposite particles */
    if (count==2) {
	/* First, check for regular head-on collisions */
	if (center8==(ONE|FOUR)) {
		if (random()%2) return(TWO|FIVE);
		else return(THREE|SIX);
	}
	if (center8==(TWO|FIVE)) {
		if (random()%2) return(ONE|FOUR);
		else return(THREE|SIX);
	}
	if (center8==(THREE|SIX)) {
		if (random()%2) return(ONE|FOUR);
		else return(TWO|FIVE);
	}
    }

    if (count==3) {
	/* First, handle the easy case -- the 3 particles are coming in along
	   either directions 1,3,5 or 2,4,6 */
	if (center8==(ONE|THREE|FIVE))
		return(TWO|FOUR|SIX);
	if (center8==(TWO|FOUR|SIX))
		return(ONE|THREE|FIVE);
	/* Well, see if it's a head-on collision with a spectator */
	if ((center8&ONE)&&(center8&FOUR)) {
		if (center8&TWO) return(TWO|THREE|SIX);
		if (center8&THREE) return(TWO|THREE|FIVE);
		if (center8&FIVE) return(THREE|FIVE|SIX);
		if (center8&SIX) return(TWO|FIVE|SIX);
	}
	if ((center8&TWO)&&(center8&FIVE)) {
		if (center8&ONE) return(ONE|THREE|SIX);
		if (center8&THREE) return(ONE|THREE|FOUR);
		if (center8&FOUR) return(THREE|FOUR|SIX);
		if (center8&SIX) return(ONE|FOUR|SIX);
	}
	if ((center8&THREE)&&(center8&SIX)) {
		if (center8&ONE) return(ONE|TWO|FIVE);
		if (center8&TWO) return(ONE|TWO|FOUR);
		if (center8&FOUR) return(TWO|FOUR|FIVE);
		if (center8&FIVE) return(ONE|FOUR|FIVE);
	}
    }

/* Collision of 4 particles -- really the complement of the 2-particle
   collisions above */
    if (count==4) {
	if (center8==(ONE|TWO|FOUR|FIVE)) {
		if (random()%2) return(ONE|THREE|FOUR|SIX);
		else return(TWO|THREE|FIVE|SIX);
	}
	if (center8==(TWO|THREE|FIVE|SIX)) {
		if (random()%2) return(ONE|TWO|FOUR|FIVE);
		else return(ONE|THREE|FOUR|SIX);
	}
	if (center8==(ONE|THREE|FOUR|SIX)) {
		if (random()%2) return(ONE|TWO|FOUR|FIVE);
		else return(TWO|THREE|FIVE|SIX);
	}
    }
/* Possible collision with a rest particle */
	if (center8&REST) {
		if (center8==(ONE|REST))
			return(TWO|SIX);
		if (center8==(TWO|REST))
			return(ONE|THREE);
		if (center8==(THREE|REST))
			return(TWO|FOUR);
		if (center8==(FOUR|REST))
			return(THREE|FIVE);
		if (center8==(FIVE|REST))
			return(FOUR|SIX);
		if (center8==(SIX|REST))
			return(FIVE|ONE);
		return(center8);
	}

/* Two properly colliding particles will produce a rest particle */
	if (center8==(ONE|THREE))
		return(REST|TWO);
	if (center8==(TWO|FOUR))
		return(REST|THREE);
	if (center8==(THREE|FIVE))
		return(REST|FOUR);
	if (center8==(FOUR|SIX))
		return(REST|FIVE);
	if (center8==(FIVE|ONE))
		return(REST|SIX);
	if (center8==(SIX|TWO))
		return(REST|ONE);

/* There's a wall here */
	if (center8&WALL) {
		if (IN_ONE) {
			if ((two8&WALL)==(six8&WALL)) return(WALL|ONE);
			if (two8&WALL) return(WALL|SIX);
			if (six8&WALL) return(WALL|TWO);
			return(WALL|ONE);
		}
		if (IN_TWO) {
			if ((one8&WALL)==(three8&WALL)) return(WALL|TWO);
			if (one8&WALL) return(WALL|THREE);
			if (three8&WALL) return(WALL|ONE);
			return(WALL|TWO);
		}
		if (IN_THREE) {
			if ((two8&WALL)==(four8&WALL)) return(WALL|THREE);
			if (two8&WALL) return(WALL|FOUR);
			if (four8&WALL) return(WALL|TWO);
			return(WALL|THREE);
		}
		if (IN_FOUR) {
			if ((three8&WALL)==(five8&WALL)) return(WALL|FOUR);
			if (three8&WALL) return(WALL|FIVE);
			if (five8&WALL) return(WALL|THREE);
			return(WALL|FOUR);
		}
		if (IN_FIVE) {
			if ((four8&WALL)==(six8&WALL)) return(WALL|FIVE);
			if (four8&WALL) return(WALL|SIX);
			if (six8&WALL) return(WALL|FOUR);
			return(WALL|FIVE);
		}
		if (IN_SIX) {
			if ((five8&WALL)==(one8&WALL)) return(WALL|SIX);
			if (five8&WALL) return(WALL|ONE);
			if (one8&WALL) return(WALL|FIVE);
			return(WALL|SIX);
		}
		return(WALL);
	}
	return(center8);
    }
	
/* Phase is 1 -- propagation phase */

	temp = 0;
	if (center8&WALL) return(WALL); /* If there's a wall here,
					    keep it here */
	/* Send in some particles from the left.  Most of them will
	   be going to the right, a few will be going in the directions
	   / and \ . */
	if (x==0) {
		if ((random()%100)<(prob/2)) return(FOUR);
		if ((random()%100)<(prob*3/4)) return(FIVE);
		if ((random()%100)<(prob)) return(THREE);
	}
	/* For the rest of the cells, just propagate the particles along
	   in the direction they're headed... */
	if (IN_ONE) temp |= FOUR;
	if (IN_TWO) temp |= FIVE;
	if (IN_THREE) temp |= SIX;
	if (IN_FOUR) temp |= ONE;
	if (IN_FIVE) temp |= TWO;
	if (IN_SIX) temp |= THREE;
	if (center8&REST) temp |= REST;
	return(temp);
}

-=-=-=-=-=-=-=-=-=
 Well, there it is...  send  comments, complaints, whatever, to:

Dave Hiebeler          Internet: hiebeler@csv.rpi.edu
R.D. Box 225A                    userfrzk%mts.rpi.edu@itsgw.rpi.edu
Chatham, NY 12037        BITNET: USERFRZK@RPITSMTS.BITNET

From POTHIERS%TUVA.SAINET.MFENET@nmfecc.arpa  Fri Apr 22 14:46:01 1988
Received: from NMFECC.ARPA by Think.COM; Fri, 22 Apr 88 14:46:01 EDT
Received: from tuva.sainet.mfenet by ccc.mfenet with Tell via MfeNet ;
	Fri, 22 Apr 88 11:47:31 PDT
Date: 	  Fri, 22 Apr 88 11:47:31 PDT
From: POTHIERS%TUVA.SAINET.MFENET@nmfecc.arpa
Message-Id: <880422114731.20a00215@NMFECC.ARPA>
To: CA@Think.COM

Subject: Video "Life"
Date:    Fri, 22-APR-1988 11:06 MST
X-VMS-Mail-To: @CA

I've noticed some interesting Cellular Automata like effect while
playing with a video camera and TV. I put the camcorder on a tripod a
couple feet from the TV started playing with feed-back.

There are about 6 parameters to this system. Four are on the TV (color
saturation, hue, brightness, and contrast). Two are on the camcorder
(zoom and rotation). 

The effects that can be acheived are amazing! I got the most
interesting effects when the room lights were off. I tilted the
camcorder a little more than 90 degrees to get symetry and rotational
movement. I then used a
flashlight aimed at the TV to interfere with the feedback in
interesting ways. Some of the effects were very much like "gliders"
and "shooters" in "Life". Long period oscillations can be easily set
up. The manipulation of the color parameters has dramatic effects. I
assume that much of the effects are due to the cameras and TVs
differing sensitivity to different parts of the color spectrum.

Some interesting stable patterns emerged that looked like brain coral.
When I put my hand between the camera and the TV I could put cracks in
the brain formation. The cracks would slowely fill in and the pattern
would restabilize. Very small changes in the amount of zoom would
cause the pattern to appear to grow inwards or to grow outwards.

Steve Pothier
pothiers%tuva.sainet@nmfecc.arpa

From cgl%raven@lanl.gov  Fri Apr 22 18:17:38 1988
Received: from LANL.GOV (beta.lanl.gov) by Think.COM; Fri, 22 Apr 88 18:17:38 EDT
Received: by LANL.GOV (5.54/1.14)
	id AA17656; Fri, 22 Apr 88 15:36:32 MDT
Received: by raven.lanl.gov.ARPA (3.2/5.17)
	id AA07642; Fri, 22 Apr 88 15:22:47 MDT
Date: Fri, 22 Apr 88 15:22:47 MDT
From: cgl%raven@lanl.gov (Chris Langton)
Message-Id: <8804222122.AA07642@raven.lanl.gov.ARPA>
To: CA@Think.COM
Subject: Re: video-feedback & CA's

Steve,

    The video-feedback that you describe is closely related to CA's.
    Due to imprecision in the system, neighborhoods of a pixel
    will determine the future state of each pixel, allowing
    information to flow across the image at a rate that depends 
    on the focal precision of the system. 
    
    Some other parameters that will affect the dynamics that you
    don't mention are 1) focus (affects the neighborhood size, among
    other things), and 2) delay (the intrinsic delay in the loop - 
    which can be played around with by putting an adjustable tape 
    delay or electronic delays in the loop. The nice thing
    about such systems is that they are effectively continuous
    in many of the areas where CA are discrete, e.g., continuous
    values for the state of each pixel, neighborhood effects that
    fall off smoothly over a region, and many of the parameters are
    continuous. Drawbacks include the fact that it is not easy
    to program - or even determine! - the rule-table in effect.

    You should check the article by Crutchfield on the dynamics
    of video-feedback in the proceedings
    of the 1983 workshop on CA, held here at Los Alamos. The 
    proceedings are also published in Physica D, V10, 1984.
    
    Crutchfield has done quite a lot of work with video-feedback
    and I understand he now has quite a nice computer controlled/
    servo-motor system for moving/zooming the camera wrt the screen.
    
    Hofstadter also gives an example of video-feedback in his
    book: Godel, Escher, Bach...


Chris Langton

Center for Nonlinear Studies		Phone: 505-665-0059
MS B258					Email: cgl@LANL.GOV
Los Alamos National Laboratory
Los Alamos, New Mexico
87545


From ca-request@Think.COM  Fri Apr 29 02:49:47 1988
Received: from ucbvax.Berkeley.EDU by Think.COM; Fri, 29 Apr 88 02:49:47 EDT
Received: by ucbvax.Berkeley.EDU (5.59/1.28)
	id AA09469; Wed, 27 Apr 88 19:27:52 PDT
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 25 Apr 88 09:56:21 GMT
From: hanley@nyu.edu  (John Hanley)
Organization: New York University
Subject: Re: video-feedback & CA's
Message-Id: <25689@cmcl2.NYU.EDU>
References: <8804222122.AA07642@raven.lanl.gov.ARPA>
Sender: ca-request@Think.COM
To: ca@Think.COM

In article <8804222122.AA07642@raven.lanl.gov.ARPA> cgl%raven@LANL.GOV (Chris Langton) writes:
>    The video-feedback ... is closely related to CA's.....
>    Hofstadter also gives an example of video-feedback in his
>    book: Goedel, Escher, Bach...

An exhibit at San Francisco's Exploratorium, done by an artist in residence,
lets you fiddle with the zoom and rotation of a camera pointed at a TV
and is capable of reproducing all of the patterns shown in Gebstadter's
Eternal Golden Braid.  I found it fascinating and played with it for a
long time, but Steve Pothier's posting makes it apparent that there are oodles
of fun parameters to tweak, and if I really want to do it right I should
probably go get a cam-corder.  (Videotape?  What do I need that for?
Oh, yes, variable delay...)  It would be extremely interesting to be able
rapidly switch the video source from a computer to the camera, for providing
an initial highly-controlled field.  If the analog ruleset can be determined
and the F/B loop computes something useful, perhaps the results could be
grabbed with a framegrabber?

BTW, I cannot exhort you strongly enough to go visit the Exploratorium.
It is the size of an aircraft hanger and it's stuffed to the gills with
interactive exhibits that reach out and say "play with me!", like the
wind tunnel with objects to stick in the flow, or the synth with a spectrum
analyzer above it.  Just about all areas of science are represented.  Go.
You'll love it.

                   --John Hanley,
 /  /   ____ __  __  System Programmer, Manhattan College [..cmcl2!manhat!jh ]
/__/ /__ /  /-< /-/  Researcher, NYU Ultracomputer Labs   [  Hanley@NYU.arpa ]

"The Ultracomputer: to boldly go in log N time where no N processors have
 gone before."

From ca-request@Think.COM  Sat May  7 11:48:55 1988
Received: from Think.COM by fafnir.think.com; Sat, 7 May 88 11:48:55 EDT
Return-Path: <ca-request@Think.COM>
Received: from ucbvax.Berkeley.EDU by Think.COM; Sat, 7 May 88 11:48:46 EDT
Received: by ucbvax.Berkeley.EDU (5.59/1.28)
	id AA11718; Sat, 7 May 88 02:56:54 PDT
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 6 May 88 16:25:49 GMT
From: imagine!pawl14.pawl.rpi.edu!puswad@itsgw.rpi.edu  (Mark-Jason Dominus)
Subject: My long article-- I need a copy
Message-Id: <858@imagine.PAWL.RPI.EDU>
Sender: ca-request@Think.COM
To: ca@Think.COM


  A few weeks ago I posted a long article titled "Deep Philosphical Questions
abot Cellular Automata That We All Should Be Thinking About."  I need a copy
of it, but I can't find it anywhere.  If you saved a copy, could you please
mail it back to me?  I would be very appreciative.

  Thanks very much.

Mark-Jason Dominus
puswad@pawl.rpi.EDU
USERf269@rpitsmts.BITNET

From ca-request@Think.COM  Mon May  9 09:35:26 1988
Received: from Think.COM by fafnir.think.com; Mon, 9 May 88 09:35:26 EDT
Return-Path: <ca-request@Think.COM>
Received: from ucbvax.Berkeley.EDU by Think.COM; Mon, 9 May 88 09:35:14 EDT
Received: by ucbvax.Berkeley.EDU (5.59/1.28)
	id AA27085; Sat, 7 May 88 18:44:30 PDT
Received: from USENET by ucbvax.Berkeley.EDU with netnews
	for ca@think.com (ca@think.com)
	(contact usenet@ucbvax.Berkeley.EDU if you have questions)
Date: 7 May 88 19:16:22 GMT
From: imagine!pawl4.pawl.rpi.edu!hiebeler@itsgw.rpi.edu  (David E. Hiebeler)
Organization: RPI Computer Science Dept.
Subject: FHP image available
Message-Id: <865@imagine.PAWL.RPI.EDU>
Sender: ca-request@Think.COM
To: ca@Think.COM

Well, now that I posted the intro to FHP, and also my horrible C code for
FHP, I might as well make available some of the results using this code.

And I've done just that.  I made available one of my data-files, the result
of running the FHP on a 1024 x 512 grid, for around 15,000 steps.  I put
a small vertical wall near the left side, and let particles flow in from
the left side.  The turbulence formed on the right side of the wall, and
extends across thoe whole grid off the right.
The image is available in two formats:  As the raw data from my CA program,
and also as a SUN Raster, where I averaged blocks of cells' velocities
(the typical way of doing it).

These files are available for anonymous FTP from 
	life.pawl.rpi.edu (128.113.10.2)
They are in the directory   pub/fluid
and there is a README file in there along with the other stuff.
Also in the directory is the intro to FHP article that I had posted before.

-- Dave Hiebeler  Internet: hiebeler@cs.rpi.edu  (preferred address)
   R.D. Box 225A            hiebeler@life.pawl.rpi.edu
   Chatham, NY 12037        userfrzk%mts.rpi.edu@itsgw.rpi.edu
		    BITNET: USERFRZK@RPITSMTS.BITNET
  

From cgl%raven@lanl.gov  Wed May 11 13:38:22 1988
Received: from Think.COM by fafnir.think.com; Wed, 11 May 88 13:38:22 EDT
Return-Path: <cgl%raven@lanl.gov>
Received: from LANL.GOV ([128.165.4.4]) by Think.COM; Wed, 11 May 88 13:37:57 EDT
Received: by LANL.GOV (5.54/1.14)
	id AA08805; Wed, 11 May 88 10:07:38 MDT
Received: by raven.lanl.gov.ARPA (3.2/5.17)
	id AA16030; Wed, 11 May 88 09:51:20 MDT
Date: Wed, 11 May 88 09:51:20 MDT
From: cgl%raven@lanl.gov (Chris Langton)
Message-Id: <8805111551.AA16030@raven.lanl.gov.ARPA>
To: ca@Think.COM
Subject: addendum on video-feedback...

On giving it a little more thought..... 
   
       Although I don't have a system to try this out on, I would think that 
   the best way to get strange-attractor-governed video-feedback phenomena 
   (a mix of info-compression and info-amplification) would be by going from 
   a magnification of just slightly < 1 (for info-retention + compression) 
   to just > 1 (for info-amplification). The retained information in the 
   infinite regress of TV's within TV's should carry some compression effects 
   across into the amplification regime. Similarly, going from mag slightly > 1 
   to slightly < 1 should carry some amplicication effects across into the 
   information compression regime. 
   
   Crutchfield may discuss this - (somebody ``borrowed'' my copy of the 
   proceedings containing his article several months ago.)

Chris Langton

Center for Nonlinear Studies		Phone: 505-665-0059
MS B258					Email: cgl@LANL.GOV
Los Alamos National Laboratory
Los Alamos, New Mexico
87545


From cgl%raven@lanl.gov  Thu May 12 09:31:06 1988
Received: from Think.COM by fafnir.think.com; Thu, 12 May 88 09:31:06 EDT
Return-Path: <cgl%raven@lanl.gov>
Received: from LANL.GOV (beta.lanl.gov) by Think.COM; Thu, 12 May 88 09:30:13 EDT
Received: by LANL.GOV (5.54/1.14)
	id AA18005; Thu, 12 May 88 07:30:41 MDT
Received: by raven.lanl.gov.ARPA (3.2/5.17)
	id AA16866; Thu, 12 May 88 07:14:17 MDT
Date: Thu, 12 May 88 07:14:17 MDT
From: cgl%raven@lanl.gov (Chris Langton)
Message-Id: <8805121314.AA16866@raven.lanl.gov.ARPA>
To: ca@Think.COM
Subject: pre-addendum message (!)

[ My previous message - "addendum on video-feedback" - was supposed 
  to be an addendum to the following message. Since I only saw
  the addendum - but not the message it was supposed to "addend" 
  - come back across the net, I am assuming that this didn't get
  to anybody else either. My apologies if this is a repeat -
  here is the whole thing together ...]
  
------------------------------------------------------------------

 
   In an email message to me, Les Clewlow points out that 
   in my comments on video-feedback, I was implicitly assuming that
   the magnification of the screen image is = 1.0, which I should have stated
   explicitly. Then - assuming that the focus is slightly fuzzy - only a small
   neighborhood of a pixel will affect the future state of that pixel (ignoring
   ambient light effects). This is the situation that most closely resembles
   classical CA's. However, zoom (both + and -) and rotation will both introduce
   global information into the update of each pixel and thus these situations
   are not so similar to classical CA's.  
   
   If the magnification (zoom) is > 1, then the system behaves 
   something like iterated maps with areas of slope > 1: it
   amplifies the noise in the system, which is one of the ways to get 
   chaotic or random behavior. With magnification < 1 (i.e. the TV image 
   is displayed in a sub-space of the screen) one gets the inverse of 
   course: info compression, with "infinite regress" of images - something
   like mirror tunnels. In this case, the area around the TV set that
   appears in the image can be used as a source of input to the system.
   
   When the mag is just slightly < 1, there is quite a lot of information 
   retention possible in the feedback loop. As I understand it, zooms across 
   the mag = 1 boundary can lead to some funny mix of the two - yielding the
   possibility for strange attractors, with both amplification and 
   compression of information occurring at the same time.
   
   Although I don't have a system
   to try this out on, I would think that this should work best going from a mag 
   of just slightly < 1 (for info retention + compression) to just > 1 (for info 
   amplification). The retained information in the infinite regress of TV's 
   within TV's should carry some compression effects across into the amplification
   regime. Similarly, going from mag slightly > 1 to slightly < 1 should carry
   some amplicication effects across into the information compression regime.
   Crutchfield may discuss this - somebody ``borrowed'' my copy of the 
   proceedings containing his article several months ago.
   
   Similarly, rotation gives rise to global effects on updating. The more
   bizarre effects are usually due to some combination of rotation and 
   zoom. One can see why it is necessary to have the camera mounted on
   some sort of servo-control mechanism to get precise, repeatable 
   results. As is typical in such systems, small differences in the
   parameters can lead to wildly different global behaviors.
   

Chris Langton

Center for Nonlinear Studies		Phone: 505-665-0059
MS B258					Email: cgl@LANL.GOV
Los Alamos National Laboratory
Los Alamos, New Mexico
87545

   

From cgl%raven@lanl.gov  Fri Jul 15 10:56:07 1988
Received: from Think.COM by fafnir.think.com; Fri, 15 Jul 88 10:56:07 EDT
Return-Path: <cgl%raven@lanl.gov>
Received: from LANL.GOV (MILNET-GW.LANL.GOV) by Think.COM; Fri, 15 Jul 88 09:58:31 EDT
Received: by LANL.GOV (5.54/1.14)
	id AA10304; Fri, 15 Jul 88 08:56:57 MDT
Received: by raven.lanl.gov.ARPA (4.0/5.17)
	id AA28307; Fri, 15 Jul 88 08:57:49 MDT
Date: Fri, 15 Jul 88 08:57:49 MDT
From: cgl%raven@lanl.gov (Chris Langton )
Message-Id: <8807151457.AA28307@raven.lanl.gov.ARPA>
To: ca@Think.COM
Subject: CA-simulator for Suns - beta-test available


   We are in the process of developing a window-based cellular automaton 
tool for Sun-3 and Sun-4 workstations. At present, we have a working beta-test 
version available, and we would be interested in having people try it out and 
give us their feedback on the sorts of features they would like to see in such a 
tool. The beta-test version is limited to running 2D, 64x64 arrays, using the von 
Neumann neighborhood with up to 8-states per cell. The final version will run 1D 
or 2D arrays, arbitrary sizes, a variety of neighborhoods, and will allow more 
states per cell. It will also provide some real-time analysis capabilities, and 
will be able to communicate with user-supplied programs via sockets. We will put 
the tool in the public domain at the end of the summer. 

If you would like to test the program and return your comments on it, please contact 
Chris Langton (cgl@LANL.GOV) or Charles Ferenbaugh (crf%hawk@LANL.GOV).


Chris Langton

Center for Nonlinear Studies		Phone: 505-665-0059
MS B258					Email: cgl@LANL.GOV
Los Alamos National Laboratory
Los Alamos, New Mexico
87545




From kubiak@uicsgva.csg.uiuc.edu  Sat Jul 16 11:48:40 1988
Received: from Think.COM by fafnir.think.com; Sat, 16 Jul 88 11:48:40 EDT
Return-Path: <kubiak@uicsgva.csg.uiuc.edu>
Received: from uxc.cso.uiuc.edu by Think.COM; Sat, 16 Jul 88 10:48:30 EDT
Received: from bach.csg.uiuc.edu
	by uxc.cso.uiuc.edu with SMTP (5.51/9.7)
	id AA19652; Sat, 16 Jul 88 08:47:49 CDT
Received: from uicsgva.csg.uiuc.edu by bach.csg.uiuc.edu (3.2/9.7)
	id AA09730; Sat, 16 Jul 88 08:45:55 CDT
Received: by uicsgva.csg.uiuc.edu (1.2/9.4),
	id AA25243; Sat, 16 Jul 88 08:51:09 cdt
Date: Sat, 16 Jul 88 08:51:09 cdt
From: kubiak@uicsgva.csg.uiuc.edu (Ken "if I seem a little strange it's because I am" Kubiak)
Message-Id: <8807161351.AA25243@uicsgva.csg.uiuc.edu>
To: ca@Think.COM

   This type of tool could be very useful.  But of course, what everybody
will want to know is "how fast is it?"

Ken Kubiak
Computer Systems Group - Coordinated Science Lab - UIUC
kubiak@debussy.csg.uiuc.edu

From cgl%cardinal@lanl.gov  Wed Aug 10 11:22:12 1988
Received: from Think.COM by fafnir.think.com; Wed, 10 Aug 88 11:22:12 EDT
Return-Path: <cgl%cardinal@lanl.gov>
Received: from LAMBDA.LANL.GOV (MILNET-GW.LANL.GOV) by Think.COM; Wed, 10 Aug 88 11:26:50 EDT
Received: by LAMBDA.LANL.GOV (5.54/1.14)
	id AA09114; Wed, 10 Aug 88 09:24:39 MDT
Received: by cardinal.lanl.gov.ARPA (3.2/5.17)
	id AA17335; Wed, 10 Aug 88 09:26:14 MDT
Date: Wed, 10 Aug 88 09:26:14 MDT
From: cgl%cardinal@lanl.gov (Chris Langton)
Message-Id: <8808101526.AA17335@cardinal.lanl.gov.ARPA>
To: ca@Think.COM
Subject: CA-simulator update



For those who have obtained the beta-test version of our CA-simulator for Suns:

Hopefully you have been able to copy the simulator and try it out.  If you have any
comments on what you've seen so far, we'd like to hear from you.  Our plan is to make the
improved version (including sources!) available on or around September 1, and if possible
we'd like to incorporate your suggestions into the finished product.

The following features have already been added since the beta-version release:
- variable array size, up to 256x256
- variable no. of states, up to 16
- choice of neighborhoods (VonNeumann, Moore, or linear (1-d))
- pullright menus (in accordance with Sunview conventions)
- options for Run command, such as intermittent display, no display, or time-bounded run
- random image generation
- socket interface with data-analysis programs
- image shifting

We are also planning to include in the forthcoming version:
- a closeup mode for inspecting small areas of the display
- the capacity to load an image of one size into a display of another size
- header comments in image and transition files

Please send any additional suggestions you might have to Chris Langton (cgl@LANL.GOV)
or Charles Ferenbaugh (crf%raven@LANL.GOV).  Thanks!

From bruce@Think.COM  Wed Aug 24 12:31:50 1988
Received: from Think.COM by fafnir.think.com; Wed, 24 Aug 88 12:31:50 EDT
Return-Path: <bruce@Think.COM>
Received: from NRL-ThinkSun.ARPA by Think.COM; Wed, 24 Aug 88 12:31:25 EDT
Received: by NRL-ThinkSun.ARPA (3.2/SMI-3.2)
	id AA10422; Wed, 24 Aug 88 12:32:58 EDT
Date: Wed, 24 Aug 88 12:32:58 EDT
From: bruce@Think.COM (Bruce Nemnich)
Message-Id: <8808241632.AA10422@NRL-ThinkSun.ARPA>
To: CA@Think.COM
Subject: CA List
Reply-To: CA-Request@Think.COM

I just caught up on two months worth of CA-Request mail.  Everyone who asked
to be removed from the list should not be receiving this.  Welcome to all new
members.

If there are any requests which have not been honored, please resubmit them; I
probably missed them the first time.

I hope we can get the discussion rolling more than it has been so far.  Don't
be shy if you have ideas or questions!

--Bruce Nemnich, Thinking Machines Corporation, Cambridge, MA
  Temporarily at Naval Research Lab, Washington, DC 
  bruce@think.com, think!bruce, bjn@mitvma.bitnet +1 202 404 7019

From @cunyvm.cuny.edu:he%idt.unit.no@norunix.BITNET  Fri Sep 23 18:26:33 1988
Received: from Think.COM by fafnir.think.com; Fri, 23 Sep 88 18:26:33 EDT
Return-Path: <@cunyvm.cuny.edu:he%idt.unit.no@norunix.BITNET>
Received: from CUNYVM.CUNY.EDU by Think.COM; Fri, 23 Sep 88 18:26:40 EDT
Received: from CUNYVM.BITNET by CUNYVM.CUNY.EDU (IBM VM SMTP R1.1) with BSMTP id 8630; Fri, 23 Sep 88 18:15:32 EDT
Received: from NORUNIX.EARN by CUNYVM.BITNET (Mailer X1.25) with BSMTP id 8285;
 Fri, 23 Sep 88 18:15:29 EDT
Received: from loke.unit.no (loke.ARPA) by runix (norunix.EARN) (1.2/4.1)
        id AA09582; Sat, 24 Sep 88 00:14:08 -0200
From: Haavard Eidnes IDT <he%idt.unit.no%NORUNIX.BITNET@cunyvm.cuny.edu>
Date: Sat, 24 Sep 88 00:15:01 +0200
Message-Id: <27403.8809232215@loke.unit.no>
To: ca@Think.COM
Cc: lasse@yme.unit.no
Subject: Request to be added to your mailing list

Will you please add the address

        cell-automata%idt.unit.no@norunix.bitnet

to your mailing list, or tell me if you have any other memberships
whithin the .NO domain? If you add the above address on your list,
please remember that it is essential that the list arrives via BITNET,
since currently our only other link to the outside world is over a
(slow) UUCP connection (that not even we pay for). Depending on your
local setup, you may have to transform the above address to conform to
Internet standards, but please keep the route via BITNET.  Thank you.

Thanks in advance.

Haavard Eidnes, Division of Computer Systems and Telematics
                Norwegian Institute of Technology
E-mail: he@idt.unit.no                  (for domain/MX mailers)
        he%idt.unit.no@enea.se          (same path as -^)
        he%idt.unit.no@norunix.bitnet   (for volume)




