

Article 323 of comp.theory.cell-automata:
Path: mimsy!haven!ames!apple!brutus.cs.uiuc.edu!rpi!hiebeler
>From: [email-masked] (Dave Hiebeler)
Newsgroups: comp.misc,comp.theory.cell-automata,comp.theory.self-org-sys,comp.theory,comp.sys.ibm.pc
Subject: Re: CA question
Message-ID: <L23=[email-masked]>
Date: 4 Feb 90 02:09:56 GMT
References: <[email-masked]>
Organization: RPI CS Dept, and LANL Center for Nonlinear Studies
Lines: 90
Xref: mimsy comp.misc:8552 comp.theory.cell-automata:323 comp.theory.self-org-sys:127 comp.theory:1332 comp.sys.ibm.pc:46926

In article <[email-masked]> [email-masked] (Peter Nelson) writes:

> [semi-negative comments about Autodesk's CA lab]

  You might want to check out Cellsim, it is a public-domain cellular
automata program (written in C), which runs under SunView.  I realize
you want something for the PC, but the inner loops for Cellsim are
just pure C, and can be run on pretty much anything.  It lets you get
up to 8 bits from each of 9 neighbors at most, in addition to a couple
of 8-bit "global" parameters.
  Rather than tell you how to get Cellsim, I'd prefer to wait, as I'm
currently working on version 2.5, which is substantially better than
previous versions.  If you're *really* desperate to get the old
versions, send me an e-mail note, although I hate to tell people where
to get the old version, since the new one will be so much better. :-)

>     Conway's Life - types of simulations 
>     are static, i.e., nothing moves from one cell to the next.  
>     I was kind of hoping I could use my new utility to simulate 
>     systems where "stuff" (information or state or something) does
>     move from one cell to another.  This might be useful in simulating
>     fluid flow or ecological systems. 

  Well, in Conway's life (as well as things like the HPP and FHP
lattice gas rules), *information* moves from one cell to another.
That is, a "particle" might be represented as an active cell; an empty
cell that sees a neighbor with a particle moving toward it, will
"create" a new particle while its neighbor "destroys" its particle.
The net effect is an information transfer, or a particle "transfer".

>     But when stuff moves between cells "collisions" may occur.  The
>     problem is not resolving the collision (that's relatively easy).
>     The problem is propagating the effects of that resolution through
>     the matrix, and doing so in a way which is not dependent on the
>     order-of-evaluation.
> [stuff about following the results of possible collisions...]

  You should check out the HPP lattice gas model, this has a simple
example of how to get around this.  The basic solution (on a square
lattice), is as follows (I'll describe it in terms of particles, since
that's the terminology associated with the HPP model):
 1. Each cell can hold up to 4 particles
 2. There cannot be 2 or more particles in the same place moving in the
   same direction.  So a "full" (4-particle) cell would have 1
   particle moving in each direction: up, down, left, right.
 3. If you think about the "worst-case" collision, this would be a cell
  that is full and whose neighbors are all full.  In that case, the
  cell would "destroy" its 4 particles (knowing its neighbors would
  get them), and it would get 1 particle from each of its 4 neighbors.
  That is, the exclusion principle in item 2 above prevents you from
  having more than 4 items try to come into the same cell.  Since each
  cell can hold at most 4 particles, you're safe.

Three sources of information about HPP, which will clarify what I'm
trying to say above are:

J. Hardy, Y. Pomeau, and O. de Pazzis, ``Time Evolution of a
Two-Dimensional Model System.  I.  Invariant states and time
correlation functions'', J. Math. Phys. [14] (1973).

J. Hardy, O. de Pazzis, Y. Pomeau, ``Molecular dynamics of a Classical
Lattice Gas: Transport Properties and Time Correlation Functions,''
Physical Review A, [13] (1976) 1949. 

T. Toffoli and N. Margolus, Cellular Automata Machines: A New
Environment for Modeling, (MIT Press, 1987).

>     Thanks in advance for any observations or comments.   I'm new
>     at much of this so if I'm making lots of stupid assumptions
>     feel free to tell me, but be nice, please.  8-)

  I've been at this for years, and I still make lots of stupid
assumptions and ask stupid questions. :-)

  Note that I'll be away at the 2nd Artificial Life conference next
week, so I'll probably be slow to reply to e-mail queries until Feb
11th or so.

  I'll try to post a summary of interesting stuff I see at the ALife
conference, probably in the following newsgroups:
 comp.theory.cell-automata, comp.theory.self-org-sys, comp.bio
and maybe a couple of other groups, so watch at least one of those
newsgroups around Feb 11-15 or so, if you're interested.

-- 
Dave Hiebeler                Internet: [email-masked] (preferred)
Computer Science Dept.         Bitnet: userF3JL@rpitsmts  (last resort)
Amos Eaton Bldg.
Rensselaer Polytechnic Institute / Troy, NY 12180-3590