FAQ
Robin Forster
Cheers,
Robin.
Bruce Boghosian
Date: Wed, 03 Aug 94 13:18:48 -0500
From: "Robin Forster" <Robin_...@f107.n163.z1.jammys.ocunix.on.ca>
Could someone repost the FAQ for this area?
Cheers,
Robin.
OK, here it is. I have just set up a crontab so that this is mailed to
the list periodically, as someone recently requested.
Regards,
--------------------------------------------------------------------
Bruce M. Boghosian | Internet: b...@think.com
Thinking Machines Corporation | Bitnet: bmb%thin...@mitvma.bitnet
245 First Street | Phone: (617) 234-2140 (work)
Cambridge, MA 02142-1264 USA | FAX: (617)-234-4444
--------------------------------------------------------------------
Frequently Asked Questions
About Cellular Automata
Contributions
from the CA community
edited by
Howard Gutowitz
ESPCI
10 rue Vauquelin
75005 Paris, France
December 8, 1993
Abstract
This FAQ (Frequently Asked Questions) list is updated regularly. Please send*
* corrections,
additions, and comments to <h...@santafe.edu>
1
Contents
1 What are Cellular Automata (CA)? *
* 4
2 General Information *
* 5
2.1 How can I get the latest FAQ? : : : : : : : : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : : 5
2.2 How do I process the CA FAQ? : : : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : 5
2.3 How do I contribute bibliographic material to the FAQ? : : : : : : : : *
*: : : : : : : : : : : : : 5
2.4 What is the cellular automata mailing list? : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : : 5
2.4.1USENET : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : 6
2.4.2BITNET : : : : : : : : : : : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : 6
2.4.3INTERNET : : : : : : : : : : : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : 6
2.4.4ARCHIVES : : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : 7
2.5 What are some good general references for CA? : : : : : : : : : : : : :*
* : : : : : : : : : : : : : 7
2.6 What is the Complex Systems Journal? : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : 7
3 Where can I get a CA Simulator? *
* 7
3.1 General-Purpose CA Simulators : : : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : 7
3.1.1automata : : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : : 8
3.1.2CALAB : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : 8
3.1.3CAMEX : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : 8
3.1.4CAM-PC : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : 8
3.1.5CART : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : : 9
3.1.6CELIP : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : : 9
3.1.7Cellsim : : : : : : : : : : : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : : 9
3.1.8CELLULAR-3.0 : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* : : : : : : : : : : : : 9
3.1.9CEPROL : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : 10
3.1.10LCAU : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : : 10
3.1.11Mathematica : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : : 10
3.1.12scamper : : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : : : 10
3.1.13Self-Directed Replicator (?) : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : : 10
3.1.14SimLife : : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : : : 11
3.1.15SLANG : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : : 11
3.1.16Wautom : : : : : : : : : : : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : : 11
3.2 Simulators for the Game of Life : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : : 11
3.2.1bugglings : : : : : : : : : : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : : 11
3.2.2Life : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : : : 11
3.2.3lifelab : : : : : : : : : : : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : : : 11
3.2.4Mac-CA : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : : 12
3.2.5Plife : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : : : 12
3.2.63dlife : : : : : : : : : : : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : : : 12
3.2.7xlife-2.0 : : : : : : : : : : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : : : 12
3.3 Does Cellsim for X exist? : : : : : : : : : : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : : : 12
3.4 What is 3D-Life? : : : : : : : : : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : : : 13
3.5 How can I make CA simulations run fast? : : : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : 13
3.6 What hardware implementations exist for CA? : : : : : : : : : : : : : :*
* : : : : : : : : : : : : 14
3.7 Are there any simulators for CAM? : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : 14
3.8 Are there simulators for self-criticality? : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : : : : 14
3.9 What about running CA's on parallel or distributed machines? : : : : : *
*: : : : : : : : : : : : 15
2
4 Applications *
* 15
4.1 What computations can CA do? : : : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : 15
4.2 How do you do computations with the Game of Life? : : : : : : : : : : : *
*: : : : : : : : : : : : 15
4.3 Can CA be used to model ecological systems? : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : 16
4.4 The Universe as a Cellular Automata? : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : 17
4.5 Can CA be used to encrypt messages? : : : : : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : 18
5 Special Types of CA *
* 18
5.1 What are Lattice Gas Automata? : : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : 18
5.1.1Does the lack of symmetry in the HPP model have any obvious bad eff*
*ect, other than
to remove the inertial term? : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : 18
5.1.2Are there unphysical conservation laws with HPP? : : : : : : : : :*
* : : : : : : : : : : : 18
5.1.3What are the physical manifestations of anisotropy? : : : : : : : *
*: : : : : : : : : : : : 19
5.2 What are continuous spatial CA? : : : : : : : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : : 19
5.3 Where can I read about the Gacs rule? : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : 19
5.4 What's the Hodge Rule? : : : : : : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : : 19
5.5 What are some good references on Eater Rules? : : : : : : : : : : : : : *
*: : : : : : : : : : : : : 20
5.6 What are Vants? : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : : : 20
5.6.1some vant simulators : : : : : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : 20
6 Properties of CA *
* 21
6.1 What is Flocking Behavior in CA? : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : 21
6.2 What about basins of attraction for CA? : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : 21
6.3 What are \inhomogeneous" CA? : : : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : 21
6.4 How important is Synchronicity in CA? : : : : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : 21
6.5 Which computations can 1D CA perform? : : : : : : : : : : : : : : : : :*
* : : : : : : : : : : : 23
6.6 Is there is universal 1D CA? : : : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : : 23
6.7 How to perform computations in the Game of Life? : : : : : : : : : : : :*
* : : : : : : : : : : : : 24
6.7.1Must one use all of the logical gates to perform computations in th*
*e Game of Life? : : 24
6.8 Where can I learn about Spaceships in the Game of Life? : : : : : : : :*
* : : : : : : : : : : : : 25
6.9 What about running a CA backwards? : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : 25
6.9.1The General Case : : : : : : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : 25
6.10 What are some reversible rules? : : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : : 26
6.11 What is known about periodic orbits in CA? : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : 26
6.12 What are Subshifts of Finite Type/Sophic Systems? : : : : : : : : : : :*
* : : : : : : : : : : : : 27
6.13 What is the mean field theory? : : : : : : : : : : : : : : : : : : : : *
*: : : : : : : : : : : : : : : 28
6.14 When is a CA injective, surjective? : : : : : : : : : : : : : : : : : :*
* : : : : : : : : : : : : : : : 28
6.15 Can one decide if a 2D rule is reversible/surjective? : : : : : : : : : *
*: : : : : : : : : : : : : : : 28
6.16 Where do I read about reversible cellular automata? : : : : : : : : : :*
* : : : : : : : : : : : : : 29
3
1 What are Cellular Automata (CA)?
contributions by:
Lyman Hurd <hu...@math.gatech.edu>
Here is one physicist's view of the relevant definitions:
A cellular automaton is a discrete dynamical system. Space, time, and the state*
*s of the system are discrete.
Each point in a regular spatial lattice, called a cell, can have any one of a f*
*inite number of states. The states
of the cells in the lattice are updated according to a local rule. That is, the*
* state of a cell at a given time
depends only on its own state one time step previously, and the states of its n*
*earby neighbors at the previous
time step. All cells on the lattice are updated synchronously. Thus the state o*
*f the entire lattice advances
in discrete time steps.
Here is one mathematician's view of the relevant definitions:
Conventions d=dimension, k=states per site, r=radius (all explained below).
For simplicity, assume d=1 for the moment.
A d-dimensional cellular automaton takes as its underlying space the lattice SZ*
* (Z=integers, infinite in both
positive and negative directions) where S is a finite set of k elements. The dy*
*namics are determined by a
global function
F : SZ ! SZ *
* (1)
whose dynamics are determined \locally" as defined below.
A \local (or neighborhood) function" f is defined on a finite region
f : S2r+1 ! S: *
* (2)
The all-important property of cellular automata, is that this function is deter*
*mined by a finite lookup table.
Both the domain and range of f are finite.
The global function F arises from f by defining:
F(c)i= f(cir ; : :;:ci+r): *
* (3)
A concrete example with k=2,r=1 would take a doubly infinite string of zeroes a*
*nd ones to a new string at
which each site is replaced by the logical and of its two neighbors (Wolfram's *
*elementary rule 90).
Some relevant facts from a topological standpoint are:
1.The base space SZ is compact and the global function F is continuous.
To insert an editorial comment, this makes CA an ideal meeting point betwee*
*n continuous dynamics
and complexity theory, since they are discretely defined but exhibit contin*
*uous dynamics.
2.The map F commutes with the shift operator which takes cito ci+1.
4
In fact cellular automata are characterized completely by properties 1) and 2) *
*(Hedlund).
The transition todmore dimensions is straightforward. The only difference is th*
*at the global function F is
defined over SZ (functions from a d-dimensional lattice to S) and the local fu*
*nction f is determined by
enumerating the image of all patches of size 2r+1d.
2 General Information
2.1 How can I get the latest FAQ?
contributions by:
The FAQ will be available by anonymous FTP at think.com. santafe.edu will serve*
* as a mirror site.
2.2 How do I process the CA FAQ?
contributions by:
Jorg Heitkotter <jo...@santafe.edu>
James Kennedy CSMR x6238 <JI...@RCC.RTI.ORG>
The CA FAQ is configurable for US letter size and standard A4 paper sizes; it a*
*lso comes with a Makefile
included. All there is to do, is (1) unpack the ca-faq.tar : (a) uudecode <thi*
*s-file> (b) uncompress ca-
faq.tar.Z (c) tar xvf ca-faq.tar then "cd" to the ca-faq folder; and type "make*
* us-ps" or "make a4-ps" (us-ps
is the default);
The makefile will take care of bibtex'ing, and will strip off the latex command*
*s, if you so desire.
2.3 How do I contribute bibliographic material to the FAQ?
Send references you do not see in "ca.bib" to h...@santafe.edu. Use bibtex forma*
*t whenever possible. If
you don't know bibtex, use the very nice utility "bibview" developed at the Tec*
*hnical Univeristy of Munich,
and avail.: ftp.informatik.tu-muenchen.de: `/pub/comp/typesetting/tex/bibview-2*
*.0.tar.Z'. Use
of bibview will significantly improve your enjoyment of "ca.bib". If you don't *
*use X-windows (needed by
bibview), then try "basetex" in the ca-faq directory. It will prompt you for en*
*tries and write them in the
right format. Use first.author.nameYEAR (lower case) for the key, e.g. "wolfram*
*84" for an article published
by Wolfram and Packard in 1984. Ties are resolved by appending "a" "b" "c" etc.
2.4 What is the cellular automata mailing list?
contributions by:
Bruce M. Boghosian <b...@think.com>
This mailing-list is for the discussion of topics relating to cellular automata*
*. For an introduction to CA,
some of the more well-known references are:
[Wol86] [TM87 ] [Gut91a]
5
Discussions on the list often cover topics such as practical applications of CA*
*, the theory of CA, implemen-
tation/performance issues, and discussions of available software packages to pe*
*rform CA experiments.
The cellular automata mailing list is really made up of three parts:
fflAn Internet mailing-list
fflA Bitnet LISTSERV-maintained mailing-list
fflThe Usenet newsgroup \comp.theory.cell-automata"
The three parts are coupled in all directions, so that a message on any one par*
*t of the list is automatically
forwarded to the other two parts.
2.4.1 USENET
If you are able to, I recommend that you read the Usenet newsgroup. That way, *
*you control your own
participation, rather than depending on me as list-maintainer. This keeps the l*
*ist smaller and much easier
to maintain, and if you move to a new account, nothing needs to be done.
2.4.2 BITNET
If you are at a Bitnet site, you may prefer to use the Bitnet LISTSERV mechanis*
*m to subscribe to the list.
LISTSERV is the standard mechanism for maintaining a mailing-list on Bitnet. Th*
*is also makes the list
easier for me to maintain, since it is more automated.
To subscribe in this way, send a message to LISTSERV@MITVMA containing the foll*
*owing line in the body
of the message:
SUBSCRIBE CA-L Your RealName
You may also send a message containing the line:
HELP
to get more information about LISTSERV.
You can also subscribe to the mailing-list through the LISTSERV even if you are*
* not directly connected to
Bitnet, by sending the message to <list...@mitvma.mit.edu>.
2.4.3 INTERNET
If you are not able to use either of the above methods, or if you simply would *
*prefer to be on the Internet
side of the list for some reason, please send mail to <cellular-automata-reques*
*t...@think.com> (or just
reply to this message) specifically requesting to be added to the Internet side*
* of the CA mailing-list, using
the format described at the beginning of this message. Again, if you don't use *
*that exact format, I'll assume
you haven't seen this message, and send it to you again.
6
2.4.4 ARCHIVES
The CA mailing-list is archived, and available via anonymous FTP to think.com (*
*131.239.2.1) if you are
on the Internet. You can FTP to that site using a login of \anonymous," and yo*
*ur e-mail address as a
password. The archives are under the \mail" directory, in the files `ca.archive*
**'. Previous years are kept
in compressed format, e.g. `ca.archive-1987.Z'. Archives for the current year *
*are not compressed, and
kept in the file `ca.archive'.
2.5 What are some good general references for CA?
contributions by:
Mark A Biggar <m...@dst17.wdl.loral.com>
John Baez <ba...@guitar.ucr.edu>
[TM87 ] [FTW84 ] [Gut91a] [WL92 ]
2.6 What is the Complex Systems Journal?
Complex Systems:
A journal devoted to the rapid publication of research on the science, mathemat*
*ics, and engineering of
systems with simple components but complex overall behavior.
Editor: Stephen Wolfram, Wolfram Research, Inc., and University of Illinois
Published six times a year by: Complex Systems Publications, Inc. P.O. Box 6149*
* Champaign, IL 61826
USA
Subscriptions: $45 (students), $75 (individuals), $250 (institutions), Outside *
*North America, add $15 (sur-
face) or $65 (air).
3 Where can I get a CA Simulator?
contributions by:
Russell Inman <in...@ceti.csustan.edu>
H.H. Chou <hhc...@cs.umd.edu>
Dana Eckart <da...@rucs.santafe.edu>
Andy Wakelin <mct...@uk.ac.dct>
Harold McIntosh <mcin...@redvax1.dgsca.unam.mx>
Rudy Rucker <ruc...@sjsumcs.SJSU.EDU>
Ken Karakotsios <kara...@apple.com>
Simone Maggi <ma...@c700-2.sm.dsi.unimi.it>
3.1 General-Purpose CA Simulators
General Reference: [Hie90].
7
3.1.1 automata
author: <cs8...@brunel.ac.uk> (Sunil Gupta)
description: Runs various two-D CA. Written in C, Based on SUIT. SUIT is a libr*
*ary of interface tools
developed at the University of Virginia to help C programmers create sophistica*
*ted mouse based interfaces.
requirements: Also central to SUIT design is portability. SUIT programs current*
*ly run without changes to
the source code on the following platforms: IBM PC, Macintosh, Sun3, Sun4 (Spar*
*cStation), SGI (Silicon
Graphics IRIS workstations), DECstation, HP. The program will not run very well*
* (if at all) on a monochrome
system. it was designed for color. The program is operated entirely through a g*
*raphics interface.
availability: anonymous ftp ftp.cs.umd.edu: `/pub/dtr.tar.Z'
3.1.2 CALAB
Autodesk has two free CA programs for the PC compatible machine on Compuserve. *
* If you can get on
Compuserve, enter GO ADESK and go into Library 4 { CA Lab/CHAOS of the Autodesk*
* Software Forum.
The CA files are CALAB1.COM (7K) and CALAB2.EXE (200K). These files are self-ex*
*tracting archives.
CALAB1.COM will give you a version of the RC program that comes with CA LAB and*
* runs a diffusion
CA, Life, Brain, Vote, and some Langton style CAs. CALAB2.EXE will give you a v*
*ersion of the CADEMO
program that comes with CA LAB and runs a variety (I think about 15) different *
*CAs in demo mode. The
CALAB1.COM program RC is interactive and runs in low resolution, the CALAB2.EXE*
* program CADEMO
is not interactive, and runs in a higher (320x200) resolution.
3.1.3 CAMEX
CAMEX is an exerciser for the CAM/PC, which is a special video controller sold *
*by Automatrix; it is also
applicable to the CAM-6 but we don't know much about people's experience with t*
*hat board. The program
is written in C, and requires minimal equipment for a PC or PC/clone which is c*
*apable of accepting one of
the boards. The program covers an extensive collection of one, two, and three d*
*imensional automata, and
can be had on request. The CAM/PC is sold with a copy of the Toffoli-Margolus b*
*ook, the FORTH program
described in the book, and a substantial collection of examples. Those examples*
* are heavily oriented toward
diffusion and reaction-diffusion rules, and rules depending on the Margolus nei*
*ghborhood. The orientation
of CAMEX is different, leaning toward very general classes of (non-Margolus) ru*
*les, and includes many of
the same rules as LCAU, as well as such features as the calculation of de Bruij*
*n diagrams, mean field curves,
and return maps.
availability: Harold V. McIntosh <mcin...@redvax1.dgsca.unam.mx>
3.1.4 CAM-PC
description: A general purpose cellular automata simulation program, called CAM*
*-PC, based on CAM-6
(Toffoli and Margolus), has been uploaded to the Alife archives. The simulator *
*extends the possibilities of
CAM-6, but (at least this first version) is not fully downwards compatible with*
* the original.
Authors: Zoltan Belso and Miklos Vargyas ELTE University, Budapest, Hungary
requirements: The program requires an IBM compatible computer, MCGA or VGA disp*
*lay and about 188
kB-s of free memory to run. It requires 100 kB-s to install.
8
availability: ftp.cognet.ucla.edu ` pub/alife/public/cam.zip ' (An alternative *
*site is cogsci.elte.hu
`cogsci/alife/CA')
3.1.5 CART
description: see [AS92].
requirements: ??
availability: ??
3.1.6 CELIP
description: see [Has90].
requirements: ??
availability: ??
3.1.7 Cellsim
description: built on top of C, also can use parallel processing power of a CM-*
*? machine
requirements: UNIX, sunview or X11 (see section 3.3 )
availability: plaza.aarnet.edu.au life.anu.edu.au think.com sun.soe.clarkson.ed*
*u sparc01.cc.ncsu.edu iear.arts.rpi.edu
uceng.uc.edu bikini.cis.ufl.edu isy.liu.se nctuccca.edu.tw
3.1.8 CELLULAR-3.0
Description: The system consists of: a programming language, Cellang 3.0, and a*
*ssociated compiler, cellc; an
\abstract" virtual machine, for execution, pe-scam; and a viewer, cellview. Com*
*piled Cellang 3.0 programs
can be run with input provided at any specified time during the execution. The *
*results of an execution can
either be viewed directly or output as a stream of cell locations and values. T*
*his stream of output data can
then be fed into cellview for viewing, or it may be passed through a filter tha*
*t compiles statistics, massages
the data, or merely acts as a valve to control the flow of data from the cellul*
*ar automata program to the
viewer. This simple UNIX toolkit view of the simulation process provides greate*
*r control than systems which
combine the language and viewer. Cellang 3.0 also provides greater flexibility,*
* particularly in the formation
of neighborhoods, than do many other systems.
Requirements: The current system supports both the X11 and Iris Graphics Librar*
*y windowing systems and
can generate shared memory multi-threaded code for multi-processor Sun and SGI *
*(Sequent?) machines.
availability: J Dana Eckart <da...@rucs.faculty.cs.runet.edu>
Also:
plaza.aarnet.edu.au (2.0) brolga.cc.uq.oz.au (2.0) gatekeeper.dec.com (2.0) res*
*eq.regent.e-technik.tu-muenchen.de
(2.0) athene.uni-paderborn.de (2.0) inf.informatik.uni-stuttgart.de (2.0) usc.e*
*du (2.0) keos.helsinki.fi (2.0)
irisa.irisa.fr (2.0) walton.maths.tcd.ie (2.0) ftp.cfi.waseda.ac.jp (2.0) lth.s*
*e (2.0) nctuccca.edu.tw (2.0) unix.hensa.ac.uk
(2.0)
9
3.1.9 CEPROL
description: see [Seu85]
requirements: ?? availability: ??
3.1.10 LCAU
Description: These programs are substantially one-dimensional, one each for sma*
*ll integer (and half-integer)
combinations of Wolfram's k and r. Each program covers evolution, probability, *
*de Bruijn diagrams, and the
calculation of ancestors. Copies of the programs and literature will be sent in*
* response to requests bearing
a complete mailing address, including city, country, and Zip Code. What will ac*
*tually be sent depends on
what is requested and what literature is 'in print' at the moment. The usual re*
*ply includes .EXE for some
of the most popular combinations, a programming manual, and the complete C sour*
*ce for LCAU23, which
can be used to study the Chate-Manneville automata.
requirements:
IBM/PC or clone with a minimum of equipment, namely CGA color and a recent DOS *
*(neither Windows
nor VGA is required, but can be used).
availability: Harold V. McIntosh <mcin...@redvax1.dgsca.unam.mx>
3.1.11 Mathematica
description: a notebook showing an array of Cellular Automata
requirements: Mathematica
availability: swdsrv.edvz.univie.ac.at ra.nrl.navy.mil
3.1.12 scamper
description: provides its own language and has a nice GUI
requirements: UNIX, X11
availability: plaza.aarnet.edu.au brolga.cc.uq.oz.au liasun3.epfl.ch gatekeepe*
*r.dec.com qiclab.scn.rain.com
reseq.regent.e-technik.tu-muenchen.de athene.uni-paderborn.de inf.informatik.un*
*i-stuttgart.de nuri.inria.fr
walton.maths.tcd.ie relay.iunet.it isfs.kuis.kyoto-u.ac.jp walhalla.germany.eu.*
*net lth.se nctuccca.edu.tw unix.hensa.ac.uk
3.1.13 Self-Directed Replicator (?)
author: Hui-Hsien Chou <hhc...@eng.umd.edu>.
description:
Simple Systems Exhibiting Self-Directed Replication: Transition Functions, Soft*
*ware, and Documentation
March, 1993
We have recently developed and studied cellular automata models of self-replica*
*ting systems [Science, 259,
1993, pp. 1282-1288]. Files containing a version of the various transition func*
*tions are now available via ftp.
10
The cellular automata software is actually fairly general and could also serve *
*as an application-independent
simulator. For further details please refer to the paper cited above. availabil*
*ity: ftp.cs.umd.edu `pub/dtr.tar.Z'
3.1.14 SimLife
description: GUI
requirements: UNIX(?) or mac or amiga or PC availability: in local software sto*
*re
3.1.15 SLANG
description: see [SC91a]
requirements: ??
availability: ??
3.1.16 Wautom
description: 1-Dimensional elementary binary cellular automata, with Wolfram's *
*rules 0 to 255. WAUTOM
features: intuitive "Windows"-like user interface, custom window size for the e*
*volution space, custom number
of iteration to compute, a button to activate/deactivate the cyclic modality, l*
*ive-cell diagram.
availability: ghost.dsi.unimi.it ` /pub2/papers/magi/wautom.zip'
requirements: 286 machine, VGA, necessarily a mouse (or equivalent pointer); Ms*
*-Dos 3.10 or later. Ms-
Windows not required.
3.2 Simulators for the Game of Life
3.2.1 bugglings
requirements: mac
availability: ??
3.2.2 Life
requirements: amiga
availability: plaza.aarnet.edu.au amiga.physik.unizh.ch rs3.hrz.th-darmstadt.de*
* reseq.regent.e-technik.tu-muenchen.de
ux1.cso.uiuc.edu ftp.luth.se nctuccca.edu.tw
3.2.3 lifelab
requirements: mac
availability: akiu.gw.tohoku.ac.jp ftp.EU.net mcsun.eu.net fastlife-2.2
requirements: amiga, Kickstart 2.04+,
11
availability: plaza.aarnet.edu.au reseq.regent.e-technik.tu-muenchen.de minnie.*
*zdv.uni-mainz.de amiga.physik.unizh.ch
ftp.luth.se nctuccca.edu.tw
3.2.4 Mac-CA
description: I've written a CA Simulator for the Mac which, although not public*
* domain, is fairly inexpensive
($30). availability: Send email to kara...@apple.com.
3.2.5 Plife
requirements: Microsoft Windows on a PC
availability: In the UK at a JANET (Joint Academic NETwork) site. The file you *
*want is `micros/ibmpc/win/a/a035/a035plife.boo'
3.2.6 3dlife
availability: life.anu.edu.au:
file/pub/complex_systems/alife/3DLIFE.ZIP
3.2.7 xlife-2.0
requirements: UNIX, X11
availability: iacrs1.unibe.ch alice.fmi.uni-passau.de uxc.cso.uiuc.edu life.c
requirements: UNIX(?), curses
availability: rs3.hrz.th-darmstadt.de agate.berkeley.edu ocf.berkeley.edu ux1.c*
*so.uiuc.edu f.ms.uky.edu bongo.cc.utexas.edu
watserv1.waterloo.edu relay.iunet.it isfs.kuis.kyoto-u.ac.jp toklab.ics.es.osak*
*a-u.ac.jp ftp.cfi.waseda.ac.jp ugle.unit.no
kth.se sune.stacken.kth.se colonsay.dcs.ed.ac.uk
3.3 Does Cellsim for X exist?
contributions by:
Dave Hiebeler <hieb...@think.com>
Felicity George <fa...@uk.ac.ed.epcc>
Hiebeler: Quite some time ago, I started trying to do an X11 version in my rare*
* spare time. I got as far
as having the very simple basics working, so I could display a 2-D image in bla*
*ck&white, load a rule and
image, and run. But very little else was in there, and I never get time to work*
* on it any more. Also, I don't
know anything about doing colors in X11. So I can't really say whether an X11 v*
*ersion will ever be released.
George: In case anyone is interested, I have written an X11 version of Cellsim,*
* which runs in black and
white. It has not been extensively tested, as I have not had time to work on it*
*, but if anyone wants a copy,
I'll fix bugs as they come up.
12
3.4 What is 3D-Life?
contributions by:
Anthony Wesley <awe...@canb.auug.org.au>
Harold V. McIntosh <MCIN...@unamvm1.dgsca.unam.mx>
John Pedersen <j...@GOEDEL.MATH.USF.EDU.>
Carter Bays gives a new rule for 3D Life in [Bay92].
The 3dlife program is available for ftp from life.anu.edu.au: `/pub/complex_sys*
*tems/alife/3DLIFE.ZIP'
References
[Dew87] [Dew88a]
3.5 How can I make CA simulations run fast?
contributions by:
Rudy Rucker <ruc...@sjsumcs.SJSU.EDU>
Richard Ottolini <stg...@st.unocal.COM>
I can think of four main tricks for making a CA program run fast.
1.Lookup table. Generally a cell takes on a NewC value which is computed on t*
*he basis of info in the
cell's neighborhood. Try to find a way to pack the neighborhood info bitwis*
*e into a nabecode number.
Then use nabecode as an index into a lookup table. Thus NewC = lookup[nabec*
*ode]. You precompute
the lookup values for all possible nabecodes before running the CA. Lookups*
* can be saved, as Walker
and I did in CA LAB.
2.Pointer swap. To run a CA, you need two buffers, one for the current world *
*of cells, and one for the
updated world of cells. After the update, *don't* copy the updated world on*
*to the current world. Just
swap the pointers to world and new world.
3.The flywheel. In stepping through the cells of the CA, you repeatedly compu*
*te a cell's nabecode, then
compute the nabecode of the next cell over, and so on. Because the neighbor*
*hoods overlap, a lot of
the info in the next cell's nabecode is the same as in the old cell's nabec*
*ode. Try to arrange nabecode
so that you can left shift out the old info and OR in the new info.
4.Assembly language. A 2D VGA CA is going to have about 300K cells. That mean*
*s you are going
to assemble nabecodes and lookup the NewC values about 300K times per scree*
*n. This means that
your inner loop for flywheeling the nabecode must be as efficient as possib*
*le. If you can write this
in assembly language, and keep an eye on the listed \clocks" per instructio*
*n, you can shave off a few
clocks here and there, which really adds up when done 300K times.
If the rule set is known to lead to sparse configurations, e.g. Life Game with *
*a small initial pattern, then
one can use sparse matrix tricks. That is, to just compute in the vicinity of o*
*ccupied cells. Generally these
do not compile as efficiently as a full matrix method, because there is more in*
*direct address and branches.
However, one could include both a sparse and full matrix method in the same pro*
*gram, then convert when
the cross-over density is reached.
13
3.6 What hardware implementations exist for CA?
contributions by:
Dr R W Taylor <r...@ohm.york.ac.uk>
See [TM87 ]
The "trick" of the CAM-6 was to encode the rules as a lookup table accessed by *
*an "address" formed of
the states of the neighborhood. For example, one bit states of cell plus eight *
*neighboors is a 512 possible
results. There was also a "rule compiler" that built the transition table and *
*other computations from a
special programming language.
You might also want to look at [HTA92 ] which describes a 3D automata engine, c*
*omputation is performed
through the reconfiguration (at a very low level) of the hardware.
3.7 Are there any simulators for CAM?
contributions by:
Don Hopkins <hop...@turing.ac.uk>
Hopkins: I've written a recreational CAM-6 simulator (Toffoli & Margolus's Cell*
*ular Automata Machine)
and ported it to HyperLook (the user interface development system I'm working o*
*n at Turing). It displays
animated cellular automata that you can edit in real time with the mouse! And i*
*t comes with a free Lava
Lamp!
The Cellular Automata Machine simulator (a SPARC binary with a bunch of PostScr*
*ipt and data files) and
the HyperLook runtime system are now available for anonymous ftp! HyperLook and*
* the CAM simulator
run under OpenWindows Version 3 on color SPARC workstations. They're available*
* for anonymous ftp
from turing.com, in the file `pub/CAM.tar.Z', or ftp.uu.net, in the file `packa*
*ges/NeWS/CAM.tar.Z'. You
will also need to retrieve the HyperLook runtime environment, from the same dir*
*ectory, with the name
`HyperLook1.5-runtime.tar.Z'. There are several text and PostScript files expla*
*ining HyperLook, and
other HyperLook demos and applications (including SimCity, which I've also port*
*ed to HyperLook). Install
and run HyperLook (set your $HLHOME environment variable), uncompress and un-ta*
*r `CAM.tar.Z' into a
directory, go there, and type \cam". Press the \Help" key at the buttons and gr*
*aphics to learn how to work
the user interface.
See also CAM-PC and CAMEX in section 3.
3.8 Are there simulators for self-criticality?
contributions by:
Richard J. Gaylord <gay...@ux1.cso.uiuc.edu>
I have written a program, in Mathematica, for a cellular automaton simulation o*
*f earthquakes, mudslides,
avalanches and other `'self-critical" phenomena.
The full article (with words) will be published in my column \Simulating Experi*
*ences: Excursions in Pro-
gramming" in \Mathematica in Education," an outstanding (and inexpensive) newsl*
*etter [contact Paul
Wellin at <wel...@Sonoma.edu> for details].
14
3.9 What about running CA's on parallel or distributed machines?
contributions by:
Dave Hiebeler <hieb...@Think.COM>
Yes, CA are pretty trivial on massively parallel computers. Especially if you h*
*ave data parallel software (e.g.
CM-Fortran or C* on the Connection Machine), then you just create a virtual pro*
*cessor for each cell, and
then have each cell fetch its neighbors and do a table-lookup or computation.
If you are not using data parallel software, but instead are using message-pass*
*ing, it is still pretty simple.
I typically partition the 2-D array into a set of \stripes". E.g. on a 128-node*
* machine, if I want to run a
1024x1024 array, I give each processor a 128x8 patch of cells (plus one extra r*
*ow of boundary condition at
the top and bottom, so actually 128x10 with some redundancy). Each processor up*
*dates its local array, and
then exchanges its top and bottom row with its neighbors. So you alternate betw*
*een a step of computation
where you loop over your patch of cells (lots of work if you have a big patch),*
* and doing 2 sends and 2
receives (hopefully pretty quick). Imagine the processors are connected as a ri*
*ng; you don't need any more
connectivity than that (although it's good to have some nice way to dump data o*
*ut to disk or a machine for
analysis).
Partitioning the array into stripes minimizes the \surface area" of the cell pa*
*tches, and so minimizes the
communication you have to do (if you partitioned it as a \checkerboard," you'd *
*have more data to exchange
with more neighbors). It also makes your inner loops more efficient, because yo*
*u have really wide rows to
loop over, instead of a bunch of short rows. It also makes each boundary a cont*
*iguous block of memory, so
it's easy to send to its neighbor.
If you have a high overhead for sending, you may want to consider having 2 boun*
*dary-rows, and doing a
little bit of redundant computation, so that you only do communication every ot*
*her step.
In fact, I implemented a CA simulation using a network of Sun workstations usin*
*g the above layout, and
BSD sockets. Using 16 Suns, I think I had CA code running about 10-12 times fas*
*ter than a single Sun.
This was a few years ago on Sun 3/50's at RPI. I had grand visions of turning t*
*he whole campus into a
monster CA simulation environment, but shortly after that, I got access to a CM*
*-2 and forgot about the
Suns. :-) Actually, there's no need to stay on Suns only { you could have some *
*other machines in there as
well, as long as they can do socket communication to exchange data with the nei*
*ghbors.
4 Applications
4.1 What computations can CA do?
contributions by:
Benedict....@cm.cf.ac.uk
If you just want a CA that does !gates then 'Wireworld', a CA that simulates 'e*
*lectron streams' is probably
an easier starting point than Conway's Life that exhibits the same level of com*
*putational complexity, just
on a more manageable scale. It's in the CA Lab (Rudy Rucker's PC-based CA packa*
*ge), but the rules are
fairly simple and it may well be elsewhere too.
4.2 How do you do computations with the Game of Life?
contributions by:
15
Chris Langton <c...@t13.lanl.gov>
The constructive proof that the game of life is capable of supporting universal*
* computation is built around
colliding glider streams into one another. colliding glider streams form the ba*
*sic AND, OR, and NOT gates,
out of which one then goes on to engineer a general purpose computer. However, *
*one need not construct a
general purpose computer, one could arrange the same computational primitives i*
*nto a device that computes
only a specific function.
One example, computing the logical NOT of a byte, is straightforward. Arrange f*
*or a stream of gliders (the
input stream) to collide with the output of a glider gun at right-angles in suc*
*h a way that the gliders in the
input stream occur with the same spacing as the gliders coming from the glider *
*gun. Furthermore, time the
arrival of gliders in the input stream so that they collide with gliders in the*
* output of the glider gun and
annihilate each other. Then, encode the byte you want to compute the logical NO*
*T of in the following way:
For every 0 in the input byte, remove a glider from the input stream, for every*
* 1, leave a glider. Thus, the
input byte 10110010 will be represented by the glider stream:
glider noglider glider glider noglider noglider glider noglider
where the "nogliders" are spots where gliders in a regular periodic stream of g*
*liders have been removed.
When this stream is collided into the regular stream of gliders coming out of a*
* glider gun, observe what
happens. For every 0 in the input byte, the missing glider in the input stream *
*allows a glider from the glider
gun to pass, whereas for every 1 in the input byte, a glider in the input strea*
*m annihilates the corresponding
glider coming from the glider gun. Thus, looking at the output stream from the *
*glider-gun DOWNSTREAM
of the collision site, there is a glider (a 1) for every "hole" in the input st*
*ream (a 0) and there is a hole (a
0) for every glider (1) in the input stream. Thus, the filtered output of the g*
*lider-gun is the logical NOT of
the encoded input stream.
And not a universal computer in sight!
By colliding this output stream (call it NOT A if the input steam is A) with an*
*other input stream, B,
one gets A AND B in the continuation of the input stream B after the collision *
*site. If one collides the
downstream portion of the NOT A stream from this latter gate with the output of*
* another glider gun, one
obtains A OR B as the continuation of the second glider gun output downstream o*
*f the collision.
By hooking up a sequence of AND, OR, and NOT gates built in this way, one can c*
*ompute any function
that can be expressed by these logical operations (a great many functions indee*
*d....;-)
For complex functions, involving many gates, one needs to cross glider streams,*
* redirect glider streams, and
so forth. This leads to more complication. However, the basic idea is as sketch*
*ed out above.
For details, see the classic [BCG82 ] which contains the proof that the game of*
* Life is computation universal.
4.3 Can CA be used to model ecological systems?
contributions by:
Matthew Burke <bu...@delta.math.wsu.edu>
Recently there has been a significant increase in the number of articles that d*
*eal with cellular automata
(CA) and ecological modeling. There are also several questions on how various a*
*spects of CA affect their
usefulness in ecological models. What follows are some quick thoughts on where *
*the major difficulties with
CA and ecological models lie. It is not intended to be thorough, and it is not *
*as well argued as I'd like. At
the end is a list of interesting references in the area.
16
The major question that needs to be addressed is that of CA's synchronicity. [*
*Hog88], and others, have
claimed that the simultaneous updating of all cells is at odds with the localne*
*ss of interaction that is one
of the strengths of CA. It has been shown that changing the definition of a CA *
*to allow for asynchronous
updating of cells can dramatically alter the behavior of the CA [Hog88] [HG93 ]*
*. In particular, frequently
the interesting structure seen in the evolution of a CA is, in fact, an artifac*
*t of the synchronous updating.
What needs to be addressed is whether or not there are ecological systems for w*
*hich universal updating is
not an unwarranted assumption. For example, [SHJD92 ] develop a CA model of com*
*petition between grass
species. I have not yet researched the characteristics of the species involved *
*in their model, but it is not
inconceivable to think that the dynamics of a set of annual plants may be model*
*ed synchronously (perhaps
the species all germinate at close enough times that on the scale of a year, we*
* can think of it as synchronous).
On the other hand, [Gre90] develops a CA model of the effects of fire and dispe*
*rsal on spatial patterns in
forests. I see no a priori reason, however, to assume that synchronous updating*
* is reasonable in this situation.
Another issue that needs to be investigated is the problems associated with mul*
*tiple scales, both spatial
and temporal. Typically CA models are developed with the assumption that a cel*
*l is a physcial region
of the right size for one (or, perhaps, a few) individuals. Consider a model of*
* plankton in the Celtic Sea
(I have, which is why I bring it up). If we assume that over a certain horizont*
*al distance, conditions are
homogeneous, it suffices to limit ourselves to a water column, i.e. we only ne*
*ed one spatial dimension.
At typical concentrations (private communication with R.A. Parker) we have enou*
*gh plankton that it is
impractical to assume one plankton (or a few) per cell. Now the relevant scales*
* for the diffusion of plankton
nutrients (such as nitrate) is even smaller. Also, consider three typical organ*
*isms: cyanobacteria, flagellates,
diatoms, and copepods. The ratio of the fastest sinking rate to the slowest is *
*200:1. Thus, if we use this
information to scale spatially or temporally, we also run into difficulties (ag*
*ain, the temporal scale of diffusion
for nutrients is smaller still).
Are these problems insurmountable? Is this even the best way to begin thinking *
*about such a model? I don't
have the answers. Finally, are there systems with inherent action-at-a-distance*
*? Returning to the plankton
model mentioned above, we note that during chlorophyll maxima (blooms of plankt*
*on) it is not uncommon
for the plankton near the surface to dramatically decrease the amount of light *
*to plankton at depth due to
shading. Thus, we have an effect that (rapidly) is felt at great distance. Is t*
*his incompatible with the CA
methodology?
Below is a list of ecologically-related papers that use CA models.
References
[DS92] [EEK93 ] [GNH85 ] [Gre82] [Gre90] [Hog88] [HH90 ] [HG93 ] [NM92 ] [SHJD9*
*2 ]
4.4 The Universe as a Cellular Automata?
contributions by:
Chris Langton c...@t13.Lanl.GOV
There is a great collection of papers [unk82]. These are the proceedings of a c*
*onference on the Physics of
Computation and Computational models of Physics.
They contain some classic papers, including many that view the universe as a CA*
*. Authors include Toffoli,
Fredkin, Bennett, Landauer, Hillis, Feynman, Wheeler, and so forth.
17
There is a fascinating paper by Marvin Minsky entitled \Cellular Vacuum" in whi*
*ch he shows that a version
of relativity holds in CA's as clocks (oscillators) approach the speed of light*
* - they slow down, but not in
the same way that they do in continuous space.
All in all, this collection is a must for those interested in computational asp*
*ects of the physical universe or
in the physics of computation.
4.5 Can CA be used to encrypt messages?
Yes. For a review see: [Gut93a].
References
[Wol85a] [Kar92] [Gua87] [Gut93a] [Gut92] [Gut93b] [Wol84a] [MS91 ]
5 Special Types of CA
5.1 What are Lattice Gas Automata?
contributions by:
Paul Larson <pala...@dal.mobil.com>
Bruce Boghosian <b...@Think.COM>
References: [Boo92] [ea90b] [Doo91] [Mon89 ] [MBVB89 ] [Alv91]
5.1.1 Does the lack of symmetry in the HPP model have any obvious bad effect, o*
*ther than
to remove the inertial term?
contributions by:
Bruce Boghosian <b...@Think.COM>
I don't think it removes the inertial term. There is still a form of the inerti*
*al term with HPP, though it is
not isotropic. And, yes, it does have another effect on the equation: The visco*
*us term, like the inertial term,
is present but anisotropic.
5.1.2 Are there unphysical conservation laws with HPP?
contributions by:
Bruce Boghosian <b...@Think.COM>
Yes, HPP has several unphysical conservation laws. First, if you color the sit*
*es white and black, like a
checkerboard, you can convince yourself that the dynamics on the white squares *
*are completely independent
of the dynamics on the black squares. Thus, all conserved quantities (mass and *
*momentum) are conserved
*separately* on the two checkerboard sublattices. More seriously, y-momentum i*
*s conserved separately
within each column, and x-momentum is conserved separately within each row (ass*
*uming periodic b.c.'s).
18
5.1.3 What are the physical manifestations of anisotropy?
contributions by:
Bruce Boghosian <b...@Think.COM>
Here is a physical manifestation of the problem of anisotropy: If you tried to *
*do a Poiseuille flow simulation
with HPP, you would find that the drag on the plates depended on the angle of o*
*rientation of the plates
with respect to the underlying lattice. This problem would be present even at l*
*ow Reynolds number. With
FHP, on the other hand, the drag would be independent of this orientation.
5.2 What are continuous spatial CA?
contributions by:
Bruce MacLennan <macl...@cs.utk.edu>
A continuous spatial automaton is analogous to a cellular automaton, except tha*
*t the cells form a continuum,
as do the possible states of the cells. After an informal mathematical descript*
*ion of spatial automata, we
describe in detail a continuous analog of Conway's \Life," and show how the aut*
*omaton can be implemented
using the basic operations of field computation.
Availability: /pub/complex_systems/ca: MacLennan-CSA.ps.Z
5.3 Where can I read about the Gacs rule?
contributions by:
Lenore Levine <lev...@symcom.math.uiuc.edu>
The first paper on the Gacs rule was published in Problems of Transmission of I*
*nformation, in 1978. The
Russian journal has been translated into English. There are two co-authors, Kur*
*dyumov and Levin.
Here are a few later papers that are probably related: [Gac83] [GR85 ] [G86] [G*
*R88 ] [G89]
One piece of further work is this: [dSM92 ]
Some related papers:
[Gra82]; this is Gray's proof of ergodicity for continuous-time monotonic neare*
*st-neighbor rules.
[Gra87]; this is Gray's proof for discrete time.
[BS88] This is a relatively simple proof of Toom's rule.
[G86] This is my Gacs' 1 dimensional construction.
[G89] This is a 2-dimensional construction which may help understanding the dif*
*ficult 1-dimensional paper
and has a little more general discussion.
5.4 What's the Hodge Rule?
contributions by:
Jorg Heitkotter <jo...@santafe.edu>
19
HODGE-C is a (`mostly ANSI') C language implementation of Gerhard & Schuster's *
*hodge-podge ma-
chine. It implements a class of cellular automata, that resemble very closely *
*autocatalytic chemical re-
actions, like for example, the Belousov-Zhabotinskii (BZ) reaction. It's availa*
*ble via anonymous ftp from
lumpi.informatik.uni-dortmund.de:`/pub/CA/src/hodge-c-0.98j.tar.Z'
References
BZ specific publications:
[Dew88b] [MPH85 ] [MPH87 ]
General CA: [Lan89] [Lea90]
Introductory books: [Dav88] [BP89]
5.5 What are some good references on Eater Rules?
contributions by:
Harold McIntosh <mcin...@redvax1.dgsca.unam.mx>
[DS91] [Eps91] [GH78 ] [GHH78 ] [GGH80 ] [MF83 ] [Mur88] [Win74] [WWS85 ]
5.6 What are Vants?
contributions by:
John N. Rachlin <rac...@cs.jhu.edu>
Charles F. Wells <cf...@po.CWRU.Edu>
A Fraser <A.Fr...@eee.salford.ac.uk>
The Vant rule, by Chris Langton, describes the path of an ant who starts pointi*
*ng in a certain direction.
If the ant is on a non-white square it turns the square red, rotates 90 degrees*
* clockwise and moves one
pixel in the direction it is pointing. If it is on a red square it turns the sq*
*uare white, rotates 90 degrees
counterclockwise and moves one pixel in the direction it is pointing.
See: [Lan86]
5.6.1 some vant simulators
Langtons_Ants by John N. Rachlin <rac...@cs.jhu.edu>
description: This program is based on "Langton's Automaton" and demonstrates th*
*e complex patterns of
one or more "ants" moving according to simple user-defined rules.
requirements: This Program was written in Turbo Pascal, ver. 6.0 It requires EG*
*A or VGA graphics.
Quick Basic Vants Description: This program implements Chris Langton's cellula*
*r automaton [unk93]
requirements: This is a QBasic program that can be run on any DOS machine with *
*VGA graphics. It was
written by Charles Wells, Department of Mathematics, Case Western Reserve Unive*
*rsity, Cleveland, OH
44106-7058, USA. <cf...@po.cwru.edu.>
20
Virtual Ants in C Borland C port of above by <A.Fr...@eee.salford.ac.uk>.
6 Properties of CA
6.1 What is Flocking Behavior in CA?
contributions by:
Rudy Rucker ruc...@sjsumcs.SJSU.EDU
The canonical flocking paper is [Rey87]
6.2 What about basins of attraction for CA?
contributions by:
Harold McIntosh <mcin...@redvax1.dgsca.unam.mx>
References
[BC75 ]
[Jen88a] [Jen88b] [Li87] [Nas78] [McI91b] [McI91a] [Wol83] [Wol84a] [Wol84b] [W*
*ol86] [Gut91b]
6.3 What are \inhomogeneous" CA?
contributions by:
Ron Bartlett bart...@memstvx1.memst.edu
Paulo Sergio Panse Silveira <silv...@fox.cce.usp.br>
Andrew Wuensche <10002...@compuserve.com>
When each cell has a different rule, the resulting CA is called \inhomogeneous".
Kauffman's "random Boolean network" model allows different rules AND connection*
*s, with applications in
theoretical biology.
[Wue93] discusses intermediate architectures between CA and random Boolean netw*
*orks. Homogeneous
rules - varying degrees of random wiring, homogeneous wiring template - various*
* degrees of rule mix.
[Hal89]: structurally dynamic CA.
References
[VTH86 ] [HV00 ] [Kau69] [Kau84]. [Wue93] [Hal89] [Ale93]
6.4 How important is Synchronicity in CA?
contributions by:
Bill Tozier <wto...@mail.sas.upenn.edu>
21
Shan Duncan <dun...@loris.cisab.indiana.edu>
Joel Rahn <RA...@vm1.ulaval.ca>
Erik Winfree <win...@druggist.gg.caltech.edu>
Jordan B Pollack <pol...@dendrite.cis.ohio-state.edu>
Cellular automata are discrete, regular, and synchronous. Those interested in *
*cellular automata as such
begin with the CA definition and work to discover the implications of these pro*
*perties. Those interested in
using CA as models in the natural sciences, on the other hand, begin with a nat*
*ural system in mind and
work to discover how well the behavior of their system can be approximated by a*
* CA model. Both those
interested in abstract properties of CA and those interested in applications fi*
*nd discreteness and regularity
uncontroversial compared to synchronicity. Many of the unique features of cellu*
*lar automaton dynamics can
be traced to the synchronous update of cell-states. An abstract of some of the *
*discussion on this matters
follows.
An example of the importance of synchronicity in CA dynamics is the work of Cha*
*te and Manneville [CM91 ]
on collective behavior in CA and coupled-map lattices. This behavior is of majo*
*r importance in the field of
dynamical systems. Indeed, before this work appeared, some had "proved" (in the*
* physicists sense of proof)
that such behavior was impossible. Collective behavior seems to be stable to al*
*l sorts of perturbations of
the model except giving up on synchronous updates.
The paper by Huberman and Glance [HG93 ] supports the opinion that the organiza*
*tion of the subunits in
a model must approximate the organization of the subunits in the system to be m*
*odeled, and the dynamics
of the model must be a good approximation of the dynamics in the real world. [n*
*ot always the case for CA]
For some examples of CA models in the natural sciences which "work" see Ermentr*
*out and Leah Edelstein-
Keshet [EEK93 ] and the section on lattice-gas automata.
An early reference: [Ing84] They investigate Wolfram's CA rules using a probabi*
*listic method for updating
cells. Some of the rules give patterns, some don't. From the Abstract: "...s*
*ome of the apparent self-
organization of (CA) is an artifact of the synchronization of the clocks."
Greenberg-Hastings type models of reaction-diffusion systems do a decent job of*
* arriving at the same qualita-
tive spatial structure as the real phenomenon (e.g. Zhabotinsky reaction), in t*
*his case stable rotating spirals
of activity. However, if the Greenberg-Hastings model is executed with asynchro*
*nous update, mayhem breaks
loose; rather than, say, one stable spiral, the spiral fractures into a thousan*
*d jumbly pieces.
Thus, synchronous and asynchronous update schemes may lead to vastly different *
*results, and a modeler
must be careful in using either one. But the real issue is is not at all new {*
* modelers must be explicit
about what assumptions they make when designing their model. In CA, conserved q*
*uantities and conserved
properties of the system have vast consequences on its subsequent evolution, an*
*d must be carefully analyzed.
For example, in the Greenberg-Hastings model, a conserved quantity is that the *
*winding number of every
closed path remains unchanged over the course of the evolution. This property i*
*s also true for simple PDE
models of excitable media. (In more complicated versions of both models, unfort*
*unately, this breaks down in
some cases.) But the point is that the CA model is decent because the conserved*
* properties of its evolution
are right. For G-H, single local applications of the CA rule may not preserve t*
*he conservation law, and thus
a radically different steady-state is seen in asynchronous simulations.
In the neural network community there is the same sort of concerns with regard *
*to synchronicity of updates.
People implementing parallel machines are interested in synchronized systems, w*
*hile others whose models
depend on a sequential update rule will argue from the biological plausibility *
*of asynchronousness.
A typical "biological plausibility" statement is found in Daniel Amit's book mo*
*deling brain function (p. 80):
22
to reiterate, the asymptotic behavior of the network, on which we focus our*
* interest, may depend
on the dynamical procedure, but such dependence is unwarranted because no p*
*articular proce-
dure is a faithful representation of the activity in the biological network*
*. We therefore look for
asymptotic properties which are insensitive to the updating procedures
6.5 Which computations can 1D CA perform?
contributions by:
Peter Ruff <rzu...@rz.uni-wuerzburg.de>
Ruff: I have set up a 1d2n22s CA which performs binary multiplication by 79 tra*
*nsition rules. Result of n
* m digits is available after maximal n + m + 2 steps.
6.6 Is there is universal 1D CA?
contributions by:
Mark A Biggar <m...@wdl39.wdl.loral.com>
Rudy Rucker <ru...@autodesk.com>
Biggar: Sure if you allow for more then 2 states and/or neighborhoods greater t*
*hen 3 wide.
First I work with more then 2 states and then with wide neighbor hoods.
Suppose that you have a N state M symbol Turning machine, this maps to a 1D (N+*
*1)*M state 3 wide
neighbor hood as follows: M of the states correspond to tape squares were thr t*
*urning machine read/write
head is not located and are direct mapping of the turning machine's tape. The o*
*ther N*M states represent
the tape square where where the read/write head is located. A state at that pos*
*ition represents the tape
has one of the allowed symbols and the machine is in a given state giving N*M p*
*ossibilities. Using a width 3
neighborhood then most cells are quiescent and don't change only the three cell*
*s with on of the M*N states
in their neighborhood can change in a given time. Defining the rules based on t*
*he original turning machine
is obvious.
Now if you start with a Universial Turning machine you end with a Universal Aut*
*omata.
w to go back to a Binary Automata. If I have N states in the above Automata it *
*can be easily mapped to a
binary automata with a neighbor hood of width 4*N+11 as follows: For now assume*
* that there are only 4
state (to make the cases to be examined small) the each cell in the 4 state 1D *
*automata will map to a row
of 9 cells like so:
state 10 cell pattern
0 110000011
1 110100011
2 110010011
3 110001011
These patterns will overlap 1 cel on each end so the turning tape : :1:02 : :w:*
*ould be represented as:
: :1:11010001110000011100100111 : : :
Using a 27 cell neighborhood it is easy to define rules that correspond to the *
*original 4 state automata. the
111's in the pattern act as registration marks
23
the other cells can determine which position they are in. The original set up o*
*f the 1D automata does not
need the registration marks already in place out to infinity they can propogte *
*themselves out automatically
and keep ahead of the non-empty part of the tape with ease. More compact coding*
* are possible, but this
one is wasly to explain and gives a automata that runs at the same speed as the*
* original.
There is a 4 symbol 7 state Univ Turing machine described in \Computation: Fini*
*te and Infinite Machines"
by Minsky.
Rucker: It is pretty simple to model a standard turing machine as a 1d CA. If t*
*he TM uses k symbols and
n states, then you can make a 1d CA with k (n + 1) states per cell. Most cells*
* are in the state i,0 for some
i < k. The cell where the \head" resides is in the state i,j for some i < k and*
* 1 < j <= n. The update rule
is for each cell to stay the same unless the cell is where the \head" is or is *
*a cell that the \head" is about to
move into.
References
[III71] [LN90]
6.7 How to perform computations in the Game of Life?
contributions by:
Wentian Li <w...@cshl.org>
McIntosh Harold V.-UAP <mcin...@redvax1.dgsca.unam.mx>
Using the interaction of glider streams, the Game of Life can be programmed to *
*perform computations.
Indeed, it is a universal computer.
References
[BCG82 ] [Pou85]
6.7.1 Must one use all of the logical gates to perform computations in the Game*
* of Life?
See: [Jay00]
the three logical gates AND, OR, NOT are sufficient for all logical functions, *
*but not necessary. not only
two basic gates are enough, one basic gate is also enough! for example, gate NA*
*ND, which is \negation of
AND," can lead to all three previously considered \basic" gates:
NOT(a) = (a NAND a)
AND(a,b) = (a NAND b) NAND (a NAND b)
OR(a,b) = (a NAND a) NAND (b NAND b)
another example is the NOR (negation of OR):
NOT(a) = (a NOR a)
OR(a,b) = (a NOR b) NOR (a NOR b)
AND(a,b) = (a NOR a) NOR (b NOR b)
24
the relevance to CA/Game of Life is that the requirement for having three logic*
*al gates in a CA rule so that
it can do all computations can be (two) too much. at least in principle, having*
* one NAND should be enough
for constructing all logical functions.
6.8 Where can I learn about Spaceships in the Game of Life?
contributions by:
Bruce Stangeland <tb...@rrc.chevron.com>
See \Spaceships in Conway's Life" by David I. Bell <db...@pdact.pd.necisa.oz.au*
*>.
Texinfo version of above by Jorg Heitkotter <jo...@santafe.edu> in the CA archiv*
*es at think.com.
There have also been a series of articles on CA that have appeared in Scientifi*
*c American, in the Computer
Recreations section. See, for example: 10/70, 8/88, 8/89, 9/89, and 1/90.
6.9 What about running a CA backwards?
contributions by:
Lyman Hurd <hu...@math.gatech.edu>
6.9.1 The General Case
I will assume that a \configuration" comprises a N x N square of symbols 0,1 wi*
*th the sites outside of this
square assumed 0 (this is what I would term a \finite" configuration.
One can ask:
1.Is there a configuration which maps onto this configuration?
2.Is there a finite configuration which maps onto this configuration?
In one-dimension there are much-explored algorithms which answer to both questi*
*ons. Fundamental to the
algorithm is the existence of bounds based on the parameters of the CA rule (sp*
*ecifically the states per site
and number of sites distant the rule takes into account, Wolfram's k and r). Ba*
*sed on these one finds a bound
phi(N) (recaall N is the initial size of our finite neighborhood) for which if *
*there is any finite predecessor,
there must be one of length at most phi(N). The first question is slightly more*
* complicated, but the procedure
is similar.
In two dimensions both questions are undecidable. This means that the function *
*phi while it still exists
abstractly (there are still a finite number of rules with a given k and r), gro*
*ws faster than any recursive
function.
The proofs of the above statements are not difficult, and relate to the undecid*
*ability of the tiling problem
for Wang tiles.
Note that none of the above discussion means that the problem cannot be solved *
*in the specific case of the
game of Life. It would be impressive to demonstrate such a technique, as Life i*
*s sufficiently complicated to
be computationally universal.
25
6.10 What are some reversible rules?
contributions by:
Bruno Durand <bdu...@ens-lyon.fr>
The following reversible cellular automaton has been presented by Jarkko Kari. *
*It has 2 neighbors (the cell
itself and its right neighbor). The set of states is 1,2,: :,:n. The local tran*
*sition rule f:
f(a; b)= a ifb <= a
1 ifb = a + 1
a + 1 ifb > a + 1
6.11 What is known about periodic orbits in CA?
contributions by:
Lyman Hurd <hu...@math.gatech.edu>
John Pedersen <j...@goedel.math.usf.edu>
Hurd: In a recent paper I used the terms temporally and spatially periodic, but*
* informally I sometimes just
say horizontally or vertically periodic. Here is an (I think) interesting resul*
*t:
Assume that a 1-d CA has a quiescent state. I will (informally) call a configur*
*ation \trivial" if it evolves to
the all-quiescent state which I will assume is a fixed point. A CA for which AL*
*L configurations are trivial,
will be called nilpotent.
1) A CA has a non-trivial temporally periodic orbit if and only if it has a non*
*-trivial spatially periodic orbit
(one half of this proof is easy).
2) There exists a cellular automaton for which EVERY periodic (spatially or tem*
*porally, equivalent by (1))
orbit is trivial BUT for which not every configuration is trivial.
This example (OK I did not give an example I just stated it exists|in fact Kari*
*, Culik and I have a specific
example with 17 states) means that there can be dynamics missed entirely by the*
* restriction to spatially
periodic configurations no matter what the finite lattice size.
PART II:
The following proof is due to K. Culik. To show that a finite configuration mus*
*t have an (eventually) periodic
predecessor, if it has a predecessor at all, consider the following state:
Assume that the rule has radius one (the proof goes through in general with obv*
*ious modifications). Denote
by k the number of states per site.
c = : :0:00c0c1: :c:N0000 : : :
has a predecessor:
d = : :d:2d1 d0d1d2: : :
Lining them up:
d = : :d:2d1 d0d1d2: :d:NdN + 1 : : :
c = : :0:0c0c1c2: :c:N0000 : : :
26
Consider a window which is two high and three wide (if R is the radius, 2R+1), *
*sliding over the pair of
configurations. Start with:
dN+1dN+2dN+3
0 0 0
and continue to the right. There are only k3 possible values so at SOME point t*
*he list must have a duplicate,
i.e.,
dN+idN+i+1dN+i+2= dN+jdN+j+1dN+j+2
0 0 0 0 0 0
Now we can replace d with a configuration periodic on the right by defining:
d0n= dn if n < dN+j;
and otherwise
d0n= d0n(ji)
A similar trick works on the left and QED. The same technique shows the stronge*
*r result (of Golze) that
periodic configurations must have periodic predecessors.
See also: [Ped92] which derives algebraic conditions for all orbits a CA being *
*periodic.
6.12 What are Subshifts of Finite Type/Sophic Systems?
contributions by:
Mike Boyle <bo...@msri.org>
Historically the study of SFT's got a lot of impetus from hyperbolic dynamics, *
*where SFT's are the natural
symbolic dynamics for making use of Markov partitions. You can do a lot of your*
* analysis of equilibrium
states and periodic points on the SFT. (The analysis of equilibrium states on s*
*ofic shifts is much harder.)
This is an historical reason for the focus on SFT's but it is also a mathematic*
*al one. It is completely
reasonable on mathematical grounds that SFT's should be distinguished as the mo*
*st important subclass
of sofic systems. It is for SFT's that finiteness conditions, coding construct*
*ions and algebraic invariants
are most transparent; and one key to studying a sofic system is to understand h*
*ow its properties relate to
those of the SFT underlying the minimal deterministic finite automaton for the *
*regular language of the sofic
system.
But: I think Prof. McIntosh's consideration of sofic systems as a fundamental c*
*lass is absolutely correct. It
is in various ways a more natural class than the class of SFT's. For example, i*
*t is closed under quotients and
unions. More fundamentally, it is much more naturally \the" class of subshifts *
*with a finite presentation
than are SFT's. I think this represents the consensus among workers in symbolic*
* dynamics.
Prof. McIntosh's interest in sofic systems is especially gratifying to me, as *
*I work in symbolic dynamics
myself and have formed the impression that most workers in cellular automata re*
*gard even SFT's which
are not full shifts as esoterica. It seems to me that symbolic dynamics provide*
*s at the least tools and a
perspective useful for some problems about automata, but these have not been mu*
*ch used in c.a.
Just one example: from the symbolic viewpoint the c.a. insistence that its auto*
*mata be block codes on full
shifts (versus block codes on SFT's or other subshifts) seems unnatural. The la*
*tter viewpoint finds some
justification in the recent work of Alejandro Maass <a...@lumimath.univ-mrs.fr>.*
* He uses techniques of
symbolic dynamics to show that any endomorphism f of a mixing SFT S is the rest*
*riction of some c.a. map
27
which has image S, under the necessary assumption that S has a fixed point. (He*
* also has more sophisticated
and less easily stated results about c.a. limit sets and dynamics.) In other wo*
*rds, to understand the limit
dynamics of c.a., you must understand the limit dynamics of endomorphisms of SF*
*T's.
This is not just a problem, it is also an opportunity, because tools for studyi*
*ng SFT's can contribute some
understanding.
6.13 What is the mean field theory?
The mean field theory is a way of approximating the action of a CA by a map wit*
*h continuous parameters.
The approximation is derived by assuming that the states of cells at different *
*locations in space are not
correlated. A simple version of the mean field theory is the parameter of Lang*
*ton, more general versions,
which take into acount spatial correlations, have also been developed.
references
[SS78] [Wol83] [Gut87] [Gut91a] [McI90]
6.14 When is a CA injective, surjective?
contributions by:
Lyman Hurd <hu...@math.gatech.edu>
A CA is injective if its global function F satisfies F(x) = F(y) implies x = y.*
* This, of course, is the general
definition for functions. In the case of CA a stronger result holds (reference?*
*).
Theorem A CA is injective if and only if it is reversible (i.e., bijective).
Surjectivity for cellular automata (although not in general) is a strictly weak*
*er condition that for all y there
exists x such that F(x) = y.
For 1-dimensional CA there exist well-known algorithms to determine surjectivit*
*y and injectivity (by an
algorithm is meant, you hand it a rule table and in guaranteed finite time the *
*answer comes back for all
possible 1D CA).
In 2 and more dimensions a highly non-trivial result of Jarkko Kari shows that *
*the question is undecidable.
The question is linked in a deep way with Berger's Theorem about the undecidabi*
*lity of tiling by Wang tiles.
It is trivially verifiable when two rules invert each other. Kari's Theorem the*
*n implies that there must exist
2D rules for which the complexity of describing its inverse vastly exceeds the *
*complexity of the rule itself.
If we take r (the radius) and a rough determinant of complexity, for any recurs*
*ive function phi, there must
exist a rule with radius r whose inverse rule has radius greater than phi(r).
6.15 Can one decide if a 2D rule is reversible/surjective?
contributions by:
Lyman Hurd <hu...@math.gatech.edu>
Jarkko Kari has proven that the reversibility question for 2D or higher CA is u*
*ndecidable. It is true in all
dimesions that a rule is reversible if and only if it is injective. Kari also h*
*as proven that the surjectivity
28
problem is undecidable (a necessary but not sufficient condition for reversibil*
*ity).
As he points out, the two questions are somewhat different. In the case of surj*
*ectivity one can demonstrate
its lack by giving a finite configuration which one can test exhaustively canno*
*t be reached. This provides a
semi-procedure even though no corresponding semi-procedure can be found in the *
*other case. On the other
hand, it can be finitely demonstrated that two rules indeed invert one another,*
* so there is a semi-procedure
to show that a CA IS reversible.
One way to show decidability in the 1D case for both questions consists of prov*
*ing recursive bounds on how
big a string one would need to find to show a counterexample to surjectivity or*
* how large a radius rule one
needs to examine to prove reversibility. In both cases such a bound (as a funct*
*ion of the number of states
per site and radius) exist, although I do not recall their exact form (I used t*
*o know, step in anyone who
remembers). Kari's proffs suffice to say that there is no such recursive bound *
*for 2 or more dimensions.
6.16 Where do I read about reversible cellular automata?
contributions by:
Harold V. McIntosh <mcin...@uapnx1.dgsca.unam.mx>
The name most prominently associated with reversible cellular automata seems to*
* be Tommaso Toffoli; his
most accessible work is probably [TM87 ]. Whereas the book describes a number o*
*f reversible rules for the
CAM-6, Edward Fredkin's analogy with second order differential equations is the*
* only background theory
mentioned, in section 14.2. The Margolus neighborhood, strongly featured in the*
* book, was evidently created
to facilitate reversibility.
In turn, Fredkin has acquired widespread fame for the replication properties of*
* the <exclusive or> when taken
as a rule of evolution. However, it is difficult to encounter a single referenc*
*e which can be cited, for either
Toffoli or Fredkin, that can be fairly said to present their own views. Martin *
*Gardner reported Fredkin's
replication in his second article on Life in 1971, reprinted in [Gar83] thereby*
* giving the idea worldwide
publicity.
Perhaps the computer science community's outstanding early contact with reversi*
*ble automata was [AP72 ].
Non-reversibility, in the form of the Garden of Eden, seems to go back to [Moo7*
*0]. What seems to be quite
remarkable is the degree to which such issues were worked out by mathematicians*
*, within the context of
symbolic dynamics, during the 1950's and 1960's. The fundamental paper in this *
*respect is [Hed69].
It is in fact a summary of quite a bit of work, carried out by Hedlund himself *
*and others. One of their
important concepts is a "subshift of finite type" which is a biinfinite string *
*of symbols from which a certain
finite set of words has been excluded. Sort of like excluding all the 1's from *
*trinary (i.e., 0, 1, 2) decimals to
get the Cantor set. Shifting the decimal point in one such number gives another.
Topology figures very strongly in symbolic dynamics, which may have restricted *
*its appreciation; on the
other hand it facilitates talking about limits and leads to a useful measure th*
*eory and probabilities. The
topology is such that two strings are closer, the longer their central segments*
* which match up; it turns out
that those continuous functions which commute with the shift are each generated*
* by the transition rule for
some linear cellular automaton. Thus symbolic dynamics is an application of aut*
*omata theory, or vice versa.
The two theories overlap, but have tended to emphasize different features. Woul*
*d a symbolic dynamicist
have discovered Wolfram's class iv on his/her own?
Subshifts of finite type arise from graphs whose nodes are symbols and whose ar*
*rows show admissible se-
quences; missing arrows result from the operative exclusions. Someone realized *
*that a much more interesting
model resulted from using the symbols as links among arbitrary nodes; the publi*
*cation generally credited
29
for this is [Wei73]. It should be noted that the language of his presentation i*
*s semigroup theory, not graph
theory.
Three papers by Ethan M. Coven and Michael E. Paul come from the same time peri*
*od: [CP74 ] [CP75 ]
[CP77 ].
Several articles by Masakazu Nasu, written in the spirit of Hedlund's symbolic *
*dynamics, appeared in the
late 70's and early 80's; perhaps the most relevant is: [[Nas78]. Somewhat late*
*r the ideas were generalized
to apply to flows through graphs: [Nas82].
An early attempt to relate reversibility and Gardens of Eden and to use the int*
*erplay between global and
local mappings was [Ric72].
A somewhat later paper [SH77] works out in considerable detail the relationship*
*s between injectivity, sur-
jectivity, and several other properties of cellular automata. Slightly earlier,*
* [Yak76] appeared.
The reasons for interest in reversible automata seem to have been varied. A for*
*mal theory such as Hed-
lund's would naturally have been concerned with the kind of details represented*
* by surjectivity, injectivity,
continuity, the existence of limits, and so on; all of his results may well hav*
*e been worked out simply for the
sake of presenting a thorough and complete theory. One would have to ask him, o*
*r someone who was very
familiar with his work.
Garden of Eden theorems seem to have resulted more as a counterbalance to von N*
*eumann's universal
constructor; the reversible machines which they imply seem to have been less of*
* an issue than the fact that
some specific automata were <<not>> reversible, and the momentary confusion bet*
*ween the implications of
the two concepts. Consequently Toffoli seems to be a plausible candidate to hav*
*e been the first proponent
of reversible automata as such.
His publications are not all that easy to track down, consisting of his thesis,*
* laboratory reports, contributions
to conference proceedings, and so on. However, [Tof77] states that "an arbitra*
*ry d-dimensional cellular
automaton can be constructively embedded in a reversible one having d + 1 dimen*
*sions," and precedes
to show how to do so. This approach is different from Fredkin's, which merely u*
*ses an arbitrary cellular
automaton to construct another which is reversible, without pretending to embed*
* the original; indeed it
usually does not. There is also a joint paper, [FT82] which goes into some of t*
*heir mutual ideas.
30
References
[AB93] R. Anderson and K. Bunas. grain size segregation and stratigraphy in a*
*eolian ripples modelled
with a cellular automaton. Nature, 365:740{743, October 1993.
[AF91] Roy Adler and Leopold Flatto. subshifts of finite type and sofic syste*
*ms (?). the Bulletin of the
American Mathematical Society, pages 239{334, October 1991.
[Ale93] Zoran Aleksic. Computation in inhomogenous celluar automata. In Davi*
*d Green and Terry
Bossomaier, editors, Complex Systems: From Biology to Computation. IOS*
* Press, Amsterdam,
1993. anonymous ftp life. anu. edu. au: `/pub/complex_systems/anu92/pa*
*pers/aleksic.ps'.
[Alv91] A. S. Alves. Discrete Models of Fluid Dynamics. World Scientific, 1991.
[AP72] S. Amoroso and Y. N. Patt. Decision procedures for surjectivity and in*
*jectivity of parallel maps
for tesselation structures. Journal of Computer and System Sciences, 6*
*:448{464, 1972.
[AS92] N. M. Allinson and M. J. Sales. CART { A cellular automata research to*
*ol. Microprocessors and
Microsystems, 16(8):403{415, 1992.
[Bar90] A. M. Barbe. A CA ruled by an eccentric conservation law. Physica D, 4*
*5:49, 1990.
[Bay87a] Carter Bays. Candidates for the game of life in three dimensions. Comp*
*lex Systems, 1(2):373{400,
April 1987.
[Bay87b] Carter Bays. Patterns for simple cellular automata in a universe of de*
*nse packed spheres. Complex
Systems, 1(6):853{875, December 1987.
[Bay90] Carter Bays. The discovery of a new glider in the game of three-dimen*
*sional life. Complex
Systems, 4(6):599{602, December 1990.
[Bay91] Carter Bays. A new game of three-dimensional life. Complex Systems, *
*5(1):15{18, February
1991.
[Bay92] Carter Bays. 3D life (?). Complex Systems, 6(5):433{442, 1992.
[BC75] R. C. Backhouse and B. A. Carre. Regular algebra applied to path-findi*
*ng problems. Journal of
the Institute for Mathematics and its Applications, 15:161{186, 1975.
[BCG82] Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy. Winning Ways f*
*or your Mathe-
matical Plays, volume 2. Academic Press, ISBN 0-12-091152-3, 1982. cha*
*pter 25.
[BGMP93] N. Boccara, E. Goles, S. Martinez, and P. Picco. Cellular Automata and*
* Cooperative Phenomena.
Kluwer Academic Publishers, 1993.
[BH92] R. J. De Boer and P. Hogeweg. Growth and recruitment in the immune net*
*work. In A. F. Perelson
and G. Weisbuch, editors, Theoretical and Experimental Insights into I*
*mmunology, volume 66,
pages 223{247. Springer Verlag, New York, 1992.
[Bin91] P.-M. Binder. unknown. J. Phys. A, 24(L21), 1991.
[Bin93] P.-M. Binder. Parametric ordering of complex systems. Physical Review *
*E, 1993.
[BNR91] N. Boccara, J. Nasser, and M. Roger. Particle-like structures and inte*
*ractions in spatio-temporal
patterns generated by one-dimensional determinsitic cellular automaton*
* rules. Phys. Rev. A, 44,
July 1991.
31
[Boo92] Jean Pierre Boon. Lattice gas automata: Theory, simulation, implementa*
*tion. J. Stat. Phys.,
68(3/4), 1992.
[BP89] John Briggs and F. David Peat. An Illustrated Guide to Chaos Theory a*
*nd the Science of
Wholeness. Harper & Row, New York, 1989.
[Bre93] X. Breckling. unknown. Ecological Modeling, 63(13-27):13{27, 1993.
[BS88] Piotr Berman and Janos Simon. Investigations of fault-tolerant network*
*s of computers. In Proc.
of the 20-th Annual ACM Symp. on the Theory of Computing, pages 66{77,*
* 1988.
[BTS91] Philippe Binder, Carole Twining, and David Sherrington. Phase{space st*
*udy of bistable cellular
automata. Complex Systems, 5(2):127{138, April 1991.
[CD90] A. Canning and E. Droz. A comparison of spin exchange and CA models fo*
*r diffusion-controlled
reactions. Physica D, 45:285, 1990.
[CK88] J. P. Crutchfield and K. Kaneko. Are attractors relevant to turbulenc*
*e? Phys. Rev. Lett.,
60:2715, 1988.
[CM90] H. Chate and P. Manneville. Criticality in CA. Physica D, 45:122, 1990.
[CM91] H. Chate and P. Maneville. Evidence of collective behavior in cellular*
* automata. EuroPhys. Let,
14:409{413, 1991.
[CP74] Ethan M. Coven and Michael E. Paul. Endomorphisms of irreducible subsh*
*ifts of finite type.
Mathematical Systems Theory, 8:167{175, 1974.
[CP75] Ethan M. Coven and Michael E. Paul. Sofic systems. Israel Journal of M*
*athematics, 20:165{177,
1975.
[CP77] Ethan M. Coven and Michael E. Paul. Finite procedures for sofic system*
*s. Monatshefte fuer
Mathematik, 83:265{278, 1977.
[Cru88] J. Crutchfield. Hunting for transients and cycles. unpublished notes, *
*March 1988.
[CS90] D. Chowdhury and D. Stauffer. Systematics of the models of the immune*
* response and the
autoimmune response. J. Stat. Phys, 59:1019{1042, 1990.
[CS92a] F. Celada and P. E. Seiden. A computer model of cellular interactions *
*in the immune system.
Immun-t, 13:56{62, 1992.
[CS92b] D. Chowdhury and D. Stauffer. Statistical physics of immune networks. *
*Physica A, 186: 1-2:61{
81, 1992.
[Dav88] Paul Davies. Cosmic Blueprint. Heinemann, London, 1988.
[Dew87] A. K. Dewdney. The game life aquires some successors in three dimensio*
*ns. Scientific American,
224(2):112{118, February 1987.
[Dew88a] A. K. Dewdney. The Armchair Universe, volume ISBN 0-7167-1939-8 pbk. W*
*. H. Freeman and
Company, New York, 1988.
[Dew88b] A. K. Dewdney. The hodgepodge machine makes waves. Scientific American*
*, 225(8), August
1988.
32
[DGT85] J. Demongeot, E. Goles, and M. Tchuente. Dynamical systems and cellula*
*r automata. Academic
Press, New York, 1985.
[Doo91] G. D. Doolen. Lattice Gas Methods for PDE's, Theory, Applications and*
* Hardware. North-
Holland, 1991.
[DS91] Richard Durrett and Jeffrey E. Steif. Some rigorous results for the gr*
*eenberg-hastings model.
Journal of Theoretical Probability, 4:669{690, 1991.
[DS92] C. Dytham and B. Shorrocks. Selection, patches and genetic variation: *
*a CA modelling drosophila
populations. Evolutionary Ecology, 6:342{351, 1992.
[dSM92] Paula Gonzaga de Sa and Christian Maes. The Gacs-Kurdyumov-Levin Autom*
*aton revisited.
Journal of Statistical Physics, 67(3/4):607{622, May 1992.
[ea90a] F. C. Richards et al. Extracting CA rules directly from experimental d*
*ata. Physica D, 45:189,
1990.
[ea90b] G. D. Doolen et al. Lattice gas methods for partial differential equat*
*ions. Addison-Wesley, New
York, 1990.
[ea90c] K. Culik II et al. Computation theoretic aspects of CA. Physica D, 45:*
*357, 1990.
[ea90d] K. Culik II et al. Formal languages and global CA behavior. Physica D,*
* 45:396, 1990.
[ea90e] R. Livi et al. Periodic orbits and long transients in coupled map latt*
*ices. Physica D, 45:452,
1990.
[ea90f] S. Qian et al. Adaptive stochastic CA: experiment. Physica D, 45:181, *
*1990.
[ea90g] W. Li et al. Transition phenomena in CA rule space. Physica D, 45:77, *
*1990.
[ea90h] Y. Aizawa et al. Soliton turbulence in 1-D CA. Physica D, 45:307, 1990.
[ea90i] Y. C. Lee et al. Adaptive stochastic CA: theory. Physica D, 45:159, 19*
*90.
[EEK93] G. Bard Ermentrout and Leah Edelstein-Keshet. Cellular automata appro*
*aches to biological
modeling. Journal of Theoretical Biology, 160:97{133, January 1993.
[Eis91] M. Eisele. Long-range correlations in chaotic cellular automata. Physi*
*ca D, 48:295{310, 1991.
[Eps91] Irving R. Epstein. Spiral waves in chemistry and biology. Science, 252*
*:67, 1991.
[Fis90a] R. Fisch. Cyclic CA and related processes. Physica D, 45:19, 1990.
[Fis90b] R. Fisch. Cyclic CA and related processes. Physica D, 45:19, 1990.
[Fre90] E. Fredkin. Digital mechanics: An informational process based on rev*
*ersible universal CA.
Physica D, 45:254, 1990.
[FT82] Edward Fredkin and Tommaso Toffoli. Conservative logic. International *
*Journal of Theoretical
Physics, 21:219{253, 1982.
[FTW84] J. D. Farmer, T. Toffoli, and S. Wolfram. Cellular automata. North-Hol*
*land, Amsterdam, 1984.
[G86] Peter Gacs. Reliable computation with cellular automata. Journal of Co*
*mputer System Science,
32(1):15{78, February 1986.
33
[G89] Peter Gacs. Self-correcting two-dimensional arrays. In Silvio Micali*
*, editor, Randomness in
Computation, volume 5 of Advances in Computing Research (a scientific *
*annual), pages 223{
326. JAI Press, Greenwich, Conn., 1989.
[Gac83] P. Gacs. Reliable computation with cellular automata. STOC, 1983.
[Gar83] Martin Gardner. Wheels, Life, and Other Mathematical Amusements. W. *
*H. Freeman and
Company, New York, 1983. ISBN 0-7167-1589-9.
[Gar90] M. Garzon. CA and discrete neural nets. Physica D, 45:431, 1990.
[GGH80] J. M. Greenberg, C. Greene, and S. Hastings. A combinatorial problem a*
*rising in the study of
reaction-diffusion equations. SIAM Journal of Algebra and Discrete Mat*
*hematics, 1:34{42, 1980.
[GH78] J. M. Greenberg and S. P. Hastings. Spatial patterns for discrete mode*
*ls of diffusion in excitable
media. SIAM Journal on Applied Mathematics, 34:515{523, 1978.
[GHH78] J. M. Greenberg, B. D. Hassard, and S. P. Hastings. Pattern formation *
*and periodic structures
in systems modelled by reaction-diffusion equations. Bulletin of the *
*American Mathematical
Society, 84:1296{1327, 1978.
[GNH85] D. G. Green, House A. P. N., and S. M. House. Simulating spatial patte*
*rns in forest ecosystems.
Mathematics and Computers in Simulation, 27:191{198, 1985.
[GR85] P. Gacs and X. Reif. A simple three-dimensional real-time reliable cel*
*lular array. STOC, 1985.
[GR88] P. Gacs and X. Reif. A simple three-dimensional real-time reliable cel*
*lular array. JCSS, 36, 1988.
[Gra82] Lawrence F. Gray. The positive rates problem for attractive nearest ne*
*ighbor spin systems on z.
Z. Wahrscheinlichkeitstheorie verw. Gebiete, 61:389{404, 1982.
[Gra84] Peter Grassberger. unknown. Physica D, 10:52, 1984.
[Gra86a] Peter Grassberger. appendix. In Stephan Wolfram, editor, Theory and Ap*
*plications of Cellular
Automata. World Scientific, 1986.
[Gra86b] Peter Grassberger. Long-range effects in an elementary cellular automa*
*ton. J. Stat. Phys, 45:27{
39, 1986.
[Gra87] Lawrence F. Gray. The behavior of processes with statistical mechanica*
*l properties. In Perco-
lation Theory and Ergodic Theory of Infinite Particle Systems, pages 1*
*31{167. Springer-Verlag,
1987.
[Gra89] Peter Grassberger. Problems in quantifying self-generated complexity. *
*Helvetica Physica Acta,
62:489, 1989.
[Gre82] D. G. Green. Simulated effects of fire, dispersal and spatial pattern *
*on ceompetition within forest
mosaics. Vegetation, 82:139{154, 1982.
[Gre90] David Geoffrey Green. Cellular automata models of crown-of-thorns outb*
*reaks. In R. H. Brad-
bury, editor, Acanthaster and the Coral Reef:A Theoretical Perspective*
*, volume 88 of Lecture
Notes in Biomathematics, pages 169{188. Springer-Verlag, Berlin, 1990.
[GS89] X. Gerhardt and X. Schuster. A cellular automation describing the form*
*ation of spatialy ordered
structures in chemical systems. Physica D, 36:209, 1989.
34
[GS92] X. Gerhardt and X. Schuster. Anregungen. Heft, 2:44{50, 1992.
[GST90] X. Gerhardt, X. Schuster, and X. Tyson. A cellular automation model of*
* excitable media includ-
ing curvature and dispersion. Science, 247:1563, 1990.
[Gua87] P. Guan. Cellular automaton public-key cryptosystems. Complex Systems,*
* 1, 1987.
[Gut87] Howard Gutowitz. Local Structure Theory for Cellular Automata. PhD the*
*sis, Rockefeller Uni-
versity, New York, New York, 1987.
[Gut89a] Howard Gutowitz. Statistical properties of cellular automata in the c*
*ontext of learning and
recognition. part I: Introduction. In K. H. Zhao, editor, Learning and*
* Recognition{A Modern
Approach, pages 233{255. World Scientific Publishing, Singapore, 1989.
[Gut89b] Howard Gutowitz. Statistical properties of cellular automata in the c*
*ontext of learning and
recognition. part II: Inverting local structure theory equations to fi*
*nd cellular automata with
specified properties. In K. H. Zhao, editor, Learning and Recognition*
*{A Modern Approach,
pages 256{280. World Scientific Publishing, Singapore, 1989.
[Gut90a] Howard Gutowitz. A hierarchical classification of CA. Physica D, 45:13*
*6, 1990.
[Gut90b] Howard Gutowitz. Introduction (to cellular automata). Physica D, 45:vi*
*i, 1990.
[Gut90c] Howard Gutowitz. Maps of recent CA and lattice gas automata literature*
*. Physica D, 45:477,
1990.
[Gut91a] Howard Gutowitz. Cellular Automata: Theory and Experiment. MIT Press/B*
*radford Books,
Cambridge Mass., 1991. ISBN 0-262-57086-6.
[Gut91b] Howard Gutowitz. Transients, cycles and complexity in cellular automat*
*a. Physical Review A,
44(12):7881{7884, December 1991.
[Gut92] Howard Gutowitz. Method and apparatus for encryption, decryption, and *
*authentication using
dynamical systems. U.S. Patent Pending, 1992.
[Gut93a] Howard Gutowitz. Cryptography with dynamical systems. In N. Boccara, E*
*. Goles, S. Martinez,
and P. Picco, editors, Cellular Automata and Cooperative Phenomena, pa*
*ges 237{274. Kluwer
Academic Publishers, 1993.
[Gut93b] Howard Gutowitz. A massively parallel cryptosystem based on cellular a*
*utomata. In B. Schneier,
editor, Applied Cryptography. K. Reidel, 1993.
[GV87] H. A. Gutowitz and J. D. Victor. Local structure theory in more than o*
*ne dimension. Complex
Systems, 1:57{68, 1987.
[GV89] H. A. Gutowitz and J. D. Victor. Local structure theory: Calculation o*
*n hexagonal arrays, and
the interaction of rule and lattice. J. Stat. Phys., 54:495{514, 1989.
[GVK87] H. A. Gutowitz, J. D. Victor, and B. W. Knight. Local structure theory*
* for cellular automata.
Physica D, 28:18{48, 1987.
[Hal89] Paul Halpern. Sticks and stones: a guide to structurally dynamic cellu*
*lar automata. American
Journal of Physics, 57(5):405{408, May 1989.
[Has90] Wilhelm Hasselbring. CELIP: A cellular language for imaging processing*
*. Parallel Computing,
14:99{109, 1990.
35
[Hed69] G. A. Hedlund. Endomorphisms and automorphisms of the shift dynamical *
*system. Mathematical
Systems Theory, 3:320{375, 1969.
[Hei93] Jorg Heitkotter. HODGE-C: An implementation of Gerhard and Schuster's *
*hodge-podge ma-
chine. C source code, Systems Analysis Research Group, LSXI, Universit*
*y of Dortmund, De-
partment of Computer Science, D-44221 Dortmund, Germany, March 1993. A*
*vailable via anon.
ftp to lumpi.informatik.uni-dortmund.de as file `hodge-c-0.98j.tar' in*
* /pub/CA/src.
[HG93] B. A. Huberman and N. Glance. Evolutionary games and computer simulati*
*ons. Proc. Natl.
Acad. Sci. USA, 90:7716{7718, August 1993.
[HH90] P. Hogeweg and B. Hesper. Crowns crowding:an individual oriented model*
* of the acanthaster
phenomenon. In R. H. In Bradbury, editor, Acanthaster and the Coral Re*
*ef:A Theoretical Per-
spective, volume 88 of Lecture Notes in Biomathematics, pages 169{188.*
* Springer-Verlag, Berlin,
1990.
[Hie90] D. Hiebeler. A brief review of CA packages. Physica D, 45:463, 1990.
[HM90] B. Hasslacher and D. A. Meyer. Knot invariants and CA. Physica D, 45:3*
*28, 1990.
[Hog88] P. Hogeweg. Cellular automata as a paradigm for ecological modeling. a*
*pplied Mathematics and
Computation, 27(81-100):81{100, 1988.
[HT90] H. Hartman and P. Tamayo. Reversible CA and chemical turbulence. Physi*
*ca D, 45:293, 1990.
[HTA92] N. Howard, R. Taylor, and N. Allinson. The design and implementation o*
*f a massively-parallel
fuzzy architecture. Proc. IEEE, pages 545{552, March 1992.
[HV00] H. Hartman and G. Vichniac. Inhomogenous cellular automata. In E. Bien*
*enstock and et al.,
editors, Disordered Systems and Biological Organization. unknown, 1900.
[III71] Alvy Ray Smith III. Simple computation-universal cellular spaces. Jour*
*nal of the Association
for Computing Machinery, 18:339{353, 1971.
[Ing84] R. L. Buvel T. E. Ingerson. Structure in asynchronous cellular automat*
*a. Physica D, 1:59{68,
1984.
[IPY89] K. Culik II, J Pachl, and S Yu. On the limit sets of cellular automat*
*a. SIAM J. Comput.,
18(4):831, 1989.
[IY88] K. Culik II and S. Yu. Undecidability of CA classification schemes. Co*
*mplex Systems, 2:177{190,
1988.
[Jay00] E. T. Jaynes. probability theory{the logic of science. unknown, 1900.
[Jen88a] E. Jen. Preimage scaling in cellular automata. Complex Systems, 2:1046*
*, 1988.
[Jen88b] Erica Jen. Cylindrical cellular automata. Communications in Mathematic*
*al Physics, 118:569{
590, 1988.
[Jen90] E. Jen. Aperiodicity in one-dimensional CA. Physica D, 45:3, 1990.
[Kar90] J. Kari. Reversibility of 2D CA is undecidable. Physica D, 45:379, 199*
*0.
[Kar92] J. Kari. Cryptosystems based on reversible cellular automata. preprint*
*, April 1992.
36
[Kau69] S. A Kauffman. Metabolic stability and epigenisis in randomly constru*
*cted genetic nets. J.
Theoretical Biology, 22:437{467, 1969.
[Kau84] S. A Kauffman. Emergent properties in random complex systems. Physica *
*D,, 10:146{156, 1984.
[KM90] S. Kim and R. McCloskey. A characterization of constant-time CA comput*
*ation. Physica D,
45:404, 1990.
[Lan86] Christopher G. Langton. Studying artificial life with cellular automat*
*a. Physica D, 22:120{149,
1986.
[Lan89] Christopher G. Langton. Artificial Life. Addison-Wesley, Redwood City,*
* CA, 1989.
[Lan90] C. G. Langton. Computation at the edge of chaos. Physica D, 42, 1990.
[Lay92] John W. Layman. Dynamics of multicellular automata with unbounded mem*
*ory. Complex
Systems, 6(4):315{332, August 1992.
[Lea90] Christopher G. Langton and et al. Artificial Life II. Addison-Wesley, *
*Reading, MA, 1990.
[Li87] Wentian Li. Power spectra of regular languages and cellular automata. *
*Complex Systems, 1:107{
130, 1987.
[Lin84] D. A. Lind. Applications of ergodic theory and sofic systems to cellul*
*ar automata. Physica D,
10:36{44, 1984.
[LN88] K. Lindgren and M. Nordahl. Complexity measures in cellular automata.*
* Complex Systems,
2:409{440, 1988.
[LN90] C. Lindgren and M. Nordahl. Universal computation in simple one dimens*
*ional cellular automata.
Complex Systems, 4:299{318, 1990.
[LN92] Wentian Li and Mats Nordahl. Transient behavior of cellular automata r*
*ule 110. Physics Letters
A, 166(5/6):335{339, 1992.
[LP90] W. Li and N. H. Packard. unknown. Compl. systems, 4:281, 1990.
[Mar90] O. Martin. Critical dynamics of 1-D irreversible systems. Physica D, 4*
*5:345, 1990.
[MBVB89] P. Manneville, N. Boccara, G. Vichniac, and R. Bidaux. Cellular automa*
*ta and the modeling of
complex physical systems. Springer, Berlin, 1989.
[MCH94] M. Mitchell, J. P. Crutchfield, and P. T. Hraber. Evolving cellula*
*r automata to per-
form computations. Physica D (submitted), 1994? available f*
*rom ftp.santafe.edu
`/pub/Users/mm/sfi-93-11-071.part1.ps.Z' and `sfi-93-11-071.part2.ps.Z*
*'.
[McI90] H. V. McIntosh. Wolfram's class IV automata and a good life. Physica D*
*, 45:105, 1990.
[McI91a] Harold V. McIntosh. Linear cellular automata via de bruijn diagrams. p*
*reprint, May 1991.
[McI91b] Harold V. McIntosh. Reversible cellular automata. preprint, January 19*
*91.
[MF83] Barry F. Madore and Wendy L. Freedman. Computer simulations of the bel*
*ousov-zhabotinsky
reaction. Science, 222:615{616, 1983.
37
[MHC93a] M. Mitchell, P. T. Hraber, and J. P. Crutchfield. Dynamic computation,*
* and the \edge of chaos":
A re-examination. In G. Cowan, D. Pines, and D. Melzner, editors, Inte*
*grative Themes, Santa
Fe Institute Proceedings, Volume 19, page (to appear), Reading, MA, 19*
*93. Addison{Wesley.
Santa Fe Institute Working Paper 93-06-040.
[MHC93b] M. Mitchell, P. T. Hraber, and J. P. Crutchfield. Evolving cellular au*
*tomata to perform com-
putation: Mechanisms and impedients. Physica D, page (submitted), Octo*
*ber 1993. Santa Fe
Institute Working Paper 93-11-071.
[MHC93c] M. Mitchell, P. T. Hraber, and J. P. Crutchfield. revisiting the egde *
*of chaos: Evolving cellular
automata to perform computations. Complex Systems, page (submitted), 1*
*993. Santa Fe Institute
Working Paper 93-03-014.
[Mon89] R. Monaco. Discrete Kinetic Theory, Lattice Gas Dynamics and Foundatio*
*ns of Hydrodynamics.
World Scientific, 1989.
[Moo70] Edward F. Moore. Machine models of self reproduction. In Arthur W. Bur*
*ks, editor, Essays on
Cellular Automata. University of Illinois Press, Urbana, 1970.
[MOW84] O. Martin, A. Odlyzko, and S. Wolfram. Algebraic properties of cellula*
*r automata. Commun.
Math. Phys., 93:219, 1984.
[MPH85] Stefan C. Muller, Theo Plesser, and Benno Hess. The structure of the c*
*ore of the spiral wave in
the B-Z reaction. Science, 230:4726, November 1985.
[MPH87] Stefan C. Muller, Theo Plesser, and Benno Hess. Threedimensional repre*
*sentation of chemical
gradients. Biophysical Chemistry, February 1987.
[MS91] W. Meier and O. Staffelbach. Analysis of pseudo random sequences gener*
*ated by cellular au-
tomata. Proceedings of Eurocrypt '91, pages 186{199, 1991.
[Mur88] James D. Murray. How the leopard gets its spots. Scientific American, *
*pages 62{69, March 1988.
[Nas78] Masakazu Nasu. Local maps inducing surjective global maps of one dime*
*nsional tesselation
automata. Mathematical Systems Theory, 11:327{351, 1978.
[Nas82] Masakazu Nasu. Uniformly finite-to-one and onto extensions of homomorp*
*hisms between strongly
connected graphs. Discrete Mathematics, 39:171{197, 1982.
[NM92] Martin A. Nowak and Robert M. May. Evolutionary games and spatial chao*
*s. Nature, 359:826{
829, 1992.
[Pac88] N. H. Packard. unknown. In J. A. S. Kelso, A. J. Mandell, and M. F. Sh*
*lesinger, editors, Dynamic
patterns in complex systems, pages 293{301. World Scientific, Singapor*
*e, 1988.
[Pan91] R. Pandey. Cellular automata approach to interacting cellular network *
*models for the dynamics
of cell population in an early HIV infection. Physica A, 179:442{470, *
*1991.
[Ped92] John Pedersen. Cellular automata as algebraic systems. Complex Systems*
*, 6(3):237{250, June
1992.
[Pou85] William Poundstone. The Recursive Universe. William Morrow and Company*
*, New York, 1985.
ISBN 0-688-03975-8.
[Rey87] Craig Reynolds. Flocks, herds, and schools: A distributed behavioral *
*model. Proceedings of
ACM Computer Graphics, 21(4):25{33, July 1987.
38
[Ric72] D. Richardson. Tesselations with local transformations. Journal of Com*
*puter and System Sci-
ences, 5:373{388, 1972.
[SC91a] Hans B. Sieburg and Oliver K. Clay. Cellular automata as algebraic sys*
*tems. Complex Systems,
5(6):575{602, December 1991.
[SC91b] Hans B. Sieburg and Oliver K. Clay. The cellular device machine develo*
*pment system for mod-
eling biology. Complex Systems, pages 575{601, 1991.
[Sch85] A. Schlijper. On some variational approximations in two-dimensional cl*
*assical lattice systems.
PhD thesis, University of Groningen, The Netherlands, 1985.
[Seu85] Friedhelm Seutter. CEPROL: A cellular programming language. Parallel*
* Computing, 2(327{
333):327{333, 1985.
[SH77] Tadakazu Sato and Namio Honda. Certain relations between properties of*
* maps of tesselation
automata. Journal of System and Computer Sciences, 15:121{145, 1977.
[SHJD92] Jonathan Silvertown, Senino Holtier, Jeff Johnson, and Pam Dale. Cellu*
*lar automaton models of
interspecific competition for space-the effect of pattern on process. *
*Journal of Ecology, 80:527{
534, 1992.
[SMC+90] H. Sieburg, X. McCutchan, X. Clay, X. Cabalerro, and X. Ostlund. Simul*
*ation of HIV infection
in artificial immune systems. Physica D, 45:208{227, 1990.
[Smi90] M. A. Smith. Representations of geometrical and topological quantities*
* in CA. Physica D, 45:271,
1990.
[SNH91a] Bhavin Sheth, Prantik Nag, and Robert W. Hellwarth. Binary addition on*
* cellular automata.
Complex Systems, 5(5):479{486, October 1991.
[SNH91b] Bhavin Sheth, Prantik Nag, and Robert W. Hellwarth. Driver mechanisms *
*on cellular automata.
Complex Systems, 5(5):487{496, October 1991.
[SP92] D. Stauffer and R. Pandey. Immunologically motivated simulation of cel*
*lular automata. Com-
puters in Physics, 6:4:404{410, 1992.
[SS78] L. S. Schulman and P. E. Seiden. Statistical mechanics of a dynamical *
*system based on conway's
game of life. J. Stat Phys., 19:293, 1978.
[Sta91] D. Stauffer. Computer simulation of cellular automata. J. Phys. A: Mat*
*h. Gen., 24:909{927,
1991.
[Sut90] K. Sutner. Classifying circular CA. Physica D, 45:386, 1990.
[Sut91] Klaus Sutner. De bruijin graphs and linear cellular automata. Complex *
*Systems, 5(1):19{30,
February 1991.
[Svo90] K. Svozil. Constructive chaos by CA and possible sources of an arrow o*
*f time. Physica D, 45:420,
1990.
[SW92] D. Stauffer and G. Weisbuch. High-dimensional simulation of the shape*
*-space model for the
immune system. Physica A, 180: 1-2:42{52, 1992.
[Tak90a] S. Takahashi. CA and multifractals:dimension spectra of linear CA. Phy*
*sica D, 45:36, 1990.
39
[Tak90b] S. Takesue. Relaxation properties of elementary reversible CA. Physica*
* D, 45:278, 1990.
[TM87] Tommaso Toffoli and Norman Margolus. Cellular Automata Machines: A New*
* Environment for
Modeling. MIT Press, Cambridge, Mass, 1987.
[TM90] T. Toffoli and N. Margolus. Invertible cellular automata: A review. Ph*
*ysica D, 45:229, 1990.
[Tof77] Tommaso Toffoli. Computation and construction universality of reversi*
*ble cellular automata.
Journal of Computer and System Sciences, 15:213{231, 1977.
[unk82] unknown, editor. Physics of Computation and Computational models of Ph*
*ysics, volume 21:3-4,
6-7, and 12, 1982.
[unk93] unknown. Chris langton's cellular automaton (?). Mathematical Intellig*
*encer, 15(2):54, 1993.
[Vic90a] G. Vichniac. Boolean derivatives on CA. Physica D, 45:63, 1990.
[Vic90b] J. D. Victor. What can automaton theory tell us about the brain? Physi*
*ca D, 45:205, 1990.
[Voo90] B. Voorhees. Nearest neighbor CA over Z_2 with periodic boundary condi*
*tions. Physica D, 45:26,
1990.
[Voo91] Burton Voorhees. Geometry and arithmetic of a simple cellular automato*
*n. Complex Systems,
5(2):169{182, April 1991.
[VTH86] G. Vichniac, P. Tamayo, and H. Hartman. Annealed and quenched inhomog*
*eneous cellular
automata. Journal of Statistical Physics, 45, 1986.
[Wal90] C. C. Walker. Attractor dominance patterns in sparsely connected bool*
*ean nets. Physica D,
45:441{451, 1990.
[Wei73] Benjamin Weiss. Subshifts of finite type and sofic systems. Monatsheft*
*e fuer Mathematik, 77:462{
474, 1973.
[Win74] Arthur T. Winfree. Rotating chemical reactions. Scientific American, p*
*ages 82{95, June 1974.
[WL90] W. W. Wootters and C. G. Langton. Is there a sharp phase transition fo*
*r deterministic CA?
Physica D, 45:95, 1990.
[WL92] Andrew Wuensche and Mike Lesser. The Global Dynamics of Cellular Autom*
*ata, volume Refer-
ence Vol 1 of Santa Fe Institute Studies in the Sciences of Complexity*
*. Addison-Wesley, 1992.
IBSN 0-201-55740-1.
[Wol83] Stephan Wolfram. Statistical mechanics of cellular automata. Rev. Mo*
*d. Phys., 55:601{644,
1983.
[Wol84a] Stephan Wolfram. Random sequence generation by cellular automata. Adv.*
* Appl. Math, 7:123,
1984.
[Wol84b] Stephan Wolfram. Universality and complexity in cellular automata. Phy*
*sica D, 10:1{35, 1984.
[Wol84c] Stephen Wolfram. Computation theory of cellular automata. Communicatio*
*ns in Mathematical
Physics, 96:15{57, 1984.
[Wol85a] Stephan Wolfram. Cryptography with cellular automata. Proceedings of C*
*rypto '85, pages 429{
432, 1985.
40
[Wol85b] Stephan Wolfram. undecidability and intractability in physics. Phys. R*
*ev. Lett., 54:735, 1985.
[Wol86] Stephan Wolfram. Theory and applications of cellular automata. World S*
*cientific, Singapore,
1986. ISBN 9971-50-124-4 pbk.
[Wue93] Andrew Wuensche. The ghost in the machine:basins of attraction of rand*
*om boolean networks.
Cognitive Science Research Paper 281, University of Sussex, 1993, 1993*
*. to be published in
Artificial Life III, Santa Fe Institute Studies in the Sciences of Com*
*plexity.
[WWS85] A. T. Winfree, E. M. Winfree, and H. Seifert. Organizing centers in a *
*cellular excitable medium.
Physica D, 17:109{115, 1985.
[Yak76] Takeo Yaku. Inverse and injectivity of parallel relations induced by c*
*ellular automata. Proceedings
of the American Mathematical Society, 58:216{220, 1976.
[Zab88] J. G. Zabolitzky. Critical properties of rule 22 elementary cellular a*
*utomata. J. Stat. Phys.,
50:1255{1262, 1988.
41